OpenRaiser/Intern-Atlas huggingface dataset:
Hard-Clustering with Gaussian Mixture Models
Venue: arXiv cs.LG 2016
Year: 2016

Training the parameters of statistical models to describe a given data set is a central task in the field of data mining and machine learning. A very popular and powerful way of parameter estimation is the method of maximum likelihood estimation (MLE). Among the most widely used families of statistical models are mixture models, especially, mixtures of Gaussian distributions. A popular hard-clustering variant of the MLE problem is the so-called complete-data maximum likelihood estimation (CMLE) method. The standard approach to solve the CMLE problem is the Classification-Expectation-Maximization (CEM) algorithm. Unfortunately, it is only guaranteed that the algorithm converges to some (possibly arbitrarily poor) stationary point of the objective function. In this paper, we present two algorithms for a restricted version of the CMLE problem. That is, our algorithms approximate reasonable solutions to the CMLE problem which satisfy certain natural properties. Moreover, they compute solutions whose cost (i.e. complete-data log-likelihood values) are at most a factor $(1+ε)$ worse than the cost of the solutions that we search for. Note the CMLE problem in its most general, i.e. unrestricted, form is not well defined and allows for trivial optimal solutions that can be thought of as degenerated solutions.
A System for Probabilistic Linking of Thesauri and Classification Systems
Venue: arXiv cs.AI 2016
Year: 2016

This paper presents a system which creates and visualizes probabilistic semantic links between concepts in a thesaurus and classes in a classification system. For creating the links, we build on the Polylingual Labeled Topic Model (PLL-TM). PLL-TM identifies probable thesaurus descriptors for each class in the classification system by using information from the natural language text of documents, their assigned thesaurus descriptors and their designated classes. The links are then presented to users of the system in an interactive visualization, providing them with an automatically generated overview of the relations between the thesaurus and the classification system.
Static and Dynamic Feature Selection in Morphosyntactic Analyzers
Venue: arXiv cs.CL 2016
Year: 2016

We study the use of greedy feature selection methods for morphosyntactic tagging under a number of different conditions. We compare a static ordering of features to a dynamic ordering based on mutual information statistics, and we apply the techniques to standalone taggers as well as joint systems for tagging and parsing. Experiments on five languages show that feature selection can result in more compact models as well as higher accuracy under all conditions, but also that a dynamic ordering works better than a static ordering and that joint systems benefit more than standalone taggers. We also show that the same techniques can be used to select which morphosyntactic categories to predict in order to maximize syntactic accuracy in a joint system. Our final results represent a substantial improvement of the state of the art for several languages, while at the same time reducing both the number of features and the running time by up to 80% in some cases.
Action-Affect Classification and Morphing using Multi-Task Representation Learning
Venue: arXiv cs.CV 2016
Year: 2016

Most recent work focused on affect from facial expressions, and not as much on body. This work focuses on body affect analysis. Affect does not occur in isolation. Humans usually couple affect with an action in natural interactions; for example, a person could be talking and smiling. Recognizing body affect in sequences requires efficient algorithms to capture both the micro movements that differentiate between happy and sad and the macro variations between different actions. We depart from traditional approaches for time-series data analytics by proposing a multi-task learning model that learns a shared representation that is well-suited for action-affect classification as well as generation. For this paper we choose Conditional Restricted Boltzmann Machines to be our building block. We propose a new model that enhances the CRBM model with a factored multi-task component to become Multi-Task Conditional Restricted Boltzmann Machines (MTCRBMs). We evaluate our approach on two publicly available datasets, the Body Affect dataset and the Tower Game dataset, and show superior classification performance improvement over the state-of-the-art, as well as the generative abilities of our model.
Information Theoretic-Learning Auto-Encoder
Venue: arXiv cs.LG 2016
Year: 2016

We propose Information Theoretic-Learning (ITL) divergence measures for variational regularization of neural networks. We also explore ITL-regularized autoencoders as an alternative to variational autoencoding bayes, adversarial autoencoders and generative adversarial networks for randomly generating sample data without explicitly defining a partition function. This paper also formalizes, generative moment matching networks under the ITL framework.
Information Processing by Nonlinear Phase Dynamics in Locally Connected Arrays
Venue: arXiv cs.NE 2016
Year: 2016

Research toward powerful information processing systems that circumvent the interconnect bottleneck by exploiting the nonlinear evolution of multiple phase dynamics in locally connected arrays is discussed. We focus on a scheme in which logic states are defined by the electrical phase of a dynamic process and information processing is realized through interactions between the elements in the array. Simulation results are given for networks comprised of neuron-like integrate-and-fire elements, which could potentially be implemented by ultra-small tunnel junctions, molecules and other types of nanoscale elements. This approach could lead to powerful information processing systems due to massive parallelism in simple, highly scalable nano-architectures. The rational for this approach, its advantages, simulation results, critical issues, and future research directions are discussed.
Real-time Adaptive Prediction Method for Smooth Haptic Rendering
Venue: arXiv cs.HC 2016
Year: 2016

