Sequential model-based optimization sequentially selects a candidate point by constructing a surrogate model with the history of evaluations, to solve a black-box optimization problem. Gaussian process (GP) regression is a popular choice as a surrogate model, because of its capability of calculating prediction uncertainty analytically. On the other hand, an ensemble of randomized trees is another option and has practical merits over GPs due to its scalability and easiness of handling continuous/discrete mixed variables. In this paper we revisit various ensembles of randomized trees to investigate their behavior in the perspective of prediction uncertainty estimation. Then, we propose a new way of constructing an ensemble of randomized trees, referred to as BwO forest, where bagging with oversampling is employed to construct bootstrapped samples that are used to build randomized trees with random splitting. Experimental results demonstrate the validity and good performance of BwO forest over existing tree-based models in various circumstances.

Bayesian optimization is a popular method for solving the problem of global optimization of an expensive-to-evaluate black-box function. It relies on a probabilistic surrogate model of the objective function, upon which an acquisition function is built to determine where next to evaluate the objective function. In general, Bayesian optimization with Gaussian process regression operates on a continuous space. When input variables are categorical or discrete, an extra care is needed. A common approach is to use one-hot encoded or Boolean representation for categorical variables which might yield a combinatorial explosion problem. In this paper we present a method for Bayesian optimization in a combinatorial space, which can operate well in a large combinatorial space. The main idea is to use a random mapping which embeds the combinatorial space into a convex polytope in a continuous space, on which all essential process is performed to determine a solution to the black-box optimization in the combinatorial space. We describe our combinatorial Bayesian optimization algorithm and present its regret analysis. Numerical experiments demonstrate that our method shows satisfactory performance compared to existing methods.

Multiple Instance Learning (MIL) involves predicting a single label for a bag of instances, given positive or negative labels at bag-level, without accessing to label for each instance in the training phase. Since a positive bag contains both positive and negative instances, it is often required to detect positive instances (key instances) when a set of instances is categorized as a positive bag. The attention-based deep MIL model is a recent advance in both bag-level classification and key instance detection (KID). However, if the positive and negative instances in a positive bag are not clearly distinguishable, the attention-based deep MIL model has limited KID performance as the attention scores are skewed to few positive instances. In this paper, we present a method to improve the attention-based deep MIL model in the task of KID. The main idea is to use the neural network inversion to find which instances made contribution to the bag-level prediction produced by the trained MIL model. Moreover, we incorporate a sparseness constraint into the neural network inversion, leading to the sparse network inversion which is solved by the proximal gradient method. Numerical experiments on an MNIST-based image MIL dataset and two real-world histopathology datasets verify the validity of our method, demonstrating the KID performance is significantly improved while the performance of bag-level prediction is maintained.

While various complexity measures for deep neural networks exist, specifying an appropriate measure capable of predicting and explaining generalization in deep networks has proven challenging. We propose Neural Complexity (NC), a meta-learning framework for predicting generalization. Our model learns a scalar complexity measure through interactions with many heterogeneous tasks in a data-driven way. The trained NC model can be added to the standard training loss to regularize any task learner in a standard supervised learning scenario. We contrast NC's approach against existing manually-designed complexity measures and other meta-learning models, and we validate NC's performance on multiple regression and classification tasks.

Generative adversarial network (GAN) has established itself as a promising model for density estimation, with its wide applications to various problems. Of particular interest in this paper is the problem of {\em anomaly detection} which involves identifying events that do not conform to expected patterns in data. Recent application of GANs to the task of anomaly detection, resort to their ability for learning probability distributions of normal examples, so that abnormal examples or outliers are detected when they reside in very low-probability regimes. Existing GAN methods often suffer from the bad {\em cycle-consistency} problem, which yields the large reconstruction error so that the anomaly detection performance is degraded. In order to alleviate this, we present a model that consists of a forward GAN and backward GAN, each of which has an individual discriminator, that are coupled by enforcing feature matching in two discriminators. We show that our forward-backward GANs (FBGANs) better captures the data distribution so that the anomaly detection performance is improved over existing GAN-based methods. Experiments on MNIST an KDD99 datasets demonstrate that our method, FBGANs, outperforms existing state-of-the-art anomaly detection methods, in terms of the area under precision recall curve (AUPR) and $F_{1}$-score.

We consider a non-projective class of inhomogeneous random graph models with interpretable parameters and a number of interesting asymptotic properties. Using the results of Bollobás et al. (2007), we show that i) the class of models is sparse and ii) depending on the choice of the parameters, the model is either scale-free, with power-law exponent greater than 2, or with an asymptotic degree distribution which is power-law with exponential cut-off. We propose an extension of the model that can accommodate an overlapping community structure. Scalable posterior inference can be performed due to the specific choice of the link probability. We present experiments on five different real world networks with up to 100,000 nodes and edges, showing that the model can provide a good fit to the degree distribution and recovers well the latent community structure.

Many machine learning tasks such as multiple instance learning, 3D shape recognition, and few-shot image classification are defined on sets of instances. Since solutions to such problems do not depend on the order of elements of the set, models used to address them should be permutation invariant. We present an attention-based neural network module, the Set Transformer, specifically designed to model interactions among elements in the input set. The model consists of an encoder and a decoder, both of which rely on attention mechanisms. In an effort to reduce computational complexity, we introduce an attention scheme inspired by inducing point methods from sparse Gaussian process literature. It reduces the computation time of self-attention from quadratic to linear in the number of elements in the set. We show that our model is theoretically attractive and we evaluate it on a range of tasks, demonstrating the state-of-the-art performance compared to recent methods for set-structured data.

We present a new method to generate fake data in unknown classes in generative adversarial networks (GANs) framework. The generator in GANs is trained to generate somewhat similar to data in known classes but the different one by modelling noisy distribution on feature space of a classifier using proposed marginal denoising autoencoder. The generated data are treated as fake instances in unknown classes and given to the classifier to make it be robust to the real unknown classes. Our results show that synthetic data can act as fake unknown classes and keep down the certainty of the classifier on real unknown classes meanwhile the classification capability of known classes is not degenerated, even improved.

Bayesian optimization is a powerful technique for finding extrema of an objective function, a closed-form expression of which is not given but expensive evaluations at query points are available. Gaussian Process (GP) regression is often used to estimate the objective function and uncertainty estimates that guide GP-Upper Confidence Bound (GP-UCB) to determine where next to sample from the objective function, balancing exploration and exploitation. In general, it requires an auxiliary optimization to tune the hyperparameter in GP-UCB, which is sometimes not easy to carry out in practice. In this paper we present a simple practical method which improves GP-UCB, especially in cases where the objective function is not smooth with sharp peaks and valleys. We first present a geometric interpretation of GP-UCB on which we base our development of the clustering-guided method to select the next observation. Clustering is applied to two-dimensional vectors whose entries correspond to the posterior mean and standard deviation computed by GP regression, which is followed by utility maximization with GP-UCB, in order to determine where next to sample from the objective function. Experiments on various functions demonstrate our method alleviates the chance of being trapped in local extrema, making small efforts for auxiliary optimization.

Gradient-based meta-learning methods leverage gradient descent to learn the commonalities among various tasks. While previous such methods have been successful in meta-learning tasks, they resort to simple gradient descent during meta-testing. Our primary contribution is the MT-net, which enables the meta-learner to learn on each layer’s activation space a subspace that the task-specific learner performs gradient descent on. Additionally, a task-specific learner of an MT-net performs gradient descent with respect to a meta-learned distance metric, which warps the activation space to be more sensitive to task identity. We demonstrate that the dimension of this learned subspace reflects the complexity of the task-specific learner’s adaptation task, and also that our model is less sensitive to the choice of initial learning rates than previous gradient-based meta-learning methods. Our method achieves state-of-the-art or comparable performance on few-shot classification and regression tasks.

Binary embedding refers to methods for embedding points in ℝdinto vertices in the Hamming cube of dimension O(d), such that the normalized Hamming distance between the codes preserves a prespecified distance between vectors in the original space. A common approach to binary embedding is to use random projection, followed by one-bit quantization to produce binary codes. Of particular interest, in this letter, is sparse circulant binary embedding (SCBE), where a sparse random circulant matrix with random sampling at a rate of 1 - s for s E (0, 1) is used for random projection. The SCBE has the space complexity O((1 - s)d), while unstructured random projection has the space complexity O(d2). We present an asymptotic analysis of SCBE, when d approaches ∞, showing that the performance of SCBE is comparable to that of binary embedding with unstructured random projection whilethe former has the space complexity O((1 - s)d) and the time complexity O(d log d) but the latter has both space and time complexities O(d2).

We present a model for random simple graphs with power law (i.e., heavy-tailed) degree distributions. To attain this behavior, the edge probabilities in the graph are constructed from Bertoin–Fujita–Roynette–Yor (BFRY) random variables, which have been recently utilized in Bayesian statistics for the construction of power law models in several applications. Our construction readily extends to capture the structure of latent factors, similarly to stochastic block-models, while maintaining its power law degree distribution. The BFRY random variables are well approximated by gamma random variables in a variational Bayesian inference routine, which we apply to several network datasets for which power law degree distributions are a natural assumption. By learning the parameters of the BFRY distribution via probabilistic inference, we are able to automatically select the appropriate power law behavior from the data. In order to further scale our inference procedure, we adopt stochastic gradient ascent routines where the gradients are computed on minibatches (i.e., subsets) of the edges in the graph.

