OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Player Bandits -- a Musical Chairs Approach
Venue: arXiv cs.LG 2015
Year: 2015

We consider a variant of the stochastic multi-armed bandit problem, where multiple players simultaneously choose from the same set of arms and may collide, receiving no reward. This setting has been motivated by problems arising in cognitive radio networks, and is especially challenging under the realistic assumption that communication between players is limited. We provide a communication-free algorithm (Musical Chairs) which attains constant regret with high probability, as well as a sublinear-regret, communication-free algorithm (Dynamic Musical Chairs) for the more difficult setting of players dynamically entering and leaving throughout the game. Moreover, both algorithms do not require prior knowledge of the number of players. To the best of our knowledge, these are the first communication-free algorithms with these types of formal guarantees. We also rigorously compare our algorithms to previous works, and complement our theoretical findings with experiments.
Where You Are Is Who You Are: User Identification by Matching Statistics
Venue: arXiv cs.LG 2015
Year: 2015

Most users of online services have unique behavioral or usage patterns. These behavioral patterns can be exploited to identify and track users by using only the observed patterns in the behavior. We study the task of identifying users from statistics of their behavioral patterns. Specifically, we focus on the setting in which we are given histograms of users' data collected during two different experiments. We assume that, in the first dataset, the users' identities are anonymized or hidden and that, in the second dataset, their identities are known. We study the task of identifying the users by matching the histograms of their data in the first dataset with the histograms from the second dataset. In recent works, the optimal algorithm for this user identification task is introduced. In this paper, we evaluate the effectiveness of this method on three different types of datasets and in multiple scenarios. Using datasets such as call data records, web browsing histories, and GPS trajectories, we show that a large fraction of users can be easily identified given only histograms of their data; hence these histograms can act as users' fingerprints. We also verify that simultaneous identification of users achieves better performance compared to one-by-one user identification. We show that using the optimal method for identification gives higher identification accuracy than heuristics-based approaches in practical scenarios. The accuracy obtained under this optimal method can thus be used to quantify the maximum level of user identification that is possible in such settings. We show that the key factors affecting the accuracy of the optimal identification algorithm are the duration of the data collection, the number of users in the anonymized dataset, and the resolution of the dataset. We analyze the effectiveness of k-anonymization in resisting user identification attacks on these datasets.
MetaSpace II: Object and full-body tracking for interaction and navigation in social VR
Venue: arXiv cs.HC 2015
Year: 2015

MetaSpace II (MS2) is a social Virtual Reality (VR) system where multiple users can not only see and hear but also interact with each other, grasp and manipulate objects, walk around in space, and get tactile feedback. MS2 allows walking in physical space by tracking each user's skeleton in real-time and allows users to feel by employing passive haptics i.e., when users touch or manipulate an object in the virtual world, they simultaneously also touch or manipulate a corresponding object in the physical world. To enable these elements in VR, MS2 creates a correspondence in spatial layout and object placement by building the virtual world on top of a 3D scan of the real world. Through the association between the real and virtual world, users are able to walk freely while wearing a head-mounted device, avoid obstacles like walls and furniture, and interact with people and objects. Most current virtual reality (VR) environments are designed for a single user experience where interactions with virtual objects are mediated by hand-held input devices or hand gestures. Additionally, users are only shown a representation of their hands in VR floating in front of the camera as seen from a first person perspective. We believe, representing each user as a full-body avatar that is controlled by natural movements of the person in the real world (see Figure 1d), can greatly enhance believability and a user's sense immersion in VR.
Stochastic Interpretation of Quasi-periodic Event-based Systems
Venue: arXiv cs.NE 2015
Year: 2015

Many networks used in machine learning and as models of biological neural networks make use of stochastic neurons or neuron-like units. We show that stochastic artificial neurons can be realized on silicon chips by exploiting the quasi-periodic behavior of mismatched analog oscillators to approximate the neuron's stochastic activation function. We represent neurons by finite state machines (FSMs) that communicate using digital events and whose transitions are event-triggered. The event generation times of each neuron are controlled by an analog oscillator internal to that neuron/FSM and the frequencies of the oscillators in different FSMs are incommensurable. We show that within this quasi-periodic system, the transition graph of a FSM can be interpreted as the transition graph of a Markov chain and we show that by using different FSMs, we can obtain approximations of different stochastic activation functions. We investigate the quality of the stochastic interpretation of such a deterministic system and we use the system to realize and sample from a restricted Boltzmann machine. We implemented the quasi-periodic event-based system on a custom silicon chip and we show that the chip behavior can be used to closely approximate a stochastic sampling task.
Get More With Less: Near Real-Time Image Clustering on Mobile Phones
Venue: arXiv cs.CV 2015
Year: 2015

