OpenRaiser/Intern-Atlas huggingface dataset:
Analysis on 60 GHz Wireless Communications with Beamwidth-Dependent Misalignment
Venue: arXiv cs.IT 2016
Year: 2016

High speed wireless access on 60 GHz spectrum relies on high-gain directional antennas to overcome the severe signal attenuation. However, perfect alignment between transmitting and receiving antenna beams is rare in practice and overheard signals from concurrent transmissions may cause significant interference. In this paper we analyze the impact of antenna beam misalignment on the system performance of 60 GHz wireless access. We quantify the signal power loss caused by beam misalignment and the interference power accumulated from neighboring concurrent transmissions whose signals are leaked either via the main-beam pointing in the similar direction or via side-lobe emission, and derive the probability distribution of the signal to interference plus noise power ratio (SINR). For scenarios where interfering transmitters are distributed uniformly at random, we derive upper and lower bounds on the cumulative distribution function (abbreviated as CDF or c.d.f.) of SINR, which can be easily applied to evaluate system performance. We validate our analytical results by simulations where random nodes are uniformly distributed within a circular hall, and evaluate the sensitivity of average throughput and outage probability against two parameters: the half-power (3 dB) beamwidth to main-lobe beamwidth ratio and the beam misalignment deviation to main-lobe beamwidth ratio. Our results indicate that the derived lower bound performs well when the half-power beamwidth to main-lobe beamwidth ratio or the number of concurrent transmission links is small. When the number of active links is high, it is desirable in antenna design to balance the degradation caused by beam misalignment (wider beam is better) and the interference from concurrent transmission (narrower beam is better).
Testing submodularity and other properties of valuation functions
Venue: arXiv cs.DS 2016
Year: 2016

We show that for any constant $ε> 0$ and $p \ge 1$, it is possible to distinguish functions $f : \{0,1\}^n \to [0,1]$ that are submodular from those that are $ε$-far from every submodular function in $\ell_p$ distance with a constant number of queries. More generally, we extend the testing-by-implicit-learning framework of Diakonikolas et al. (2007) to show that every property of real-valued functions that is well-approximated in $\ell_2$ distance by a class of $k$-juntas for some $k = O(1)$ can be tested in the $\ell_p$-testing model with a constant number of queries. This result, combined with a recent junta theorem of Feldman and Vondrak (2016), yields the constant-query testability of submodularity. It also yields constant-query testing algorithms for a variety of other natural properties of valuation functions, including fractionally additive (XOS) functions, OXS functions, unit demand functions, coverage functions, and self-bounding functions.
Double-quantitative $γ^{\ast}-$fuzzy coverings approximation operators
Venue: arXiv cs.AI 2016
Year: 2016

In digital-based information boom, the fuzzy covering rough set model is an important mathematical tool for artificial intelligence, and how to build the bridge between the fuzzy covering rough set theory and Pawlak's model is becoming a hot research topic. In this paper, we first present the $γ-$fuzzy covering based probabilistic and grade approximation operators and double-quantitative approximation operators. We also study the relationships among the three types of $γ-$fuzzy covering based approximation operators. Second, we propose the $γ^{\ast}-$fuzzy coverings based multi-granulation probabilistic and grade lower and upper approximation operators and multi-granulation double-quantitative lower and upper approximation operators. We also investigate the relationships among these types of $γ-$fuzzy coverings based approximation operators. Finally, we employ several examples to illustrate how to construct the lower and upper approximations of fuzzy sets with the absolute and relative quantitative information.
Search on a Line by Byzantine Robots
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of fault-tolerant parallel search on an infinite line by $n$ robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed $1$ and can communicate in wireless mode among themselves. However, among the $n$ robots, there are $f$ robots that exhibit {\em byzantine faults}. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of $S_d(n,f)$, the time to find a target at a distance $d$ from the origin by $n$ robots among which $f$ are faulty. We give several different algorithms whose running time depends on the ratio $f/n$, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.
Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors
Venue: arXiv cs.LG 2016
Year: 2016