We propose a Bayesian evidence framework to facilitate transfer learning from pre-trained deep convolutional neural networks (CNNs). Our framework is formulated on top of a least squares SVM (LS-SVM) classifier, which is simple and fast in both training and testing, and achieves competitive performance in practice. The regularization parameters in LS-SVM is estimated automatically without grid search and cross-validation by maximizing evidence, which is a useful measure to select the best performing CNN out of multiple candidates for transfer learning, the evidence is optimized efficiently by employing Aitken's delta-squared process, which accelerates convergence of fixed point update. The proposed Bayesian evidence framework also provides a good solution to identify the best ensemble of heterogeneous CNNs through a greedy algorithm. Our Bayesian evidence framework for transfer learning is tested on 12 visual recognition datasets and illustrates the state-of-the-art performance consistently in terms of prediction accuracy and modeling efficiency.

Latent Dirichlet allocation (LDA) is a widely-used topic model where a set of hidden topics is learned to model a collection of data in the form of bag-of-words. Correlated topic model (CTM) extends LDA, modelling topic correlation by using logistic normal prior for topic proportion vectors, instead of Dirichlet prior. However, in the case of bag-of-words from multiple data sources (for instance, streams of time-stamped measurements in sensor networks), where each word in a document is labeled with one of data sources from which the data comes, it is desirable to consider correlations across topics as well as across data sources. In this paper we present two-dimensional correlated topic model (2D-CTM) where we use a matrix-variate logistic normal distribution for a topic proportion matrix, in which correlations across topics as well as across data sources are captured by two covariance matrices of the matrix-variate normal distribution. We develop a mean-field variational inference algorithm for approximate posterior inference in our model 2D-CTM. We apply 2D-CTM to the problem of human activity recognition and sport tactic analysis, using data collected on multiple on-body sensors, with comparison to existing topic models.

Human activity recognition involves classifying times series data, measured at inertial sensors such as accelerometers or gyroscopes, into one of pre-defined actions. Recently, convolutional neural network (CNN) has established itself as a powerful technique for human activity recognition, where convolution and pooling operations are applied along the temporal dimension of sensor signals. In most of existing work, 1D convolution operation is applied to individual univariate time series, while multi-sensors or multi-modality yield multivariate time series. 2D convolution and pooling operations are applied to multivariate time series, in order to capture local dependency along both temporal and spatial domains for uni-modal data, so that it achieves high performance with less number of parameters compared to 1D operation. However for multi-modal data existing CNNs with 2D operation handle different modalities in the same way, which cause interferences between characteristics from different modalities. In this paper, we present CNNs (CNN-pf and CNN-pff), especially CNN-pff, for multi-modal data. We employ both partial weight sharing and full weight sharing for our CNN models in such a way that modality-specific characteristics as well as common characteristics across modalities are learned from multi-modal (or multi-sensor) data and are eventually aggregated in upper layers. Experiments on benchmark datasets demonstrate the high performance of our CNN models, compared to state of the arts methods.

Anomaly detection involves identifying the events which do not conform to an expected pattern in data. A common approach to anomaly detection is to identify outliers in a latent space learned from data. For instance, PCA has been successfully used for anomaly detection. Variational autoencoder (VAE) is a recently-developed deep generative model which has established itself as a powerful method for learning representation from data in a nonlinear way. However, the VAE does not take the temporal dependence in data into account, so it limits its applicability to time series. In this paper we combine the echo-state network, which is a simple training method for recurrent networks, with the VAE, in order to learn representation from multivariate time series data. We present an echo-state conditional variational autoencoder (ES-CVAE) and demonstrate its useful behavior in the task of anomaly detection in multivariate time series data.

Bayesian nonparametric methods based on the Dirichlet process (DP), gamma process and beta process, have proven effective in capturing aspects of various datasets arising in machine learning. However, it is now recognized that such processes have their limitations in terms of the ability to capture power law behavior. As such there is now considerable interest in models based on the Stable Processs (SP), Generalized Gamma process (GGP) and Stable-beta process (SBP). These models present new challenges in terms of practical statistical implementation. In analogy to tractable processes such as the finite-dimensional Dirichlet process, we describe a class of random processes, we call iid finite-dimensional BFRY processes, that enables one to begin to develop efficient posterior inference algorithms such as variational Bayes that readily scale to massive datasets. For illustrative purposes, we describe a simple variational Bayes algorithm for normalized SP mixture models, and demonstrate its usefulness with experiments on synthetic and real-world datasets.

Canonical correlation analysis (CCA) has been successfully used for extracting frequency components of steady-state visual evoked potential (SSVEP) in electroencephalography (EEG). Recently, a few efforts on CCA-based SSVEP methods have been made to demonstrate the benefits for brain computer interface (BCI). Most of these methods are limited to linear CCA. In this paper consider a deep extension of CCA where input data are processed through multiple layers before their correlations are computed. To our best knowledge, it is the first time to apply deep CCA (DCCA) to the task of frequency component extraction in SSVEP. Our empirical study demonstrates that DCCA extracts more robust feature, which has significantly higher signal to noise ratio (SNR) compared to those of CCA, and it results in better performance in classification with the averaged accuracy of 92%.

A commercial web search engine shards its index among many servers, and therefore the response time of a search query is dominated by the slowest server that processes the query. Prior approaches target improving responsiveness by reducing the tail latency , or high-percentile response time, of an individual search server. They predict query execution time, and if a query is predicted to be long-running, it runs in parallel; otherwise, it runs sequentially. These approaches are, however, not accurate enough for reducing a high tail latency when responses are aggregated from many servers because this requires each server to reduce a substantially higher tail latency (e.g., the 99.99th percentile), which we call extreme tail latency. To address tighter requirements of extreme tail latency, we propose a new design space for the problem, subsuming existing work and also proposing a new solution space. Existing work makes a prediction using features available at indexing time and focuses on optimizing prediction features for accelerating tail queries. In contrast, we identify “when to predict?” as another key optimization question. This opens up a new solution of delaying a prediction by a short duration to allow many short-running queries to complete without parallelization and, at the same time, to allow the predictor to collect a set of dynamic features using runtime information. This new question expands a solution space in two meaningful ways. First, we see a significant reduction of tail latency by leveraging “dynamic” features collected at runtime that estimate query execution time with higher accuracy. Second, we can ask whether to override prediction when the “predictability” is low. We show that considering predictability accelerates the query by achieving a higher recall. With this prediction, we propose to accelerate the queries that are predicted to be long-running. In our preliminary work, we focused on parallelization as an acceleration scenario. We extend to consider heterogeneous multicore hardware for acceleration. This hardware combines processor cores with different microarchitectures such as energy-efficient little cores and high-performance big cores, and accelerating web search using this hardware has remained an open problem. We evaluate the proposed prediction framework in two scenarios: (1) query parallelization on a multicore processor and (2) query scheduling on a heterogeneous processor. Our extensive evaluation results show that, for both scenarios of query acceleration using parallelization and heterogeneous cores, the proposed framework is effective in reducing the extreme tail latency compared to a start-of-the-art predictor because of its higher recall, and it improves server throughput by more than 70% because of its improved precision.

Bayesian hierarchical clustering (BHC) is an agglomerative clustering method, where a probabilistic model is defined and its marginal likelihoods are evaluated to decide which clusters to merge. While BHC provides a few advantages over traditional distance-based agglomerative clustering algorithms, successive evaluation of marginal likelihoods and careful hyperparameter tuning are cumbersome and limit the scalability. In this paper we relax BHC into a non-probabilistic formulation, exploring smallvariance asymptotics in conjugate-exponential models. We develop a novel clustering algorithm, referred to as relaxed BHC (RBHC), from the asymptotic limit of the BHC model that exhibits the scalability of distance-based agglomerative clustering algorithms as well as the flexibility of Bayesian nonparametric models. We also investigate the reducibility of the dissimilarity measure emerged from the asymptotic limit of the BHC model, allowing us to use scalable algorithms such as the nearest neighbor chain algorithm. Numerical experiments on both synthetic and real-world datasets demonstrate the validity and high performance of our method.

Locality-sensitive hashing (LSH) is a popular data-independent indexing method for approximate similarity search, where random projections followed by quantization hash the points from the database so as to ensure that the probability of collision is much higher for objects that are close to each other than for those that are far apart. Most of high-dimensional visual descriptors for images exhibit a natural matrix structure. When visual descriptors are represented by high-dimensional feature vectors and long binary codes are assigned, a random projection matrix requires expensive complexities in both space and time. In this paper we analyze a bilinear random projection method where feature matrices are transformed to binary codes by two smaller random projection matrices. We base our theoretical analysis on extending Raginsky and Lazebnik's result where random Fourier features are composed with random binary quantizers to form locality sensitive binary codes. To this end, we answer the following two questions: (1) whether a bilinear random projection also yields similarity-preserving binary codes; (2) whether a bilinear random projection yields performance gain or loss, compared to a large linear projection. Regarding the first question, we present upper and lower bounds on the expected Hamming distance between binary codes produced by bilinear random projections. In regards to the second question, we analyze the upper and lower bounds on covariance between two bits of binary codes, showing that the correlation between two bits is small. Numerical experiments on MNIST and Flickr45K datasets confirm the validity of our method.

