OpenRaiser/Intern-Atlas huggingface dataset:
Improving Semantic Embedding Consistency by Metric Learning for Zero-Shot Classification
Venue: arXiv cs.CV 2016
Year: 2016

This paper addresses the task of zero-shot image classification. The key contribution of the proposed approach is to control the semantic embedding of images -- one of the main ingredients of zero-shot learning -- by formulating it as a metric learning problem. The optimized empirical criterion associates two types of sub-task constraints: metric discriminating capacity and accurate attribute prediction. This results in a novel expression of zero-shot learning not requiring the notion of class in the training phase: only pairs of image/attributes, augmented with a consistency indicator, are given as ground truth. At test time, the learned model can predict the consistency of a test image with a given set of attributes , allowing flexible ways to produce recognition inferences. Despite its simplicity, the proposed approach gives state-of-the-art results on four challenging datasets used for zero-shot recognition evaluation.
Automatically Reinforcing a Game AI
Venue: arXiv cs.AI 2016
Year: 2016

A recent research trend in Artificial Intelligence (AI) is the combination of several programs into one single, stronger, program; this is termed portfolio methods. We here investigate the application of such methods to Game Playing Programs (GPPs). In addition, we consider the case in which only one GPP is available - by decomposing this single GPP into several ones through the use of parameters or even simply random seeds. These portfolio methods are trained in a learning phase. We propose two different offline approaches. The simplest one, BestArm, is a straightforward optimization of seeds or parame- ters; it performs quite well against the original GPP, but performs poorly against an opponent which repeats games and learns. The second one, namely Nash-portfolio, performs similarly in a "one game" test, and is much more robust against an opponent who learns. We also propose an online learning portfolio, which tests several of the GPP repeatedly and progressively switches to the best one - using a bandit algorithm.
MLPnP - A Real-Time Maximum Likelihood Solution to the Perspective-n-Point Problem
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a statistically optimal solution to the Perspective-n-Point (PnP) problem is presented. Many solutions to the PnP problem are geometrically optimal, but do not consider the uncertainties of the observations. In addition, it would be desirable to have an internal estimation of the accuracy of the estimated rotation and translation parameters of the camera pose. Thus, we propose a novel maximum likelihood solution to the PnP problem, that incorporates image observation uncertainties and remains real-time capable at the same time. Further, the presented method is general, as is works with 3D direction vectors instead of 2D image points and is thus able to cope with arbitrary central camera models. This is achieved by projecting (and thus reducing) the covariance matrices of the observations to the corresponding vector tangent space.
The Kinematic Image of RR, PR, and RP Dyads
Venue: arXiv cs.RO 2016
Year: 2016

We provide necessary and sufficient conditions for admissible transformations in the projectivised dual quaternion model of rigid body displacements and we characterise constraint varieties of dyads with revolute and prismatic joints in this model. Projective transformations induced by coordinate changes in moving and/or fixed frame fix the quadrics of a pencil and preserve the two families of rulings of an exceptional three-dimensional quadric. The constraint variety of a dyad with two revolute joints is a regular ruled quadric in a three-space that contains a "null quadrilateral". If a revolute joint is replaced by a prismatic joint, this quadrilateral collapses into a pair of conjugate complex null lines and a real line but these properties are not sufficient to characterise such dyads. We provide a complete characterisation by introducing a new invariant, the "fiber projectivity", and we present examples that demonstrate its potential to explain hitherto not sufficiently well understood phenomena.
N-opcode Analysis for Android Malware Classification and Categorization
Venue: arXiv cs.CR 2016
Year: 2016

Malware detection is a growing problem particularly on the Android mobile platform due to its increasing popularity and accessibility to numerous third party app markets. This has also been made worse by the increasingly sophisticated detection avoidance techniques employed by emerging malware families. This calls for more effective techniques for detection and classification of Android malware. Hence, in this paper we present an n-opcode analysis based approach that utilizes machine learning to classify and categorize Android malware. This approach enables automated feature discovery that eliminates the need for applying expert or domain knowledge to define the needed features. Our experiments on 2520 samples that were performed using up to 10-gram opcode features showed that an f-measure of 98% is achievable using this approach.
Suffix arrays with a twist
Venue: arXiv cs.DS 2016
Year: 2016

The suffix array is a classic full-text index, combining effectiveness with simplicity. We discuss three approaches aiming to improve its efficiency even more: changes to the navigation, data layout and adding extra data. In short, we show that $(i)$ how we search for the right interval boundary impacts significantly the overall search speed, $(ii)$ a B-tree data layout easily wins over the standard one, $(iii)$ the well-known idea of a lookup table for the prefixes of the suffixes can be refined with using compression, $(iv)$ caching prefixes of the suffixes in a helper array can pose a(nother) practical space-time tradeoff.
Calorie Counter: RGB-Depth Visual Estimation of Energy Expenditure at Home
Venue: arXiv cs.CV 2016
Year: 2016

