OpenRaiser/Intern-Atlas huggingface dataset:
A Low-complexity Channel Shortening Receiver with Diversity Support for Evolved 2G Device
Venue: arXiv cs.IT 2015
Year: 2015

The second generation (2G) cellular networks are the current workhorse for machine-to-machine (M2M) communications. Diversity in 2G devices can be present both in form of multiple receive branches and blind repetitions. In presence of diversity, intersymbol interference (ISI) equalization and co-channel interference (CCI) suppression are usually very complex. In this paper, we consider the improvements for 2G devices with receive diversity. We derive a low-complexity receiver based on a channel shortening filter, which allows to sum up all diversity branches to a single stream after filtering while keeping the full diversity gain. The summed up stream is subsequently processed by a single stream Max-log-MAP (MLM) equalizer. The channel shortening filter is designed to maximize the mutual information lower bound (MILB) with the Ungerboeck detection model. Its filter coefficients can be obtained mainly by means of discrete-Fourier transforms (DFTs). Compared with the state-of-art homomorphic (HOM) filtering based channel shortener which cooperates with a delayed-decision feedback MLM (DDF-MLM) equalizer, the proposed MILB channel shortener has superior performance. Moreover, the equalization complexity, in terms of real-valued multiplications, is decreased by a factor that equals the number of diversity branches.
Searching for Objects using Structure in Indoor Scenes
Venue: arXiv cs.CV 2015
Year: 2015

To identify the location of objects of a particular class, a passive computer vision system generally processes all the regions in an image to finally output few regions. However, we can use structure in the scene to search for objects without processing the entire image. We propose a search technique that sequentially processes image regions such that the regions that are more likely to correspond to the query class object are explored earlier. We frame the problem as a Markov decision process and use an imitation learning algorithm to learn a search strategy. Since structure in the scene is essential for search, we work with indoor scene images as they contain both unary scene context information and object-object context in the scene. We perform experiments on the NYU-depth v2 dataset and show that the unary scene context features alone can achieve a significantly high average precision while processing only 20-25\% of the regions for classes like bed and sofa. By considering object-object context along with the scene context features, the performance is further improved for classes like counter, lamp, pillow and sofa.
DiffSharp: Automatic Differentiation Library
Venue: arXiv cs.MS 2015
Year: 2015

In this paper we introduce DiffSharp, an automatic differentiation (AD) library designed with machine learning in mind. AD is a family of techniques that evaluate derivatives at machine precision with only a small constant factor of overhead, by systematically applying the chain rule of calculus at the elementary operator level. DiffSharp aims to make an extensive array of AD techniques available, in convenient form, to the machine learning community. These including arbitrary nesting of forward/reverse AD operations, AD with linear algebra primitives, and a functional API that emphasizes the use of higher-order functions and composition. The library exposes this functionality through an API that provides gradients, Hessians, Jacobians, directional derivatives, and matrix-free Hessian- and Jacobian-vector products. Bearing the performance requirements of the latest machine learning techniques in mind, the underlying computations are run through a high-performance BLAS/LAPACK backend, using OpenBLAS by default. GPU support is currently being implemented.
The Shortest Connection Game
Venue: arXiv cs.GT 2015
Year: 2015

We introduce Shortest Connection Game, a two-player game played on a directed graph with edge costs. Given two designated vertices in which they start, the players take turns in choosing edges emanating from the vertex they are currently located at. In this way, each of the players forms a path that origins from its respective starting vertex. The game ends as soon as the two paths meet, i.e., a connection between the players is established. Each player has to carry the cost of its chosen edges and thus aims at minimizing its own total cost. In this work we analyze the computational complexity of Shortest Connection Game. On the negative side, the game turns out to be computationally hard even on restricted graph classes such as bipartite, acyclic and cactus graphs. On the positive side, we can give a polynomial time algorithm for cactus graphs when the game is restricted to simple paths.
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Venue: arXiv cs.CC 2015
Year: 2015

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. $\bullet$ We prove that for all $ε\gg \sqrt{\log(n)/n}$, the linear-time computable Andreev's function cannot be computed on a $(1/2+ε)$-fraction of $n$-bit inputs by depth-two linear threshold circuits of $o(ε^3 n^{3/2}/\log^3 n)$ gates, nor can it be computed with $o(ε^{3} n^{5/2}/\log^{7/2} n)$ wires. This establishes an average-case ``size hierarchy'' for threshold circuits, as Andreev's function is computable by uniform depth-two circuits of $o(n^3)$ linear threshold gates, and by uniform depth-three circuits of $O(n)$ majority gates. $\bullet$ We present a new function in $P$ based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two linear threshold circuits with $o(n^{3/2}/\log^3 n)$ gates, nor with $o(n^{5/2}/\log^{7/2}n)$ wires. $\bullet$ We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits. The key is a new random restriction lemma for linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.
Competitive Charging Station Pricing for Plug-in Electric Vehicles
Venue: arXiv cs.GT 2015
Year: 2015