Normalized random measures (NRMs) provide a broad class of discrete random measures that are often used as priors for Bayesian nonparametric models. Dirichlet process is a well-known example of NRMs. Most of posterior inference methods for NRM mixture models rely on MCMC methods since they are easy to implement and their convergence is well studied. However, MCMC often suffers from slow convergence when the acceptance rate is low. Tree-based inference is an alternative deterministic posterior inference method, where Bayesian hierarchical clustering (BHC) or incremental Bayesian hierarchical clustering (IBHC) have been developed for DP or NRM mixture (NRMM) models, respectively. Although IBHC is a promising method for posterior inference for NRMM models due to its efficiency and applicability to online inference, its convergence is not guaranteed since it uses heuristics that simply selects the best solution after multiple trials are made. In this paper, we present a hybrid inference algorithm for NRMM models, which combines the merits of both MCMC and IBHC. Trees built by IBHC outlinespartitions of data, which guides Metropolis-Hastings procedure to employ appropriate proposals. Inheriting the nature of MCMC, our tree-guided MCMC (tgMCMC) is guaranteed to converge, and enjoys the fast convergence thanks to the effective proposals guided by trees. Experiments on both synthetic and real world datasets demonstrate the benefit of our method.

Convolutional neural network (CNN), which comprises one or more convolutional and pooling layers followed by one or more fully-connected layers, has gained popularity due to its ability to learn fruitful representations from images or speeches, capturing local dependency and slight-distortion invariance. CNN has recently been applied to the problem of activity recognition, where 1D kernels are applied to capture local dependency over time in a series of observations measured at inertial sensors (3-axis accelerometers and gyroscopes). In this paper we present a multi-modal CNN where we use 2D kernels in both convolutional and pooling layers, to capture local dependency over time as well as spatial dependency over sensors. Experiments on benchmark datasets demonstrate the high performance of our multi-modal CNN, compared to several state of the art methods.

Latent Dirichlet allocation (LDA) is a generative probabilistic model of discrete data, where each observed item is represented as a finite mixture over latent topics. Several multi-modal extensions of LDA to model annotated data are available for image annotation. Most of existing methods model the joint distribution of image features and caption texts, in order to capture statistical correlations between the two modalities, introducing an association module to correlate two sets of hidden topics. In this paper we present an alternative probabilistic model, referred to as pseudo-supervised LDA (psLDA), for image annotation, where we directly explore the caption topics to train the image model. Our model consists of two LDAs, each of which corresponds to caption model and image model, respectively, which are trained individually. However, empirical frequencies of the topics in the caption model are served as pseudo-labels for the image model, so that image and caption models are correlated via these pseudo-labels, instead of via latent variables as in most of existing methods. Numerical experiments on 2688-image Label Me dataset demonstrate the outstanding performance of psLDA, compared to existing methods such as corresponding LDA (cLDA) and topic-regression multi-modal LDA (trmmLDA), as measured by caption perplexity.

Near-duplicate image discovery is the task of detecting all clusters of images which duplicate at a significant region. Previous work generally take divide and conquer approaches composed of two steps: generating cluster seeds using min-hashing, and growing the seeds by searching the entire image space with the seeds as queries. Since the computational complexity of the seed growing step is generally O (NL) where N and L are the number of images and seeds respectively, existing work can hardly be scaled up to a billion-scale dataset because L is typically millions. In this paper, we study a feasible solution of near-duplicate image discovery on one billion images, which is easily implemented on MapReduce framework. The major contribution of this work is to introduce the seed growing step designed to efficiently reduce the number of false positives among cluster seeds with O (cNL) time complexity, where c is small enough for a billion-scale dataset. The basis component of the seed growing step is a bottom-k min-hash, which generates different signatures in a sketch to remove all candidate images that share only one common visual word with a cluster seed. Our evaluations suggest that the proposed method can discover near-duplicate clusters with high precision and recall, and represent some interesting properties of our 1 billion dataset.

A commercial web search engine shards its index among many servers, and therefore the response time of a search query is dominated by the slowest server that processes the query. Prior approaches target improving responsiveness by reducing the tail latency of an individual search server. They predict query execution time, and if a query is predicted to be long-running, it runs in parallel, otherwise it runs sequentially. These approaches are, however, not accurate enough for reducing a high tail latency when responses are aggregated from many servers because this requires each server to reduce a substantially higher tail latency (e.g., the 99.99th-percentile), which we call extreme tail latency.

Bayesian matrix factorization (BMF) is a popular method for collaborative prediction, because of its robustness to overfitting as well as of being free from cross-validation for fine tuning of regularization parameters. In practice, however, due to its cubic time complexity with respect to the rank of factor matrices, existing variational inference algorithms for BMF are not well suited to web-scale datasets where billions of ratings provided by millions of users are available. The time complexity even increases when the side information, such as user binary implicit feedback or item content information, is incorporated into variational Bayesian matrix factorization (VBMF). For instance, a state of the arts in VBMF with side information, is to place Gaussian priors on user and item factor matrices, where mean of each prior is regressed on the corresponding side information. Since this approach introduces additional cubic time complexity with respect to the size of feature vectors, the use of rich side information in a form of high-dimensional feature vector is prohibited. In this paper, we present a scalable inference for VBMF with side information, the complexity of which is linear in the rank K of factor matrices. Moreover, the algorithm can be easily parallelized on multi-core systems. Experiments on large-scale datasets demonstrate the useful behavior of our algorithm such as scalability, fast learning, and prediction accuracy.

Normalized random measures (NRMs) form a broad class of discrete random measures that are used as priors for Bayesian nonparametric models. Dependent normalized random measures (DNRMs) introduce dependencies in a set of NRMs, to facilitate the handling of data where the assumption of exchangeability is violated. Various methods have been developed to construct DNRMs; of particular interest is mixed normalized random measures (MNRMs), where DNRM is represented as a mixture of underlying shared normalized random measures. Emphasis in existing works is placed on the construction methods of DNRMs, but there is a little work on efficient inference for DNRMs. In this paper, we present a tree-based inference method for MNRM mixture models, extending Bayesian hierarchical clustering (BHC) which was originally developed as a deterministic approximate inference for Dirichlet process mixture (DPM) models. We also present an incremental inference for MNRM mixture models, building a tree incrementally in the sense that the tree structure is partially updated whenever a new data point comes in. The tree, when constructed in such a way, allows us to efficiently perform tree-consistent MAP inference in MRNM mixture models, determining a most probable tree-consistent partition, as well as to compute a marginal likelihood approximately. Numerical experiments on both synthetic and real-world datasets demonstrate the usefulness of our algorithm, compared to MCMC methods.

Multi-modal topic models are probabilistic generative models where hidden topics are learned from data of different types. In this paper we present supervised multi-modal latent Dirichlet allocation (smmLDA), where we incorporate class label (global description) into the joint modeling of visual words and caption words (local description), for image annotation task. We derive variational inference algorithm to approximately compute posterior distribution over latent variables. Experiments on a subset of LabelMe dataset demonstrate the useful behavior of our model, compared to existing topic models.

We present a semi-supervised learning algorithm based on local and global consistency, working on a bi-relational graph of images and labels. By incorporating two types of different entities (images and labels) in a single graph, label propagation can exploit label correlations for measuring the relevance between unannotated images and labels, leading to a significant improvement in performance. In our propagation process, images belonging to the same label (or labels belonging to the same image) are not treated equally: our method allows that those images (or labels) have different weights in the label propagation process according to their semantic reliability to the label (or to the image), so that can achieve further improvement in the image annotation performance, compared to the existing work using a bi-relational graph. We apply our method to two benchmark multi-label image datasets, and obtain some encouraging experimental results.

A stochastic blockmodel is a generative model for blocks, where a block is a set of coherent nodes and relations between the nodes are explained by the corresponding pair of blocks. Most existing methods make use of both the presence and the absence of links between nodes, encoded by the adjacency matrix, to learn the corresponding models. In this paper, we present a new method in which we use only the presence of links to learn the model, exploiting the dependency between source and destination nodes, leading to a dependent stochastic blockmodel. We allow for mixed membership and the degrees of nodes in our dependent stochastic blockmodel. Experiments on the political books network and Twitter social network indicate that the behavior of our dependent stochastic blockmodel is superior to that of existing methods.

Existing multi-view feature extraction methods are based on restrictive assumptions on the connections between feature vectors and input data. These assumptions damage the quality of learned features, and also require more effort on choosing right dimensions of feature vector components connected to each view. In this paper we present adaptive multi-view harmonium (SA-MVH) for multi-view feature extraction, where its each hidden node chooses the views to connect with while training phase via switch parameters. "Switch" parameters are multiplied to the connection weights of ordinary exponential family harmoniums (EFH) to decide the existence of connection between hidden nodes and views. With switch parameters, a SA-MVH automatically adapts its structure to achieve better representation of data distribution. The model can also be easily trained using the same training algorithms used for EFHs. Numerical experiments on synthetic and real-world datasets demonstrate the useful behavior of the SA-MVH, compared to the existing multi-view feature extraction methods.