In this paper, we propose a real-time adaptive prediction method to calculate smooth and accurate haptic feedback in complex scenarios. Smooth haptic feedback is an important task for haptic rendering with complex virtual objects. However, commonly the update rate of the haptic rendering may drop down during multi-point contact in complex scenarios because high computational cost is required for collision detection and physically-based dynamic simulation. If the haptic rendering is done at a lower update rate, it may cause discontinuous or instable force/torque feedback. Therefore, to implement smooth and accurate haptic rendering, the update rate of force/torque calculation should be kept in a high and constant frequency. In the proposed method, the auto-regressive model with real-time coefficients update is proposed to predict interactive forces/torques during the physical simulation. In addition, we introduce a spline function to dynamically interpolate smooth forces/torques in haptic display according to the update rate of physical simulation. In the experiments, we show the feasibility of the proposed method and compare its performance with other methods and algorithms. The result shows that the proposed method can provide smooth and accurate haptic force feedback at a high update rate for complex scenarios.
Efficient Approximation of Well-Designed SPARQL Queries
Venue: arXiv cs.DB 2016
Year: 2016

Query response time often influences user experience in the real world. However, it possibly takes more time to answer a query with its all exact solutions, especially when it contains the OPT operations since the OPT operation is the least conventional operator in SPARQL. So it becomes essential to make a trade-off between the query response time and the accuracy of their solutions. In this paper, based on the depth of the OPT operation occurring in a query, we propose an approach to obtain its all approximate queries with less depth of the OPT operation. This paper mainly discusses those queries with well-designed patterns since the OPT operation in a well-designed pattern is really "optional". Firstly, we transform a well-designed pattern in OPT normal form into a well-designed tree, whose inner nodes are labeled by OPT operation and leaf nodes are labeled by patterns containing other operations such as the AND operation and the FILTER operation. Secondly, based on this well-designed tree, we remove "optional" well-designed subtrees with less depth of the OPT operation and then obtain approximate queries with different depths of the OPT operation. Finally, we evaluate the approximate query efficiency with the degree of approximation.
Multi-domain machine translation enhancements by parallel data extraction from comparable corpora
Venue: arXiv cs.CL 2016
Year: 2016

Parallel texts are a relatively rare language resource, however, they constitute a very useful research material with a wide range of applications. This study presents and analyses new methodologies we developed for obtaining such data from previously built comparable corpora. The methodologies are automatic and unsupervised which makes them good for large scale research. The task is highly practical as non-parallel multilingual data occur much more frequently than parallel corpora and accessing them is easy, although parallel sentences are a considerably more useful resource. In this study, we propose a method of automatic web crawling in order to build topic-aligned comparable corpora, e.g. based on the Wikipedia or Euronews.com. We also developed new methods of obtaining parallel sentences from comparable data and proposed methods of filtration of corpora capable of selecting inconsistent or only partially equivalent translations. Our methods are easily scalable to other languages. Evaluation of the quality of the created corpora was performed by analysing the impact of their use on statistical machine translation systems. Experiments were presented on the basis of the Polish-English language pair for texts from different domains, i.e. lectures, phrasebooks, film dialogues, European Parliament proceedings and texts contained medicines leaflets. We also tested a second method of creating parallel corpora based on data from comparable corpora which allows for automatically expanding the existing corpus of sentences about a given domain on the basis of analogies found between them. It does not require, therefore, having past parallel resources in order to train a classifier.
A Bandwidth-saving Optimization for MPI Broadcast Collective Operation
Venue: arXiv cs.DC 2016
Year: 2016

The efficiency and scalability of MPI collective operations, in particular the broadcast operation, plays an integral part in high performance computing applications. MPICH, as one of the contemporary widely-used MPI software stacks, implements the broadcast operation based on point-to-point operation. Depending on the parameters, such as message size and process count, the library chooses to use different algorithms, as for instance binomial dissemination, recursive-doubling exchange or ring all-to-all broadcast (allgather). However, the existing broadcast design in latest release of MPICH does not provide good performance for large messages (\textit{lmsg}) or medium messages with non-power-of-two process counts (\textit{mmsg-npof2}) due to the inner suboptimal ring allgather algorithm. In this paper, based on the native broadcast design in MPICH, we propose a tuned broadcast approach with bandwidth-saving in mind catering to the case of \textit{lmsg} and \textit{mmsg-npof2}. Several comparisons of the native and tuned broadcast designs are made for different data sizes and program sizes on Cray XC40 cluster. The results show that the performance of the tuned broadcast design can get improved by a range from 2\% to 54\% for \textit{lmsg} and \textit{mmsg-npof2} in terms of user-level testing.
Report on Dirty Paper Coding Estimation with multidimensional lattices
Venue: arXiv cs.IT 2016
Year: 2016

