OpenRaiser/Intern-Atlas huggingface dataset:
Cube vs. Cube Low Degree Test
Venue: arXiv cs.CC 2016
Year: 2016

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension $3$) that intersect on a point $x\in \mathbf{F}^m$, and checks that the assignments to the cubes agree with each other on the point $x$. Our main result is a new combinatorial proof for a low degree test that comes closer to the soundness limit, as it works for all $ε\ge poly(d)/{\mathbf{F}}^{1/2}$, where $d$ is the degree. This should be compared to the previously best soundness value of $ε\ge poly(m, d)/\mathbf{F}^{1/8}$. Our soundness limit improves upon the dependence on the field size and does not depend on the dimension of the ambient space. Our proof is combinatorial and direct: unlike the Raz-Safra proof, it proceeds in one shot and does not require induction on the dimension of the ambient space. The ideas in our proof come from works on direct product testing which are even simpler in the current setting thanks to the low degree. Along the way we also prove a somewhat surprising fact about connection between different agreement tests: it does not matter if the tester chooses the cubes to intersect on points or on lines: for every given table, its success probability in either test is nearly the same.
The SP Theory of Intelligence as a Foundation for the Development of a General, Human-Level Thinking Machine
Venue: arXiv cs.AI 2016
Year: 2016

This paper summarises how the "SP theory of intelligence" and its realisation in the "SP computer model" simplifies and integrates concepts across artificial intelligence and related areas, and thus provides a promising foundation for the development of a general, human-level thinking machine, in accordance with the main goal of research in artificial general intelligence. The key to this simplification and integration is the powerful concept of "multiple alignment", borrowed and adapted from bioinformatics. This concept has the potential to be the "double helix" of intelligence, with as much significance for human-level intelligence as has DNA for biological sciences. Strengths of the SP system include: versatility in the representation of diverse kinds of knowledge; versatility in aspects of intelligence (including: strengths in unsupervised learning; the processing of natural language; pattern recognition at multiple levels of abstraction that is robust in the face of errors in data; several kinds of reasoning (including: one-step `deductive' reasoning; chains of reasoning; abductive reasoning; reasoning with probabilistic networks and trees; reasoning with 'rules'; nonmonotonic reasoning and reasoning with default values; Bayesian reasoning with 'explaining away'; and more); planning; problem solving; and more); seamless integration of diverse kinds of knowledge and diverse aspects of intelligence in any combination; and potential for application in several areas (including: helping to solve nine problems with big data; helping to develop human-level intelligence in autonomous robots; serving as a database with intelligence and with versatility in the representation and integration of several forms of knowledge; serving as a vehicle for medical knowledge and as an aid to medical diagnosis; and several more).
DroidGen: Constraint-based and Data-Driven Policy Generation for Android
Venue: arXiv cs.CR 2016
Year: 2016

We present DroidGen a tool for automatic anti-malware policy inference. DroidGen employs a data-driven approach: it uses a training set of malware and benign applications and makes call to a constraint solver to generate a policy under which a maximum of malware is excluded and a maximum of benign applications is allowed. Preliminary results are encouraging. We are able to automatically generate a policy which filters out 91% of the tested Android malware. Moreover, compared to black-box machine learning classifiers, our method has the advantage of generating policies in a declarative readable format. We illustrate our approach, describe its implementation and report on the preliminary results.
Deep Learning and Its Applications to Machine Health Monitoring: A Survey
Venue: arXiv cs.LG 2016
Year: 2016

Since 2006, deep learning (DL) has become a rapidly growing research direction, redefining state-of-the-art performances in a wide range of areas such as object recognition, image segmentation, speech recognition and machine translation. In modern manufacturing systems, data-driven machine health monitoring is gaining in popularity due to the widespread deployment of low-cost sensors and their connection to the Internet. Meanwhile, deep learning provides useful tools for processing and analyzing these big machinery data. The main purpose of this paper is to review and summarize the emerging research work of deep learning on machine health monitoring. After the brief introduction of deep learning techniques, the applications of deep learning in machine health monitoring systems are reviewed mainly from the following aspects: Auto-encoder (AE) and its variants, Restricted Boltzmann Machines and its variants including Deep Belief Network (DBN) and Deep Boltzmann Machines (DBM), Convolutional Neural Networks (CNN) and Recurrent Neural Networks (RNN). Finally, some new trends of DL-based machine health monitoring methods are discussed.
Gated Recurrent Unit (GRU) for Emotion Classification from Noisy Speech
Venue: arXiv cs.HC 2016
Year: 2016

Despite the enormous interest in emotion classification from speech, the impact of noise on emotion classification is not well understood. This is important because, due to the tremendous advancement of the smartphone technology, it can be a powerful medium for speech emotion recognition in the outside laboratory natural environment, which is likely to incorporate background noise in the speech. We capitalize on the current breakthrough of Recurrent Neural Network (RNN) and seek to investigate its performance for emotion classification from noisy speech. We particularly focus on the recently proposed Gated Recurrent Unit (GRU), which is yet to be explored for emotion recognition from speech. Experiments conducted with speech compounded with eight different types of noises reveal that GRU incurs an 18.16% smaller run-time while performing quite comparably to the Long Short-Term Memory (LSTM), which is the most popular Recurrent Neural Network proposed to date. This result is promising for any embedded platform in general and will initiate further studies to utilize GRU to its full potential for emotion recognition on smartphones.
BSEPACK User's Guide
Venue: arXiv cs.MS 2016
Year: 2016

This is the user manual for the software package BSEPACK (Bethe--Salpeter Eigenvalue Solver Package).
Surveillance and Intervention of Infrastructure-Free Mobile Communications: A New Wireless Security Paradigm
Venue: arXiv cs.IT 2016
Year: 2016

Conventional wireless security assumes wireless communications are rightful and aims to protect them against malicious eavesdropping and jamming attacks. However, emerging infrastructure-free mobile communication networks are likely to be illegally used (e.g., by criminals or terrorists) but difficult to be monitored, thus imposing new challenges on the public security. To tackle this issue, this article presents a paradigm shift of wireless security to the surveillance and intervention of infrastructure-free suspicious and malicious wireless communications, by exploiting legitimate eavesdropping and jamming jointly. In particular, {\emph{proactive eavesdropping}} (via jamming) is proposed to intercept and decode information from suspicious communication links for the purpose of inferring their intentions and deciding further measures against them. {\emph{Cognitive jamming}} (via eavesdropping) is also proposed so as to disrupt, disable, and even spoof the targeted malicious wireless communications to achieve various intervention tasks.
Semi-coherent Detection and Performance Analysis for Ambient Backscatter System
Venue: arXiv cs.IT 2016
Year: 2016

We study a novel communication mechanism, ambient backscatter, that utilizes radio frequency (RF) signals transmitted from an ambient source as both energy supply and information carrier to enable communications between low-power devices. Different from existing non-coherent schemes, we here design the semi-coherent detection, where channel parameters can be obtained from unknown data symbols and a few pilot symbols. We first derive the optimal detector for the complex Gaussian ambient RF signal from likelihood ratio test and compute the corresponding closed-form bit error rate (BER). To release the requirement for prior knowledge of the ambient RF signal, we next design a suboptimal energy detector with ambient RF signals being either the complex Gaussian or the phase shift keying (PSK). The corresponding detection thresholds, the analytical BER, and the outage probability are also obtained in closed-form. Interestingly, the complex Gaussian source would cause an error floor while the PSK source does not, which brings nontrivial indication of constellation design as opposed to the popular Gaussian-embedded literatures. Simulations are provided to corroborate the theoretical studies.
A Base Camp for Scaling AI
Venue: arXiv cs.AI 2016
Year: 2016

Modern statistical machine learning (SML) methods share a major limitation with the early approaches to AI: there is no scalable way to adapt them to new domains. Human learning solves this in part by leveraging a rich, shared, updateable world model. Such scalability requires modularity: updating part of the world model should not impact unrelated parts. We have argued that such modularity will require both "correctability" (so that errors can be corrected without introducing new errors) and "interpretability" (so that we can understand what components need correcting). To achieve this, one could attempt to adapt state of the art SML systems to be interpretable and correctable; or one could see how far the simplest possible interpretable, correctable learning methods can take us, and try to control the limitations of SML methods by applying them only where needed. Here we focus on the latter approach and we investigate two main ideas: "Teacher Assisted Learning", which leverages crowd sourcing to learn language; and "Factored Dialog Learning", which factors the process of application development into roles where the language competencies needed are isolated, enabling non-experts to quickly create new applications. We test these ideas in an "Automated Personal Assistant" (APA) setting, with two scenarios: that of detecting user intent from a user-APA dialog; and that of creating a class of event reminder applications, where a non-expert "teacher" can then create specific apps. For the intent detection task, we use a dataset of a thousand labeled utterances from user dialogs with Cortana, and we show that our approach matches state of the art SML methods, but in addition provides full transparency: the whole (editable) model can be summarized on one human-readable page. For the reminder app task, we ran small user studies to verify the efficacy of the approach.
HADAS Green Assistant: designing energy-efficient applications
Venue: arXiv cs.SE 2016
Year: 2016

The number of works addressing the role of energy efficiency in the software development has been increasing recently. But, designers and programmers still complain about the lack of tools that help them to make energy-efficiency decisions. Some works show that energy-aware design decisions tend to have a larger impact in the power consumed by applications, than code optimizations. In this paper we present the HADAS green assistant, which helps developers to identify the energy-consuming concerns of their applications (i.e., points in the application that consume more energy, like storing or transferring data), and also to model, analyse and reason about different architectural solutions for each of these concerns. This tool models the variability of more or less green architectural practices and the dependencies between different energy-consuming concerns using variabilty models. Finally, this tool will automatically generate the architectural configuration derived from the selections made by the developer from an energy consumption point of view.
Perturbation Robust Stable Matching
Venue: arXiv cs.GT 2016
Year: 2016

A well known result states that stability criterion for matchings in two-sided markets doesn't ensure uniqueness. This opens the door for a moral question with regard to the optimal stable matching from a social point of view. Here, a new notion of social optimality is proposed. Its novelty is its ability to take into account the possibility of agents to leave the matching after it has already been established. To formalize this real-life scenario, this work includes a well-defined probability model and a social cost function that maintain the general guidelines of leaving-agents situations. Finally, efficient algorithms to optimize this function are developed either under stability constraint or without it.
Fundamental Rate Limits of Physical Layer Spoofing
Venue: arXiv cs.IT 2016
Year: 2016

This letter studies an emerging wireless communication intervention problem at the physical layer, where a legitimate spoofer aims to spoof a malicious link from Alice to Bob, by replacing Alice's transmitted source message with its target message at Bob side. From an information-theoretic perspective, we are interested in characterizing the maximum achievable spoofing rate of this new spoofing channel, which is equivalent to the maximum achievable rate of the target message at Bob, under the condition that Bob cannot decode the source message from Alice. We propose a novel combined spoofing approach, where the spoofer sends its own target message, combined with a processed version of the source message to cancel the source message at Bob. For both cases when Bob treats interference as noise (TIN) or applies successive interference cancelation (SIC), we obtain the maximum achievable spoofing rates by optimizing the power allocation between the target and source messages at the spoofer.
Fredkin and Toffoli gates implemented in Oregonator model of Belousov-Zhabotinsky medium
Venue: arXiv cs.ET 2016
Year: 2016

A thin-layer Belousov-Zhabotinsky (BZ) medium is a powerful computing device capable for implementing logical circuits, memory, image processors, robot controllers, and neuromorphic architectures. We design the reversible logical gates --- Fredkin gate and Toffoli gate --- in a BZ medium network of excitable channels with sub-excitable junctions. Local control of the BZ medium excitability is an important feature of the gates' design. A excitable thin-layer BZ medium responds to a localised perturbation with omnidirectional target or spiral excitation waves. A sub-excitable BZ medium responds to an asymmetric perturbation by producing travelling localised excitation wave-fragments similar to dissipative solitons. We employ interactions between excitation wave-fragments to perform computation. We interpret the wave-fragments as values of Boolean variables. A presence of a wave-fragment at a given site of a circuit represents logical truth, absence of the wave-fragment --- logical false. Fredkin gate consists of ten excitable channels intersecting at eleven junctions eight of which are sub-excitable. Toffoli gate consists of six excitable channels intersecting at six junctions four of which are sub-excitable. The designs of the gates are verified using numerical integration of two-variable Oregonator equations.
Streaming Virtual Reality Content
Venue: arXiv cs.MM 2016
Year: 2016

The recent rise of interest in Virtual Reality (VR) came with the availability of commodity commercial VR prod- ucts, such as the Head Mounted Displays (HMD) created by Oculus and other vendors. To accelerate the user adoption of VR headsets, content providers should focus on producing high quality immersive content for these devices. Similarly, multimedia streaming service providers should enable the means to stream 360 VR content on their platforms. In this study, we try to cover different aspects related to VR content representation, streaming, and quality assessment that will help establishing the basic knowledge of how to build a VR streaming system.
Bayesian Nonparametric Models for Synchronous Brain-Computer Interfaces
Venue: arXiv cs.CV 2016
Year: 2016

A brain-computer interface (BCI) is a system that aims for establishing a non-muscular communication path for subjects who had suffer from a neurodegenerative disease. Many BCI systems make use of the phenomena of event-related synchronization and de-synchronization of brain waves as a main feature for classification of different cognitive tasks. However, the temporal dynamics of the electroencephalographic (EEG) signals contain additional information that can be incorporated into the inference engine in order to improve the performance of the BCIs. This information about the dynamics of the signals have been exploited previously in BCIs by means of generative and discriminative methods. In particular, hidden Markov models (HMMs) have been used in previous works. These methods have the disadvantage that the model parameters such as the number of hidden states and the number of Gaussian mixtures need to be fix "a priori". In this work, we propose a Bayesian nonparametric model for brain signal classification that does not require "a priori" selection of the number of hidden states and the number of Gaussian mixtures of a HMM. The results show that the proposed model outperform other methods based on HMM as well as the winner algorithm of the BCI competition IV.
On the Multi-User, Multi-Cell Massive Spatial Modulation Uplink: How Many Antennas for Each User?
Venue: arXiv cs.IT 2016
Year: 2016

Massive spatial modulation aided multiple-input multiple-output (SM-MIMO) systems have recently been proposed as a novel combination of spatial modulation (SM) and of conventional massive MIMO, where the base station (BS) is equipped with a large number of antennas and simultaneously serves multiple user equipment (UE) that employ SM for their uplink transmission. Since the massive SM-MIMO concept combines the benefits of both the SM and massive MIMO techniques, it has recently attracted substantial research interest. In this paper, we study the achievable uplink spectral efficiency (SE) of a multi-cell massive SM-MIMO system, and derive closed-form expressions to asymptotically lower-bound the SE yielded by two linear BS combining schemes, including maximum ratio (MR) combining and zero forcing (ZF) combining, when a sufficiently large number of BS antennas are equipped. The derivation takes into account the impact of transmitter spatial correlations, of imperfect channel estimations, of user-specific power controls and of different pilot reuse factors. The proposed asymptotic bounds are shown to be tight, even when the scale of BS antennas is limited. The new SE results facilitate a system-level investigation of the optimal number of uplink transmit antennas (TAs) $N$ with respect to SE maximization. Explicitly, we provide theoretical insights on the SE of massive SM-MIMO systems. Furthermore, we demonstrate that massive SM-MIMO systems are capable of outperforming the SE of conventional massive MIMOs relying on single-TA UEs.
An FFT-based Synchronization Approach to Recognize Human Behaviors using STN-LFP Signal
Venue: arXiv cs.CV 2016
Year: 2016

Classification of human behavior is key to developing closed-loop Deep Brain Stimulation (DBS) systems, which may be able to decrease the power consumption and side effects of the existing systems. Recent studies have shown that the Local Field Potential (LFP) signals from both Subthalamic Nuclei (STN) of the brain can be used to recognize human behavior. Since the DBS leads implanted in each STN can collect three bipolar signals, the selection of a suitable pair of LFPs that achieves optimal recognition performance is still an open problem to address. Considering the presence of synchronized aggregate activity in the basal ganglia, this paper presents an FFT-based synchronization approach to automatically select a relevant pair of LFPs and use the pair together with an SVM-based MKL classifier for behavior recognition purposes. Our experiments on five subjects show the superiority of the proposed approach compared to other methods used for behavior classification.
The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders
Venue: arXiv cs.GT 2016
Year: 2016

A seminal result of Bulow and Klemperer [1989] demonstrates the power of competition for extracting revenue: when selling a single item to $n$ bidders whose values are drawn i.i.d. from a regular distribution, the simple welfare-maximizing VCG mechanism (in this case, a second price-auction) with one additional bidder extracts at least as much revenue in expectation as the optimal mechanism. The beauty of this theorem stems from the fact that VCG is a {\em prior-independent} mechanism, where the seller possesses no information about the distribution, and yet, by recruiting one additional bidder it performs better than any prior-dependent mechanism tailored exactly to the distribution at hand (without the additional bidder). In this work, we establish the first {\em full Bulow-Klemperer} results in {\em multi-dimensional} environments, proving that by recruiting additional bidders, the revenue of the VCG mechanism surpasses that of the optimal (possibly randomized, Bayesian incentive compatible) mechanism. For a given environment with i.i.d. bidders, we term the number of additional bidders needed to achieve this guarantee the environment's {\em competition complexity}. Using the recent duality-based framework of Cai et al. [2016] for reasoning about optimal revenue, we show that the competition complexity of $n$ bidders with additive valuations over $m$ independent, regular items is at most $n+2m-2$ and at least $\log(m)$. We extend our results to bidders with additive valuations subject to downward-closed constraints, showing that these significantly more general valuations increase the competition complexity by at most an additive $m-1$ factor. We further improve this bound for the special case of matroid constraints, and provide additional extensions as well.
Middlemen and Contestation in Directed Networks
Venue: arXiv cs.SI 2016
Year: 2016

This paper studies critical nodes or "middlemen" that intermediate flows in a directed network. The contestability of a node is introduced as a network topological concept of competitiveness meaning that an intermediary's role in the brokering of flows in the network can be substituted by a group of other nodes. We establish the equivalence of uncontested intermediaries and middlemen. The notion of node contestability gives rise to a measure that quantifies the control exercised by a middleman in a network. We present a comparison of this middleman centrality measures with relevant, established network centrality measures. Furthermore, we provide concepts and measures expressing the robustness of a middleman as the number of links or nodes that have to be added to or removed from the network to nullify the middleman's power. We use these concepts to identify and measure middleman power and robustness in two empirical networks: Krackhardt's advice network of managers in a medium sized corporation and the well-known Florentine marriage network as a proxy of power brokerage between houses in Renaissance Florence.