Collaborative prediction involves filling in missing entries of a user-item matrix to predict preferences of users based on their observed preferences. Most of existing models assume that the data is missing at random (MAR), which is often violated in recommender systems in practice. Incorrect assumption on missing data ignores the missing data mechanism, leading to biased inferences and prediction. In this paper we present a Bayesian binomial mixture model for collaborative prediction, where the generative process for data and missing data mechanism are jointly modeled to handle non-random missing data. Missing data mechanism is modeled by three factors, each of which is related to users, items, and rating values. Each factor is modeled by Bernoulli random variable, and the observation of rating value is determined by the Boolean OR operation of three binary variables. We develop computationally-efficient variational inference algorithms, where variational parameters have closed-form update rules and the computational complexity depends on the number of observed ratings, instead of the size of the rating data matrix. We also discuss implementation issues on hyperparameter tuning and estimation based on empirical Bayes. Experiments on Yahoo! Music and MovieLens datasets confirm the useful behavior of our model by demonstrating that: (1) it outperforms state-of-the-art methods in yielding higher predictive performance; (2) it finds meaningful solutions instead of undesirable boundary solutions; (3) it provides rating trend analysis on why ratings are observed.

Multiclass problems are often decomposed into multiple binary problems that are solved by individual binary classifiers whose results are integrated into a final answer. Various methods, including all-pairs (APs), one-versus-all (OVA), and error correcting output code (ECOC), have been studied, to decompose multiclass problems into binary problems. However, little study has been made to optimally aggregate binary problems to determine a final answer to the multiclass problem. In this paper we present a convex optimization method for an optimal aggregation of binary classifiers to estimate class membership probabilities in multiclass problems. We model the class membership probability as a softmax function which takes a conic combination of discrepancies induced by individual binary classifiers, as an input. With this model, we formulate the regularized maximum likelihood estimation as a convex optimization problem, which is solved by the primal-dual interior point method. Connections of our method to large margin classifiers are presented, showing that the large margin formulation can be considered as a limiting case of our convex formulation. In the experiments on human disease classification, we demonstrate that our method outperforms existing aggregation methods as well as direct methods, in terms of the classification accuracy and F-score.

Glossokinetic potential (GKP) is the potential response generated from tongue movements. The tongue is one of main articulators determining the sound of spoken language, and tongue-oriented GKP can severely interfere electroencephalography (EEG) signals involved in language-related tasks. To clarify the relation between GKP and language, and provide information such that what kinds of phonemes evoke GKP response and where the response can be observed, we investigate GKP responses from various phonemes. In detail, we record EEG signals when the tongue touches each place of articulation (the reference points used for the categorization of consonants in phonetics), then analyze their spatial and scale patterns. The results showed pronouncing dental, palato-alveolar, and palatal consonants evokes potential decrease in the frontal region, and potential increase in the occipital region. On the other hand, pronouncing retroflex consonant evokes potential increase in the frontal region, and decrease in the occipital region. We believe that the surveyed GKP patterns will be useful for developing artifact removal techniques eliminating language-related artifacts. The GKP removal could be beneficial for neuroscience in language processing, implementing brain-computer interface in real-world condition, and developing a novel silent speech recognition technique.

Cells execute their functions through dynamic operations of biological networks. Dynamic networks delineate the operation of biological networks in terms of temporal changes of abundances or activities of nodes (proteins and RNAs), as well as formation of new edges and disappearance of existing edges over time. Global genomic and proteomic technologies can be used to decode dynamic networks. However, using these experimental methods, it is still challenging to identify temporal transition of nodes and edges. Thus, several computational methods for estimating dynamic topological and functional characteristics of networks have been introduced. In this review, we summarize concepts and applications of these computational methods for inferring dynamic networks and further summarize methods for estimating spatial transition of biological networks.

MOTIVATION: Time-evolving differential protein-protein interaction (PPI) networks are essential to understand serial activation of differentially regulated (up- or downregulated) cellular processes (DRPs) and their interplays over time. Despite developments in the network inference, current methods are still limited in identifying temporal transition of structures of PPI networks, DRPs associated with the structural transition and the interplays among the DRPs over time. RESULTS: Here, we present a probabilistic model for estimating Time-Evolving differential PPI networks with MultiPle Information (TEMPI). This model describes probabilistic relationships among network structures, time-course gene expression data and Gene Ontology biological processes (GOBPs). By maximizing the likelihood of the probabilistic model, TEMPI estimates jointly the time-evolving differential PPI networks (TDNs) describing temporal transition of PPI network structures together with serial activation of DRPs associated with transiting networks. This joint estimation enables us to interpret the TDNs in terms of temporal transition of the DRPs. To demonstrate the utility of TEMPI, we applied it to two time-course datasets. TEMPI identified the TDNs that correctly delineated temporal transition of DRPs and time-dependent associations between the DRPs. These TDNs provide hypotheses for mechanisms underlying serial activation of key DRPs and their temporal associations. AVAILABILITY AND IMPLEMENTATION: Source code and sample data files are available at http://sbm.postech.ac.kr/tempi/sources.zip. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Link-based dissimilarity measures, such as shortest path or Euclidean commute time distance, base their distance on paths between nodes of a weighted graph. These measures are known to be better suited to data manifold with nonconvex-shaped clusters, compared to Euclidean distance, so that k-nearest neighbor (NN) search is improved in such metric spaces. In this paper we present a new link-based dissimilarity measure based on minimax paths between nodes. Two main benefits of minimax path-based dissimilarity measure are: (1) only a subset of paths is considered to make it scalable, while Euclidean commute time distance considers all possible paths; (2) it better captures nonconvex-shaped cluster structure, compared to shortest path distance. We define the total cost assigned to a path between nodes as Lp norm of intermediate costs of edges involving the path, showing that minimax path emerges from our Lp norm over paths framework. We also define minimax distance as the intermediate cost of the longest edge on the minimax path, then present a greedy algorithm to compute k smallest minimax distances between a query and N data points in O(log N + k log k) time. Numerical experiments demonstrate that our minimax k-NN algorithm reduce the search time by several orders of magnitude, compared to existing methods, while the quality of k-NN search is significantly improved over Euclidean distance.

Common spatial patterns (CSP) or its probabilistic counterpart, PCSP, is a popular discriminative feature extraction method for electroencephalography (EEG) classification. Models in CSP or PCSP are trained on a subject-by-subject basis so that inter-subject information is not used. In the case of multi-subject EEG classification where brain waves recorded from multiple subjects who undergo the same mental task are available, it is desirable to capture inter-subject relatedness in learning a model. In this paper we present a nonparametric Bayesian model for a multi-subject extension of CSP where subject relatedness is captured by assuming that spatial patterns across subjects share a latent subspace. Spatial patterns and the shared latent subspace are jointly learned by variational inference. We use an infinite latent feature model to automatically infer the dimension of the shared latent subspace, placing Indian Buffet process (IBP) priors on our model. Numerical experiments on BCI competition IV 2a dataset demonstrate the high performance of our method, compared to PCSP and existing Bayesian multi-task CSP models.

Multi-view hashing seeks compact integrated binary codes which preserve similarities averaged over multiple representations of objects. Most of existing multi-view hashing methods resort to linear hash functions where data manifold is not considered. In this paper we present multi-view anchor graph hashing (MVAGH), where nonlinear integrated binary codes are efficiently determined by a subset of eigenvectors of an averaged similarity matrix. The efficiency behind MVAGH is due to a low-rank form of the averaged similarity matrix induced by multi-view anchor graph, where the similarity between two points is measured by two-step transition probability through view-specific anchor (i.e. landmark) points. In addition, we observe that MVAGH suffers from the performance degradation when the high recall is required. To overcome this drawback, we propose a simple heuristic to combine MVAGH with locality sensitive hashing (LSH). Numerical experiments on CIFAR-10 dataset confirms that MVAGH(+LSH) outperforms the existing multi- and single-view hashing methods.

Multi-label learning refers to methods for learning a set of functions that assigns a set of relevant labels to each instance. One of popular approaches to multi-label learning is label ranking, where a set of ranking functions are learned to order all the labels such that relevant labels are ranked higher than irrelevant ones. Rank-SVM is a representative method for label ranking where ranking loss is minimized in the framework of max margin. However, the dual form in Rank-SVM involves a quadratic programming which is generally solved in cubic time in the size of training data. The primal form is appealing for the development of online learning but involves a nonsmooth convex loss function. In this paper we present a method for online multi-label learning where we minimize the primal form using the accelerated nonsmooth stochastic gradient descent which has been recently developed to extend Nesterov's smoothing method to the stochastic setting. Numerical experiments on several large-scale datasets demonstrate the computational efficiency and fast convergence of our proposed method, compared to existing methods including subgradient-based algorithms.

