Rank minimization with affine constraints has various applications in different area. Due to the intractability of rank function in the objective, many alternative functions have been widely studied in the literature, e.g., nuclear norm, and have been shown an effective way both theoretically and practically. The intractability was bypassed as those functions hold some nice properties such as convexity and differentiability. In this dissertation, we make efforts to improve the rank minimization performance while retaining computation efficiency by exploring the use of a non-convex surrogate of the rank function, namely the so-called Schatten quasi p norm (0 < p < 1). Although the resulting optimization problem is non-convex, we show, for the first time, that a first-order critical point can be approximated to arbitrary accuracy in polynomial time using the proposed potential reduction algorithm in this dissertation. / We then apply the resulting potential reduction algorithm to Sensor Network Localization problem. Currently, a popular approach to localization is using convex relaxation. In a typical application of this approach, the localization problem is first formulated as a rank-constrained semidefinite program (SDP), where the rank corresponds to the target dimension in which the sensors should be localized. Then, the non-convex rank constraint is either dropped or replaced by a convex approximation, thus resulting into a convex optimization problem. Our potential reduction algorithm is applied to the localization problem while the Schatten quasi p norm is employed in localization aiming to minimize the solution rank. Moreover, we show that the first-order critical point, the output of the algorithm, is already suffcient for recovering the node locations in the target dimension if the input instance satisfies certain conditions which has been shown in the literature. Finally, our simulation results show that in many scenarios, our proposed algorithm can achieve better localization in terms of accuracy than the popular SDP relaxations of the problem and its variations. / 线性约束下的矩阵秩最小化在诸多领域有着广泛的应用。然而由于秩的复杂性质，许多研究致力于寻找它的替代函数。例如，核模是其中非常流行的一种，研究已经表明其在理论和应用上的有效性。由于这些替代函数往往具有秩函数所没有的特性，比如凸性，可微分性等等，正是由于这些特性使得其在计算上有着更高的效率保证。在本文中，我们希望通过一种非凸的替代函数来提高这种替代方法的有效性，并且在同时希望能继续保持在计算上的效率，我们使用的这种非凸替代函数被称为Schatten 拟p 模（0 < p < 1）。尽管该优化问题的目标函数是非凸的，我们还是能够第一次证明可以在多项式时间内以任意精度逼近该问题的一阶临界点。 / 同时，我们将得到的势削减算法应用于传感器网络定位问题中。当前，处理该问题的流行方法是使用凸放松。在这种方法中，我们首先将传感器网络定位问题写成一个秩限制条件下的半正定规划问题，它的秩限制条件对应于传感器所在空间的维度。在凸放松方法中，通常这些秩限制条件被直接去除，或者被一个凸函数取代。在我们的方法中，我们使用Schatten拟模作为惩罚函数来优化所得解的秩。我们还证明了在某些条件被满足的情况下，该问题的一阶临界点已经足够用来还原节点的位置。最后我们对多种情景做了模拟实验，结果表明我们提出的算法在准确性上相比流行的半正定规划及其衍生的方法更有优势。 / Ji, Senshan. / Thesis Ph.D. Chinese University of Hong Kong 2015. / Includes bibliographical references (leaves 102-110). / Abstracts also in Chinese. / Title from PDF title page (viewed on 06, October, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.

Leung, Kin Pang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (p. 70-71). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Model --- p.4 / Chapter 2.1 --- The Basic Thurstonian Model --- p.4 / Chapter 2.2 --- The Thurstonian Model with Mean Structure in 3-object Ranking Data --- p.6 / Chapter 3 --- Implementation Using the Mx --- p.13 / Chapter 4 --- Simulation Study --- p.21 / Chapter 4.1 --- 2 covariate values --- p.23 / Chapter 4.2 --- 4 covariate values --- p.23 / Chapter 4.3 --- 10 covariate values --- p.23 / Chapter 4.4 --- 50 covariate values --- p.24 / Chapter 5 --- Discussion --- p.37 / Chapter A --- Sample Mx script-2 covariate values --- p.39 / Chapter B --- Sample Mx script-50 covariate values --- p.60 / Bibliography --- p.70

Hur företag förhåller sig till rankinglistor tros enligt tidigare forskning bero på ett proaktivt agerande från företagens sida för att motverka risken att dras med ett dåligt rykte, vilket är något som företagsledare i dag ser som den mest oroande risken. Ryktet kan ses som en reaktion på ett företags arbete utifrån uppfattningar från dess intressenter gällande företagets beteende. Dessa reaktioner och uppfattningar kan tydliggöras genom bland annat rankingar och andra mätningar. Syftet med denna uppsats är att öka förståelsen för hur företag förhåller sig till rankinglistor. Undersökningen utgår från Sustainable Brand Insights (SBI) årliga index över Sveriges mest hållbara varumärke och genomfördes genom intervjuer med sex av de 20 högst rankade företagen, samt SBI. Studien visar för det första att företagen förhåller sig olika till rankingen. För det andra att det hållbara arbetet är nära knutet till kärnverksamheten och för det tredje att rankingen inte har någon inverkan på hur företagen arbetar med hållbarhet.

Delivering the right information to the user is fundamental in information retrieval system. Many traditional information retrieval models assume word independence and view a document as bag-of-words, however getting the right information requires a deep understanding of the content of the document and the relationships that exist between words in the text. This study focuses on developing two new document ranking techniques, which are based on a lexical cohesive relationship of collocation. Collocation relationship is a semantic relationship that exists between words that co-occur in the same lexical environment. Two types of collocation relationship have been considered; collocation in the same grammatical structure (such as a sentence), and collocation in the same semantic structure where query terms occur in different sentences but they co-occur with the same words. In the first technique, we only considered the first type of collocation to calculate the document score; where the positional frequency of query terms co-occurrence have been used to identify collocation relationship between query terms and calculating query term’s weight. In the second technique, both types of collocation have been considered; where the co-occurrence frequency distribution within a predefined window has been used to determine query terms collocations and computing query term’s weight. Evaluation of the proposed techniques show performance gain in some of the collocations over the chosen baseline runs.

Delivering the right information to the user is fundamental in information retrieval system. Many traditional information retrieval models assume word independence and view a document as bag-of-words, however getting the right information requires a deep understanding of the content of the document and the relationships that exist between words in the text. This study focuses on developing two new document ranking techniques, which are based on a lexical cohesive relationship of collocation. Collocation relationship is a semantic relationship that exists between words that co-occur in the same lexical environment. Two types of collocation relationship have been considered; collocation in the same grammatical structure (such as a sentence), and collocation in the same semantic structure where query terms occur in different sentences but they co-occur with the same words. In the first technique, we only considered the first type of collocation to calculate the document score; where the positional frequency of query terms co-occurrence have been used to identify collocation relationship between query terms and calculating query term’s weight. In the second technique, both types of collocation have been considered; where the co-occurrence frequency distribution within a predefined window has been used to determine query terms collocations and computing query term’s weight. Evaluation of the proposed techniques show performance gain in some of the collocations over the chosen baseline runs.

Physical distribution networks are integral parts of modern supply chains. When faced with a question of which node in a network is more important, cost immediately jumps to mind. However, in a world of uncertainty, there are other significant factors which should be considered when trying to answer such a question. The integrity of a network, as well as its robustness are factors that we consider, in making a judgement of importance. We develop algorithms to measure several properties of a class of networks. To accelerate the optimization of multiple related linear programs, we develop a modification of the revised simplex method, which exploits several key aspects to gain efficiency. We combine these algorithms and methods, to give rankings of the relative importance of nodes in networks. In order to better understand the usefulness of our method, we analyse the effect parameter changes have on the relative importance of nodes. We present a large, realistic network, whose nodes we rank in importance. We then vary the network's parameters and observe the impact of each change.

Variable Selection has always been a very important problem in statistics. We often meet situations where a huge data set is given and we want to find out the relationship between the response and the corresponding variables. With a huge number of variables, we often end up with a big model even if we delete those that are insignificant. There are two reasons why we are unsatisfied with a final model with too many variables. The first reason is the prediction accuracy. Though the prediction bias might be small under a big model, the variance is usually very high. The second reason is interpretation. With a large number of variables in the model, it's hard to determine a clear relationship and explain the effects of variables we are interested in. A lot of variable selection methods have been proposed. However, one disadvantage of variable selection is that different sizes of model require different tuning parameters in the analysis, which is hard to choose for non-statisticians. Xin and Zhu advocate variable ranking instead of variable selection. Once variables are ranked properly, we can make the selection by adopting a threshold rule. In this thesis, we try to rank the variables using Least Angle Regression (LARS). Some shrinkage methods like Lasso and LARS can shrink the coefficients to zero. The advantage of this kind of methods is that they can give a solution path which describes the order that variables enter the model. This provides an intuitive way to rank variables based on the path. However, Lasso can sometimes be difficult to apply to variable ranking directly. This is because that in a Lasso solution path, variables might enter the model and then get dropped. This dropping issue makes it hard to rank based on the order of entrance. However, LARS, which is a modified version of Lasso, doesn't have this problem. We'll make use of this property and rank variables using LARS solution path.

No description available.

Nowadays, search engines are more relying on machine learning techniques to construct a model, using past user queries and clicks as training data, for ranking web pages. There are several learning to rank methods for information retrieval, and among them ranking support vector machine (SVM) attracts a lot of attention in the information retrieval community. One difficulty with Ranking SVM is that the computation cost is very high for constructing a ranking model due to the huge number of training data pairs when the size of training dataset is large. We adopt the MapReduce programming model to solve this difficulty. MapReduce is a distributed computing framework introduced by Google and is commonly adopted in cloud computing centers. It can deal easily with large-scale datasets using a large number of computers. Moreover, it hides the messy details of parallelization, fault-tolerance, data distribution, and load balancing from the programmer and allows him/her to focus on only the underlying problem to be solved. In this paper, we apply MapReduce to Ranking SVM for processing large-scale datasets. We specify the Map function to solve the dual sub problems involved in Ranking SVM and the Reduce function to aggregate all the outputs having the same intermediate key from Map functions of distributed machines. Experimental results show efficiency improvement on ranking SVM by our proposed approach.

We present the design and implementation of the Standard Template Adap- tive Parallel Library (stapl) pList, a parallel container that has the properties of a sequential list, but allows for scalable concurrent access when used in a paral- lel program. The stapl is a parallel programming library that extends C with support for parallelism. stapl provides a collection of distributed data structures (pContainers) and parallel algorithms (pAlgorithms) and a generic methodology for extending them to provide customized functionality. stapl pContainers are thread-safe, concurrent objects, providing appropriate interfaces (pViews) that can be used by generic pAlgorithms. The pList provides Standard Template Library (stl) equivalent methods, such as insert, erase, and splice, additional methods such as split, and efficient asyn- chronous (non-blocking) variants of some methods for improved parallel performance. List related algorithms such as list ranking, Euler Tour (ET), and its applications to compute tree based functions can be computed efficiently and expressed naturally using the pList. Lists are not usually considered useful in parallel algorithms because they do not allow random access to its elements. Instead, they access elements through a serializing traversal of the list. Our design of the pList, which consists of a collec- tion of distributed lists (base containers), provides almost random access to its base containers. The degree of parallelism supported can be tuned by setting the number of base containers. Thus, a key feature of the pList is that it offers the advantages of a classical list while enabling scalable parallelism. We evaluate the performance of the stapl pList on an IBM Power 5 cluster and on a CRAY XT4 massively parallel processing system. Although lists are generally not considered good data structures for parallel processing, we show that pList methods and pAlgorithms, and list related algorithms such as list ranking and ET technique operating on pLists provide good scalability on more than 16, 000 processors. We also show that the pList compares favorably with other dynamic data structures such as the pVector that explicitly support random access.