Intellectual property has gained more attention in recent decades because innovations have become one of the most important resources. This paper implements a probabilistic topic model using nonnegative matrix factorization (NMF) to discover some of the key elements in computer patent, as the industry grew from 1990 to 2009. This paper proposes a new “shrinking model” based on NMF and also performs a close examination of some variations of the base model. Note that rather than studying the strategy to pick the optimized number of topics (“rank”), this paper is particularly interested in which factorization (including different kinds of initiation) methods are able to construct “topics” with the best quality given the predetermined rank. Performing NMF to the description text of patent features, we observe key topics emerge such as “platform” and “display” with strong presence across all years but we also see other short-lived significant topics such as “power” and “heat” which signify the saturation of the industry.

Finding new examples of compact simply connected spaces admitting a Riemannian metric of positive sectional curvature is a fundamental problem in differential geometry. Likewise, studying topological properties of families of manifolds is very interesting to topologists. The Eschenburg spaces combine both of those interests: they are positively curved Riemannian manifolds whose topological classification is known. There is a second family consisting of the Witten manifolds: they are the examples of compact simply connected spaces admitting Einstein metrics of positive Ricci curvature. Thirdly, there is a notion of generalized Witten manifold as well. Topologically, all three families share the same cohomology ring. This common ring structure motivates the definition of a manifold of type r, where r is the order of the fourth cohomology group. In 1991, M. Kreck and S. Stolz classified manifolds M of type r up to homeomorphism and dieomorphism using invariants s̄[subscript i](M) and s[subscript i](M), for i = 1, 2, 3. This gave rise to many new examples of nondieomorphic but homeomorphic manifolds. In this dissertation, new versions of the homeomorphism and dieomorphism classification of manifolds of type r are proven. In particular, we can replace s̄₁ and s̄₃ by the first Pontrjagin class and the self-linking number in the homeomorphism classification of spin manifolds of type r. As the formulas of the two latter invariants are in general much easier to compute, this simplifies the classification of these manifolds up to homeomorphism significantly. / Graduation date: 2012

Objects such as documents, people, words or utilities, that are related in some way, for instance by citations, friendship, appearance in definitions or physical connections, may be conveniently represented using graphs or networks. An increasing number of such relational databases, as for instance the World Wide Web, digital libraries, social networking web sites or phone calls logs, are available. Relevant information may be hidden in these networks. A user may for instance need to get authority web pages on a particular topic or a list of similar documents from a digital library, or to determine communities of friends from a social networking site or a phone calls log. Unfortunately, extracting this information may not be easy. This thesis is devoted to the study of problems related to information extraction in large graphs with the help of dominant vectors of nonnegative matrices. The graph structure is indeed very useful to retrieve information from a relational database. The correspondence between nonnegative matrices and graphs makes Perron--Frobenius methods a powerful tool for the analysis of networks. In a first part, we analyze the fixed points of a normalized affine iteration used by a database matching algorithm. Then, we consider questions related to PageRank, a ranking method of the web pages based on a random surfer model and used by the well known web search engine Google. In a second part, we study optimal linkage strategies for a web master who wants to maximize the average PageRank score of a web site. Finally, the third part is devoted to the study of a nonlinear variant of PageRank. The simple model that we propose takes into account the mutual influence between web ranking and web surfing.

While much research has been done regarding different Nonnegative Matrix Factorization (NMF) algorithms, less time has been spent looking at initialization techniques. In this thesis, four different initializations are considered. After a brief discussion of NMF, the four initializations are described and each one is independently examined, followed by a comparison of the techniques. Next, each initialization's performance is investigated with respect to the changes in the size of the data set. Finally, a method by which smaller data sets may be used to determine how to treat larger data sets is examined.