In this report we include some derivations on a channel estimation method based on the use of Dirty Paper Coding. Specifically, we analyze the proposed method, named Dirty Paper-based Channel Estimation (DPCE), when the considered codebooks are high-dimensional lattices.
Narrow-Sense BCH Codes over $\gf(q)$ with Length $n=\frac{q^m-1}{q-1}$
Venue: arXiv cs.IT 2016
Year: 2016

Cyclic codes over finite fields are widely employed in communication systems, storage devices and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over $\gf(q)$ with length $n=(q^m-1)/(q-1)$. Little is known about this class of BCH codes when $q>2$. The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length $n=(3^m-1)/2$ are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated.
Profiling vs. Time vs. Content: What does Matter for Top-k Publication Recommendation based on Twitter Profiles? - An Extended Technical Report
Venue: arXiv cs.DL 2016
Year: 2016

So far it is unclear how different factors of a scientific publication recommender system based on users' tweets have an influence on the recommendation performance. We examine three different factors, namely profiling method, temporal decay, and richness of content. Regarding profiling, we compare CF-IDF that replaces terms in TF-IDF by semantic concepts, HCF-IDF as novel hierarchical variant of CF-IDF, and topic modeling. As temporal decay functions, we apply sliding window and exponential decay. In terms of the richness of content, we compare recommendations using both full-texts and titles of publications and using only titles. Overall, the three factors make twelve recommendation strategies. We have conducted an online experiment with 123 participants and compared the strategies in a within-group design. The best recommendations are achieved by the strategy combining CF-IDF, sliding window, and with full-texts. However, the strategies using the novel HCF-IDF profiling method achieve similar results with just using the titles of the publications. Therefore, HCF-IDF can make recommendations when only short and sparse data is available.
Descriptive complexity of graph spectra
Venue: arXiv cs.LO 2016
Year: 2016

Two graphs are co-spectral if their respective adjacency matrices have the same multi-set of eigenvalues. A graph is said to be determined by its spectrum if all graphs that are co-spectral with it are isomorphic to it. We consider these properties in relation to logical definability. We show that any pair of graphs that are elementarily equivalent with respect to the three-variable counting first-order logic $C^3$ are co-spectral, and this is not the case with $C^2$, nor with any number of variables if we exclude counting quantifiers. We also show that the class of graphs that are determined by their spectra is definable in partial fixed-point logic with counting. We relate these properties to other algebraic and combinatorial problems.
Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain
Venue: arXiv cs.CC 2016
Year: 2016

