OpenRaiser/Intern-Atlas huggingface dataset:
Breaking Through the Full-Duplex Wi-Fi Capacity Gain
Venue: arXiv cs.NI 2016
Year: 2016

In this work we identify a seminal design guideline that prevents current Full-Duplex (FD) MAC protocols to scale the FD capacity gain (i.e. 2x the half-duplex throughput) in single-cell Wi-Fi networks. Under such guideline (referred to as 1:1), a MAC protocol attempts to initiate up to two simultaneous transmissions in the FD bandwidth. Since in single-cell Wi-Fi networks MAC performance is bounded by the PHY layer capacity, this implies gains strictly less than 2x over half-duplex at the MAC layer. To face this limitation, we argue for the 1:N design guideline. Under 1:N, FD MAC protocols 'see' the FD bandwidth through N>1 orthogonal narrow-channel PHY layers. Based on theoretical results and software defined radio experiments, we show the 1:N design can leverage the Wi-Fi capacity gain more than 2x at and below the MAC layer. This translates the denser modulation scheme incurred by channel narrowing and the increase in the spatial reuse offer enabled by channel orthogonality. With these results, we believe our design guideline can inspire a new generation of Wi-Fi MAC protocols that fully embody and scale the FD capacity gain.
Towards ontology driven learning of visual concept detectors
Venue: arXiv cs.IR 2016
Year: 2016

The maturity of deep learning techniques has led in recent years to a breakthrough in object recognition in visual media. While for some specific benchmarks, neural techniques seem to match if not outperform human judgement, challenges are still open for detecting arbitrary concepts in arbitrary videos. In this paper, we propose a system that combines neural techniques, a large scale visual concepts ontology, and an active learning loop, to provide on the fly model learning of arbitrary concepts. We give an overview of the system as a whole, and focus on the central role of the ontology for guiding and bootstrapping the learning of new concepts, improving the recall of concept detection, and, on the user end, providing semantic search on a library of annotated videos.
Technical Report: Directed Controller Synthesis of Discrete Event Systems
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents a Directed Controller Synthesis (DCS) technique for discrete event systems. The DCS method explores the solution space for reactive controllers guided by a domain-independent heuristic. The heuristic is derived from an efficient abstraction of the environment based on the componentized way in which complex environments are described. Then by building the composition of the components on-the-fly DCS obtains a solution by exploring a reduced portion of the state space. This work focuses on untimed discrete event systems with safety and co-safety (i.e. reachability) goals. An evaluation for the technique is presented comparing it to other well-known approaches to controller synthesis (based on symbolic representation and compositional analyses).
Nonnegative tensor factorization with frequency modulation cues for blind audio source separation
Venue: arXiv cs.SD 2016
Year: 2016

We present Vibrato Nonnegative Tensor Factorization, an algorithm for single-channel unsupervised audio source separation with an application to separating instrumental or vocal sources with nonstationary pitch from music recordings. Our approach extends Nonnegative Matrix Factorization for audio modeling by including local estimates of frequency modulation as cues in the separation. This permits the modeling and unsupervised separation of vibrato or glissando musical sources, which is not possible with the basic matrix factorization formulation. The algorithm factorizes a sparse nonnegative tensor comprising the audio spectrogram and local frequency-slope-to-frequency ratios, which are estimated at each time-frequency bin using the Distributed Derivative Method. The use of local frequency modulations as separation cues is motivated by the principle of common fate partial grouping from Auditory Scene Analysis, which hypothesizes that each latent source in a mixture is characterized perceptually by coherent frequency and amplitude modulations shared by its component partials. We derive multiplicative factor updates by Minorization-Maximization, which guarantees convergence to a local optimum by iteration. We then compare our method to the baseline on two separation tasks: one considers synthetic vibrato notes, while the other considers vibrato string instrument recordings.
Quantifying the probable approximation error of probabilistic inference programs
Venue: arXiv cs.AI 2016
Year: 2016

