16 research outputs found
샘플 부분 공간 압축을 통한 효율적이고 정확한 대규모 양의 준정부호 행렬 고유 분해
No full text학위논문(박사) - 한국과학기술원 : 전산학부, 2017.8,[vi, 69 p. :]Nystrm method is a sampling based method for spectral decomposition of positive semi-definite (PSD) matrices, and is widely used in kernel-based machine learning for large-scale data sets.Since its introduction, there has been a large body of work that improves the approximation accuracy while maintaining computational efficiency. In this paper, we present novel Nystrm schemes that improve both accuracy and efficiency based on a new theoretical analysis.We first prove that One-shot Nystrm Method (ONM) which is one of the existing Nystrm methods solves sample-based kernel PCA problem given the sample subspace,and suggest that the subspace distance measure is important for accuracy of Nystrm methods.We then prove novel upper error bounds based on subspace distance measure, and propose Principal Subspace Approximation (PSA) sampling that minimizes our error bounds based on the notion of compression of sample matrices with sparse representation.By combining the ONM and PSA sampling, we present our Double Nystrm Method (DNM) that efficiently reduces the size of the decomposition problem in two stages.We report the results of extensive experiments that provide a detailed comparison of various sampling strategies and our PSA sampling, and show that PSA sampling is superior even to the sampling strategies that use clustering algorithms in terms of both accuracy and efficiency.We also demonstrate our DNM is highly efficient and accurate compared to other state-of-the-art Nystrm methods for large-scale data sets.Next, we generalize DNM, and present Nested Nystrm Method (NNM) which is a multilayer method based on a nested sequence of subsamples and multiple compressions.To compute spectral decomposition of PSD matrices,it compresses sample matrices and solves a smaller sized optimization problem, and updates the eigenspace on each layer.We prove that its upper error bound decreases as we use additional layers. Experimental results show that NNM is more accurate than DNM within the same short time.Finally, we tackle the local triangle counting problem on graph streams by using Nystrm extension. We first derive a local triangle counting algorithm based on Nystrm method, and design MELTING-U which is a memory-efficient and accurate local triangle counting algorithm on graph streams. We also propose a fast version of MELTING-U, called MELTING. By using DNM, we show that MELTING-U and MELTING are memory-efficient and more accurate compared to the competitive algorithms on a number of real data sets..한국과학기술원 :전산학부
Hierarchical ordering with partial pairwise hierarchical relationships on the macaque brain data sets.
No full textHierarchical organizations of information processing in the brain networks have been known to exist and widely studied. To find proper hierarchical structures in the macaque brain, the traditional methods need the entire pairwise hierarchical relationships between cortical areas. In this paper, we present a new method that discovers hierarchical structures of macaque brain networks by using partial information of pairwise hierarchical relationships. Our method uses a graph-based manifold learning to exploit inherent relationship, and computes pseudo distances of hierarchical levels for every pair of cortical areas. Then, we compute hierarchy levels of all cortical areas by minimizing the sum of squared hierarchical distance errors with the hierarchical information of few cortical areas. We evaluate our method on the macaque brain data sets whose true hierarchical levels are known as the FV91 model. The experimental results show that hierarchy levels computed by our method are similar to the FV91 model, and its errors are much smaller than the errors of hierarchical clustering approaches
Anti-distortion bioinspired camera with an inhomogeneous photo-pixel array
No full textThe bioinspired camera, comprising a single lens and a curved image sensor-a photodiode array on a curved surface-, was born of flexible electronics. Its economical build lends itself well to space-constrained machine vision applications. The curved sensor, much akin to the retina, helps image focusing, but the curvature also creates a problem of image distortion, which can undermine machine vision tasks such as object recognition. Here we report an anti-distortion single-lens camera, where 4096 silicon photodiodes arrayed on a curved surface in a nonuniform pattern assimilated to the distorting optics are the key to anti-distortion engineering. That is, the photo-pixel distribution pattern itself is warped in the same manner as images are warped, which correctively reverses distortion. Acquired images feature no appreciable distortion across a 120 degrees horizontal view, as confirmed by their neural-network recognition accuracies. This distortion correction via photo-pixel array reconfiguration is a form of in-sensor computing. Curvature of image sensors that match the focal plane of the lens facilitate focussing but can cause image distortion. Here, an anti-distortion single-lens camera was developed using a curved image sensor with a photo-pixel distribution pattern warped like image warping to correctively reverse distortion.Y
CoDiNMF: Co-Clustering of Directed Graphs via NMF
No full textCo-clustering computes clusters of data items and the related features concurrently, and it has been used in many applications such as community detection, product recommendation, computer vision, and pricing optimization. In this paper, we propose a new co-clustering method, called CoDiNMF, which improves the clustering quality and finds directional patterns among co-clusters by using multiple directed and undirected graphs. We design the objective function of co-clustering by using min-cut criterion combined with an additional term which controls the sum of net directional flow between different co-clusters. In addition, we show that a variant of Nonnegative Matrix Factorization (NMF) can solve the proposed objective function effectively. We run experiments on the US patents and BlogCatalog data sets whose ground truth have been known, and show that CoDiNMF improves clustering results compared to other co-clustering methods in terms of average F1 score, Rand index, and adjusted Rand index (ARI). Finally, we compare CoDiNMF and other co-clustering methods on the Wikipedia data set of philosophers, and we can find meaningful directional flow of influence among co-clusters of philosophers
Data/Feature Distributed Stochastic Coordinate Descent for Fast, Scalable, and High-Dim. Logistic Regression
No full textReward Shaping for Model-Based Bayesian Reinforcement Learning
No full textBayesian reinforcement learning (BRL) provides a formal framework for optimal exploration-exploitation tradeoff in reinforcement learning. Unfortunately, it is generally intractable to find the Bayes-optimal behavior except for restricted cases. As a consequence, many BRL algorithms, model-based approaches in particular, rely on approximated models or real-time search methods. In this paper, we present potential-based shaping for improving the learning performance in model-based BRL. We propose a number of potential functions that are particularly well suited for BRL, and are domain-independent in the sense that they do not require any prior knowledge about the actual environment. By incorporating the potential function into real-time heuristic search, we show that we can significantly improve the learning performance in standard benchmark domains