We present a new framework for vision-based estimation of calorific expenditure from RGB-D data - the first that is validated on physical gas exchange measurements and applied to daily living scenarios. Deriving a person's energy expenditure from sensors is an important tool in tracking physical activity levels for health and lifestyle monitoring. Most existing methods use metabolic lookup tables (METs) for a manual estimate or systems with inertial sensors which ultimately require users to wear devices. In contrast, the proposed pose-invariant and individual-independent vision framework allows for a remote estimation of calorific expenditure. We introduce, and evaluate our approach on, a new dataset called SPHERE-calorie, for which visual estimates can be compared against simultaneously obtained, indirect calorimetry measures based on gas exchange. % based on per breath gas exchange. We conclude from our experiments that the proposed vision pipeline is suitable for home monitoring in a controlled environment, with calorific expenditure estimates above accuracy levels of commonly used manual estimations via METs. With the dataset released, our work establishes a baseline for future research for this little-explored area of computer vision.
Analysis of a Frequency-Hopping Millimeter-Wave Cellular Uplink
Venue: arXiv cs.IT 2016
Year: 2016

Fifth-generation (5G) cellular networks are expected to exhibit at least three primary physical-layer differences relative to fourth-generation ones: millimeter-wave propagation, massive antenna arrays, and densification of base stations. As in fourth-generation systems, such as LTE, 5G systems are likely to continue to use single-carrier frequency division multiple-access (SC-FDMA) on the uplink due to its advantageous peak-to-average power ratio. Moreover, 5G systems are likely to use frequency hopping on the uplink to help randomize interference and provide diversity against frequency-selective fading. In this paper, the implications of these and other physical-layer features on uplink performance are assessed using a novel millimeter-wave propagation model featuring distance-dependent parameters that characterize the path-loss, shadowing, and fading. The analysis proceeds by first fixing the location of the mobile devices and finding the performance conditioned on the topology. The spatially averaged performance is then found by averaging with respect to the location of the mobile devices. The analysis allows for the use of actual base-station topologies and the propagation model can leverage empirical millimeter-wave measurements. The benefits of base-station densification, highly directional sectorization, frequency hopping, a large available bandwidth, and a high code rate are illustrated. The minor importance of fractional power control is shown.
arXiv@25: Key findings of a user survey
Venue: arXiv cs.DL 2016
Year: 2016

As part of its 25th anniversary vision-setting process, the arXiv team at Cornell University Library conducted a user survey in April 2016 to seek input from the global user community about arXiv's current services and future directions. We were heartened to receive 36,000 responses from 127 countries, representing arXiv's diverse, global community. The prevailing message is that users are happy with the service as it currently stands, with 95 percent of survey respondents indicating they are very satisfied or satisfied with arXiv. Furthermore, 72 percent of respondents indicated that arXiv should continue to focus on its main purpose, which is to quickly make available scientific papers, and this will be enough to sustain the value of arXiv in the future. This theme was pervasively reflected in the open text comments; a significant number of respondents suggested remaining focused on the core mission and enabling arXiv's partners and related service providers to continue to build new services and innovations on top of arXiv.
The Sum Rate of Vector Gaussian Multiple Description Coding with Tree-Structured Covariance Distortion Constraints
Venue: arXiv cs.IT 2016
Year: 2016

A single-letter lower bound on the sum rate of multiple description coding with tree-structured distortion constraints is established by generalizing Ozarow's celebrated converse argument through the introduction of auxiliary random variables that form a Markov tree. For the quadratic vector Gaussian case, this lower bound is shown to be achievable by an extended version of the El Gamal-Cover scheme, yielding a complete sum-rate characterization.
Automata for Specifying and Orchestrating Service Contracts
Venue: arXiv cs.LO 2016
Year: 2016

An approach to the formal description of service contracts is presented in terms of automata. We focus on the basic property of guaranteeing that in the multi-party composition of principals each of them gets his requests satisfied, so that the overall composition reaches its goal. Depending on whether requests are satisfied synchronously or asynchronously, we construct an orchestrator that at static time either yields composed services enjoying the required properties or detects the principals responsible for possible violations. To do that in the asynchronous case we resort to Linear Programming techniques. We also relate our automata with two logically based methods for specifying contracts.
On Stable Throughput of Cognitive Radio Networks With Cooperating Secondary Users
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study cooperative cognitive radio networks consisting of a primary user and multiple secondary users. Secondary users transmit only when primary user is sensed as silent and may interfere with primary transmission due to imperfect sensing. When primary activity is sensed correctly, secondary users cooperate with primary user by assisting retransmission of failed packets of primary user. We analyze packet throughput of primary and secondary users for three variations of proposed cooperation method. Signal flow graph (SFG) based approach is employed to obtain closed form expressions of packet throughput. The analysis is done for two cases; individual sensing and cooperative sensing. Further, we characterize optimal transmission probability of secondary users that maximizes individual secondary packet throughput keeping all queues in the system stable. Results present a comparison of throughput performance of proposed cooperation methods under different scenarios and show their benefits for both primary as well as secondary user throughput.
Randomised Algorithm for Feature Selection and Classification
Venue: arXiv cs.LG 2016
Year: 2016