We prove a complexity classification theorem that classifies all counting constraint satisfaction problems ($\#$CSP) over Boolean variables into exactly three categories: (1) Polynomial-time tractable; (2) $\#$P-hard for general instances, but solvable in polynomial-time over planar graphs; and (3) $\#$P-hard over planar graphs. The classification applies to all sets of local, not necessarily symmetric, constraint functions on Boolean variables that take complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in category (2).
LLR-based Successive-Cancellation List Decoder for Polar Codes with Multi-bit Decision
Venue: arXiv cs.IT 2016
Year: 2016

Due to their capacity-achieving property, polar codes have become one of the most attractive channel codes. To date, the successive cancellation list (SCL) decoding algorithm is the primary approach that can guarantee outstanding error-correcting performance of polar codes. However, the hardware designs of the original SCL decoder have large silicon area and long decoding latency. Although some recent efforts can reduce either the area or latency of SCL decoders, these two metrics still cannot be optimized at the same time. This paper, for the first time, proposes a general log-likelihood-ratio (LLR)-based SCL decoding algorithm with multi-bit decision. This new algorithm, referred as LLR-2Kb-SCL, can determine 2K bits simultaneously for arbitrary K with the use of LLR messages. In addition, a reduced-data-width scheme is presented to reduce the critical path of the sorting block. Then, based on the proposed algorithm, a VLSI architecture of the new SCL decoder is developed. Synthesis results show that for an example (1024, 512) polar code with list size 4, the proposed LLR-2Kb-SCL decoders achieve significant reduction in both area and latency as compared to prior works. As a result, the hardware efficiency of the proposed designs with K=2 and 3 are 2.33 times and 3.32 times of that of the state-of-the-art works, respectively.
Enabling Cognitive Intelligence Queries in Relational Databases using Low-dimensional Word Embeddings
Venue: arXiv cs.CL 2016
Year: 2016

We apply distributed language embedding methods from Natural Language Processing to assign a vector to each database entity associated token (for example, a token may be a word occurring in a table row, or the name of a column). These vectors, of typical dimension 200, capture the meaning of tokens based on the contexts in which the tokens appear together. To form vectors, we apply a learning method to a token sequence derived from the database. We describe various techniques for extracting token sequences from a database. The techniques differ in complexity, in the token sequences they output and in the database information used (e.g., foreign keys). The vectors can be used to algebraically quantify semantic relationships between the tokens such as similarities and analogies. Vectors enable a dual view of the data: relational and (meaningful rather than purely syntactical) text. We introduce and explore a new class of queries called cognitive intelligence (CI) queries that extract information from the database based, in part, on the relationships encoded by vectors. We have implemented a prototype system on top of Spark to exhibit the power of CI queries. Here, CI queries are realized via SQL UDFs. This power goes far beyond text extensions to relational systems due to the information encoded in vectors. We also consider various extensions to the basic scheme, including using a collection of views derived from the database to focus on a domain of interest, utilizing vectors and/or text from external sources, maintaining vectors as the database evolves and exploring a database without utilizing its schema. For the latter, we consider minimal extensions to SQL to vastly improve query expressiveness.
Lightweight Unsupervised Domain Adaptation by Convolutional Filter Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

End-to-end learning methods have achieved impressive results in many areas of computer vision. At the same time, these methods still suffer from a degradation in performance when testing on new datasets that stem from a different distribution. This is known as the domain shift effect. Recently proposed adaptation methods focus on retraining the network parameters. However, this requires access to all (labeled) source data, a large amount of (unlabeled) target data, and plenty of computational resources. In this work, we propose a lightweight alternative, that allows adapting to the target domain based on a limited number of target samples in a matter of minutes rather than hours, days or even weeks. To this end, we first analyze the output of each convolutional layer from a domain adaptation perspective. Surprisingly, we find that already at the very first layer, domain shift effects pop up. We then propose a new domain adaptation method, where first layer convolutional filters that are badly affected by the domain shift are reconstructed based on less affected ones. This improves the performance of the deep network on various benchmark datasets.
A Tutorial on Deep Neural Networks for Intelligent Systems
Venue: arXiv cs.NE 2016
Year: 2016

Developing Intelligent Systems involves artificial intelligence approaches including artificial neural networks. Here, we present a tutorial of Deep Neural Networks (DNNs), and some insights about the origin of the term "deep"; references to deep learning are also given. Restricted Boltzmann Machines, which are the core of DNNs, are discussed in detail. An example of a simple two-layer network, performing unsupervised learning for unlabeled data, is shown. Deep Belief Networks (DBNs), which are used to build networks with more than two layers, are also described. Moreover, examples for supervised learning with DNNs performing simple prediction and classification tasks, are presented and explained. This tutorial includes two intelligent pattern recognition applications: hand- written digits (benchmark known as MNIST) and speech recognition.
On the characterization of models of H*: The semantical aspect
Venue: arXiv cs.LO 2016
Year: 2016

We give a characterization, with respect to a large class of models of untyped lambda-calculus, of those models that are fully abstract for head-normalization, i.e., whose equational theory is H* (observations for head normalization). An extensional K-model $D$ is fully abstract if and only if it is hyperimmune, {\em i.e.}, not well founded chains of elements of D cannot be captured by any recursive function. This article, together with its companion paper, form the long version of [Bre14]. It is a standalone paper that presents a purely semantical proof of the result as opposed to its companion paper that presents an independent and purely syntactical proof of the same result.
Applications of incidence bounds in point covering problems
Venue: arXiv cs.CG 2016
Year: 2016

In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalization of Line Cover, the task is to cover the points using curves with d degrees of freedom. Another generalization is the Hyperplane Cover problem where points in d-dimensional space are to be covered by hyperplanes. All these problems have kernels of polynomial size, where the parameter is the minimum number of lines, curves, or hyperplanes needed. First we give a non-parameterized algorithm for both problems in O*(2^n) (where the O*(.) notation hides polynomial factors of n) time and polynomial space, beating a previous exponential-space result. Combining this with incidence bounds similar to the famous Szemeredi-Trotter bound, we present a Curve Cover algorithm with running time O*((Ck/log k)^((d-1)k)), where C is some constant. Our result improves the previous best times O*((k/1.35)^k) for Line Cover (where d=2), O*(k^(dk)) for general Curve Cover, as well as a few other bounds for covering points by parabolas or conics. We also present an algorithm for Hyperplane Cover in R^3 with running time O*((Ck^2/log^(1/5) k)^k), improving on the previous time of O*((k^2/1.3)^k).