Šio magistro darbo tikslas yra ištirti daugdarų dimensijos atpažinimo daugiamačiuose duomenyse metodus. Darbe buvo išnagrinėti 3 lokalūs dimensijos vertinimo metodai, koreliacinis, artimiausių kaimynų ir didžiausio tikėtinumo, ir su įvairių matmenų duomenimis atlikti tyrimai. Atstumai tarp kaimyninių taškų buvo skaičiuojami dviem būdais: Euklido ir geodeziniu. Atlikus tyrimus buvo padarytos tokios išvados: • Maksimalaus tikėtinumo vertinimo metodas tiksliausiai vertina vidinį matmenų skaičių dirbtiniams duomenims, taip pat realiems duomenims, kai tarp kaimynų skaičiuojami geodeziniai atstumai. • Koreliacinis vertinimo metodas dirbtiniams duomenims, ir realiems duomenims, kai tarp kaimynų skaičiuojami geodeziniai atstumai, vidinį matmenų skaičių nustato gerai, kai tarp kaimynų skaičiuojami Euklido atstumai, vidinį matmenų skaičių nustato labai blogai. • Koreliacinis metodas nėra geras, nes yra sunku parinkti tinkamus parametrus – spindulius. • Artimiausių kaimynų vertinimo metodas vidinį matmenų skaičių nustato gerai tik realiems duomenims, kai tarp kaimynų skaičiuojami geodeziniai atstumai, visais kitais nagrinėjamais atvejais – blogai. • Artimiausių kaimynų metodas vidinį matmenų skaičių nustato blogiausiai iš visų trijų nagrinėjamų metodų. / The objective of this master thesis is to explore different techniques of dataset intrinsic dimensionality estimation. The purpose was to examine three local estimators for intrinsic dimensionality: the correlation dimension estimator, the nearest neighbor dimension estimator, and the maximum likelihood estimator. Data with various intrinsic dimensionalities were examined. The distances between neighboring points were calculated using two metrics: Euclidean and Geodesic. The investigation revealed the following conclusions: • The results by maximum likelihood estimation method were closest to the real intrinsic dimensionality of an artificial data, as well as real data, in cases when distances between neighbors were calculated using Geodesic metrics. • The correlation dimension estimator showed good results for artificial and real data when distances between neighbors were estimated using Geodesic metrics. When distances between neighbors were calculated by Euclidean metrics, the intrinsic dimension estimation results were very bad. • Correlation dimension estimator is not a good method because it is difficult to select proper settings – radiuses. • The nearest neighbor estimation method works well only when determining intrinsic dimension of real data when distances between neighbors are estimated using Geodesic metrics. In all other cases it is almost useless. • The nearest neighbor method is the worst method amongst all.

Doctor of Philosophy (PhD) / This thesis addresses the problem of building statistical models for multi-sensor perception in unstructured outdoor environments. The perception problem is divided into three distinct tasks: recognition, representation and association. Recognition is cast as a statistical classification problem where inputs are images or a combination of images and ranging information. Given the complexity and variability of natural environments, this thesis investigates the use of Bayesian statistics and supervised dimensionality reduction to incorporate prior information and fuse sensory data. A compact probabilistic representation of natural objects is essential for many problems in field robotics. This thesis presents techniques for combining non-linear dimensionality reduction with parametric learning through Expectation Maximisation to build general representations of natural features. Once created these models need to be rapidly processed to account for incoming information. To this end, techniques for efficient probabilistic inference are proposed. The robustness of localisation and mapping algorithms is directly related to reliable data association. Conventional algorithms employ only geometric information which can become inconsistent for large trajectories. A new data association algorithm incorporating visual and geometric information is proposed to improve the reliability of this task. The method uses a compact probabilistic representation of objects to fuse visual and geometric information for the association decision. The main contributions of this thesis are: 1) a stochastic representation of objects through non-linear dimensionality reduction; 2) a landmark recognition system using a visual and ranging sensors; 3) a data association algorithm combining appearance and position properties; 4) a real-time algorithm for detection and segmentation of natural objects from few training images and 5) a real-time place recognition system combining dimensionality reduction and Bayesian learning. The theoretical contributions of this thesis are demonstrated with a series of experiments in unstructured environments. In particular, the combination of recognition, representation and association algorithms is applied to the Simultaneous Localisation and Mapping problem (SLAM) to close large loops in outdoor trajectories, proving the benefits of the proposed methodology.