We here introduce a novel classification approach adopted from the nonlinear model identification framework, which jointly addresses the feature selection and classifier design tasks. The classifier is constructed as a polynomial expansion of the original attributes and a model structure selection process is applied to find the relevant terms of the model. The selection method progressively refines a probability distribution defined on the model structure space, by extracting sample models from the current distribution and using the aggregate information obtained from the evaluation of the population of models to reinforce the probability of extracting the most important terms. To reduce the initial search space, distance correlation filtering can be applied as a preprocessing technique. The proposed method is evaluated and compared to other well-known feature selection and classification methods on standard benchmark classification problems. The results show the effectiveness of the proposed method with respect to competitor methods both in terms of classification accuracy and model complexity. The obtained models have a simple structure, easily amenable to interpretation and analysis.
On the security of the Blockchain Bix Protocol and Certificates
Venue: arXiv cs.CR 2016
Year: 2016

The BIX protocol is a blockchain-based protocol that allows distribution of certificates linking a subject with his public key, hence providing a service similar to that of a PKI but without the need of a CA. In this paper we analyze the security of the BIX protocol in a formal way, in four steps. First, we identify formal security assumptions which are well-suited to this protocol. Second, we present some attack scenarios against the BIX protocol. Third, we provide a formal security proof that some of these attacks are not feasible under our previously established assumptions. Finally, we show how another attack may be carried on.
Overlay Secondary Spectrum Sharing with Independent Re-attempts in Cognitive Radios
Venue: arXiv cs.PF 2016
Year: 2016

Opportunistic spectrum access (OSA) is a promising reform paradigm envisioned to address the issue of spectrum scarcity in cognitive radio networks (CRNs). While current models consider various aspects of the OSA scheme, the impact of retrial phenomenon in multi-channel CRNs has not yet been analyzed. In this work, we present a continuous-time Markov chain (CTMC) model in which the blocked/preempted secondary users (SUs) enter a finite retrial group (or orbit) and re-attempt independently for service in an exponentially distributed random manner. Taking into account the inherent retrial tendency of SUs, we numerically assess the performance of the proposed scheme in terms of dropping probability and throughput of SUs.
Economics of Resilient Cloud Services
Venue: arXiv cs.CR 2016
Year: 2016

Computer systems today must meet and maintain service availability, performance, and security requirements. Each of these demands requires redundancy and some form of isolation. When service requirements are implemented separately, the system architecture cannot easily share common components of redundancy and isolation. We will present these service traits collectively as cyber resilience with a system called Self Cleansing Intrusion Tolerance or SCIT. Further, we will demonstrate that SCIT provides an effective resilient cloud implementation making cost effective utilization of cloud excess capacity and economies of scale. Lastly, we will introduce the notion of serverless applications utilizing AWS Lambda and how a stateless architecture can drastically reduce operational costs by utilizing cloud function services.
The Study of Transient Faults Propagation in Multithread Applications
Venue: arXiv cs.AR 2016
Year: 2016

Whereas contemporary Error Correcting Codes (ECC) designs occupy a significant fraction of total die area in chip-multiprocessors (CMPs), approaches to deal with the vulnerability increase of CMP architecture against Single Event Upsets (SEUs) and Multi-Bit Upsets (MBUs) are sought. In this paper, we focus on reliability assessment of multithreaded applications running on CMPs to propose an adaptive application-relevant architecture design to accommodate the impact of both SEUs and MBUs in the entire CMP architecture. This work concentrates on leveraging the intrinsic soft-error-immunity feature of Spin-Transfer Torque RAM (STT-RAM) as an alternative for SRAM-based storage and operation components. We target a specific portion of working set for reallocation to improve the reliability level of the CMP architecture design. A selected portion of instructions in multithreaded program which experience high rate of referencing with the lowest memory modification are ideal candidate to be stored and executed in STT-RAM based components. We argue about why we cannot use STT-RAM for the global storage and operation counterparts and describe the obtained resiliency compared to the baseline setup. In addition, a detail study of the impact of SEUs and MBUs on multithreaded programs will be presented in the Appendix.
Measuring and Modeling Bipartite Graphs with Community Structure
Venue: arXiv cs.SI 2016
Year: 2016