This paper introduces a new technique for quantifying the approximation error of a broad class of probabilistic inference programs, including ones based on both variational and Monte Carlo approaches. The key idea is to derive a subjective bound on the symmetrized KL divergence between the distribution achieved by an approximate inference program and its true target distribution. The bound's validity (and subjectivity) rests on the accuracy of two auxiliary probabilistic programs: (i) a "reference" inference program that defines a gold standard of accuracy and (ii) a "meta-inference" program that answers the question "what internal random choices did the original approximate inference program probably make given that it produced a particular result?" The paper includes empirical results on inference problems drawn from linear regression, Dirichlet process mixture modeling, HMMs, and Bayesian networks. The experiments show that the technique is robust to the quality of the reference inference program and that it can detect implementation bugs that are not apparent from predictive performance.
Boda-RTC: Productive Generation of Portable, Efficient Code for Convolutional Neural Networks on Mobile Computing Platforms
Venue: arXiv cs.DC 2016
Year: 2016

The popularity of neural networks (NNs) spans academia, industry, and popular culture. In particular, convolutional neural networks (CNNs) have been applied to many image based machine learning tasks and have yielded strong results. The availability of hardware/software systems for efficient training and deployment of large and/or deep CNN models has been, and continues to be, an important consideration for the field. Early systems for NN computation focused on leveraging existing dense linear algebra techniques and libraries. Current approaches use low-level machine specific programming and/or closed-source, purpose-built vendor libraries. In this work, we present an open source system that, compared to existing approaches, achieves competitive computational speed while achieving higher portability. We achieve this by targeting the vendor-neutral OpenCL platform using a code-generation approach. We argue that our approach allows for both: (1) the rapid development of new computational kernels for existing hardware targets, and (2) the rapid tuning of existing computational kernels for new hardware targets. Results are presented for a case study of targeting the Qualcomm Snapdragon 820 mobile computing platform for CNN deployment.
It's Time: OS Mechanisms for Enforcing Asymmetric Temporal Integrity
Venue: arXiv cs.OS 2016
Year: 2016

Mixed-criticality systems combine real-time components of different levels of criticality, i.e. severity of failure, on the same processor, in order to obtain good resource utilisation. They must guarantee deadlines of highly-critical tasks at the expense of lower-criticality ones in the case of overload. Present operating systems provide inadequate support for this kind of system, which is of growing importance in avionics and other verticals. We present an approach that provides the required asymmetric integrity and its implementation in the high-assurance seL4 microkernel.
Hardness of the Pricing Problem for Chains in Barter Exchanges
Venue: arXiv cs.DS 2016
Year: 2016

Kidney exchange is a barter market where patients trade willing but medically incompatible donors. These trades occur via cycles, where each patient-donor pair both gives and receives a kidney, and via chains, which begin with an altruistic donor who does not require a kidney in return. For logistical reasons, the maximum length of a cycle is typically limited to a small constant, while chains can be much longer. Given a compatibility graph of patient-donor pairs, altruists, and feasible potential transplants between them, finding even a maximum-cardinality set of vertex-disjoint cycles and chains is NP-hard. There has been much work on developing provably optimal solvers that are efficient in practice. One of the leading techniques has been branch and price, where column generation is used to incrementally bring cycles and chains into the optimization model on an as-needed basis. In particular, only positive-price columns need to be brought into the model. We prove that finding a positive-price chain is NP-complete. This shows incorrectness of two leading branch-and-price solvers that suggested polynomial-time chain pricing algorithms.
Contextual Bandits with Latent Confounders: An NMF Approach
Venue: arXiv cs.LG 2016
Year: 2016