This paper considers the problem of charging station pricing and plug-in electric vehicles (PEVs) station selection. When a PEV needs to be charged, it selects a charging station by considering the charging prices, waiting times, and travel distances. Each charging station optimizes its charging price based on the prediction of the PEVs' charging station selection decisions and the other station's pricing decision, in order to maximize its profit. To obtain insights of such a highly coupled system, we consider a one-dimensional system with two competing charging stations and Poisson arriving PEVs. We propose a multi-leader-multi-follower Stackelberg game model, in which the charging stations (leaders) announce their charging prices in Stage I, and the PEVs (followers) make their charging station selections in Stage II. We show that there always exists a unique charging station selection equilibrium in Stage II, and such equilibrium depends on the charging stations' service capacities and the price difference between them. We then characterize the sufficient conditions for the existence and uniqueness of the pricing equilibrium in Stage I. We also develop a low complexity algorithm that efficiently computes the pricing equilibrium and the subgame perfect equilibrium of the two-stage Stackelberg game.
Natural Language Understanding with Distributed Representation
Venue: arXiv cs.CL 2015
Year: 2015

This is a lecture note for the course DS-GA 3001 <Natural Language Understanding with Distributed Representation> at the Center for Data Science , New York University in Fall, 2015. As the name of the course suggests, this lecture note introduces readers to a neural network based approach to natural language understanding/processing. In order to make it as self-contained as possible, I spend much time on describing basics of machine learning and neural networks, only after which how they are used for natural languages is introduced. On the language front, I almost solely focus on language modelling and machine translation, two of which I personally find most fascinating and most fundamental to natural language understanding.
Learning Halfspaces and Neural Networks with Random Initialization
Venue: arXiv cs.LG 2015
Year: 2015

We study non-convex empirical risk minimization for learning halfspaces and neural networks. For loss functions that are $L$-Lipschitz continuous, we present algorithms to learn halfspaces and multi-layer neural networks that achieve arbitrarily small excess risk $ε>0$. The time complexity is polynomial in the input dimension $d$ and the sample size $n$, but exponential in the quantity $(L/ε^2)\log(L/ε)$. These algorithms run multiple rounds of random initialization followed by arbitrary optimization steps. We further show that if the data is separable by some neural network with constant margin $γ>0$, then there is a polynomial-time algorithm for learning a neural network that separates the training data with margin $Ω(γ)$. As a consequence, the algorithm achieves arbitrary generalization error $ε>0$ with ${\rm poly}(d,1/ε)$ sample and time complexity. We establish the same learnability result when the labels are randomly flipped with probability $η<1/2$.
MOOCs Meet Measurement Theory: A Topic-Modelling Approach
Venue: arXiv cs.LG 2015
Year: 2015

This paper adapts topic models to the psychometric testing of MOOC students based on their online forum postings. Measurement theory from education and psychology provides statistical models for quantifying a person's attainment of intangible attributes such as attitudes, abilities or intelligence. Such models infer latent skill levels by relating them to individuals' observed responses on a series of items such as quiz questions. The set of items can be used to measure a latent skill if individuals' responses on them conform to a Guttman scale. Such well-scaled items differentiate between individuals and inferred levels span the entire range from most basic to the advanced. In practice, education researchers manually devise items (quiz questions) while optimising well-scaled conformance. Due to the costly nature and expert requirements of this process, psychometric testing has found limited use in everyday teaching. We aim to develop usable measurement models for highly-instrumented MOOC delivery platforms, by using participation in automatically-extracted online forum topics as items. The challenge is to formalise the Guttman scale educational constraint and incorporate it into topic models. To favour topics that automatically conform to a Guttman scale, we introduce a novel regularisation into non-negative matrix factorisation-based topic modelling. We demonstrate the suitability of our approach with both quantitative experiments on three Coursera MOOCs, and with a qualitative survey of topic interpretability on two MOOCs by domain expert interviews.
Toward interoperability for the Internet of Things with meta-hubs
Venue: arXiv cs.SE 2015
Year: 2015

