OpenRaiser/Intern-Atlas huggingface dataset:
Schema Independent Relational Learning
Venue: arXiv cs.DB 2017
Year: 2017

Learning novel concepts and relations from relational databases is an important problem with many applications in database systems and machine learning. Relational learning algorithms learn the definition of a new relation in terms of existing relations in the database. Nevertheless, the same data set may be represented under different schemas for various reasons, such as efficiency, data quality, and usability. Unfortunately, the output of current relational learning algorithms tends to vary quite substantially over the choice of schema, both in terms of learning accuracy and efficiency. This variation complicates their off-the-shelf application. In this paper, we introduce and formalize the property of schema independence of relational learning algorithms, and study both the theoretical and empirical dependence of existing algorithms on the common class of (de) composition schema transformations. We study both sample-based learning algorithms, which learn from sets of labeled examples, and query-based algorithms, which learn by asking queries to an oracle. We prove that current relational learning algorithms are generally not schema independent. For query-based learning algorithms we show that the (de) composition transformations influence their query complexity. We propose Castor, a sample-based relational learning algorithm that achieves schema independence by leveraging data dependencies. We support the theoretical results with an empirical study that demonstrates the schema dependence/independence of several algorithms on existing benchmark and real-world datasets under (de) compositions.
Rapid Exact Signal Scanning with Deep Convolutional Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

A rigorous formulation of the dynamics of a signal processing scheme aimed at dense signal scanning without any loss in accuracy is introduced and analyzed. Related methods proposed in the recent past lack a satisfactory analysis of whether they actually fulfill any exactness constraints. This is improved through an exact characterization of the requirements for a sound sliding window approach. The tools developed in this paper are especially beneficial if Convolutional Neural Networks are employed, but can also be used as a more general framework to validate related approaches to signal scanning. The proposed theory helps to eliminate redundant computations and renders special case treatment unnecessary, resulting in a dramatic boost in efficiency particularly on massively parallel processors. This is demonstrated both theoretically in a computational complexity analysis and empirically on modern parallel processors.
A Proof of the Strong Converse Theorem for Gaussian Broadcast Channels via the Gaussian Poincaré Inequality
Venue: arXiv cs.IT 2017
Year: 2017

We prove that the Gaussian broadcast channel with two destinations admits the strong converse property. This implies that for every sequence of block codes operated at a common rate pair with an asymptotic average error probability $<1$, the rate pair must lie within the capacity region derived by Cover and Bergmans. The main mathematical tool required for our analysis is a logarithmic Sobolev inequality known as the Gaussian Poincaré inequality.
Bandwidth Analysis of Multiport Radio-Frequency Systems
Venue: arXiv cs.IT 2017
Year: 2017

When multiple radio-frequency sources are connected to multiple loads through a passive multiport matching network, perfect power transfer to the loads across all frequencies is generally impossible. In this two-part paper, we provide analyses of bandwidth over which power transfer is possible. Our principal tools include broadband multiport matching upper bounds, presented herein, on the integral over all frequency of the logarithm of a suitably defined power loss ratio. In general, the larger the integral, the larger the bandwidth over which power transfer can be accomplished. We apply these bounds in several ways: We show how the number of sources and loads, and the coupling between loads, affect achievable bandwidth. We analyze the bandwidth of networks constrained to have certain architectures. We characterize systems whose bandwidths scale as the ratio between the numbers of loads and sources. The first part of the paper presents the bounds and uses them to analyze loads whose frequency responses can be represented by analytical circuit models. The second part analyzes the bandwidth of realistic loads whose frequency responses are available numerically. We provide applications to wireless transmitters where the loads are antennas being driven by amplifiers. The derivations of the bounds are also included.
An algorithm of frequency estimation for multi-channel coprime sampling
Venue: arXiv cs.IT 2017
Year: 2017

In some applications of frequency estimation, it is challenging to sample at as high as the Nyquist rate due to hardware limitations. An effective solution is to use multiple sub-Nyquist channels with coprime undersampling ratios to jointly sample. In this paper, an algorithm suitable for any number of channels is proposed, which is based on subspace techniques. Numerical simulations show that the proposed algorithm has high accuracy and good robustness.
Caratheodory's Theorem in Depth
Venue: arXiv cs.CG 2017
Year: 2017

Let $X$ be a finite set of points in $\mathbb{R}^d$. The Tukey depth of a point $q$ with respect to $X$ is the minimum number $τ_X(q)$ of points of $X$ in a halfspace containing $q$. In this paper we prove a depth version of Carathéodory's theorem. In particular, we prove that there exists a constant $c$ (that depends only on $d$ and $τ_X(q)$) and pairwise disjoint sets $X_1,\dots, X_{d+1} \subset X$ such that the following holds. Each $X_i$ has at least $c|X|$ points, and for every choice of points $x_i$ in $X_i$, $q$ is a convex combination of $x_1,\dots, x_{d+1}$. We also prove depth versions of Helly's and Kirchberger's theorems.
The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
Venue: arXiv cs.FL 2017
Year: 2017