Machine learning algorithms, in conjunction with user data, hold the promise of revolutionizing the way we interact with our phones, and indeed their widespread adoption in the design of apps bear testimony to this promise. However, currently, the computationally expensive segments of the learning pipeline, such as feature extraction and model training, are offloaded to the cloud, resulting in an over-reliance on the network and under-utilization of computing resources available on mobile platforms. In this paper, we show that by combining the computing power distributed over a number of phones, judicious optimization choices, and contextual information it is possible to execute the end-to-end pipeline entirely on the phones at the edge of the network, efficiently. We also show that by harnessing the power of this combination, it is possible to execute a computationally expensive pipeline at near real-time. To demonstrate our approach, we implement an end-to-end image-processing pipeline -- that includes feature extraction, vocabulary learning, vectorization, and image clustering -- on a set of mobile phones. Our results show a 75% improvement over the standard, full pipeline implementation running on the phones without modification -- reducing the time to one minute under certain conditions. We believe that this result is a promising indication that fully distributed, infrastructure-less computing is possible on networks of mobile phones; enabling a new class of mobile applications that are less reliant on the cloud.
Network Coding Applications for 5G Millimeter-Wave Communications
Venue: arXiv cs.NI 2015
Year: 2015

The millimeter-wave bands have been attracting significant interest as a means to achieve major improvements in data rates and network efficiencies. One significant limitation for use of the millimeter-wave bands for cellular communication is that the communication suffers from much higher path-loss compared to the microwave bands. Millimeter-wave links have also been shown to change rapidly, causing links between devices and access points to switch among line-of-sight, non-line-of-sight and outage states. We propose using Random Linear Network Coding to overcome the unreliability of individual communication links in such millimeter-wave systems. Our system consists of devices transmitting and receiving network-coded packets through several access points. For downlink communication, network-coded packets are transmitted to a device via multiple access points. For uplink communication, the access points perform network coding of packets of several devices, and then send the network-coded packets to the core network. We compare our approach against a naive approach in which non-network coded packets are transmitted via multiple access points ("Forwarding" approach). We find that the network coding approach significantly outperforms the forwarding approach. In particular, network coding greatly improves the efficiency of the air-interface transmissions and the efficiency of the backhaul transmissions for the downlink and uplink communication, respectively.
User Mobility Evaluation for 5G Small Cell Networks Based on Individual Mobility Model
Venue: arXiv cs.NI 2015
Year: 2015

With small cell networks becoming core parts of the fifth generation (5G) cellular networks, it is an important problem to evaluate the impact of user mobility on 5G small cell networks. However, the tendency and clustering habits in human activities have not been considered in traditional user mobility models. In this paper, human tendency and clustering behaviors are first considered to evaluate the user mobility performance for 5G small cell networks based on individual mobility model (IMM). As key contributions, user pause probability, user arrival and departure probabilities are derived in this paper for evaluat-ing the user mobility performance in a hotspot-type 5G small cell network. Furthermore, coverage probabilities of small cell and macro cell BSs are derived for all users in 5G small cell networks, respectively. Compared with the traditional random waypoint (RWP) model, IMM provides a different viewpoint to investigate the impact of human tendency and clustering behaviors on the performance of 5G small cell networks.
Semantic Arabic Information Retrieval Framework
Venue: arXiv cs.IR 2015
Year: 2015

The continuous increasing in the amount of the published and stored information requires a special Information Retrieval (IR) frameworks to search and get information accurately and speedily. Currently, keywords-based techniques are commonly used in information retrieval. However, a major drawback of the keywords approach is its inability of handling the polysemy and synonymy phenomenon of the natural language. For instance, the meanings of words and understanding of concepts differ in different communities. Same word use for different concepts (polysemy) or use different words for the same concept (synonymy). Most of information retrieval frameworks have a weakness to deal with the semantics of the words in term of (indexing, Boolean model, Latent Semantic Analysis (LSA) , Latent semantic Index (LSI) and semantic ranking, etc.). Traditional Arabic Information Retrieval (AIR) models performance insufficient with semantic queries, which deal with not only the keywords but also with the context of these keywords. Therefore, there is a need for a semantic information retrieval model with a semantic index structure and ranking algorithm based on semantic index.
Histogram Arithmetic under Uncertainty of Probability Density Function
Venue: arXiv cs.NA 2015
Year: 2015

In this article we propose a method of performing arithmetic operations on varia-bles with unknown distribution. The approach to the evaluation results of arithme-tic operations can select probability intervals of the algebraic equations and their systems solutions, of differential equations and their systems in case of histogram evaluation of the empirical density distributions of random parameters.
An Encrypted Trust-Based Routing Protocol
Venue: arXiv cs.CR 2015
Year: 2015

