OpenRaiser/Intern-Atlas huggingface dataset:
Zadoff-Chu sequence design for random access initial uplink synchronization
Venue: arXiv cs.IT 2016
Year: 2016

The autocorrelation of a Zadoff-Chu (ZC) sequence with a non-zero cyclically shifted version of itself is zero. Due to the interesting property, ZC sequences are widely used in the LTE air interface in the primary synchronization signal (PSS), random access preamble (PRACH), uplink control channel (PUCCH) etc. However, this interesting property of ZC sequence is not useful in the random access initial uplink synchronization problem due to some specific structures of the underlying problem. In particular, the state of the art uplink synchronization algorithms do not perform equally for all ZC sequences. In this work, we show a systematic procedure to choose the ZC sequences that yield the optimum performance of the uplink synchronization algorithms. At first, we show that the uplink synchronization is a sparse signal recovery problem on an overcomplete basis. Next, we use the theory of sparse recovery algorithms and identify a factor that controls performance of the algorithms. We then suggest a ZC sequence design procedure to optimally choose this factor. The simulation results show that the performance of most of the state of the art uplink synchronization algorithms improve significantly when the ZC sequences are chosen by using the proposed technique.
Simple and Efficient Learning using Privileged Information
Venue: arXiv cs.LG 2016
Year: 2016

The Support Vector Machine using Privileged Information (SVM+) has been proposed to train a classifier to utilize the additional privileged information that is only available in the training phase but not available in the test phase. In this work, we propose an efficient solution for SVM+ by simply utilizing the squared hinge loss instead of the hinge loss as in the existing SVM+ formulation, which interestingly leads to a dual form with less variables and in the same form with the dual of the standard SVM. The proposed algorithm is utilized to leverage the additional web knowledge that is only available during training for the image categorization tasks. The extensive experimental results on both Caltech101 andWebQueries datasets show that our proposed method can achieve a factor of up to hundred times speedup with the comparable accuracy when compared with the existing SVM+ method.
Axiomatic Characterization of Committee Scoring Rules
Venue: arXiv cs.GT 2016
Year: 2016

Committee scoring rules form a rich class of aggregators of voters' preferences for the purpose of selecting subsets of objects with desired properties, e.g., a shortlist of candidates for an interview, a representative collective body such as a parliament, or a set of locations for a set of public facilities. In the spirit of celebrated Young's characterization result that axiomatizes single-winner scoring rules, we provide an axiomatic characterization of multiwinner committee scoring rules. We show that committee scoring rules---despite forming a remarkably general class of rules---are characterized by the set of four standard axioms, anonymity, neutrality, consistency and continuity, and by one axiom specific to multiwinner rules which we call committee dominance. In the course of our proof, we develop several new notions and techniques. In particular, we introduce and axiomatically characterize multiwinner decision scoring rules, a class of rules that broadly generalizes the well-known majority relation.
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs
Venue: arXiv cs.CC 2016
Year: 2016

In this paper we establish an exponential lower bound on the size of syntactic non-deterministic read $d$-times branching programs for $d \leq \log n /10^5$ computing a class of monotone CNFs with a linear number of clauses. This result provides the first separation of classes NP and co-NP for syntactic branching programs with a logarithmic repetition and the first separation of syntactic non-deterministic branching programs with a logarithmic repetition from small monotone CNFs.
Achievable Rates for Gaussian Degraded Relay Channels with Non-Vanishing Error Probabilities
Venue: arXiv cs.IT 2016
Year: 2016

This paper revisits the Gaussian degraded relay channel, where the link that carries information from the source to the destination is a physically degraded version of the link that carries information from the source to the relay. The source and the relay are subject to expected power constraints. The $\varepsilon$-capacity of the channel is characterized and it is strictly larger than the capacity for $\varepsilon>0$, which implies that the channel does not possess the strong converse property. The proof of the achievability part is based on several key ideas: block Markov coding which is used in the classical decode-forward strategy, power control for Gaussian channels under expected power constraints, and a careful scaling between the block size and the total number of block uses. The converse part is proved by first establishing two non-asymptotic lower bounds on the error probability, which are derived from the type-II errors of some binary hypothesis tests. Subsequently, each lower bound is simplified by conditioning on an event related to the power of some linear combination of the codewords transmitted by the source and the relay. Lower and upper bounds on the second-order term of the optimal coding rate in terms of blocklength and error probability are also obtained.
Fast $(1+ε)$-approximation of the Löwner extremal matrices of high-dimensional symmetric matrices
Venue: arXiv cs.CG 2016
Year: 2016