For two given $ω$-terms $α$ and $β$, the word problem for $ω$-terms over a variety $\boldsymbol{\mathrm{V}}$ asks whether $α=β$ in all monoids in $\boldsymbol{\mathrm{V}}$. We show that the word problem for $ω$-terms over each level of the Trotter-Weil Hierarchy is decidable. More precisely, for every fixed variety in the Trotter-Weil Hierarchy, our approach yields an algorithm in nondeterministic logarithmic space (NL). In addition, we provide deterministic polynomial time algorithms which are more efficient than straightforward translations of the NL-algorithms. As an application of our results, we show that separability by the so-called corners of the Trotter-Weil Hierarchy is witnessed by $ω$-terms (this property is also known as $ω$-reducibility). In particular, the separation problem for the corners of the Trotter-Weil Hierarchy is decidable.
Magnetic Tunnel Junction Mimics Stochastic Cortical Spiking Neurons
Venue: arXiv cs.ET 2017
Year: 2017

Brain-inspired computing architectures attempt to mimic the computations performed in the neurons and the synapses in the human brain in order to achieve its efficiency in learning and cognitive tasks. In this work, we demonstrate the mapping of the probabilistic spiking nature of pyramidal neurons in the cortex to the stochastic switching behavior of a Magnetic Tunnel Junction in presence of thermal noise. We present results to illustrate the efficiency of neuromorphic systems based on such probabilistic neurons for pattern recognition tasks in presence of lateral inhibition and homeostasis. Such stochastic MTJ neurons can also potentially provide a direct mapping to the probabilistic computing elements in Belief Networks for performing regenerative tasks.
Population-Contrastive-Divergence: Does Consistency help with RBM training?
Venue: arXiv cs.LG 2017
Year: 2017

Estimating the log-likelihood gradient with respect to the parameters of a Restricted Boltzmann Machine (RBM) typically requires sampling using Markov Chain Monte Carlo (MCMC) techniques. To save computation time, the Markov chains are only run for a small number of steps, which leads to a biased estimate. This bias can cause RBM training algorithms such as Contrastive Divergence (CD) learning to deteriorate. We adopt the idea behind Population Monte Carlo (PMC) methods to devise a new RBM training algorithm termed Population-Contrastive-Divergence (pop-CD). Compared to CD, it leads to a consistent estimate and may have a significantly lower bias. Its computational overhead is negligible compared to CD. However, the variance of the gradient estimate increases. We experimentally show that pop-CD can significantly outperform CD. In many cases, we observed a smaller bias and achieved higher log-likelihood values. However, when the RBM distribution has many hidden neurons, the consistent estimate of pop-CD may still have a considerable bias and the variance of the gradient estimate requires a smaller learning rate. Thus, despite its superior theoretical properties, it is not advisable to use pop-CD in its current form on large problems.
A framework for the measurement and prediction of an individual scientist's performance
Venue: arXiv cs.DL 2017
Year: 2017

Quantitative bibliometric indicators are widely used to evaluate the performance of scientists. However, traditional indicators do not much rely on the analysis of the processes intended to measure and the practical goals of the measurement. In this study, I propose a simple framework to measure and predict an individual researcher's scientific performance that takes into account the main regularities of publication and citation processes and the requirements of practical tasks. Statistical properties of the new indicator - a scientist's personal impact rate - are illustrated by its application to a sample of Estonian researchers.
Sustainability-Aware Cloud Computing Using Virtual Carbon Tax
Venue: arXiv cs.DC 2017
Year: 2017

In this paper, a solution for sustainable cloud system is proposed and then implemented on a real testbed. The solution composes of optimization of a profit model and introduction of virtual carbon tax to limit environmental footprint of the cloud. The proposed multi-criteria optimizer of the cloud system suggests new optimum CPU frequencies for CPU-cores when the local grid energy mix or the cloud workload changes. The cloud system is implemented on a blade system, and proper middlewares are developed to interact with the blades. The experimental results show that it is possible to significantly decrease the targeted environmental footprint of the system and keep it profitable.
Learning multi-faceted representations of individuals from heterogeneous evidence using neural networks
Venue: arXiv cs.SI 2017
Year: 2017