The interest in trust-based routing protocols has grown with the advancements achieved in ad-hoc wireless networks.However, regardless of the many security approaches and trust metrics available, trust-based routing still faces some security challenges, especially with respect to privacy. In this paper, we propose a novel trust-based routing protocol based on a fully homomorphic encryption scheme. The new protocol allows nodes, which collaborate in a dynamic environment, to evaluate their knowledge on the trustworthiness of specific routes and securely share this knowledge.
Diversity and Intelligence in Multi-robot Teams
Venue: arXiv cs.RO 2015
Year: 2015

This research proposes new tools for investigation of behavioral diversity in multi-robot systems and a significant body of results using these tools in simulated and real mobile robot experiments. The experiments specifically describe a framework of defining behavior-based strategies for multi-robot tasks as robot foraging, robot soccer and robot formation. The research focuses specifically on motor schema-based multi-robot systems, which are an important example of behavior-based control.
Approximating the Integral Fréchet Distance
Venue: arXiv cs.CG 2015
Year: 2015

A pseudo-polynomial time $(1 + \varepsilon)$-approximation algorithm is presented for computing the integral and average Fréchet distance between two given polygonal curves $T_1$ and $T_2$. In particular, the running time is upper-bounded by $\mathcal{O}( ζ^{4}n^4/\varepsilon^{2})$ where $n$ is the complexity of $T_1$ and $T_2$ and $ζ$ is the maximal ratio of the lengths of any pair of segments from $T_1$ and $T_2$. The Fréchet distance captures the minimal cost of a continuous deformation of $T_1$ into $T_2$ and vice versa and defines the cost of a deformation as the maximal distance between two points that are related. The integral Fréchet distance defines the cost of a deformation as the integral of the distances between points that are related. The average Fréchet distance is defined as the integral Fréchet distance divided by the lengths of $T_1$ and $T_2$. Furthermore, we give relations between weighted shortest paths inside a single parameter cell $C$ and the monotone free space axis of $C$. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.
Neural Self Talk: Image Understanding via Continuous Questioning and Answering
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we consider the problem of continuously discovering image contents by actively asking image based questions and subsequently answering the questions being asked. The key components include a Visual Question Generation (VQG) module and a Visual Question Answering module, in which Recurrent Neural Networks (RNN) and Convolutional Neural Network (CNN) are used. Given a dataset that contains images, questions and their answers, both modules are trained at the same time, with the difference being VQG uses the images as input and the corresponding questions as output, while VQA uses images and questions as input and the corresponding answers as output. We evaluate the self talk process subjectively using Amazon Mechanical Turk, which show effectiveness of the proposed method.
A Fast Heuristic for Exact String Matching
Venue: arXiv cs.DS 2015
Year: 2015

Given a pattern string $P$ of length $n$ consisting of $δ$ distinct characters and a query string $T$ of length $m$, where the characters of $P$ and $T$ are drawn from an alphabet $Σ$ of size $Δ$, the {\em exact string matching} problem consists of finding all occurrences of $P$ in $T$. For this problem, we present a randomized heuristic that in $O(nδ)$ time preprocesses $P$ to identify $sparse(P)$, a rarely occurring substring of $P$, and then use it to find all occurrences of $P$ in $T$ efficiently. This heuristic has an expected search time of $O( \frac{m}{min(|sparse(P)|, Δ)})$, where $|sparse(P)|$ is at least $δ$. We also show that for a pattern string $P$ whose characters are chosen uniformly at random from an alphabet of size $Δ$, $E[|sparse(P)|]$ is $Ω(Δlog (\frac{2Δ}{2Δ-δ}))$.
Subsumptive reflection in SNOMED CT: a large description logic-based terminology for diagnosis
Venue: arXiv cs.AI 2015
Year: 2015

Description logic (DL) based biomedical terminology (SNOMED CT) is used routinely in medical practice. However, diagnostic inference using such terminology is precluded by its complexity. Here we propose a model that simplifies these inferential components. We propose three concepts that classify clinical features and examined their effect on inference using SNOMED CT. We used PAIRS (Physician Assistant Artificial Intelligence Reference System) database (1964 findings for 485 disorders, 18 397 disease feature links) for our analysis. We also use a 50-million medical word corpus for estimating the vectors of disease-feature links. Our major results are 10% of finding-disorder links are concomitant in both assertion and negation where as 90% are either concomitant in assertion or negation. Logical implications of PAIRS data on SNOMED CT include 70% of the links do not share any common system while 18% share organ and 12% share both system and organ. Applications of these principles for inference are discussed and suggestions are made for deriving a diagnostic process using SNOMED CT. Limitations of these processes and suggestions for improvements are also discussed.
Words are not Equal: Graded Weighting Model for building Composite Document Vectors
Venue: arXiv cs.CL 2015
Year: 2015