Matrix data sets are common nowadays like in biomedical imaging where the Diffusion Tensor Magnetic Resonance Imaging (DT-MRI) modality produces data sets of 3D symmetric positive definite matrices anchored at voxel positions capturing the anisotropic diffusion properties of water molecules in biological tissues. The space of symmetric matrices can be partially ordered using the Löwner ordering, and computing extremal matrices dominating a given set of matrices is a basic primitive used in matrix-valued signal processing. In this letter, we design a fast and easy-to-implement iterative algorithm to approximate arbitrarily finely these extremal matrices. Finally, we discuss on extensions to matrix clustering.
A Synthetic MIMO PLC Channel Model
Venue: arXiv cs.IT 2016
Year: 2016

The huge and increasing demand of data connectivity motivates the development of new and effective power line communication (PLC) channel models, which are able to faithfully describe a real communication scenario. This is of fundamental importance since a good model represents a quick evaluation tool for new standards or devices, allowing a considerable saving in time and costs. The aim of this paper is to discuss a novel top-down MIMO PLC synthetic channel model, able to numerically emulate a real PLC environment. First, the most common channel modeling strategies are briefly described, highlighting strengths and weaknesses. Afterwards, the basic model approach is described considering the SISO scenario. The implementation strategy is then extended to the MIMO case. The validity of the proposed model is proved making a comparison between the simulated channels and channels obtained with measurements in terms of both performance and statistical metrics. The focus is on the broadband frequency spectrum.
Reversible k-valued logic circuits are finitely generated for odd k
Venue: arXiv cs.ET 2016
Year: 2016

In his 2003 paper "Towards an algebraic theory of Boolean circuits", Lafont notes that the class of reversible circuits over a set of k truth values is finitely generated when k is odd. He cites a private communication for the proof. The purpose of this short note is to make the content of that communication available.
Fusing Face and Periocular biometrics using Canonical correlation analysis
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a novel face and periocular biometric fusion at feature level using canonical correlation analysis. Face recognition itself has limitations such as illumination, pose, expression, occlusion etc. Also, periocular biometrics has spectacles, head angle, hair and expression as its limitations. Unimodal biometrics cannot surmount all these limitations. The recognition accuracy can be increased by fusing dual information (face and periocular) from a single source (face image) using canonical correlation analysis (CCA). This work also proposes a new wavelet decomposed local binary pattern (WD-LBP) feature extractor which provides sufficient features for fusion. A detailed analysis on face and periocular biometrics shows that WD-LBP features are more accurate and faster than local binary pattern (LBP) and gabor wavelet. The experimental results using Muct face database reveals that the proposed multimodal biometrics performs better than the unimodal biometrics.
Face Image Analysis using AAM, Gabor, LBP and WD features for Gender, Age, Expression and Ethnicity Classification
Venue: arXiv cs.CV 2016
Year: 2016

The growth in electronic transactions and human machine interactions rely on the information such as gender, age, expression and ethnicity provided by the face image. In order to obtain these information, feature extraction plays a major role. In this paper, retrieval of age, gender, expression and race information from an individual face image is analysed using different feature extraction methods. The performance of four major feature extraction methods such as Active Appearance Model (AAM), Gabor wavelets, Local Binary Pattern (LBP) and Wavelet Decomposition (WD) are analyzed for gender recognition, age estimation, expression recognition and racial recognition in terms of accuracy (recognition rate), time for feature extraction, neural training and time to test an image. Each of this recognition system is compared with four feature extractors on same dataset (training and validation set) to get a better understanding in its performance. Experiments carried out on FG-NET, Cohn-Kanade, PAL face database shows that each method has its own merits and demerits. Hence it is practically impossible to define a method which is best at all circumstances with less computational complexity. Further, a detailed comparison of age estimation and age estimation using gender information is provided along with a solution to overcome aging effect in case of gender recognition. An attempt has been made in obtaining all (i.e. gender, age range, expression and ethnicity) information from a test image in a single go.
A Corpus and Evaluation Framework for Deeper Understanding of Commonsense Stories
Venue: arXiv cs.CL 2016
Year: 2016