Dictionary learning is the task of determining a data-dependent transform that yields a sparse representation of some observed data. The dictionary learning problem is non-convex, and usually solved via computationally complex iterative algorithms. Furthermore, the resulting transforms obtained generally lack structure that permits their fast application to data. To address this issue, this paper develops a framework for learning orthonormal dictionaries which are built from products of a few Householder reflectors. Two algorithms are proposed to learn the reflector coefficients: one that considers a sequential update of the reflectors and one with a simultaneous update of all reflectors that imposes an additional internal orthogonal constraint. The proposed methods have low computational complexity and are shown to converge to local minimum points which can be described in terms of the spectral properties of the matrices involved. The resulting dictionaries balance between the computational complexity and the quality of the sparse representations by controlling the number of Householder reflectors in their product. Simulations of the proposed algorithms are shown in the image processing setting where well-known fast transforms are available for comparisons. The proposed algorithms have favorable reconstruction error and the advantage of a fast implementation relative to the classical, unstructured, dictionaries.
InstanceCut: from Edges to Instances with MultiCut
Venue: arXiv cs.CV 2016
Year: 2016

This work addresses the task of instance-aware semantic segmentation. Our key motivation is to design a simple method with a new modelling-paradigm, which therefore has a different trade-off between advantages and disadvantages compared to known approaches. Our approach, we term InstanceCut, represents the problem by two output modalities: (i) an instance-agnostic semantic segmentation and (ii) all instance-boundaries. The former is computed from a standard convolutional neural network for semantic segmentation, and the latter is derived from a new instance-aware edge detection model. To reason globally about the optimal partitioning of an image into instances, we combine these two modalities into a novel MultiCut formulation. We evaluate our approach on the challenging CityScapes dataset. Despite the conceptual simplicity of our approach, we achieve the best result among all published methods, and perform particularly well for rare object classes.
Proxy Voting for Better Outcomes
Venue: arXiv cs.GT 2016
Year: 2016

We consider a social choice problem where only a small number of people out of a large population are sufficiently available or motivated to vote. A common solution to increase participation is to allow voters use a proxy, that is, transfer their voting rights to another voter. Considering social choice problems on metric spaces, we compare voting with and without the use of proxies to see which mechanism better approximates the optimal outcome, and characterize the regimes in which proxy voting is beneficial. When voters' opinions are located on an interval, both the median mechanism and the mean mechanism are substantially improved by proxy voting. When voters vote on many binary issues, proxy voting is better when the sample of active voters is too small to provide a good outcome. Our theoretical results extend to situations where available voters choose strategically whether to participate. We support our theoretical findings with empirical results showing substantial benefits of proxy voting on simulated and real preference data.
On Human Intellect and Machine Failures: Troubleshooting Integrative Machine Learning Systems
Venue: arXiv cs.LG 2016
Year: 2016

We study the problem of troubleshooting machine learning systems that rely on analytical pipelines of distinct components. Understanding and fixing errors that arise in such integrative systems is difficult as failures can occur at multiple points in the execution workflow. Moreover, errors can propagate, become amplified or be suppressed, making blame assignment difficult. We propose a human-in-the-loop methodology which leverages human intellect for troubleshooting system failures. The approach simulates potential component fixes through human computation tasks and measures the expected improvements in the holistic behavior of the system. The method provides guidance to designers about how they can best improve the system. We demonstrate the effectiveness of the approach on an automated image captioning system that has been pressed into real-world use.
The Impact of Vehicular Traffic Demand on 5G Caching Architectures: a Data-Driven Study
Venue: arXiv cs.NI 2016
Year: 2016

The emergence of in-vehicle entertainment systems and self-driving vehicles, and the latter's need for high-resolution, up-to-date maps, will bring a further increase in the amount of data vehicles consume. Considering how difficult WiFi offloading in vehicular environments is, the bulk of this additional load will be served by cellular networks. Cellular networks, in turn, will resort to caching at the network edge in order to reduce the strain on their core network, an approach also known as mobile edge computing, or fog computing. In this work, we exploit a real-world, large-scale trace coming from the users of the We-Fi app in order to (i) understand how significant the contribution of vehicular users is to the global traffic demand; (ii) compare the performance of different caching architectures; and (iii) studying how such a performance is influenced by recommendation systems and content locality. We express the price of fog computing through a metric called price-of-fog, accounting for the extra caches to deploy compared to a traditional, centralized approach. We find that fog computing allows a very significant reduction of the load on the core network, and the price thereof is low in all cases and becomes negligible if content demand is location specific. We can therefore conclude that vehicular networks make an excellent case for the transition to mobile-edge caching: thanks to the peculiar features of vehicular demand, we can obtain all the benefits of fog computing, including a reduction of the load on the core network, reducing the disadvantages to a minimum.
Fine-grained Mining of Illicit Drug Use Patterns Using Social Multimedia Data from Instagram
Venue: arXiv cs.SI 2016
Year: 2016