Motivated by online recommendation and advertising systems, we consider a causal model for stochastic contextual bandits with a latent low-dimensional confounder. In our model, there are $L$ observed contexts and $K$ arms of the bandit. The observed context influences the reward obtained through a latent confounder variable with cardinality $m$ ($m \ll L,K$). The arm choice and the latent confounder causally determines the reward while the observed context is correlated with the confounder. Under this model, the $L \times K$ mean reward matrix $\mathbf{U}$ (for each context in $[L]$ and each arm in $[K]$) factorizes into non-negative factors $\mathbf{A}$ ($L \times m$) and $\mathbf{W}$ ($m \times K$). This insight enables us to propose an $ε$-greedy NMF-Bandit algorithm that designs a sequence of interventions (selecting specific arms), that achieves a balance between learning this low-dimensional structure and selecting the best arm to minimize regret. Our algorithm achieves a regret of $\mathcal{O}\left(L\mathrm{poly}(m, \log K) \log T \right)$ at time $T$, as compared to $\mathcal{O}(LK\log T)$ for conventional contextual bandits, assuming a constant gap between the best arm and the rest for each context. These guarantees are obtained under mild sufficiency conditions on the factors that are weaker versions of the well-known Statistical RIP condition. We further propose a class of generative models that satisfy our sufficient conditions, and derive a lower bound of $\mathcal{O}\left(Km\log T\right)$. These are the first regret guarantees for online matrix completion with bandit feedback, when the rank is greater than one. We further compare the performance of our algorithm with the state of the art, on synthetic and real world data-sets.
Parked Cars are Excellent Roadside Units
Venue: arXiv cs.NI 2016
Year: 2016

A comprehensive implementation of the envisioned traffic safety and efficiency applications of the IEEE 802.11p and WAVE standards assume the premise of the use of DSRC technology both as on-board units (OBUs) and as Roadside Units (RSUs). The high cost associated with RSUs, however, has so far prevented massive deployment of RSUs. Finding alternative solutions to this longstanding problem is therefore very important. In this paper, we propose a self-organizing network approach to using parked cars in urban areas as RSUs. This self-organizing network approach enables parked cars to create coverage maps based on received signal strength and make important decisions, such as if and when a parked car should serve as an RSU. Our results show the feasibility and cost-effectiveness of the proposed approach, which is able to provide excellent coverage using only a small fraction of the cars parked in a city.
Automatic tagging using deep convolutional neural networks
Venue: arXiv cs.SD 2016
Year: 2016

We present a content-based automatic music tagging algorithm using fully convolutional neural networks (FCNs). We evaluate different architectures consisting of 2D convolutional layers and subsampling layers only. In the experiments, we measure the AUC-ROC scores of the architectures with different complexities and input types using the MagnaTagATune dataset, where a 4-layer architecture shows state-of-the-art performance with mel-spectrogram input. Furthermore, we evaluated the performances of the architectures with varying the number of layers on a larger dataset (Million Song Dataset), and found that deeper models outperformed the 4-layer architecture. The experiments show that mel-spectrogram is an effective time-frequency representation for automatic tagging and that more complex models benefit from more training data.
Short Communication on QUIST: A Quick Clustering Algorithm
Venue: arXiv cs.LG 2016
Year: 2016

In this short communication we introduce the quick clustering algorithm (QUIST), an efficient hierarchical clustering algorithm based on sorting. QUIST is a poly-logarithmic divisive clustering algorithm that does not assume the number of clusters, and/or the cluster size to be known ahead of time. It is also insensitive to the original ordering of the input.
Temporal Topic Modeling to Assess Associations between News Trends and Infectious Disease Outbreaks
Venue: arXiv cs.SI 2016
Year: 2016

In retrospective assessments, internet news reports have been shown to capture early reports of unknown infectious disease transmission prior to official laboratory confirmation. In general, media interest and reporting peaks and wanes during the course of an outbreak. In this study, we quantify the extent to which media interest during infectious disease outbreaks is indicative of trends of reported incidence. We introduce an approach that uses supervised temporal topic models to transform large corpora of news articles into temporal topic trends. The key advantages of this approach include, applicability to a wide range of diseases, and ability to capture disease dynamics - including seasonality, abrupt peaks and troughs. We evaluated the method using data from multiple infectious disease outbreaks reported in the United States of America (U.S.), China and India. We noted that temporal topic trends extracted from disease-related news reports successfully captured the dynamics of multiple outbreaks such as whooping cough in U.S. (2012), dengue outbreaks in India (2013) and China (2014). Our observations also suggest that efficient modeling of temporal topic trends using time-series regression techniques can estimate disease case counts with increased precision before official reports by health organizations.
On the equivalence between Kolmogorov-Smirnov and ROC curve metrics for binary classification
Venue: arXiv cs.AI 2016
Year: 2016