In pattern recognition, data integration is an important issue, and when properly done, it can lead to improved performance. Also, data integration can be used to help model and understand multimodal processing in the brain. Amari proposed α-integration as a principled way of blending multiple positive measures (e.g., stochastic models in the form of probability distributions), enabling an optimal integration in the sense of minimizing the α-divergence. It also encompasses existing integration methods as its special case, for example, a weighted average and an exponential mixture. The parameter α determines integration characteristics, and the weight vector w assigns the degree of importance to each measure. In most work, however, α and w are given in advance rather than learned. In this letter, we present a parameter learning algorithm for learning α and ω from data when multiple integrated target values are available. Numerical experiments on synthetic as well as real-world data demonstrate the effectiveness of the proposed method.

Matrix factorization with trace norm regularization is a popular approach to matrix completion and collaborative filtering. When entries of the matrix are sampled non-uniformly (which is the case for collaborative prediction), a properly weighted correction to the trace norm regularization is known to improve the performance dramatically. While the weighted trace norm regularization has been rigorously studied, its generative counterpart is not known yet. In this paper we show that the weighted trace norm regularization emerges from variational Bayesian matrix factorization where variational distributions over factor matrices are restricted to be isotropic Gaussians with the common variance. We show that variational variance corresponds to the regularization parameter. Thus, the regularization parameter can be automatically learned by variational inference rather than cross-validation. Experiments on MovieLens and Netflix datasets confirm the variational Bayesian perspective of the weighted trace norm regularization, demonstrating that variational parameter learned by variational inference agrees with the value of the regularization parameter found by cross-validation.

Common spatial patterns (CSP) is a popular feature extraction method for discriminating between positive andnegative classes in electroencephalography (EEG) data.Two probabilistic models for CSP were recently developed: probabilistic CSP (PCSP), which is trained by expectation maximization (EM), and variational BayesianCSP (VBCSP) which is learned by variational approx-imation. Parameter expansion methods use auxiliaryparameters to speed up the convergence of EM or thedeterministic approximation of the target distributionin variational inference. In this paper, we describethe development of parameter-expanded algorithms forPCSP and VBCSP, leading to PCSP-PX and VBCSP-PX, whose convergence speed-up and high performanceare emphasized. The convergence speed-up in PCSP-PX and VBCSP-PX is a direct consequence of parame-ter expansion methods. The contribution of this study is the performance improvement in the case of CSP,which is a novel development. Numerical experimentson the BCI competition datasets, III IV a and IV 2ademonstrate the high performance and fast convergenceof PCSP-PX and VBCSP-PX, as compared to PCSP andVBCSP.

Matrix co-factorization involves jointly decomposing several data matrices to approximate each data matrix as a product of two factor matrices, sharing some factor matrices in the factorization. We have recently developed variational Bayesian matrix co-factorization where factor matrices are inferred by computing variational posterior distributions in the case of Gaussian likelihood with Gaussian prior placed on factor matrices. Empirical Bayesian method was used, so hyperparameters are set to specific values determined by maximizing marginal likelihood. In this paper we present a hierarchical Bayesian model for matrix co-factorization in which we derive a variational inference algorithm to approximately compute posterior distributions over factor matrices as well as hyperparameters, placing Gaussian-Wishart prior on hyperparameters. Numerical experiments on MovieLens data demonstrate that the hierarchical variational Bayesian matrix co-factorization alleviates the over-fitting better than the empirical variational Bayesian matrix co-factorization, leading to the improved performance in terms of MAE and RMSE.

Hashing seeks an embedding of high-dimensional objects into a similarity-preserving low-dimensional Hamming space such that similar objects are indexed by binary codes with small Hamming distances. A variety of hashing methods have been developed, but most of them resort to a single view (representation) of data. However, objects are often described by multiple representations. For instance, images are described by a few different visual descriptors (such as SIFT, GIST, and HOG), so it is desirable to incorporate multiple representations into hashing, leading to multi-view hashing. In this paper we present a deep network for multi-view hashing, referred to as deep multi-view hashing, where each layer of hidden nodes is composed of view-specific and shared hidden nodes, in order to learn individual and shared hidden spaces from multiple views of data. Numerical experiments on image datasets demonstrate the useful behavior of our deep multi-view hashing (DMVH), compared to recently-proposed multi-modal deep network as well as existing shallow models of hashing.

Hashing, which involves learning binary codes to embed high-dimensional data into a similarity-preserving low-dimensional Hamming space, is often formulated as linear dimensionality reduction followed by binary quantization. Linear dimensionality reduction, based on maximum variance formulation, requires leading eigenvectors of data covariance or graph Laplacian matrix. Computing leading singular vectors or eigenvectors in the case of high-dimension and large sample size, is a main bottleneck in most of data-driven hashing methods. In this paper we address the use of generalized Nystrom method where a subset of rows and columns are used to approximately compute leading singular vectors of the data matrix, in order to improve the scalability of hashing methods in the case of high-dimensional data with large sample size. Especially we validate the useful behavior of generalized Nystrom approximation with uniform sampling, in the case of a recently-developed hashing method based on principal component analysis (PCA) followed by an iterative quantization, referred to as PCA+ITQ, developed by Gong and Lazebnik. We compare the performance of generalized Nystrom approximation with uniform and non-uniform sampling, to the full singular value decomposition (SVD) method, confirming that the uniform sampling improves the computational and space complexities dramatically, while the performance is not much sacrificed. In addition we present low-rank approximation error bounds for generalized Nystrom approximation with uniform sampling, which is not a trivial extension of available results on the non-uniform sampling case.

Multi-subject electroencephalography (EEG) classification involves the categorization of brain waves measured from multiple subjects, each of whom undergoes the same mental task. Common spatial patterns (CSP) or probabilistic CSP (PCSP) are widely used for extracting discriminative features from EEG, although they are trained on a subject-by-subject basis and inter-subject information is neglected. Moreover, the performance is degraded when only a few training samples are available for each subject. In this paper, we present a method for Bayesian CSP with Dirichlet process (DP) priors, where spatial patterns (corresponding to basis vectors) are simultaneously learned and clustered across subjects using variational Bayesian inference, which facilitates a flexible mixture model where the number of components are also learned. Spatial patterns in the same cluster share the hyperparameters of their prior distributions, which means information transfer is facilitated among subjects with similar spatial patterns. Numerical experiments using the BCI competition IV 2a dataset demonstrated the high performance of our method, compared with existing PCSP and Bayesian CSP methods with a single prior distribution.

The P300 wave refers to a positive peak with a latency of 300 ms, produced in response to task-relevant stimuli. It is a widely-used event related potential (ERP) in practical brain computer interface (BCI) systems, where a classifier is trained using discriminative features extracted from a set of labeled examples, in order to detect the presence of P300. Given a small training examples, the intra- and inter-subject variations in amplitude and latency of P300 degrade the performance of classifier. Thus, it requires a longer training period (calibration time) with more labeled examples for satisfactory performance. In this paper we present a self-labeling method, where confident unlabeled data, together with their predicted labels, are gradually added to the training set, in order to re-train the classifier. Linear discriminant analysis with singular value decomposition is used to progressively extract discriminate features. Experiments demonstrate the high performance of our method, especially in the case where a small number of training examples are available. We also apply the method to the zero-calibration P300-based BCI, which removes subject-dependent calibration procedures by using the training set already recorded from other subjects.

Kernel nonnegative matrix factorization (KNMF) is a recent kernel extension of NMF, where matrix factorization is carried out in a reproducing kernel Hilbert space (RKHS) with a feature mapping φ(·). Given a data matrix X ∈ ℝm×n, KNMF seeks a decomposition, φ(X) ≈ UVT, where the basis matrix takes the form U = φ(X)W and parameters W ∈ ℝn×rand V ∈ ℝ+n×rare estimated without explicit knowledge of φ(·). As in most of kernel methods, the performance of KNMF also heavily depends on the choice of kernel. In order to alleviate the kernel selection problem when a single kernel is used, we present multiple kernel NMF (MKNMF) where two learning problems are jointly solved in unsupervised manner: (1) learning the best convex combination of kernel matrices; (2) learning parameters W and V. We formulate multiple kernel learning in MKNMF as a linear programming and estimate W and V using multiplicative updates as in KNMF. Experiments on benchmark face datasets confirm the high performance of MKNMF over several existing variants of NMF, in the task of feature extrac tion for face classification.

Multiclass classification problems are often decomposed into multiple binary problems that are solved by individual binary classifiers whose results are integrated into a final answer. We present a convex optimization-based method for aggregating results of binary classifiers in an optimal way to estimate class membership probabilities. We model the class membership probability as a softmax function whose input argument is a conic combination of discrepancies induced by individual binary classifiers. With this model, we formulate the £ι -regularized maximum likelihood estimation as a convex optimization that is solved by geometric programming. Numerical experiments on several UCI datasets demonstrate the high performance of our method, compared to existing methods.