The Internet of Things (IoT) envisions that objects may be connected to the Internet, producing and consuming data in real-time. Today, numerous middleware platforms are available to facilitate the communication with these objects. Unfortunately, the interoperability of these platforms is very limited because it requires to "manually" connect the services proposed by each platform. One key design goal for our contribution is not to build yet another middleware, but rather to augment the functionalities of existing systems via an extension to support their integration into a network of heterogeneous IoT hubs. The extension includes a RESTful API to manipulate the basic component of our extension, the IoT feeds. The IoT feeds allow the platform's owner to dynamically marshal the IoT features connected to the platform, as well as the data that they produce. Furthermore, the feeds enable the owner to manage and control the data flows before connecting them to his applications. Subsequently, these feeds may also be published to meta-hubs in order to expose them to third parties. We evaluated an implementation our extension for Android systems to show the feasibility of managing the data flows using the RESTful API on this platform.
Group Centric Networking: A New Approach for Wireless Multi-Hop Networking to Enable the Internet of Things
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we introduce a new networking architecture called Group Centric Networking (GCN), which is designed to support the large number of devices expected with the emergence of the Internet of Things. GCN is designed to enable these devices to operate collaboratively in a highly efficient and resilient fashion, while not sacrificing their ability to communicate with one another. We do a full protocol implementation of GCN in NS3, and demonstrate that GCN utilizes up to an order of magnitude fewer network resources than traditional wireless networking schemes, while providing high connectivity and reliability.
Deseeding Energy Consumption of Network Stacks
Venue: arXiv cs.NI 2015
Year: 2015

Regular works on energy efficiency strategies for wireless communications are based on classical energy models that account for the wireless card only. Nevertheless, there is a non-negligible energy toll called "cross-factor" that encompasses the energy drained while a frame crosses the network stack of an OS. This paper addresses the challenge of deepen into the roots of the cross-factor, deseed its components and analyse its causes. Energy issues are critical for IoT devices. Thus, this paper conceives and validates a new comprehensive framework that enables us to measure a wide range of wireless devices, as well as multiple devices synchronously. We also present a rigorous methodology to perform whole-device energy measurements in laptops, a more generic and suitable device to perform energy debugging. Finally, and using this framework, we provide a collection of measurements and insights that deepens our understanding of the cross-factor.
Beyond One Third Byzantine Failures
Venue: arXiv cs.DC 2015
Year: 2015

The Byzantine agreement problem requires a set of $n$ processes to agree on a value sent by a transmitter, despite a subset of $b$ processes behaving in an arbitrary, i.e. Byzantine, manner and sending corrupted messages to all processes in the system. It is well known that the problem has a solution in a (an eventually) synchronous message passing distributed system iff the number of processes in the Byzantine subset is less than one third of the total number of processes, i.e. iff $n > 3b+1$. The rest of the processes are expected to be correct: they should never deviate from the algorithm assigned to them and send corrupted messages. But what if they still do? We show in this paper that it is possible to solve Byzantine agreement even if, beyond the $ b$ ($< n/3 $) Byzantine processes, some of the other processes also send corrupted messages, as long as they do not send them to all. More specifically, we generalize the classical Byzantine model and consider that Byzantine failures might be partial. In each communication step, some of the processes might send corrupted messages to a subset of the processes. This subset of processes - to which corrupted messages might be sent - could change over time. We compute the exact number of processes that can commit such faults, besides those that commit classical Byzantine failures, while still solving Byzantine agreement. We present a corresponding Byzantine agreement algorithm and prove its optimality by giving resilience and complexity bounds.
An Approach to Complex Bayesian-optimal Approximate Message Passing
Venue: arXiv cs.IT 2015
Year: 2015

In this work we aim to solve the compressed sensing problem for the case of a complex unknown vector by utilizing the Bayesian-optimal structured signal approximate message passing (BOSSAMP) algorithm on the jointly sparse real and imaginary parts of the unknown. By introducing a latent activity variable, BOSSAMP separates the tasks of activity detection and value estimation to overcome the problem of detecting different supports in the real and imaginary parts. We complement the recovery algorithm by two novel support detection schemes that utilize the updated auxiliary variables of BOSSAMP. Simulations show the superiority of our proposed method against approximate message passing (AMP) and its Bayesian-optimal sibling (BAMP), both in mean squared error and support detection performance.
Hierarchical classification of e-commerce related social media
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we attempt to classify tweets into root categories of the Amazon browse node hierarchy using a set of tweets with browse node ID labels, a much larger set of tweets without labels, and a set of Amazon reviews. Examining twitter data presents unique challenges in that the samples are short (under 140 characters) and often contain misspellings or abbreviations that are trivial for a human to decipher but difficult for a computer to parse. A variety of query and document expansion techniques are implemented in an effort to improve information retrieval to modest success.
Code-Based Cryptosystems Using Generalized Concatenated Codes
Venue: arXiv cs.IT 2015
Year: 2015