Abstract Raw data sets taken with various capturing devices are usually multidimensional and need to be preprocessed before applying subsequent operations, such as clustering, classification, outlier detection, noise filtering etc. One of the steps of data preprocessing is dimensionality reduction. It has been developed with an aim to reduce or eliminate information bearing secondary importance, and retain or highlight meaningful information while reducing the dimensionality of data. Since the nature of real-world data is often nonlinear, linear dimensionality reduction techniques, such as principal component analysis (PCA), fail to preserve a structure and relationships in a highdimensional space when data are mapped into a low-dimensional space. This means that nonlinear dimensionality reduction methods are in demand in this case. Among them is a method called locally linear embedding (LLE), which is the focus of this thesis. Its main attractive characteristics are few free parameters to be set and a non-iterative solution avoiding the convergence to a local minimum. In this thesis, several extensions to the conventional LLE are proposed, which aid us to overcome some limitations of the algorithm. The study presents a comparison between LLE and three nonlinear dimensionality reduction techniques (isometric feature mapping (Isomap), self-organizing map (SOM) and fast manifold learning based on Riemannian normal coordinates (S-LogMap) applied to manifold learning. This comparison is of interest, since all of the listed methods reduce high-dimensional data in different ways, and it is worth knowing for which case a particular method outperforms others. A number of applications of dimensionality reduction techniques exist in data mining. One of them is visualization of high-dimensional data sets. The main goal of data visualization is to find a one, two or three-dimensional descriptive data projection, which captures and highlights important knowledge about data while eliminating the information loss. This process helps people to explore and understand the data structure that facilitates the choice of a proper method for the data analysis, e.g., selecting simple or complex classifier etc. The application of LLE for visualization is described in this research. The benefits of dimensionality reduction are commonly used in obtaining compact data representation before applying a classifier. In this case, the main goal is to obtain a low-dimensional data representation, which possesses good class separability. For this purpose, a supervised variant of LLE (SLLE) is proposed in this thesis.

Abstract Training a visual inspection device is not straightforward but suffers from the high variation in material to be inspected. This variation causes major difficulties for a human, and this is directly reflected in classifier training. Many inspection devices utilize rule-based classifiers the building and training of which rely mainly on human expertise. While designing such a classifier, a human tries to find the questions that would provide proper categorization. In training, an operator tunes the classifier parameters, aiming to achieve as good classification accuracy as possible. Such classifiers require lot of time and expertise before they can be fully utilized. Supervised classifiers form another common category. These learn automatically from training material, but rely on labels that a human has set for it. However, these labels tend to be inconsistent and thus reduce the classification accuracy achieved. Furthermore, as class boundaries are learnt from training samples, they cannot in practise be later adjusted if needed. In this thesis, a visual based training method is presented. It avoids the problems related to traditional training methods by combining a classifier and a user interface. The method relies on unsupervised projection and provides an intuitive way to directly set and tune the class boundaries of high-dimensional data. As the method groups the data only by the similarities of its features, it is not affected by erroneous and inconsistent labelling made for training samples. Furthermore, it does not require knowledge of the internal structure of the classifier or iterative parameter tuning, where a combination of parameter values leading to the desired class boundaries are sought. On the contrary, the class boundaries can be set directly, changing the classification parameters. The time need to take such a classifier into use is small and tuning the class boundaries can happen even on-line, if needed. The proposed method is tested with various experiments in this thesis. Different projection methods are evaluated from the point of view of visual based training. The method is further evaluated using a self-organizing map (SOM) as the projection method and wood as the test material. Parameters such as accuracy, map size, and speed are measured and discussed, and overall the method is found to be an advantageous training and classification scheme.

The large amount of available data on a diverse range of human activities provides many opportunities for understanding, improving and revealing unknown patterns in them. Powerful automatic methods for extracting this knowledge from data are already available from machine learning and data mining. They, however, rely on the expertise of analysts to improve their results when those are not satisfactory. In this context, interactive multidimensional projections are a useful tool for the analysis of multidimensional data by revealing their underlying structure while allowing the user to manipulate the results to provide further insight into this structure. This manipulation, however, has received little attention regarding their influence on the mappings, as they can change the final layout in unpredictable ways. This is the main motivation for this research: understanding the effects caused by changes in these mappings. We approach this problem from two perspectives. First, the user perspective, we designed and developed visualizations that help reduce the trial and error in this process by providing the right piece of information for performing manipulations. Furthermore, these visualizations help explain the changes in the map caused by such manipulations. Second, we defined the effectiveness of manipulation in quantitative terms, then developed an experimental framework for assessing manipulations in multidimensional projections under this view. This framework is based on improving mappings using known evaluation measures for these techniques. Using the improvement of measures as different types of manipulations, we perform a series of experiments on five datasets, five measures, and four techniques. Our experimental results show that there are possible types of manipulations that can happen effectively, with some techniques being more susceptible to manipulations than others. / O grande volume de dados disponíveis em uma diversa gama de atividades humanas cria várias oportunidades para entendermos, melhorarmos e revelarmos padrões previamente desconhecidos em tais atividades. Métodos automáticos para extrair esses conhecimentos a partir de dados já existem em áreas como aprendizado de máquina e mineração de dados. Entretanto, eles dependem da perícia do analista para obter melhores resultados quando estes não são satisfatórios. Neste contexto, técnicas de projeção multidimensional interativas são uma ferramenta útil para a análise de dados multidimensionais, revelando sua estrutura subjacente ao mesmo tempo que permite ao analista manipular os resultados interativamente, estendendo o processo de exploração. Essa interação, entretanto, não foi estudada com profundidade com respeito à sua real influência nos mapeamentos, já que podem causar mudanças não esperadas no mapeamento final. Essa é a principal motivação desta pesquisa: entender os efeitos causados pelas mudanças em tais mapeamentos. Abordamos o problema de duas perspectivas. Primeiro, da perspectiva do usuário, desenvolvemos visualizações que ajudam a diminuir tentativas e erros neste processo provendo a informação necessária a cada passo da interação. Além disso, essas visualizações ajudam a explicar as mudanças causadas no mapeamento pela manipulação. A segunda perspectiva é a efetividade da manipulação. Definimos de forma quantitativa a efetividade da manipulação, e então desenvolvemos um arcabouço para avaliar manipulações sob a visão da efetividade. Este arcabouço é baseado em melhorias nos mapeamentos usando medidas de avaliação conhecidas para tais técnicas. Usando tais melhorias como diferentes formas de manipulação, realizamos uma série de experimentos em cinco bases de dados, cinco medidas e quatro técnicas. Nossos resultados experimentais nos dão evidências que existem certos tipos de manipulação que podem acontecer efetivamente, com algumas técnicas sendo mais suscetíveis a manipulações do que outras.

Dimensionality reduction techniques such as t-SNE and UMAP are useful both for overview of high-dimensional datasets and as part of a machine learning pipeline. These techniques create a non-parametric model of the manifold by fitting a density kernel about each data point using the distances to its k-nearest neighbors. In dense regions, this approach works well, but in sparse regions, it tends to draw unrelated points into the nearest cluster. Our work focuses on a homotopy method which imposes graph-based regularization over the manifold parameters to update the embedding. As the homotopy parameter increases, so does the cost of modeling different scales between adjacent neighborhoods. This gradually imposes a more uniform scale over the manifold, resulting in a more faithful embedding which preserves structure in dense areas while pushing sparse anomalous points outward.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第21546号 / 理博第4453号 / 新制||理||1639(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)准教授 池田 隆介, 教授 前野 悦輝, 教授 川上 則雄 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

In this dissertation, novel techniques for hyperspectral classification and signal reconstruction from random projections are presented. A classification paradigm designed to exploit the rich statistical structure of hyperspectral data is proposed. The proposed framework employs the local Fisher’s discriminant analysis to reduce the dimensionality of the data while preserving its multimodal structure, followed by a subsequent Gaussianmixture- model or support-vector-machine classifier. An extension of this framework in a kernel induced space is also studied. This classification approach employs a maximum likelihood classifier and dimensionality reduction based on a kernel local Fisher’s discriminant analysis. The technique imposes an additional constraint on the kernel mapping—it ensures that neighboring points in the input space stay close-by in the projected subspace. In a typical remote sensing flow, the sender needs to invoke an appropriate compression strategy for downlinking signals (e.g., imagery to a base station). Signal acquisition using random projections significantly decreases the sender-side computational cost, while preserving useful information. In this dissertation, a novel class-dependent hyperspectral image reconstruction strategy is also proposed. The proposed method employs statistics pertinent to each class as opposed to the average statistics estimated over the entire dataset, resulting in a more accurate reconstruction from random projections. An integrated spectral-spatial model for signal reconstruction from random projections is also developed. In this approach, spatially homogeneous segments are combined with spectral pixel-wise classification results in the projected subspace. An appropriate reconstruction strategy, such as compressive projection principal component analysis (CPPCA), is employed individually in each category based on this integrated map. The proposed method provides better reconstruction performance as compared to traditional methods and the class-dependent CPPCA approach.

Real-world data can often be high-dimensional and contain redundant or irrelevant attributes. High-dimensional data are problematic for machine learning as the high dimensionality causes learning to take more time and, unless the dataset is sufficiently large to provide an ample number of samples for each class, the accuracy will suffer. Redundant and irrelevant attributes cause the data to take on a higher dimensionality than necessary and obfuscates the important attributes. Because of this, it is of interest to be able to reduce the dimensionality of the data whilst preserving the important attributes. Several techniques have been presented in the field of computer science in order to reduce the dimensionality of data. One of these is the autoencoder which is an unsupervised learning neural network which uses its input as the target output, and by limiting the number of neurons in the hidden layer the autoencoder is forced to learn a lower dimensional representation of the data. This study focuses on using the autoencoder to reduce the dimensionality, and eliminate irrelevant or redundant attributes, of four different datasets from different domains. The results show that the autoencoder can eliminate redundant attributes, that are a linear combination of the other attributes, and provide a better lower dimensional representation of the data than that of the unreduced data. However, in data that is gathered under a controlled and carefully managed situation, the autoencoder cannot always provide a better lower dimensional representation than the data with redundant attributes. Lastly, the results show that the autoencoder cannot eliminate irrelevant attributes which have no correlation to the class or other attributes. / Verklig data kan ofta vara högdimensionella och innehålla överflödiga eller irrelevanta attribut. Högdimensionell data är problematisk för maskininlärning, eftersom det medför att lärandet tar längre tid och om inte datasetet är tillräckligt stort för att ge ett tillräckligt antal instanser för varje klass kommer precisionen att drabbas. Överflödiga och irrelevanta attribut gör att datan får en högre dimension än vad som är nödvändigt och gör de svårare att avgöra vilka de viktiga attributen är. På grund av detta är det av intresse att kunna reducera datans dimensionalitet samtidigt som de viktiga attributen bevaras. Flera tekniker har presenterats för dimensionsreducering av data. En utav dessa tekniker är autoencodern, som är ett oövervakat lärande neuralt nätverk som använder sin indata som målutdata, och genom att begränsa antalet neuroner i det dolda lagret tvingas autoencodern att lära sig en representation av datan i en lägre dimension. Denna studie fokuserar på att använda autoencodern för att minska dimensionerna och eliminera irrelevanta eller överflödiga attribut, av fyra olika dataset från olika domäner. Resultaten visar att autoenkodern kan eliminera redundanta attribut, som är en linjär kombination av de andra attributen, och ge en bättre lägre dimensionell representation av datan än den ej reducerade datan. I data som samlats in under en kontrollerad och noggrant hanterad situation kan emellertid autoencodern inte alltid ge en bättre lägre dimensionell representation än datan med redundanta attribut. Slutligen visar resultaten att autoencodern inte kan eliminera irrelevanta attribut, som inte har någon korrelation med klassen eller andra attribut.

Hyperspectral imagery is a highly dimensional type of data resulting in high computational costs during analysis. Band selection aims to reduce the original hyperspectral image to a smaller subset that reduces these costs while preserving the maximum amount of spectral information within the data. This thesis explores various types of band selection techniques used in hyperspectral image processing. Modifying Neural network-based techniques and observing the effects on the band selection process due to the change in network architecture or objective are of particular focus in this thesis. Herein, a generalized neural network-based band selection technique is developed and compared to state-of-the-art algorithms that are applied to a unique dataset and the Pavia City Center dataset where the subsequent selected bands are fed into a classifier to gather comparison results.