Binary decisions are very common in artificial intelligence. Applying a threshold on the continuous score gives the human decider the power to control the operating point to separate the two classes. The classifier,s discriminating power is measured along the continuous range of the score by the Area Under the ROC curve (AUC_ROC) in most application fields. Only finances uses the poor single point metric maximum Kolmogorov-Smirnov (KS) distance. This paper proposes the Area Under the KS curve (AUC_KS) for performance assessment and proves AUC_ROC = 0.5 + AUC_KS, as a simpler way to calculate the AUC_ROC. That is even more important for ROC averaging in ensembles of classifiers or n fold cross-validation. The proof is geometrically inspired on rotating all KS curve to make it lie on the top of the ROC chance diagonal. On the practical side, the independent variable on the abscissa on the KS curve simplifies the calculation of the AUC_ROC. On the theoretical side, this research gives insights on probabilistic interpretations of classifiers assessment and integrates the existing body of knowledge of the information theoretical ROC approach with the proposed statistical approach based on the thoroughly known KS distribution.
Model-based Testing of Mobile Systems -- An Empirical Study on QuizUp Android App
Venue: arXiv cs.SE 2016
Year: 2016

We present an empirical study in which model-based testing (MBT) was applied to a mobile system: the Android client of QuizUp, the largest mobile trivia game in the world. The study shows that traditional MBT approaches based on extended finite-state machines can be used to test a mobile app in an effective and efficient way. Non-trivial defects were detected on a deployed system that has millions of users and was already well tested. The duration of the overall testing effort was of three months, including the construction of the models. Maintaining a single behavioral model for the app was key in order to test it in an efficient way.
Monitoring Assumptions in Assume-Guarantee Contracts
Venue: arXiv cs.SE 2016
Year: 2016

Pre-deployment verification of software components with respect to behavioral specifications in the assume-guarantee form does not, in general, guarantee absence of errors at run time. This is because assumptions about the environment cannot be discharged until the environment is fixed. An intuitive approach is to complement pre-deployment verification of guarantees, up to the assumptions, with post-deployment monitoring of environment behavior to check that the assumptions are satisfied at run time. Such a monitor is typically implemented by instrumenting the application code of the component. An additional challenge for the monitoring step is that environment behaviors are typically obtained through an I/O library, which may alter the component's view of the input format. This transformation requires us to introduce a second pre-deployment verification step to ensure that alarms raised by the monitor would indeed correspond to violations of the environment assumptions. In this paper, we describe an approach for constructing monitors and verifying them against the component assumption. We also discuss limitations of instrumentation-based monitoring and potential ways to overcome it.
Randomized Polynomial Time Identity Testing for Noncommutative Circuits
Venue: arXiv cs.CC 2016
Year: 2016

In this paper we show that the black-box polynomial identity testing for noncommutative polynomials $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ of degree $D$ and sparsity $t$, can be done in randomized $\poly(n,\log t,\log D)$ time. As a consequence, if the black-box contains a circuit $C$ of size $s$ computing $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ which has at most $t$ non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in $s$ and $n$ and $\log t$. This makes significant progress on a question that has been open for over ten years. The earlier result by Bogdanov and Wee [BW05], using the classical Amitsur-Levitski theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit. Our algorithm is based on automata-theoretic ideas introduced in [AMS08,AM08]. In those papers, the main idea was to construct deterministic finite automata that isolate a single monomial from the set of nonzero monomials of a polynomial $f$ in $\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$. In the present paper, since we need to deal with exponential degree monomials, we carry out a different kind of monomial isolation using nondeterministic automata.
Kick Motions for the NAO Robot using Dynamic Movement Primitives
Venue: arXiv cs.RO 2016
Year: 2016