This dissertation shows that nonnegative matrix factorization (NMF) can be extended to a general and efficient clustering method. Clustering is one of the fundamental tasks in machine learning. It is useful for unsupervised knowledge discovery in a variety of applications such as text mining and genomic analysis. NMF is a dimension reduction method that approximates a nonnegative matrix by the product of two lower rank nonnegative matrices, and has shown great promise as a clustering method when a data set is represented as a nonnegative data matrix. However, challenges in the widespread use of NMF as a clustering method lie in its correctness and efficiency: First, we need to know why and when NMF could detect the true clusters and guarantee to deliver good clustering quality; second, existing algorithms for computing NMF are expensive and often take longer time than other clustering methods. We show that the original NMF can be improved from both aspects in the context of clustering. Our new NMF-based clustering methods can achieve better clustering quality and run orders of magnitude faster than the original NMF and other clustering methods. Like other clustering methods, NMF places an implicit assumption on the cluster structure. Thus, the success of NMF as a clustering method depends on whether the representation of data in a vector space satisfies that assumption. Our approach to extending the original NMF to a general clustering method is to switch from the vector space representation of data points to a graph representation. The new formulation, called Symmetric NMF, takes a pairwise similarity matrix as an input and can be viewed as a graph clustering method. We evaluate this method on document clustering and image segmentation problems and find that it achieves better clustering accuracy. In addition, for the original NMF, it is difficult but important to choose the right number of clusters. We show that the widely-used consensus NMF in genomic analysis for choosing the number of clusters have critical flaws and can produce misleading results. We propose a variation of the prediction strength measure arising from statistical inference to evaluate the stability of clusters and select the right number of clusters. Our measure shows promising performances in artificial simulation experiments. Large-scale applications bring substantial efficiency challenges to existing algorithms for computing NMF. An important example is topic modeling where users want to uncover the major themes in a large text collection. Our strategy of accelerating NMF-based clustering is to design algorithms that better suit the computer architecture as well as exploit the computing power of parallel platforms such as the graphic processing units (GPUs). A key observation is that applying rank-2 NMF that partitions a data set into two clusters in a recursive manner is much faster than applying the original NMF to obtain a flat clustering. We take advantage of a special property of rank-2 NMF and design an algorithm that runs faster than existing algorithms due to continuous memory access. Combined with a criterion to stop the recursion, our hierarchical clustering algorithm runs significantly faster and achieves even better clustering quality than existing methods. Another bottleneck of NMF algorithms, which is also a common bottleneck in many other machine learning applications, is to multiply a large sparse data matrix with a tall-and-skinny dense matrix. We use the GPUs to accelerate this routine for sparse matrices with an irregular sparsity structure. Overall, our algorithm shows significant improvement over popular topic modeling methods such as latent Dirichlet allocation, and runs more than 100 times faster on data sets with millions of documents.

L'objectif de cette thèse est l'investigation de nouvelles méthodes de surface de réponse afin de réaliser l'analyse de sensibilité de modèles numériques complexes et coûteux en temps de calcul. Pour ce faire, nous nous sommes intéressés aux méthodes basées sur la décomposition ANOVA. Nous avons proposé l'utilisation d'une méthode basée sur les splines de lissage de type ANOVA, alliant procédures d'estimation et de sélection de variables. L'étape de sélection de variable peut devenir très coûteuse en temps de calcul, particulièrement dans le cas d'un grand nombre de paramètre d'entrée. Pour cela nous avons développé un algorithme de seuillage itératif dont l'originalité réside dans sa simplicité d'implémentation et son efficacité. Nous avons ensuite proposé une méthode directe pour estimer les indices de sensibilité. En s'inspirant de cette méthode de surface de réponse, nous avons développé par la suite une méthode adaptée à l'approximation de modèles très irréguliers et discontinus, qui utilise une base d'ondelettes. Ce type de méthode a pour propriété une approche multi-résolution permettant ainsi une meilleure approximation des fonctions à forte irrégularité ou ayant des discontinuités. Enfin, nous nous sommes penchés sur le cas où les sorties du simulateur sont des séries temporelles. Pour ce faire, nous avons développé une méthodologie alliant la méthode de surface de réponse à base de spline de lissage avec une décomposition en ondelettes. Afin d'apprécier l'efficacité des méthodes proposées, des résultats sur des fonctions analytiques ainsi que sur des cas d'ingénierie de réservoir sont présentées.