Inferring latent attributes of people online is an important social computing task, but requires integrating the many heterogeneous sources of information available on the web. We propose learning individual representations of people using neural nets to integrate rich linguistic and network evidence gathered from social media. The algorithm is able to combine diverse cues, such as the text a person writes, their attributes (e.g. gender, employer, education, location) and social relations to other people. We show that by integrating both textual and network evidence, these representations offer improved performance at four important tasks in social media inference on Twitter: predicting (1) gender, (2) occupation, (3) location, and (4) friendships for users. Our approach scales to large datasets and the learned representations can be used as general features in and have the potential to benefit a large number of downstream tasks including link prediction, community detection, or probabilistic reasoning over social networks.
AdaCluster : Adaptive Clustering for Heterogeneous Data
Venue: arXiv cs.LG 2017
Year: 2017

Clustering algorithms start with a fixed divergence, which captures the possibly asymmetric distance between a sample and a centroid. In the mixture model setting, the sample distribution plays the same role. When all attributes have the same topology and dispersion, the data are said to be homogeneous. If the prior knowledge of the distribution is inaccurate or the set of plausible distributions is large, an adaptive approach is essential. The motivation is more compelling for heterogeneous data, where the dispersion or the topology differs among attributes. We propose an adaptive approach to clustering using classes of parametrized Bregman divergences. We first show that the density of a steep exponential dispersion model (EDM) can be represented with a Bregman divergence. We then propose AdaCluster, an expectation-maximization (EM) algorithm to cluster heterogeneous data using classes of steep EDMs. We compare AdaCluster with EM for a Gaussian mixture model on synthetic data and nine UCI data sets. We also propose an adaptive hard clustering algorithm based on Generalized Method of Moments. We compare the hard clustering algorithm with k-means on the UCI data sets. We empirically verified that adaptively learning the underlying topology yields better clustering of heterogeneous data.
Cache-Aided Interference Channels
Venue: arXiv cs.IT 2017
Year: 2017

Over the past decade, the bulk of wireless traffic has shifted from speech to content. This shift creates the opportunity to cache part of the content in memories closer to the end users, for example in base stations. Most of the prior literature focuses on the reduction of load in the backhaul and core networks due to caching, i.e., on the benefits caching offers for the wireline communication link between the origin server and the caches. In this paper, we are instead interested in the benefits caching can offer for the wireless communication link between the caches and the end users. To quantify the gains of caching for this wireless link, we consider an interference channel in which each transmitter is equipped with an isolated cache memory. Communication takes place in two phases, a content placement phase followed by a content delivery phase. The objective is to design both the placement and the delivery phases to maximize the rate in the delivery phase in response to any possible user demands. Focusing on the three-user case, we show that through careful joint design of these phases, we can reap three distinct benefits from caching: a load balancing gain, an interference cancellation gain, and an interference alignment gain. In our proposed scheme, load balancing is achieved through a specific file splitting and placement, producing a particular pattern of content overlap at the caches. This overlap allows to implement interference cancellation. Further, it allows us to create several virtual transmitters, each transmitting a part of the requested content, which increases interference-alignment possibilities.
Information-Theoretic Privacy for Smart Metering Systems with a Rechargeable Battery
Venue: arXiv cs.IT 2017
Year: 2017

Smart-metering systems report electricity usage of a user to the utility provider on almost real-time basis. This could leak private information about the user to the utility provider. In this work we investigate the use of a rechargeable battery in order to provide privacy to the user. We assume that the user load sequence is a first-order Markov process, the battery satisfies ideal charge conservation, and that privacy is measured using normalized mutual information (leakage rate) between the user load and the battery output. We consider battery charging policies in this setup that satisfy the feasibility constraints. We propose a series reductions on the original problem and ultimately recast it as a Markov Decision Process (MDP) that can be solved using a dynamic program. In the special case of i.i.d. demand, we explicitly characterize the optimal policy and show that the associated leakage rate can be expressed as a single-letter mutual information expression. In this case we show that the optimal charging policy admits an intuitive interpretation of preserving a certain invariance property of the state. Interestingly an alternative proof of optimality can be provided that does not rely on the MDP approach, but is based on purely information theoretic reductions.
Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
Venue: arXiv cs.CC 2017
Year: 2017

$δ$-hyperbolic graphs, originally conceived by Gromov in 1987, occur often in many network applications; for fixed $δ$, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of "non-expander" graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure $δ$ on expansion and cut-size bounds on graphs (here $δ$ need not be a constant), and the asymptotic ranges of $δ$ for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for $δ$-hyperbolic graphs as a function of $δ$, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s-t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for $δ$-hyperbolic graphs (where $δ$ is a function $f$ of the number of nodes, the exact nature of growth of $f$ being dependent on the particular problem considered).
Short-Term Plasticity and Long-Term Potentiation in Magnetic Tunnel Junctions: Towards Volatile Synapses
Venue: arXiv cs.ET 2017
Year: 2017