Hashing refers to methods for embedding high dimensional data into a similarity-preserving low-dimensional Hamming space such that similar objects are indexed by binary codes whose Hamming distances are small. Learning hash functions from data has recently been recognized as a promising approach to approximate nearest neighbor search for high dimensional data. Most of 'learning to hash' methods resort to either unsupervised or supervised learning to determine hash functions. Recently semi-supervised learning approach was introduced in hashing where pair wise constraints (must link and cannot-link) using labeled data are leveraged while unlabeled data are used for regularization to avoid over-fitting. In this paper we base our semi-supervised hashing on linear discriminant analysis, where hash functions are learned such that labeled data are used to maximize the separability between binary codes associated with different classes while unlabeled data are used for regularization as well as for balancing condition and pair wise decor relation of bits. The resulting method is referred to as semi-supervised discriminant hashing (SSDH). Numerical experiments on MNIST and CIFAR-10 datasets demonstrate that our method outperforms existing methods, especially in the case of short binary codes.

MOTIVATION: Systems biology attempts to describe complex systems behaviors in terms of dynamic operations of biological networks. However, there is lack of tools that can effectively decode complex network dynamics over multiple conditions. RESULTS: We present principal network analysis (PNA) that can automatically capture major dynamic activation patterns over multiple conditions and then generate protein and metabolic subnetworks for the captured patterns. We first demonstrated the utility of this method by applying it to a synthetic dataset. The results showed that PNA correctly captured the subnetworks representing dynamics in the data. We further applied PNA to two time-course gene expression profiles collected from (i) MCF7 cells after treatments of HRG at multiple doses and (ii) brain samples of four strains of mice infected with two prion strains. The resulting subnetworks and their interactions revealed network dynamics associated with HRG dose-dependent regulation of cell proliferation and differentiation and early PrPSc accumulation during prion infection. AVAILABILITY: The web-based software is available at: http://sbm.postech.ac.kr/pna.

Methods for discriminative motif discovery in DNA sequences identify transcription factor binding sites (TFBSs), searching only for patterns that differentiate two sets (positive and negative sets) of sequences. On one hand, discriminative methods increase the sensitivity and specificity of motif discovery, compared to generative models. On the other hand, generative models can easily exploit unlabeled sequences to better detect functional motifs when labeled training samples are limited. In this paper, we develop a hybrid generative/discriminative model which enables us to make use of unlabeled sequences in the framework of discriminative motif discovery, leading to semisupervised discriminative motif discovery. Numerical experiments on yeast ChIP-chip data for discovering DNA motifs demonstrate that the best performance is obtained between the purely-generative and the purely-discriminative and the semisupervised learning improves the performance when labeled sequences are limited.

Sensory data integration is an important task in human brain for multimodal processing as well as in machine learning for multisensor processing. α-integration was proposed by Amari as a principled way of blending multiple positive measures (e.g., stochastic models in the form of probability distributions), providing an optimal integration in the sense of minimizing the α-divergence. It also encompasses existing integration methods as its special case, e.g., weighted average and exponential mixture. In α-integration, the value of α determines the characteristics of the integration and the weight vector w assigns the degree of importance to each measure. In most of the existing work, however, α and w are given in advance rather than learned. In this paper we present two algorithms, for learning α and w from data when only a few integrated target values are available. Numerical experiments on synthetic as well as real-world data confirm the proposed method's effectiveness.

In pattern recognition, data integration is a processing method to combine multiple sources so that the combined result can be more accurate than a single source. Evidence theory is one of the methods that have been successfully applied to the data integration task. Since Dempster-Shafer theory as the first evidence theory can be against our intuitive reasoning with some data sets, many researchers have proposed different rules for evidence theory. Among all these rules, the averaging rule is known to be better than others. On the other hand, a-integration was proposed by Amari as a principled way of blending multiple positive measures. It is a generalized averaging algorithm including arithmetic, geometric and harmonic means as its special case. In this paper, we generalize evidence theory with α-integration. Our experimental results show how our proposed methods work.

An unsupervised method is proposed aiming at extracting rhythmic sources from commercial polyphonic music whose number of channels is limited to one. Commercial music signals are not usually provided with more than two channels while they often contain multiple instruments including singing voice. Therefore, instead of using conventional ways, such as modeling mixing environments or statistical characteristics, we should introduce other source-specific characteristics for separating or extracting the sources. In this paper, we concentrate on extracting rhythmic sources from the mixture with the other harmonic sources. An extension of nonnegative matrix factorization (NMF) is used to analyze multiple relationships between spectral and temporal properties in the given input matrices. Moreover, temporal repeatability of the rhythmic sound sources is implicated as common rhythmic property among segments of an input mixture signal. The proposed method shows acceptable, but not superior separation quality to the referred drum source separation systems. However, it has better applicability due to its blind manner in separation.

We address a problem of separating drums from polyphonic music containing various pitched instruments as well as drums. Nonnegative matrix factorization (NMF) was successfully applied to spectrograms of music to learn basis vectors, followed by support vector machine (SVM) to classify basis vectors into ones associated with drums (rhythmic source) only and pitched instruments (harmonic sources). Basis vectors associated with pitched instruments are used to reconstruct drum-eliminated music. However, it is cumbersome to construct a training set for pitched instruments since various instruments are involved. In this paper, we propose a method which only incorporates prior knowledge on drums, not requiring such training sets of pitched instruments. To this end, we present nonnegative matrix partial co-factorization (NMPCF) where the target matrix (spectrograms of music) and drum-only-matrix (collected from various drums a priori) are simultaneously decomposed, sharing some factor matrix partially, to force some portion of basis vectors to be associated with drums only. We develop a simple multiplicative algorithm for NMPCF and show its usefulness empirically, with numerical experiments on real-world music signals.

Multiclass classification problems are often decomposed into multiple binary problems that are solved by individual binary classifiers whose results are integrated into a final answer. Various methods have been developed to aggregate binary classifiers, including voting heuristics, loss-based decoding, and probabilistic decoding methods, but a little work on the optimal aggregation has been done. In this paper we present a Bayesian method for optimally aggregating binary classifiers where class membership probabilities are determined by predictive probabilities. We model the class membership probability as a softmax function whose input argument is a linear combination of discrepancies between code words and probability estimates obtained by the binary classifiers. We consider a lower bound on the softmax function, which is represented as a product of logistic sigmoids, and we formulate the problem of learning aggregation weights as a variational logistic regression. Predictive probabilities computed by variational logistic regression yield the class membership probabilities. We stress two notable advantages over existing methods in the viewpoint of complexity and over fitting. Numerical experiments on several datasets confirm its useful behavior.

Nonnegative matrix factorization (NMF) is a popular method for low-rank approximation of nonnegative matrix, providing a useful tool for representation learning that is valuable for clustering and classification. When a portion of data are labeled, the performance of clustering or classification is improved if the information on class labels is incorporated into NMF. To this end, we present semi-supervised NMF (SSNMF), where we jointly incorporate the data matrix and the (partial) class label matrix into NMF. We develop multiplicative updates for SSNMF to minimize a sum of weighted residuals, each of which involves the nonnegative 2-factor decomposition of the data matrix or the label matrix, sharing a common factor matrix. Experiments on document datasets and EEG datasets in BCI competition confirm that our method improves clustering as well as classification performance, compared to the standard NMF, stressing that semi-supervised NMF yields semi-supervised feature extraction.

Nonnegative matrix factorization (NMF) is a widely-used method for low-rank approximation (LRA) of a nonnegative matrix (matrix with only nonnegative entries), where nonnegativity constraints are imposed on factor matrices in the decomposition. A large body of past work on NMF has focused on the case where the data matrix is complete. In practice, however, we often encounter with an incomplete data matrix where some entries are missing (e.g., a user-rating matrix). Weighted low-rank approximation (WLRA) has been studied to handle incomplete data matrix. However, there is only few work on weighted nonnegative matrix factorization (WNMF) that is WLRA with nonnegativity constraints. Existing WNMF methods are limited to a direct extension of NMF multiplicative updates, which suffer from slow convergence while the implementation is easy. In this paper we develop relatively fast and scalable algorithms for WNMF, borrowed from well-studied optimization techniques: (1) alternating nonnegative least squares; (2) generalized expectation maximization. Numerical experiments on MovieLens and Netflix prize datasets confirm the useful behavior of our methods, in a task of collaborative prediction.

Landmark multidimensional scaling (LMDS) uses a subset of data (landmark points) to solve classical MDS, where the scalability is increased but the approximation is noise-sensitive. In this paper we present an ensemble of LMDSs, referred to as landmark MDS ensemble (LMDSE), where we use a portion of the input in a piecewise manner to solve classical MDS, combining individual LMDS solutions which operate on different partitions of the input. Ground control points (GCPs) that are shared by partitions considered in the ensemble, allow us to align individual LMDS solutions in a common coordinate system through affine transformations. LMDSE solution is determined by averaging aligned LMDS solutions. We show that LMDSE is less noise-sensitive while maintaining the scalability as well as the speed of LMDS. Experiments on synthetic data (noisy grid) and real-world data (similar image retrieval) confirm the high performance of the proposed LMDSE.

