One of the most significant challenges in Computing Determinant of Rectangular Matrices is high time complexity of its algorithm. Among all definitions of determinant of rectangular matrices, used definition has special features which make it more notable. But in this definition, C(n m) sub matrices of the order m*m needed to be generated that put this problem in NP hard class. On the other hand, any row or column reduction operation may hardly lead to diminish the volume of calculation. Therefore, in this paper we try to present the parallel algorithm which can decrease the time complexity of computing the determinant of non-square matrices to O(pow(n,2)).
Motivated by applications in genomics, finance, and biomolecular simulation, we introduce a Bayesian framework for modeling changepoints that tend to co-occur across multiple related data sequences. We infer the locations and sequence memberships of changepoints in our hierarchical model by developing efficient Markov chain Monte Carlo sampling and posterior mode finding algorithms based on dynamic programming recursions. We further propose an empirical Bayesian Monte Carlo expectation-maximization procedure for estimating unknown prior parameters from data. The resulting framework accommodates a broad range of data and changepoint types, including real-valued sequences with changing mean or variance and sequences of counts or binary observations. We demonstrate on simulated data that our changepoint estimation accuracy is competitive with the best methods in the literature, and we apply our methodology to the discovery of DNA copy number variations in cancer cell lines and the analysis of historical price volatility in U.S. stocks.
The Bin Packing Problem is one of the most important optimization problems. In recent years, due to its NP-hard nature, several approximation algorithms have been presented. It is proved that the best algorithm for the Bin Packing Problem has the approximation ratio 3/2 and the time order O(n), unless P=NP. In this paper, first, a 3/2-approximation algorithm is presented, then a modification to FFD algorithm is proposed to decrease time order to linear. Finally, these suggested approximation algorithms are compared with some other approximation algorithms. The experimental results show the suggested algorithms perform efficiently. In summary, the main goal of the research is presenting methods which not only enjoy the best theoretical criteria, but also perform considerably efficient in practice.
When the training data in a two-class classification problem is overwhelmed by one class, most classification techniques fail to correctly identify the data points belonging to the underrepresented class. We propose Similarity-based Imbalanced Classification (SBIC) that learns patterns in the training data based on an empirical similarity function. To take the imbalanced structure of the training data into account, SBIC utilizes the concept of absent data, i.e. data from the minority class which can help better find the boundary between the two classes. SBIC simultaneously optimizes the weights of the empirical similarity function and finds the locations of absent data points. As such, SBIC uses an embedded mechanism for synthetic data generation which does not modify the training dataset, but alters the algorithm to suit imbalanced datasets. Therefore, SBIC uses the ideas of both major schools of thoughts in imbalanced classification: Like cost-sensitive approaches SBIC operates on an algorithm level to handle imbalanced structures; and similar to synthetic data generation approaches, it utilizes the properties of unobserved data points from the minority class. The application of SBIC to imbalanced datasets suggests it is comparable to, and in some cases outperforms, other commonly used classification techniques for imbalanced datasets.
We present Listen, Attend and Spell (LAS), a neural network that learns to transcribe speech utterances to characters. Unlike traditional DNN-HMM models, this model learns all the components of a speech recognizer jointly. Our system has two components: a listener and a speller. The listener is a pyramidal recurrent network encoder that accepts filter bank spectra as inputs. The speller is an attention-based recurrent network decoder that emits characters as outputs. The network produces character sequences without making any independence assumptions between the characters. This is the key improvement of LAS over previous end-to-end CTC models. On the Google Voice Search task, LAS achieves a word error rate (WER) of 14.2% without a dictionary or a language model, and 11.2% with language model rescoring over the top 32 beams. In comparison, the state-of-the-art CLDNN-HMM model achieves a WER of 10.9%.
State-of-the-art extractive multi-document summarization systems are usually designed without any concern about privacy issues, meaning that all documents are open to third parties. In this paper we propose a privacy-preserving approach to multi-document summarization. Our approach enables other parties to obtain summaries without learning anything else about the original documents’ content. We use a hashing scheme known as Secure Binary Embeddings to convert documents representation containing key phrases and bag-of-words into bit strings, allowing the computation of approximate distances, instead of exact ones. Our experiments indicate that our system yields similar results to its non-private counterpart on standard multi-document evaluation datasets.
Nonlinear kernels are used extensively in regression models in statistics and machine learning since they often improve predictive accuracy. Variable selection is a challenge in the context of kernel based regression models. In linear regression the concept of an effect size for the regression coefficients is very useful for variable selection. In this paper we provide an analog for the effect size of each explanatory variable for Bayesian kernel regression models when the kernel is shift-invariant—for example the Gaussian kernel. The key idea that allows for the extraction of effect sizes is a random Fourier expansion for shift-invariant kernel functions. These random Fourier bases serve as a linear vector space in which a linear model can be defined and regression coefficients in this vector space can be projected onto the original explanatory variables. This projection serves as the analog for effect sizes. We apply this idea to specify a class of scalable Bayesian kernel regression models (SBKMs) for both nonparametric regression and binary classification. We also demonstrate how this framework encompasses both fixed and mixed effects modeling characteristics. We illustrate the utility of our approach on simulated and real data.
In this paper, we present a novel way to summarize the structure of large graphs, based on non-parametric estimation of edge density in directed multigraphs. Following coclustering approach, we use a clustering of the vertices, with a piecewise constant estimation of the density of the edges across the clusters, and address the problem of automatically and reliably inferring the number of clusters, which is the granularity of the coclustering. We use a model selection technique with data-dependent prior and obtain an exact evaluation criterion for the posterior probability of edge density estimation models. We demonstrate, both theoretically and empirically, that our data-dependent modeling technique is consistent, resilient to noise, valid non asymptotically and asymptotically behaves as an universal approximator of the true edge density in directed multigraphs. We evaluate our method using artificial graphs and present its practical interest on real world graphs. The method is both robust and scalable. It is able to extract insightful patterns in the unsupervised learning setting and to provide state of the art accuracy when used as a preparation step for supervised learning.