The security of public-key cryptosystems is mostly based on number theoretic problems like factorization and the discrete logarithm. There exists an algorithm which solves these problems in polynomial time using a quantum computer. Hence, these cryptosystems will be broken as soon as quantum computers emerge. Code-based cryptography is an alternative which resists quantum computers since its security is based on an NP-complete problem, namely decoding of random linear codes. The McEliece cryptosystem is the most prominent scheme to realize code-based cryptography. Many codeclasses were proposed for the McEliece cryptosystem, but most of them are broken by now. Sendrier suggested to use ordinary concatenated codes, however, he also presented an attack on such codes. This work investigates generalized concatenated codes to be used in the McEliece cryptosystem. We examine the application of Sendrier's attack on generalized concatenated codes and present alternative methods for both partly finding the code structure and recovering the plaintext from a cryptogram. Further, we discuss modifications of the cryptosystem making it resistant against these attacks.
Towards Automatic Image Editing: Learning to See another You
Venue: arXiv cs.CV 2015
Year: 2015

Learning the distribution of images in order to generate new samples is a challenging task due to the high dimensionality of the data and the highly non-linear relations that are involved. Nevertheless, some promising results have been reported in the literature recently,building on deep network architectures. In this work, we zoom in on a specific type of image generation: given an image and knowing the category of objects it belongs to (e.g. faces), our goal is to generate a similar and plausible image, but with some altered attributes. This is particularly challenging, as the model needs to learn to disentangle the effect of each attribute and to apply a desired attribute change to a given input image, while keeping the other attributes and overall object appearance intact. To this end, we learn a convolutional network, where the desired attribute information is encoded then merged with the encoded image at feature map level. We show promising results, both qualitatively as well as quantitatively, in the context of a retrieval experiment, on two face datasets (MultiPie and CAS-PEAL-R1).
Decidability and Complexity for Quiescent Consistency and its Variations
Venue: arXiv cs.LO 2015
Year: 2015

Quiescent consistency is a notion of correctness for a concurrent object that gives meaning to the object's behaviours in quiescent states, i.e., states in which none of the object's operations are being executed. Correctness of an implementation object is defined in terms of a corresponding abstract specification. This gives rise to two important verification questions: membership (checking whether a behaviour of the implementation is allowed by the specification) and correctness (checking whether all behaviours of the implementation are allowed by the specification). In this paper, we show that the membership problem for quiescent consistency is NP-complete and that the correctness problem is decidable, but coNP-hard and in EXPSPACE. For both problems, we consider restricted versions of quiescent consistency by assuming an upper limit on the number of events between two quiescent points. Here, we show that the membership problem is in PTIME, whereas correctness is in PSPACE. Quiescent consistency does not guarantee sequential consistency, i.e., it allows operation calls by the same process to be reordered when mapping to an abstract specification. Therefore, we also consider quiescent sequential consistency, which strengthens quiescent consistency with an additional sequential consistency condition. We show that the unrestricted versions of membership and correctness are NP-complete and undecidable, respectively. When by placing a limit on the number of events between two quiescent points, membership is in PTIME, while correctness is in PSPACE. Finally, we consider a version of quiescent sequential consistency that places an upper limit on the number of processes for every run of the implementation, and show that the membership problem for quiescent sequential consistency with this restriction is in PTIME.
Creativity in Mind: Evaluating and Maintaining Advances in Network Steganographic Research
Venue: arXiv cs.MM 2015
Year: 2015

The research discipline of network steganography deals with the hiding of information within network transmissions, e.g. to transfer illicit information in networks with Internet censorship. The last decades of research on network steganography led to more than hundred techniques for hiding data in network transmissions. However, previous research has shown that most of these hiding techniques are either based on the same idea or introduce limited novelty, enabling the application of existing countermeasures. In this paper, we provide a link between the field of creativity and network steganographic research. We propose a framework and a metric to help evaluating the creativity bound to a given hiding technique. This way, we support two sides of the scientific peer review process as both authors and reviewers can use our framework to analyze the novelty and applicability of hiding techniques. At the same time, we contribute to a uniform terminology in network steganography.