Network science is a powerful tool for analyzing complex systems in fields ranging from sociology to engineering to biology. This paper is focused on generative models of large-scale bipartite graphs, also known as two-way graphs or two-mode networks. We propose two generative models that can be easily tuned to reproduce the characteristics of real-world networks, not just qualitatively, but quantitatively. The characteristics we consider are the degree distributions and the metamorphosis coefficient. The metamorphosis coefficient, a bipartite analogue of the clustering coefficient, is the proportion of length-three paths that participate in length-four cycles. Having a high metamorphosis coefficient is a necessary condition for close-knit community structure. We define edge, node, and degreewise metamorphosis coefficients, enabling a more detailed understanding of the bipartite connectivity that is not explained by degree distribution alone. Our first model, bipartite Chung-Lu (CL), is able to reproduce real-world degree distributions, and our second model, bipartite block two-level Erdös-Rényi (BTER), reproduces both the degree distributions as well as the degreewise metamorphosis coefficients. We demonstrate the effectiveness of these models on several real-world data sets.
Semi-supervised evidential label propagation algorithm for graph data
Venue: arXiv cs.SI 2016
Year: 2016

In the task of community detection, there often exists some useful prior information. In this paper, a Semi-supervised clustering approach using a new Evidential Label Propagation strategy (SELP) is proposed to incorporate the domain knowledge into the community detection model. The main advantage of SELP is that it can take limited supervised knowledge to guide the detection process. The prior information of community labels is expressed in the form of mass functions initially. Then a new evidential label propagation rule is adopted to propagate the labels from labeled data to unlabeled ones. The outliers can be identified to be in a special class. The experimental results demonstrate the effectiveness of SELP.
Two-Level Spatial Multiplexing using Hybrid Beamforming Antenna Arrays for mmWave Communications
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we consider a two-level hierarchical MIMO antenna array system, where each antenna of the upper level is made up of a subarray on the lower one. The concept of spatial multiplexing is applied twice in this situation: Firstly, the spatial multiplexing of a Line-of-Sight (LoS) MIMO system is exploited. It is based on appropriate (sub-)array distances and achieves multiplexing gain due to phase differences among the signals at the receive (sub-)arrays. Secondly, one or more additional reflected paths of different angles (separated from the LoS path by different spatial beams at the subarrays) are used to exploit spatial multiplexing between paths. By exploiting the above two multiplexing kinds simultaneously, a high dimensional system with maximum spatial multiplexing is proposed by jointly using 'phase differences' within paths and 'angular differences' between paths. The system includes an advanced hybrid beamforming architecture with large subarray separation, which could occur in millimeter wave backhaul scenarios. The possible gains of the system w.r.t. a pure LOS MIMO system are illustrated by evaluating the capacities with total transmit power constraints.
Exponentially fast convergence to (strict) equilibrium via hedging
Venue: arXiv cs.GT 2016
Year: 2016

Motivated by applications to data networks where fast convergence is essential, we analyze the problem of learning in generic N-person games that admit a Nash equilibrium in pure strategies. Specifically, we consider a scenario where players interact repeatedly and try to learn from past experience by small adjustments based on local - and possibly imperfect - payoff information. For concreteness, we focus on the so-called "hedge" variant of the exponential weights algorithm where players select an action with probability proportional to the exponential of the action's cumulative payoff over time. When players have perfect information on their mixed payoffs, the algorithm converges locally to a strict equilibrium and the rate of convergence is exponentially fast - of the order of $\mathcal{O}(\exp(-a\sum_{j=1}^{t}γ_{j}))$ where $a>0$ is a constant and $γ_{j}$ is the algorithm's step-size. In the presence of uncertainty, convergence requires a more conservative step-size policy, but with high probability, the algorithm remains locally convergent and achieves an exponential convergence rate.
A Gb/s Parallel Block-based Viterbi Decoder for Convolutional Codes on GPU
Venue: arXiv cs.DC 2016
Year: 2016

In this paper, we propose a parallel block-based Viterbi decoder (PBVD) on the graphic processing unit (GPU) platform for the decoding of convolutional codes. The decoding procedure is simplified and parallelized, and the characteristic of the trellis is exploited to reduce the metric computation. Based on the compute unified device architecture (CUDA), two kernels with different parallelism are designed to map two decoding phases. Moreover, the optimal design of data structures for several kinds of intermediate information are presented, to improve the efficiency of internal memory transactions. Experimental results demonstrate that the proposed decoder achieves high throughput of 598Mbps on NVIDIA GTX580 and 1802Mbps on GTX980 for the 64-state convolutional code, which are 1.5 times speedup compared to the existing fastest works on GPUs.