Representation and learning of commonsense knowledge is one of the foundational problems in the quest to enable deep language understanding. This issue is particularly challenging for understanding casual and correlational relationships between events. While this topic has received a lot of interest in the NLP community, research has been hindered by the lack of a proper evaluation framework. This paper attempts to address this problem with a new framework for evaluating story understanding and script learning: the 'Story Cloze Test'. This test requires a system to choose the correct ending to a four-sentence story. We created a new corpus of ~50k five-sentence commonsense stories, ROCStories, to enable this evaluation. This corpus is unique in two ways: (1) it captures a rich set of causal and temporal commonsense relations between daily events, and (2) it is a high quality collection of everyday life stories that can also be used for story generation. Experimental evaluation shows that a host of baselines and state-of-the-art models based on shallow language understanding struggle to achieve a high score on the Story Cloze Test. We discuss these implications for script and story learning, and offer suggestions for deeper language understanding.
Distributed Synthesis of State-Dependent Switching Control
Venue: arXiv cs.SY 2016
Year: 2016

We present a correct-by-design method of state-dependent control synthesis for linear discrete-time switching systems. Given an objective region R of the state space, the method builds a capture set S and a control which steers any element of S into R. The method works by iterated backward reachability from R. More precisely, S is given as a parametric extension of R, and the maximum value of the parameter is solved by linear programming. The method can also be used to synthesize a stability control which maintains indefinitely within R all the states starting at R. We explain how the synthesis method can be performed in a distributed manner. The method has been implemented and successfully applied to the synthesis of a distributed control of a concrete floor heating system with 11 rooms and 2^11 = 2048 switching modes.
The shape of health: A comparison of five alternative ways of visualizing personal health and wellbeing
Venue: arXiv cs.HC 2016
Year: 2016

The combination of clinical and personal health and wellbeing data can tell us much about our behaviors, risks and overall status. The way this data is visualized may affect our understanding of our own health. To study this effect, we conducted a small experiment with 30 participants in which we presented a holistic overview of the health and wellbeing of two modeled individuals, one of them with metabolic syndrome. We used an insight-based methodology to assess the effectiveness of the visualizations. The results show that adequate visualization of holistic health data helps users without medical background to better understand the overall health situation and possible health risks related to lifestyles. Furthermore, we found that the application of insight-based methodology in the health and wellbeing domain remains unexplored and additional research and methodology development are needed.
Clustering Via Crowdsourcing
Venue: arXiv cs.DS 2016
Year: 2016

In recent years, crowdsourcing, aka human aided computation has emerged as an effective platform for solving problems that are considered complex for machines alone. Using human is time-consuming and costly due to monetary compensations. Therefore, a crowd based algorithm must judiciously use any information computed through an automated process, and ask minimum number of questions to the crowd adaptively. One such problem which has received significant attention is {\em entity resolution}. Formally, we are given a graph $G=(V,E)$ with unknown edge set $E$ where $G$ is a union of $k$ (again unknown, but typically large $O(n^α)$, for $α>0$) disjoint cliques $G_i(V_i, E_i)$, $i =1, \dots, k$. The goal is to retrieve the sets $V_i$s by making minimum number of pair-wise queries $V \times V\to\{\pm1\}$ to an oracle (the crowd). When the answer to each query is correct, e.g. via resampling, then this reduces to finding connected components in a graph. On the other hand, when crowd answers may be incorrect, it corresponds to clustering over minimum number of noisy inputs. Even, with perfect answers, a simple lower and upper bound of $Θ(nk)$ on query complexity can be shown. A major contribution of this paper is to reduce the query complexity to linear or even sublinear in $n$ when mild side information is provided by a machine, and even in presence of crowd errors which are not correctable via resampling. We develop new information theoretic lower bounds on the query complexity of clustering with side information and errors, and our upper bounds closely match with them. Our algorithms are naturally parallelizable, and also give near-optimal bounds on the number of adaptive rounds required to match the query complexity.
Analysis of Temporal Features for Interaction Quality Estimation
Venue: arXiv cs.HC 2016
Year: 2016

Many different approaches for estimating the Interaction Quality (IQ) of Spoken Dialogue Systems have been investigated. While dialogues clearly have a sequential nature, statistical classification approaches designed for sequential problems do not seem to work better on automatic IQ estimation than static approaches, i.e., regarding each turn as being independent of the corresponding dialogue. Hence, we analyse this effect by investigating the subset of temporal features used as input for statistical classification of IQ. We extend the set of temporal features to contain the system and the user view. We determine the contribution of each feature sub-group showing that temporal features contribute most to the classification performance. Furthermore, for the feature sub-group modeling the temporal effects with a window, we modify the window size increasing the overall performance significantly by +15.69%.
MPP3D: Multi-Precision Pointing using the 3rd Dimension
Venue: arXiv cs.HC 2016
Year: 2016