Regression analysis constitutes a large portion of the statistical repertoire in applications. In case where such analysis is used for exploratory purposes with no previous knowledge of the structure one would not wish to impose any constraints on the problem. But in many applications we are interested in a simple parametric model to describe the structure of a system with some prior knowledge of the structure. An important example of this occurs when the experimenter has the strong belief that the regression function changes monotonically in some or all of the predictor variables in a region of interest. The analyses needed for statistical inference under such constraints are nonstandard. The specific aim of this study is to introduce a technique which can be used for statistical inferences of a multivariate simple regression with some non-standard constraints.

L’imagerie hyperspectrale est un type d’imagerie émergent qui connaît un essor important depuis le début des années 2000. Grâce à une structure spectrale très fine qui produit un volume de donnée très important, elle apporte, par rapport à l’imagerie visible classique, un supplément d’information pouvant être mis à profit dans de nombreux domaines d’exploitation. Nous nous intéressons spécifiquement à la détection et l’analyse de changements entre deux images de la même scène, pour des applications orientées vers la défense.Au sein de ce manuscrit, nous commençons par présenter l’imagerie hyperspectrale et les contraintes associées à son utilisation pour des problématiques de défense. Nous présentons ensuite une méthode de détection et de classification de changements basée sur la recherche de directions spécifiques dans l’espace généré par le couple d’images, puis sur la fusion des directions proches. Nous cherchons ensuite à exploiter l’information obtenue sur les changements en nous intéressant aux possibilités de dé-mélange de séries temporelles d’images d’une même scène. Enfin, nous présentons un certain nombre d’extensions qui pourront être réalisées afin de généraliser ou améliorer les travaux présentés et nous concluons. / Hyperspectral imagery is an emerging imagery technology which has known a growing interest since the 2000’s. This technology allows an impressive growth of the data registered from a specific scene compared to classical RGB imagery. Indeed, although the spatial resolution is significantly lower, the spectral resolution is very small and the covered spectral area is very wide. We focus on change detection between two images of a given scene for defense oriented purposes.In the following, we start by introducing hyperspectral imagery and the specificity of its exploitation for defence purposes. We then present a change detection and analysis method based on the search for specifical directions in the space generated by the image couple, followed by a merging of the nearby directions. We then exploit this information focusing on theunmixing capabilities of multitemporal hyperspectral data. Finally, we will present a range of further works that could be done in relation with our work and conclude about it.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19341号 / 情博第593号 / 新制||情||103(附属図書館) / 32343 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 中村 佳正, 教授 矢ｹ崎 一幸, 教授 西村 直志 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Hyperspectral imagery is often associated with high storage and transmission costs. Dimensionality reduction aims to reduce the time and space complexity of hyperspectral imagery by projecting data into a low-dimensional space such that all the important information in the data is preserved. Dimensionality-reduction methods based on transforms are widely used and give a data-dependent representation that is unfortunately costly to compute. Recently, there has been a growing interest in data-independent representations for dimensionality reduction; of particular prominence are random projections which are attractive due to their computational efficiency and simplicity of implementation. This dissertation concentrates on exploring the realm of computationally fast and efficient random projections by considering projections based on a random Hadamard matrix. These Hadamard-based projections are offered as an alternative to more widely used random projections based on dense Gaussian matrices. Such Hadamard matrices are then coupled with a fast singular value decomposition in order to implement a two-stage dimensionality reduction that marries the computational benefits of the data-independent random projection to the structure-capturing capability of the data-dependent singular value transform. Finally, random projections are applied in conjunction with nonnegative least squares to provide a computationally lightweight methodology for the well-known spectral-unmixing problem. Overall, it is seen that random projections offer a computationally efficient framework for dimensionality reduction that permits hyperspectral-analysis tasks such as unmixing and classification to be conducted in a lower-dimensional space without sacrificing analysis performance while reducing computational costs significantly.