Synaptic memory is considered to be the main element responsible for learning and cognition in humans. Although traditionally non-volatile long-term plasticity changes have been implemented in nanoelectronic synapses for neuromorphic applications, recent studies in neuroscience have revealed that biological synapses undergo meta-stable volatile strengthening followed by a long-term strengthening provided that the frequency of the input stimulus is sufficiently high. Such "memory strengthening" and "memory decay" functionalities can potentially lead to adaptive neuromorphic architectures. In this paper, we demonstrate the close resemblance of the magnetization dynamics of a Magnetic Tunnel Junction (MTJ) to short-term plasticity and long-term potentiation observed in biological synapses. We illustrate that, in addition to the magnitude and duration of the input stimulus, frequency of the stimulus plays a critical role in determining long-term potentiation of the MTJ. Such MTJ synaptic memory arrays can be utilized to create compact, ultra-fast and low power intelligent neural systems.
Towards Reading Hidden Emotions: A comparative Study of Spontaneous Micro-expression Spotting and Recognition Methods
Venue: arXiv cs.CV 2017
Year: 2017

Micro-expressions (MEs) are rapid, involuntary facial expressions which reveal emotions that people do not intend to show. Studying MEs is valuable as recognizing them has many important applications, particularly in forensic science and psychotherapy. However, analyzing spontaneous MEs is very challenging due to their short duration and low intensity. Automatic ME analysis includes two tasks: ME spotting and ME recognition. For ME spotting, previous studies have focused on posed rather than spontaneous videos. For ME recognition, the performance of previous studies is low. To address these challenges, we make the following contributions: (i)We propose the first method for spotting spontaneous MEs in long videos (by exploiting feature difference contrast). This method is training free and works on arbitrary unseen videos. (ii)We present an advanced ME recognition framework, which outperforms previous work by a large margin on two challenging spontaneous ME databases (SMIC and CASMEII). (iii)We propose the first automatic ME analysis system (MESR), which can spot and recognize MEs from spontaneous video data. Finally, we show our method outperforms humans in the ME recognition task by a large margin, and achieves comparable performance to humans at the very challenging task of spotting and then recognizing spontaneous MEs.
A bi-criteria path planning algorithm for robotics applications
Venue: arXiv cs.RO 2017
Year: 2017

Realistic path planning applications often require optimizing with respect to several criteria simultaneously. Here we introduce an efficient algorithm for bi-criteria path planning on graphs. Our approach is based on augmenting the state space to keep track of the "budget" remaining to satisfy the constraints on secondary cost. The resulting augmented graph is acyclic and the primary cost can be then minimized by a simple upward sweep through budget levels. The efficiency and accuracy of our algorithm is tested on Probabilistic Roadmap graphs to minimize the distance of travel subject to a constraint on the overall threat exposure of the robot. We also present the results from field experiments illustrating the use of this approach on realistic robotic systems.
Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations
Venue: arXiv cs.CC 2017
Year: 2017

Low rank matrix approximation is an important tool in machine learning. Given a data matrix, low rank approximation helps to find factors, patterns and provides concise representations for the data. Research on low rank approximation usually focus on real matrices. However, in many applications data are binary (categorical) rather than continuous. This leads to the problem of low rank approximation of binary matrix. Here we are given a $d \times n$ binary matrix $A$ and a small integer $k$. The goal is to find two binary matrices $U$ and $V$ of sizes $d \times k$ and $k \times n$ respectively, so that the Frobenius norm of $A - U V$ is minimized. There are two models of this problem, depending on the definition of the dot product of binary vectors: The $\mathrm{GF}(2)$ model and the Boolean semiring model. Unlike low rank approximation of real matrix which can be efficiently solved by Singular Value Decomposition, approximation of binary matrix is $NP$-hard even for $k=1$. In this paper, we consider the problem of Column Subset Selection (CSS), in which one low rank matrix must be formed by $k$ columns of the data matrix. We characterize the approximation ratio of CSS for binary matrices. For $GF(2)$ model, we show the approximation ratio of CSS is bounded by $\frac{k}{2}+1+\frac{k}{2(2^k-1)}$ and this bound is asymptotically tight. For Boolean model, it turns out that CSS is no longer sufficient to obtain a bound. We then develop a Generalized CSS (GCSS) procedure in which the columns of one low rank matrix are generated from Boolean formulas operating bitwise on columns of the data matrix. We show the approximation ratio of GCSS is bounded by $2^{k-1}+1$, and the exponential dependency on $k$ is inherent.