Distant pointing is still not efficient, accurate or flexible enough for many applications, although many researchers have focused on it. To improve upon distant pointing, we propose MPP3D, which is especially suitable for high-resolution displays. MPP3D uses two dimensions of hand positioning to move a pointer, and it also uses the third dimension to adjust the precision of the movement. Based on the idea of MPP3D, we propose four techniques which combine two ways of mapping and two techniques for precision adjustment. We further provide three types of mapping scheme and visual feedback for each technique. The potential of the proposed techniques was investigated through experimentation. The results show that these techniques were competent for usual computer operations with a cursor, and the adjustment for pointing precision was beneficial for both pointing efficiency and accuracy.
Sentence Level Recurrent Topic Model: Letting Topics Speak for Themselves
Venue: arXiv cs.LG 2016
Year: 2016

We propose Sentence Level Recurrent Topic Model (SLRTM), a new topic model that assumes the generation of each word within a sentence to depend on both the topic of the sentence and the whole history of its preceding words in the sentence. Different from conventional topic models that largely ignore the sequential order of words or their topic coherence, SLRTM gives full characterization to them by using a Recurrent Neural Networks (RNN) based framework. Experimental results have shown that SLRTM outperforms several strong baselines on various tasks. Furthermore, SLRTM can automatically generate sentences given a topic (i.e., topics to sentences), which is a key technology for real world applications such as personalized short text conversation.
A MultiPath Network for Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

The recent COCO object detection dataset presents several new challenges for object detection. In particular, it contains objects at a broad range of scales, less prototypical images, and requires more precise localization. To address these challenges, we test three modifications to the standard Fast R-CNN object detector: (1) skip connections that give the detector access to features at multiple network layers, (2) a foveal structure to exploit object context at multiple object resolutions, and (3) an integral loss function and corresponding network adjustment that improve localization. The result of these modifications is that information can flow along multiple paths in our network, including through features from multiple network layers and from multiple object views. We refer to our modified classifier as a "MultiPath" network. We couple our MultiPath network with DeepMask object proposals, which are well suited for localization and small objects, and adapt our pipeline to predict segmentation masks in addition to bounding boxes. The combined system improves results over the baseline Fast R-CNN detector with Selective Search by 66% overall and by 4x on small objects. It placed second in both the COCO 2015 detection and segmentation challenges.
Aware: Controlling App Access to I/O Devices on Mobile Platforms
Venue: arXiv cs.OS 2016
Year: 2016

Smartphones' cameras, microphones, and device displays enable users to capture and view memorable moments of their lives. However, adversaries can trick users into authorizing malicious apps that exploit weaknesses in current mobile platforms to misuse such on-board I/O devices to stealthily capture photos, videos, and screen content without the users' consent. Contemporary mobile operating systems fail to prevent such misuse of I/O devices by authorized apps due to lack of binding between users' interactions and accesses to I/O devices performed by these apps. In this paper, we propose Aware, a security framework for authorizing app requests to perform operations using I/O devices, which binds app requests with user intentions to make all uses of certain I/O devices explicit. We evaluate our defense mechanisms through laboratory-based experimentation and a user study, involving 74 human subjects, whose ability to identify undesired operations targeting I/O devices increased significantly. Without Aware, only 18% of the participants were able to identify attacks from tested RAT apps. Aware systematically blocks all the attacks in absence of user consent and supports users in identifying 82% of social-engineering attacks tested to hijack approved requests, including some more sophisticated forms of social engineering not yet present in available RATs. Aware introduces only 4.79% maximum performance overhead over operations targeting I/O devices. Aware shows that a combination of system defenses and user interface can significantly strengthen defenses for controlling the use of on-board I/O devices.
Adaptive Load-Aware Sampling for Network Monitoring on Multicore Commodity Hardware
Venue: arXiv cs.NI 2016
Year: 2016

Many current traffic monitoring systems employ deep packet inspection (DPI) in order to analyze network traffic. These systems include intrusion detection systems, software for network traffic accounting, traffic classification, or systems for monitoring service-level agreements. Traffic volumes and link speeds of current enterprise and ISP networks transform the process of inspecting traffic payload into a challenging task. In this paper we propose a novel adaptive sampling algorithm that selects the maximum number of packets from the network that the DPI system is able to consume. Our algorithm adapts its sampling rate according to the network traffic currently observed, and the number of packets that a monitoring application is able to process. It can be used in conjunction with current multicore-aware network traffic analysis setups, which allow for exploiting current multi-core hardware. We show the applicability of our algorithm with live-tests on a heavily used 10G link with real network monitoring tools.