According to NSDUH (National Survey on Drug Use and Health), 20 million Americans consumed drugs in the past few 30 days. Combating illicit drug use is of great interest to public health and law enforcement agencies. Despite of the importance, most of the existing studies on drug uses rely on surveys. Surveys on sensitive topics such as drug use may not be answered truthfully by the people taking them. Selecting a representative sample to survey is another major challenge. In this paper, we explore the possibility of using big multimedia data, including both images and text, from social media in order to discover drug use patterns at fine granularity with respect to demographics. Instagram posts are searched and collected by drug related terms by analyzing the hashtags supplied with each post. A large and dynamic dictionary of frequent drug related slangs is used to find these posts. User demographics are extracted using robust face image analysis algorithms. These posts are then mined to find common trends with regard to the time and location they are posted, and further in terms of age and gender of the drug users. Furthermore, by studying the accounts followed by the users of drug related posts, we extract common interests shared by drug users.
A Multimodal Approach to Estimating Vigilance Using EEG and Forehead EOG
Venue: arXiv cs.HC 2016
Year: 2016

Objective. Covert aspects of ongoing user mental states provide key context information for user-aware human computer interactions. In this paper, we focus on the problem of estimating the vigilance of users using EEG and EOG signals. Approach. To improve the feasibility and wearability of vigilance estimation devices for real-world applications, we adopt a novel electrode placement for forehead EOG and extract various eye movement features, which contain the principal information of traditional EOG. We explore the effects of EEG from different brain areas and combine EEG and forehead EOG to leverage their complementary characteristics for vigilance estimation. Considering that the vigilance of users is a dynamic changing process because the intrinsic mental states of users involve temporal evolution, we introduce continuous conditional neural field and continuous conditional random field models to capture dynamic temporal dependency. Main results. We propose a multimodal approach to estimating vigilance by combining EEG and forehead EOG and incorporating the temporal dependency of vigilance into model training. The experimental results demonstrate that modality fusion can improve the performance compared with a single modality, EOG and EEG contain complementary information for vigilance estimation, and the temporal dependency-based models can enhance the performance of vigilance estimation. From the experimental results, we observe that theta and alpha frequency activities are increased, while gamma frequency activities are decreased in drowsy states in contrast to awake states. Significance. The forehead setup allows for the simultaneous collection of EEG and EOG and achieves comparative performance using only four shared electrodes in comparison with the temporal and posterior sites.
Fast deterministic tourist walk for texture analysis
Venue: arXiv cs.CV 2016
Year: 2016

Deterministic tourist walk (DTW) has attracted increasing interest in computer vision. In the last years, different methods for analysis of dynamic and static textures were proposed. So far, all works based on the DTW for texture analysis use all image pixels as initial point of a walk. However, this requires much runtime. In this paper, we conducted a study to verify the performance of the DTW method according to the number of initial points to start a walk. The proposed method assigns a unique code to each image pixel, then, the pixels whose code is not divisible by a given $k$ value are ignored as initial points of walks. Feature vectors were extracted and a classification process was performed for different percentages of initial points. Experimental results on the Brodatz and Vistex datasets indicate that to use fewer pixels as initial points significantly improves the runtime compared to use all image pixels. In addition, the correct classification rate decreases very little.
On the DoF of Two-way $2\times2\times2$ Relay Networks with or without Relay Caching
Venue: arXiv cs.IT 2016
Year: 2016

Two-way relay is potentially an effective approach to spectrum sharing and aggregation by allowing simultaneous bidirectional transmissions between source-destinations pairs. This paper studies the two-way $2\times2\times2$ relay network, a class of four-unicast networks, where there are four source/destination nodes and two relay nodes, with each source sending a message to its destination. We show that without relay caching the total degrees of freedom (DoF) is bounded from above by $8/3$, indicating that bidirectional links do not double the DoF (It is known that the total DoF of one-way $2\times2\times2$ relay network is $2$.). Further, we show that the DoF of $8/3$ is achievable for the two-way $2\times2\times2$ relay network with relay caching. Finally, even though the DoF of this network is no more than $8/3$ for generic channel gains, DoF of $4$ can be achieved for a symmetric configuration of channel gains.
Cryptanalysis of Xinyu et al.'s NTRU-Lattice Based Key Exchange Protocol
Venue: arXiv cs.CR 2016
Year: 2016