In this paper we present a method for extracting a speech signal of target speaker from noisy convolutive mixtures of target speech and an interference source, when training utterances of the target speaker are available. We incorporate a statistical latent variable model into blind source separation (BSS), where we make use of spectral bases learned from the training utterances of the target speaker to identify which source corresponds to the target speaker. Combined with any existing BSS methods, our post-processing (which is the main contribution) consists of two steps: (1) channel selection where we identify the source corresponding to the target speaker; (2) enhancement where we further suppress the remaining interference. Numerical experiments confirm that our method substantially improves the separation quality of existing BSS methods and successfully restores the target speaker's speech.

Nonnegative matrix tri-factorization (NMTF) is a 3-factor decomposition of a nonnegative data matrix, X ap USVT, where factor matrices, U, S, and V , are restricted to be nonnegative as well. Motivated by the aspect model used for dyadic data analysis as well as in probabilistic latent semantic analysis (PLSA), we present a probabilistic model with two dependent latent variables for NMTF, referred to as probabilistic matrix tri-factorization (PMTF). Each latent variable in the model is associated with the cluster variable for the corresponding object in the dyad, leading the model suited to co-clustering. We develop an EM algorithm to learn the PMTF model, showing its equivalence to multiplicative updates derived by an algebraic approach. We demonstrate the useful behavior of PMTF in a task of document clustering. Moreover, we incorporate the likelihood in the PMTF model into existing information criteria so that the number of clusters can be detected, while the algebraic NMTF cannot.

Most of existing methods for DNA motif discovery consider only a single set of sequences to find an over-represented motif. In contrast, we consider multiple sets of sequences where we group sets associated with the same motif into a cluster, assuming that each set involves a single motif. Clustering sets of sequences yields clusters of coherent motifs, improving signal-to-noise ratio or enabling us to identify multiple motifs. We present a probabilistic model for DNA motif discovery where we identify multiple motifs through searching for patterns which are shared across multiple sets of sequences. Our model infers cluster-indicating latent variables and learns motifs simultaneously, where these two tasks interact with each other. We show that our model can handle various motif discovery problems, depending on how to construct multiple sets of sequences. Experiments on three different problems for discovering DNA motifs emphasize the useful behavior and confirm the substantial gains over existing methods where only single set of sequences is considered.

Common spatial pattern (CSP) is a popular feature extraction method for electroencephalogram (EEG) classification. Most of existing CSP-based methods exploit covariance matrices on a subject-by-subject basis so that inter-subject information is neglected. In this paper we present modifications of CSP for subject-to-subject transfer, where we exploit a linear combination of covariance matrices of subjects in consideration. We develop two methods to determine a composite covariance matrix that is a weighted sum of covariance matrices involving subjects, leading tocompositeCSP. Numerical experiments on dataset IVa in BCI competition III confirm that our composite CSP methods improve classification performance over the standard CSP (on a subject-by-subject basis), especially in the case of subjects with fewer number of training samples.

Nonnegative tucker decomposition (NTD) is a recent multiway extension of nonnegative matrix factorization (NMF), where nonnega- tivity constraints are incorporated into Tucker model. In this paper we consider alpha-divergence as a discrepancy measure and derive multiplicative updating algorithms for NTD. The proposed multiplicative algorithm includes some existing NMF and NTD algorithms as its special cases, since alpha-divergence is a one-parameter family of divergences which accommodates KL-divergence, Hellinger divergence, X2divergence, and so on. Numerical experiments on face images show how different values of alpha affect the factorization results under different types of noise.

In this paper we present a probabilistic method for source separation in the case where each source has a certain unknown temporal structure. We tackle the problem of source separation by maximum pseudo-likelihood estimation, representing the latent function which characterizes the temporal structure of each source by a random process with a Gaussian prior. The resulting pseudo-likelihood of the data is Gaussian, determined by a mixing matrix as well as by the predictive mean and covariance matrix that can be easily computed by Gaussian process (GP) regression. Gradient-based optimization is applied to estimate the demixing matrix through maximizing the log-pseudo-likelihood of the data. Numerical experiments confirm the useful behavior of our method, compared to existing source separation methods.

Speaker independent feature extraction is a critical problem in speech recognition. Oriented principal component analysis (OPCA) is a potential solution that can find a subspace robust against noise of the data set. The objective of this paper is to find a speaker-independent subspace by generalizing OPCA in two steps: First, we find a nonlinear subspace with the help of a kernel trick, which we refer to as kernel OPCA. Second, we generalize OPCA to problems with more than two phonemes, which leads to oriented discriminant analysis (ODA). In addition, we equip ODA with the kernel trick again, which we refer to as kernel ODA. The models are tested on the CMU ARCTIC speech database. Our results indicate that our proposed kernel methods can outperform linear OPCA and linear ODA at finding a speaker-independent phoneme space.

Nonnegative matrix factorization (NMF) is a widely-used method for multivariate analysis of nonnegative data, the goal of which is decompose a data matrix into a basis matrix and an encoding variable matrix with all of these matrices allowed to have only nonnegative elements. In this paper we present simple algorithms for orthogonal NMF, where orthogonality constraints are imposed on basis matrix or encoding matrix. We develop multiplicative updates directly from the true gradient (natural gradient) in Stiefel manifold, whereas existing algorithms consider additive orthogonality constraints. Numerical experiments on face image data for a image representation task show that our orthogonal NMF algorithm preserves the orthogonality, while the goodness-of-fit (GOF) is minimized. We also apply our orthogonal NMF to a clustering task, showing that it works better than the original NMF, which is confirmed by experiments on several UCI repository data sets.

Nonnegative matrix factorization (NMF) is a popular method for multivariate analysis of nonnegative data. It was successfully applied to learn spectral features from EEG data. However, the size of a data matrix grows, NMF suffers from ‘out of memory’ problem. In this paper we present a memory-reduced method where we downsize the data matrix using CUR decomposition before NMF is applied. Experimental results with two EEG data sets in BCI competition, confirm the useful behavior of the proposed method.

Gaussian process (GP) model is a flexible nonparametric Bayesian method that is widely used in regression and classification. In this paper we present a probabilistic method where we solve voice activity detection (VAD) and speech enhancement in a single framework of GP regression, modeling clean speech by a GP smoother. Optimized hyperparameters in GP models lead us to a novel VAD method since learned length-scale parameters in covariance functions are much different between voiced and unvoiced frames. Clean speech is estimated by posterior means in GP models. Numerical experiments confirm the validity of our method.

Nonnegative tensor factorization (NTF) is a recent multiway (multilinear) extension of nonnegative matrix factorization (NMF), where nonnegativity constraints are imposed on the CANDECOMP/PARAFAC model. In this paper we consider the Tucker model with nonnegativity constraints and develop a new tensor factorization method, referred to as nonnegative Tucker decomposition (NTD). The main contributions of this paper include: (1) multiplicative updating algorithms for NTD; (2) an initialization method for speeding up convergence; (3) a sparseness control method in tensor factorization. Through several computer vision examples, we show the useful behavior of the NTD, over existing NTF and NMF methods.

In this paper we propose new algorithms for 3D tensor decomposition/factorization with many potential applications, especially in multi-way blind source separation (BSS), multidimensional data analysis, and sparse signal/image representations. We derive and compare three classes of algorithms: multiplicative, fixed-point alternating least squares (FPALS) and alternating interior-point gradient (AIPG) algorithms. Some of the proposed algorithms are characterized by improved robustness, efficiency and convergence rates and can be applied for various distributions of data and additive noise.

Nonnegative matrix factorization (NMF) is a widely-used method for multivariate nonnegative data analysis, due to its ability to learn a parts-based representation. However, the standard NMF algorithm does not always find spatially localized basis images in practice, unless sparseness constraints are employed. In this paper we present a method of structured initialization which enables the standard NMF algorithm to find spatially localized basis images. The initialization method is based on the hierarchical clustering of attributes through a similarity measure reflecting 'closeness to rank-one'. Numerical experiments with face image data, confirm the validity of our initialization method.

In this paper we present a kernel method for data clustering, where the soft k-means is carried out in a feature space, instead of input data space, leading to soft kernel k-means. We also incorporate a geodesic kernel into the soft kernel k-means, in order to take the data manifold structure into account. The method is referred to as soft geodesic kernel k-means. In contrast to k-means, our method is able to identify clusters that are not linearly separable. In addition, soft responsibilities as well as geodesic kernel, improve the clustering performance, compared to kernel k-means. Numerical experiments with toy data sets and real-world data sets (UCI and document clustering), confirm the useful behavior of the proposed method.

Neighbor search is a fundamental task in machine learning, especially in classification and retrieval. Efficient nearest neighbor search methods have been widely studied, with their emphasis on data structures but most of them did not consider the underlying global geometry of a data set. Recent graph-based semi-supervised learning methods capture the global geometry, but suffer from scalability and parameter tuning problems. In this paper we present a (nearest) neighbor search method where the underlying global geometry is incorporated and the parameter tuning is not required. To this end, we introduce deterministic walks as a deterministic counterpart of Markov random walks, leading us to use the minimax distance as a global dissimilarity measure. Then we develop a message passing algorithm for efficient minimax distance calculation, which scales linearly in both time and space. Empirical study reveals the useful behavior of the method in image retrieval and semi-supervised learning.