In this paper, we present the probably first application of the popular \emph{Dynamic Movement Primitives (DMP)} approach to the domain of soccer-playing humanoid robots. DMPs are known for their ability to imitate previously demonstrated motions as well as to flexibly adapt to unforeseen changes to the desired trajectory with respect to speed and direction. As demonstrated in this paper, this makes them a useful approach for describing kick motions. Furthermore, we present a mathematical motor model that compensates for the NAO robot's motor control delay as well as a novel minor extension to the DMP formulation. The motor model is used in the calculation of the Zero Moment Point (ZMP), which is needed to keep the robot in balance while kicking. All approaches have been evaluated on real NAO robots.
Unified Scalable Equivalent Formulations for Schatten Quasi-Norms
Venue: arXiv cs.IT 2016
Year: 2016

The Schatten quasi-norm can be used to bridge the gap between the nuclear norm and rank function, and is the tighter approximation to matrix rank. However, most existing Schatten quasi-norm minimization (SQNM) algorithms, as well as for nuclear norm minimization, are too slow or even impractical for large-scale problems, due to the SVD or EVD of the whole matrix in each iteration. In this paper, we rigorously prove that for any p, p1, p2>0 satisfying 1/p=1/p1+1/p2, the Schatten-p quasi-norm of any matrix is equivalent to minimizing the product of the Schatten-p1 norm (or quasi-norm) and Schatten-p2 norm (or quasi-norm) of its two factor matrices. Then we present and prove the equivalence relationship between the product formula of the Schatten quasi-norm and its weighted sum formula for the two cases of p1 and p2: p1=p2 and p1\neq p2. In particular, when p>1/2, there is an equivalence between the Schatten-p quasi-norm of any matrix and the Schatten-2p norms of its two factor matrices, where the widely used equivalent formulation of the nuclear norm can be viewed as a special case. That is, various SQNM problems with p>1/2 can be transformed into the one only involving smooth, convex norms of two factor matrices, which can lead to simpler and more efficient algorithms than conventional methods. We further extend the theoretical results of two factor matrices to the cases of three and more factor matrices, from which we can see that for any 0<p<1, the Schatten-p quasi-norm of any matrix is the minimization of the mean of the Schatten-(p3+1)p norms of all factor matrices, where p3 denotes the largest integer not exceeding 1/p. In other words, for any 0<p<1, the SQNM problem can be transformed into an optimization problem only involving the smooth, convex norms of multiple factor matrices.
Hardware Decoders for Polar Codes: An Overview
Venue: arXiv cs.IT 2016
Year: 2016

Polar codes are an exciting new class of error correcting codes that achieve the symmetric capacity of memoryless channels. Many decoding algorithms were developed and implemented, addressing various application requirements: from error-correction performance rivaling that of LDPC codes to very high throughput or low-complexity decoders. In this work, we review the state of the art in polar decoders implementing the successive-cancellation, belief propagation, and list decoding algorithms, illustrating their advantages.
Barriers to the Integration of Information Technology within Early Childhood Education and Care Organisations: A Review of the Literature
Venue: arXiv cs.CY 2016
Year: 2016

Employees of early childhood education and care (ECEC) organisations may experience a wide range of barriers as they attempt to integrate information technology (IT) into their work practices. However, studies within the ECEC organisational literature which attempt to identify and understand these barriers are scant. This literature review is the first to present consolidated findings from the body of knowledge on barriers to the integration of IT within ECEC organisations. In addition to highlighting limitations and gaps in the literature, it proposes a tri-perspective framework to provide for future research to develop a deeper understanding of not only what barriers exist but also how they interrelate and shape the IT integration process and the work practices of ECEC organisational employees.