Xinyu et al. proposed a public key exchange protocol, which is based on the NTRU-lattice based cryptography. In this paper, we show how Xinyu et al.'s NTRU-KE: A lattice based key exchange protocol can be broken, under the assumption that a man-in-the middle attack is used for extracting private keys of users who participate in the key exchange protocol.
Machine Learning on Human Connectome Data from MRI
Venue: arXiv cs.LG 2016
Year: 2016

Functional MRI (fMRI) and diffusion MRI (dMRI) are non-invasive imaging modalities that allow in-vivo analysis of a patient's brain network (known as a connectome). Use of these technologies has enabled faster and better diagnoses and treatments of neurological disorders and a deeper understanding of the human brain. Recently, researchers have been exploring the application of machine learning models to connectome data in order to predict clinical outcomes and analyze the importance of subnetworks in the brain. Connectome data has unique properties, which present both special challenges and opportunities when used for machine learning. The purpose of this work is to review the literature on the topic of applying machine learning models to MRI-based connectome data. This field is growing rapidly and now encompasses a large body of research. To summarize the research done to date, we provide a comparative, structured summary of 77 relevant works, tabulated according to different criteria, that represent the majority of the literature on this topic. (We also published a living version of this table online at http://connectomelearning.cs.sfu.ca that the community can continue to contribute to.) After giving an overview of how connectomes are constructed from dMRI and fMRI data, we discuss the variety of machine learning tasks that have been explored with connectome data. We then compare the advantages and drawbacks of different machine learning approaches that have been employed, discussing different feature selection and feature extraction schemes, as well as the learning models and regularization penalties themselves. Throughout this discussion, we focus particularly on how the methods are adapted to the unique nature of graphical connectome data. Finally, we conclude by summarizing the current state of the art and by outlining what we believe are strategic directions for future research.
Structural Correspondence Learning for Cross-lingual Sentiment Classification with One-to-many Mappings
Venue: arXiv cs.LG 2016
Year: 2016

Structural correspondence learning (SCL) is an effective method for cross-lingual sentiment classification. This approach uses unlabeled documents along with a word translation oracle to automatically induce task specific, cross-lingual correspondences. It transfers knowledge through identifying important features, i.e., pivot features. For simplicity, however, it assumes that the word translation oracle maps each pivot feature in source language to exactly only one word in target language. This one-to-one mapping between words in different languages is too strict. Also the context is not considered at all. In this paper, we propose a cross-lingual SCL based on distributed representation of words; it can learn meaningful one-to-many mappings for pivot words using large amounts of monolingual data and a small dictionary. We conduct experiments on NLP\&CC 2013 cross-lingual sentiment analysis dataset, employing English as source language, and Chinese as target language. Our method does not rely on the parallel corpora and the experimental results show that our approach is more competitive than the state-of-the-art methods in cross-lingual sentiment classification.
Handwriting Profiling using Generative Adversarial Networks
Venue: arXiv cs.CV 2016
Year: 2016

Handwriting is a skill learned by humans from a very early age. The ability to develop one's own unique handwriting as well as mimic another person's handwriting is a task learned by the brain with practice. This paper deals with this very problem where an intelligent system tries to learn the handwriting of an entity using Generative Adversarial Networks (GANs). We propose a modified architecture of DCGAN (Radford, Metz, and Chintala 2015) to achieve this. We also discuss about applying reinforcement learning techniques to achieve faster learning. Our algorithm hopes to give new insights in this area and its uses include identification of forged documents, signature verification, computer generated art, digitization of documents among others. Our early implementation of the algorithm illustrates a good performance with MNIST datasets.
Multiuser separation and performance analysis of millimeter wave channels with linear precoding
Venue: arXiv cs.IT 2016
Year: 2016

In the conventional multiuser MIMO systems, user selection and scheduling has previously been used as an effective way to increase the sum rate performance of the system. However, the recent concepts of the massive MIMO systems (at centimeter wavelength frequencies) have shown that with higher spatial resolution of antenna arrays different users in the dense scenarios can be spatially separated. This in turn significantly reduces the signal processing efforts required for multiuser selection algorithms. On the other hand, recent measurements at millimeter wave frequencies show that multipath components only arrive from few angular directions leading to high spatial correlation between the paths and co-located users. This paper focus at the investigation of spatial separation among the users at the millimeter wave frequencies with fully digital linear zero-forcing transmit precoding considering various channel propagation parameters. Our analysis results convincingly give a proof that multiuser selection algorithms are still important for millimeter wave communication systems. Results also show that increased number of antenna elements does not give a major benefit to sum rate improvements as compared to the selection of correct number of users to be selected/scheduled.