In this paper we introduce a coupled Helmholtz machine for principal component analysis (PCA), where sub-machines are related through sharing some latent variables and associated weights. We present a wake-sleep algorithm for PCA (referred to as WS-PCA), leading both generative and recognition weights to converge to principal eigenvectors of a data covariance matrix without rotational ambiguity, in contrast to probabilistic PCA and EM-PCA. Then we also present a kernerlized variation, i.e., a wake-sleep algorithm for kernel PCA (WS-KPCA). The coupled Helmholtz machine provides a unified view of principal component analysis, including various existing algorithms as its special cases. The validity of wake-sleep PCA and KPCA algorithms are confirmed by numerical experiments.

In this paper we present a method for continuous EEG classification, where we employ nonnegative tensor factorization (NTF) to determine discriminative spectral features and use the Viterbi algorithm to continuously classify multiple mental tasks. This is an extension of our previous work on the use of nonnegative matrix factorization (NMF) for EEG classification. Numerical experiments with two data sets in BCI competition, confirm the useful behavior of the method for continuous EEG classification.

In this letter, we present a method of two-dimensional canonical correlation analysis (2D-CCA) where we extend the standard CCA in such a way that relations between two different sets of image data are directly sought without reshaping images into vectors. We stress that 2D-CCA dramatically reduces the computational complexity, compared to the standard CCA. We show the useful behavior of 2D-CCA through numerical examples of correspondence learning between face images in different poses and illumination conditions.

In this paper we introduce a new error measure, integrated reconstruction error (IRE), the minimization of which leads to principal eigenvectors (without rotational ambiguity) of the data covariance matrix. Then we present iterative algorithms for the IRE minimization, through the projection approximation. The proposed algorithm is referred to as COnstrained Projection Approximation (COPA) algorithm and its limiting case is called COPAL. We also discuss regularized algorithms, referred to as R-COPA and R-COPAL. Numerical experiments demonstrate that these algorithms successfully find exact principal eigenvectors of the data covariance matrix.

Independent subspace analysis (ISA) is a generalization of independent component analysis (ICA), where multidimensional ICA is incorporated with the idea of invariant feature subspaces, allowing components in the same subspace to be dependent, but requiring independence between feature subspaces. In this paper we present a relative gradient algorithm for ISA, derived in the framework of the relative optimization as well as in a direct manner. Empirical comparison with the gradient ISA algorithm, shows that the relative gradient ISA algorithm achieves faster convergence, compared to the conventional gradient algorithm.

In this paper we present a method of sequential speech enhancement, where we infer clean speech signal using a Rao-Blackwellized particle filter (RBPF), given a noise-contaminated observed signal. In contrast to Kalman filtering-based methods, we consider a non-Gaussian speech generative model that is based on the generalized auto-regressive (GAR) model. Model parameters are learned by sequential expectation maximization, incorporating the RBPF. Empirical comparison to Kalman filter, confirms the high performance of the proposed method.

In this paper, we introduce a new error measure, integrated reconstruction error (IRE) and show that the minimization of IRE leads to principal eigenvectors (without rotational ambiguity) of the data covariance matrix. Then, we present iterative algorithms for the IRE minimization, where we use the projection approximation. The proposed algorithm is referred to as COnstrained Projection Approximation (COPA) algorithm and its limiting case is called COPAL. Numerical experiments demonstrate that these algorithms successfully find exact principal eigenvectors of the data covariance matrix.

We present a new learning method, relative trust-region learning, where we incorporate the relative optimization technique (M. Zibulevsky, Proc. ICA, pp. 897-902, 2003) into the trust-region method. We apply this relative trust-region learning method to the problem of independent component analysis (ICA), which leads to the relative TR-ICA algorithm which turns out to be faster than Newton-type ICA algorithms as well as gradient-based ICA algorithms and to possess the equivariant property. Empirical comparisons with several existing ICA algorithms confirm the fast convergence of the relative TR-ICA algorithm.

Minimization of the reconstruction error (squared-error) leads to a principal subspace analysis (PSA) which estimates the scaled and rotated principal axes of a set of observed data. In this paper, we introduce a new alternative error, the so called integrated-squared-error, the minimization of which determines the exact principal axes (without rotational ambiguity) of a set of observed data. We consider the properties of the integrated-squared-error in the framework of a coupled generative model, giving efficient EM algorithms for integrated-squared-error minimization. We revisit the generalized Hebbian algorithm (GHA) and show that it emerges from the integrated-squared-error minimization in a single-layer linear feedforward neural network.

We present a generalization of the nonnegative matrix factorization (NMF), where a multilayer generative network with nonnegative weights is used to approximate the observed nonnegative data. The multilayer generative network with nonnegativity constraints, is learned by a multiplicative uppropagation algorithm, where the weights in each layer are updated in a multiplicative fashion while the mismatch ratio is propagated from the bottom to the top layer. The monotonic convergence of the multiplicative up-propagation algorithm is shown. In contrast to NMF, the multiplicative uppropagation is an algorithm that can learn hierarchical representations, where complex higher-level representations are defined in terms of less complex lower-level representations. The interesting behavior of our algorithm is demonstrated with face image data. 1.

A trust-region method is a quite attractive optimization technique, which finds a direction and a step size in an efficient and reliable manner with the help of a quadratic model of the objective function. It is, in general, faster than the steepest descent method and is free of a pre-selected constant learning rate. In addition to its convergence property (between linear and quadratic convergence), its stability is always guaranteed, in contrast to the Newton's method. We present an efficient implementation of the maximum likelihood independent component analysis (ICA) using the trust-region method, which leads to trust-region-based ICA (TR-ICA) algorithms. The useful behavior of our TR-ICA algorithms is confirmed through numerical experimental results.

This paper addresses an information-theoretic aspect of k-means and spectral clustering. First, we revisit the k-means clustering and show that its objective function is approximately derived from the minimum entropy principle when the Renyi's quadratic entropy is used. Then we present a maximum within-clustering association that is derived using a quadratic distance measure in the framework of minimum entropy principle, which is very similar to a class of spectral clustering algorithms that is based on the eigen-decomposition method.

Stochastic neighbor embedding (SNE) is a probabilistic method of embedding objects, described by high-dimensional vectors or by pair wise dissimilarities, into a lower dimensional space in a way that neighbor identities are preserved. Despite of the useful behavior of SNE, it suffers from its slow convergence due to a gradient-based implementation. In this paper we present a fast SNE algorithm which is approximately 4-6 times faster than the gradient-based SNE algorithm. Our fast SNE algorithm, named TR-SNE employs a trust-region (TR) method which finds a direction and a step size in an efficient and reliable manner with the help of a quadratic model of the objective function. We confirm the high performance and the fast convergence of our TR-SNR through numerical experiments.

In this paper we present a method of sound classification which exploits a parts-based representation of spectrotemporal sounds, employing the nonnegative matrix factorization (NMF) [1]. We illustrate a new way of learning nonnegative features using a variant of NMF and show its useful behavior in the task of general sound classification with comparison to independent component analysis (ICA) which produces holistic features.

This paper presents a learning algorithm for differential decorrelation, the goal of which is to find a linear transform that minimizes the concurrent change of associated output nodes. First the algorithm is derived from the minimization of the objective function which measures the differential correlation. Then we show that the differential decorrelation learning algorithm can also be derived in the framework of maximum likelihood estimation of a linear generative model with assuming a random walk model for latent variables. Algorithm derivation and local stability analysis are given with a simple numerical example.

Linear decomposition models such as principal component analysis (PCA) and independent component analysis (ICA) were shown to be useful in analyzing high dimensional DNA microarray data, compared to clustering methods. Assuming that gene expression is controlled by a linear combination of uncorrelated/independent latent variables, linear modes were shown to be related to some biological functions. However, grouping co-expressed genes using these methods is not quite successful since they take some biological dependence into account. In this paper, we employ the independent feature subspace analysis (IFSA) method which finds phase- and shift-invariant features. We propose a new membership scoring method based on invariant features from IFSA and show its usefulness in grouping functionally-related genes in the presence of time-shift and expression phase variance. This is confirmed through PathCalling.

This paper addresses local stability analysis for the flexible independent component analysis (ICA) algorithm where the generalized Gaussian density model was employed for blind separation of mixtures of sub- and super-Gaussian sources. In the flexible ICA algorithm, the shape of nonlinear function in the learning algorithm varies depending on the Gaussian exponent which is properly selected according to the kurtosis of estimated source. In the framework of the natural gradient in Stiefel manifold, the flexible ICA algorithm is revisited and some new results about its local stability analysis are presented.

Keywords: speech Reference EPFL-CONF-82643 Record created on 2006-03-10, modified on 2017-05-10

We present and compare two different spatio-temporal decorrelation learning algorithms for updating the weights of a linear feedforward network with FIR synapses (MIMO FIR filter). Both standard gradient and the natural gradient are employed to derive the spatio-temporal decorrelation algorithms. These two algorithms are applied to multichannel blind deconvolution task and their performance is compared. The rigorous derivation of algorithms and computer simulation results are presented.