Despite the success of distributional semantics, composing phrases from word vectors remains an important challenge. Several methods have been tried for benchmark tasks such as sentiment classification, including word vector averaging, matrix-vector approaches based on parsing, and on-the-fly learning of paragraph vectors. Most models usually omit stop words from the composition. Instead of such an yes-no decision, we consider several graded schemes where words are weighted according to their discriminatory relevance with respect to its use in the document (e.g., idf). Some of these methods (particularly tf-idf) are seen to result in a significant improvement in performance over prior state of the art. Further, combining such approaches into an ensemble based on alternate classifiers such as the RNN model, results in an 1.6% performance improvement on the standard IMDB movie review dataset, and a 7.01% improvement on Amazon product reviews. Since these are language free models and can be obtained in an unsupervised manner, they are of interest also for under-resourced languages such as Hindi as well and many more languages. We demonstrate the language free aspects by showing a gain of 12% for two review datasets over earlier results, and also release a new larger dataset for future testing (Singh,2015).
Optimizing the Gossip Algorithm with Non-Uniform Clock Distribution over Classical & Quantum Networks
Venue: arXiv cs.SY 2015
Year: 2015

Distributed gossip algorithm has been studied in literature for practical implementation of the distributed consensus algorithm as a fundamental algorithm for the purpose of in-network collaborative processing. This paper focuses on optimizing the convergence rate of the gossip algorithm for both classical and quantum networks. A novel model of the gossip algorithm with non-uniform clock distribution is proposed which can reach the optimal convergence rate of the continuous-time consensus algorithm. It is described that how the non-uniform clock distribution is achievable by modifying the rate of the Poisson process modeling the clock of the gossip algorithm. The minimization problem for optimizing the asymptotic convergence rate of the proposed gossip algorithm and its corresponding semidefinite programming formulation is addressed analytically. It is shown that the optimal results obtained for uniform clock distribution are suboptimal compared to those of the non-uniform one and for non-uniform distribution the optimal answer is not unique i.e. there is more than one set of probabilities that can achieve the optimal convergence rate. Based on the optimal continuous-time consensus algorithm and the detailed balance property, an effective method of obtaining one of these optimal answers is proposed. Regarding quantum gossip algorithm, by expanding the density matrix in terms of the generalized Gell-Mann matrices, the evolution equation of the quantum gossip algorithm is transformed to the state update equation of the classical gossip algorithm. By defining the quantum gossip operator, the original optimization problem is formulated as a convex optimization problem, which can be addressed by semidefinite programming.
An overview of visible light communication systems
Venue: arXiv cs.NI 2015
Year: 2015

Visible Light Communication (VLC) has gained great interest in the last decade due to the rapid developments in Light Emitting Diodes (LEDs) fabrication. Efficiency, durability and long life span of LEDs make them a promising residential lighting equipment as well as an alternative cheap and fast data transfer equipment. Appliance of visual light in data communication by means of LEDs has been densely searched in academia. In this paper, we explore the fundamentals and challenges of indoor VLC systems. Basics of optical transmission such as transmitter, receiver, and links are investigated. Moreover, characteristics of channel models in indoor VLC systems are identified and theoretical details about channel modelling are presented in detail.
Control Flow Analysis for SF Combinator Calculus
Venue: arXiv cs.PL 2015
Year: 2015

Programs that transform other programs often require access to the internal structure of the program to be transformed. This is at odds with the usual extensional view of functional programming, as embodied by the lambda calculus and SK combinator calculus. The recently-developed SF combinator calculus offers an alternative, intensional model of computation that may serve as a foundation for developing principled languages in which to express intensional computation, including program transformation. Until now there have been no static analyses for reasoning about or verifying programs written in SF-calculus. We take the first step towards remedying this by developing a formulation of the popular control flow analysis 0CFA for SK-calculus and extending it to support SF-calculus. We prove its correctness and demonstrate that the analysis is invariant under the usual translation from SK-calculus into SF-calculus.
Deep Tracking: Visual Tracking Using Deep Convolutional Networks
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we study a discriminatively trained deep convolutional network for the task of visual tracking. Our tracker utilizes both motion and appearance features that are extracted from a pre-trained dual stream deep convolution network. We show that the features extracted from our dual-stream network can provide rich information about the target and this leads to competitive performance against state of the art tracking methods on a visual tracking benchmark.
Convergence Analysis of Proportionate-type Least Mean Square Algorithms
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we present the convergence analysis of proportionate-type least mean square (Pt-LMS) algorithm that identifies the sparse system effectively and more suitable for real time VLSI applications. Both first and second order convergence analysis of Pt-LMS algorithm is studied. Optimum convergence behavior of Pt-LMS algorithm is studied from the second order convergence analysis provided in this paper. Simulation results were conducted to verify the analytical results.