An efficient parallel algorithm for computing determinant of non square matrices

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)).

An Empirical Bayesian Analysis of Simultaneous Changepoints in Multiple Data Sequences

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.

Bin Packing Problem: Two Approximation Algorithms

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.

Empirical Similarity for Absent Data Generation in Imbalanced Classification

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.

Listen, Attend and Spell

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%.

Privacy-Preserving Multi-Document Summarization

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.

Scalable Bayesian Kernel Models with Variable Selection

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.

Universal Approximation of Edge Density in Large Graphs

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.

A Hopf algebra of subword complexes

A method that reveals the multi-level ultrametric tree hidden in p-spin glass like systems

A Stopped Negative Binomial Distribution

Algebraic structures defined on $m$-Dyck paths

An O(1)-Approximation for Minimum Spanning Tree Interdiction

Anti-concentration of inhomogeneous random walks

Any Data, Any Time, Anywhere: Global Data Access for Science

Asymptotic Matrix Variate von-Mises Fisher and Bingham Distributions with Applications

Asymptotics of the truncated variation of model-free price paths and semimartingales with jumps

Calculating Greene’s function via root polytopes and subdivision algebras

Cartesian Product and Acyclic Edge Colouring

Degree-constrained Subgraph Reconfiguration is in P

Discrete Responses in Bivariate Generalized Additive Models

Enhanced Usability of Managing Workflows in an Industrial Data Gateway

Ergodic Theorems for Lower Probabilities

Even $(\bar{s}, \bar{t})$-core partitions and self-associate characters of $\tilde{S}_n$

Even-integer continued fractions and the Farey tree

Expander $\ell_0$-Decoding

Field theory of molecular cooperators

Fitting Laguerre tessellation approximations to tomographic image data

From infinite urn schemes to decompositions of self-similar Gaussian processes

Fuzzy Logic Based Direct Torque Control Of Induction Motor With Space Vector Modulation

Graph Homology and Stability of Coupled Oscillator Networks

Interval minors of complete multipartite graphs

Knowledge, Level of Symmetry, and Time of Leader Election

Kolmogorov’s axioms for probabilities with values in hyperbolic numbers

Measuring educational attainment as a continuous variable: a new database (1970-2010)

Mitosis algorithm for Grothendieck polynomials

Modified Knapp-Hartung random-effects meta-analysis recommended for applications in rare diseases

Non-isometric Curve to Surface Matching with Incomplete Data for Functional Calibration

On the entropy of a noisy function

Probabilistic temperature forecasting based on an ensemble AR modification

Replication and Generalization of PRECISE

Resource Oblivious Sorting on Multicores

Sparse Pseudo-input Local Kriging for Large Non-stationary Spatial Datasets with Exogenous Variables

Spatio-Temporal Change of Support with Application to American Community Survey Multi-Year Period Estimates

Stochastic Coalescence Multi-Fragmentation Processes

Teaching Statistics at Google Scale

The Influence Function of Semiparametric Estimators

The quenched critical point for self-avoiding walk on random conductors

The study of cuckoo optimization algorithm for production planning problem

Two Extensions of the Sury’s Identity

Unimodality for free Lévy processes

Unique colorability and clique minors

Using Linguistic Analysis to Translate Arabic Natural Language Queries to SPARQL