OpenRaiser/Intern-Atlas huggingface dataset:
Towards Principled Unsupervised Learning
Venue: arXiv cs.LG 2015
Year: 2015

General unsupervised learning is a long-standing conceptual problem in machine learning. Supervised learning is successful because it can be solved by the minimization of the training error cost function. Unsupervised learning is not as successful, because the unsupervised objective may be unrelated to the supervised task of interest. For an example, density modelling and reconstruction have often been used for unsupervised learning, but they did not produced the sought-after performance gains, because they have no knowledge of the supervised tasks. In this paper, we present an unsupervised cost function which we name the Output Distribution Matching (ODM) cost, which measures a divergence between the distribution of predictions and distributions of labels. The ODM cost is appealing because it is consistent with the supervised cost in the following sense: a perfect supervised classifier is also perfect according to the ODM cost. Therefore, by aggressively optimizing the ODM cost, we are almost guaranteed to improve our supervised performance whenever the space of possible predictions is exponentially large. We demonstrate that the ODM cost works well on number of small and semi-artificial datasets using no (or almost no) labelled training cases. Finally, we show that the ODM cost can be used for one-shot domain adaptation, which allows the model to classify inputs that differ from the input distribution in significant ways without the need for prior exposure to the new domain.
Embarrassingly Parallel Time Series Analysis for Large Scale Weak Memory Systems
Venue: arXiv cs.DC 2015
Year: 2015

Second order stationary models in time series analysis are based on the analysis of essential statistics whose computations follow a common pattern. In particular, with a map-reduce nomenclature, most of these operations can be modeled as mapping a kernel that only depends on short windows of consecutive data and reducing the results produced by each computation. This computational pattern stems from the ergodicity of the model under consideration and is often referred to as weak or short memory when it comes to data indexed with respect to time. In the following we will show how studying weak memory systems can be done in a scalable manner thanks to a framework relying on specifically designed overlapping distributed data structures that enable fragmentation and replication of the data across many machines as well as parallelism in computations. This scheme has been implemented for Apache Spark but is certainly not system specific. Indeed we prove it is also adapted to leveraging high bandwidth fragmented memory blocks on GPUs.
Bidirectional Warping of Active Appearance Model
Venue: arXiv cs.CV 2015
Year: 2015

Active Appearance Model (AAM) is a commonly used method for facial image analysis with applications in face identification and facial expression recognition. This paper proposes a new approach based on image alignment for AAM fitting called bidirectional warping. Previous approaches warp either the input image or the appearance template. We propose to warp both the input image, using incremental update by an affine transformation, and the appearance template, using an inverse compositional approach. Our experimental results on Multi-PIE face database show that the bidirectional approach outperforms state-of-the-art inverse compositional fitting approaches in extracting landmark points of faces with shape and pose variations.
ElSe: Ellipse Selection for Robust Pupil Detection in Real-World Environments
Venue: arXiv cs.CV 2015
Year: 2015

Fast and robust pupil detection is an essential prerequisite for video-based eye-tracking in real-world settings. Several algorithms for image-based pupil detection have been proposed, their applicability is mostly limited to laboratory conditions. In realworld scenarios, automated pupil detection has to face various challenges, such as illumination changes, reflections (on glasses), make-up, non-centered eye recording, and physiological eye characteristics. We propose ElSe, a novel algorithm based on ellipse evaluation of a filtered edge image. We aim at a robust, resource-saving approach that can be integrated in embedded architectures e.g. driving. The proposed algorithm was evaluated against four state-of-the-art methods on over 93,000 hand-labeled images from which 55,000 are new images contributed by this work. On average, the proposed method achieved a 14.53% improvement on the detection rate relative to the best state-of-the-art performer. download:ftp://emmapupildata@messor.informatik.unituebingen. de (password:eyedata).
Top-N recommendations from expressive recommender systems
Venue: arXiv cs.LG 2015
Year: 2015

Normalized nonnegative models assign probability distributions to users and random variables to items; see [Stark, 2015]. Rating an item is regarded as sampling the random variable assigned to the item with respect to the distribution assigned to the user who rates the item. Models of that kind are highly expressive. For instance, using normalized nonnegative models we can understand users' preferences as mixtures of interpretable user stereotypes, and we can arrange properties of users and items in a hierarchical manner. These features would not be useful if the predictive power of normalized nonnegative models was poor. Thus, we analyze here the performance of normalized nonnegative models for top-N recommendation and observe that their performance matches the performance of methods like PureSVD which was introduced in [Cremonesi et al., 2010]. We conclude that normalized nonnegative models not only provide accurate recommendations but they also deliver (for free) representations that are interpretable. We deepen the discussion of normalized nonnegative models by providing further theoretical insights. In particular, we introduce total variational distance as an operational similarity measure, we discover scenarios where normalized nonnegative models yield unique representations of users and items, we prove that the inference of optimal normalized nonnegative models is NP-hard and finally, we discuss the relationship between normalized nonnegative models and nonnegative matrix factorization.
WLAN Specific IoT Enable Power Efficient RAM Design on 40nm FPGA
Venue: arXiv cs.OH 2015
Year: 2015

Increasing the speed of computer is one of the important aspects of the Random Access Memory (RAM) and for better and fast processing it should be efficient. In this work, the main focus is to design energy efficient RAM and it also can be accessed through internet. A 128-bit IPv6 address is added to the RAM in order to control it via internet. Four different types of Low Voltage CMOS (LCVMOS) IO standards are used to make it low power under five different WLAN frequencies is taken. At WLAN frequency 2.4GHz, there is maximum power reduction of 85% is achieved when LVCMOS12 is taken in place of LVCMOS25. This design is implemented using Virtex-6 FPGA, Device xc6vlx75t and Package FF484
Real-Valued Khatri-Rao Subspace Approaches on the ULA and a New Nested Array
Venue: arXiv cs.IT 2015
Year: 2015

In underdetermined direction-of-arrival (DOA) estimation using the covariance-based signal models, the computational complexity turns into a noticeable issue because of the high dimension of the virtual array manifold. In this paper, real-valued Khatri-Rao (KR) approaches are developed on the uniform linear array (ULA) and the nested array. The complexities of subspace decomposition and spectral search are reduced compared with the complex-valued KR approach. By designing a special transformation matrix, the influence of the noise is removed in the mean time while the data is transformed from the complex domain to the real domain. Deploying the sensors with nonuniform spacings can raise the degree of freedom (DOF) and hence help detect more sources in the underdetermined situation. To increase the DOF further, a new nested array geometry is designed. The real-valued denoising KR approach developed on the new nested array can resolve more sources with reduced complexities. The performance improvement is demonstrated by numerical studies.
On the Linear Algebraic Structure of Distributed Word Representations
Venue: arXiv cs.CL 2015
Year: 2015

In this work, we leverage the linear algebraic structure of distributed word representations to automatically extend knowledge bases and allow a machine to learn new facts about the world. Our goal is to extract structured facts from corpora in a simpler manner, without applying classifiers or patterns, and using only the co-occurrence statistics of words. We demonstrate that the linear algebraic structure of word embeddings can be used to reduce data requirements for methods of learning facts. In particular, we demonstrate that words belonging to a common category, or pairs of words satisfying a certain relation, form a low-rank subspace in the projected space. We compute a basis for this low-rank subspace using singular value decomposition (SVD), then use this basis to discover new facts and to fit vectors for less frequent words which we do not yet have vectors for.
Understanding Music Playlists
Venue: arXiv cs.MM 2015
Year: 2015

As music streaming services dominate the music industry, the playlist is becoming an increasingly crucial element of music consumption. Con- sequently, the music recommendation problem is often casted as a playlist generation prob- lem. Better understanding of the playlist is there- fore necessary for developing better playlist gen- eration algorithms. In this work, we analyse two playlist datasets to investigate some com- monly assumed hypotheses about playlists. Our findings indicate that deeper understanding of playlists is needed to provide better prior infor- mation and improve machine learning algorithms in the design of recommendation systems.
Max-sum diversity via convex programming
Venue: arXiv cs.DS 2015
Year: 2015

Diversity maximization is an important concept in information retrieval, computational geometry and operations research. Usually, it is a variant of the following problem: Given a ground set, constraints, and a function $f(\cdot)$ that measures diversity of a subset, the task is to select a feasible subset $S$ such that $f(S)$ is maximized. The \emph{sum-dispersion} function $f(S) = \sum_{x,y \in S} d(x,y)$, which is the sum of the pairwise distances in $S$, is in this context a prominent diversification measure. The corresponding diversity maximization is the \emph{max-sum} or \emph{sum-sum diversification}. Many recent results deal with the design of constant-factor approximation algorithms of diversification problems involving sum-dispersion function under a matroid constraint. In this paper, we present a PTAS for the max-sum diversification problem under a matroid constraint for distances $d(\cdot,\cdot)$ of \emph{negative type}. Distances of negative type are, for example, metric distances stemming from the $\ell_2$ and $\ell_1$ norm, as well as the cosine or spherical, or Jaccard distance which are popular similarity metrics in web and image search.
A reduction of the logspace shortest path problem to biconnected graphs
Venue: arXiv cs.CC 2015
Year: 2015

In this paper, we reduce the logspace shortest path problem to biconnected graphs; in particular, we present a logspace shortest path algorithm for general graphs which uses a logspace shortest path oracle for biconnected graphs. We also present a linear time logspace shortest path algorithm for graphs with bounded vertex degree and biconnected component size, which does not rely on an oracle. The asymptotic time-space product of this algorithm is the best possible among all shortest path algorithms.
Optimizing Solution Quality in Synchronization Synthesis
Venue: arXiv cs.PL 2015
Year: 2015

Given a multithreaded program written assuming a friendly, non-preemptive scheduler, the goal of synchronization synthesis is to automatically insert synchronization primitives to ensure that the modified program behaves correctly, even with a preemptive scheduler. In this work, we focus on the quality of the synthesized solution: we aim to infer synchronization placements that not only ensure correctness, but also meet some quantitative objectives such as optimal program performance on a given computing platform. The key step that enables solution optimization is the construction of a set of global constraints over synchronization placements such that each model of the constraints set corresponds to a correctness-ensuring synchronization placement. We extract the global constraints from generalizations of counterexample traces and the control-flow graph of the program. The global constraints enable us to choose from among the encoded synchronization solutions using an objective function. We consider two types of objective functions: ones that are solely dependent on the program (e.g., minimizing the size of critical sections) and ones that are also dependent on the computing platform. For the latter, given a program and a computing platform, we construct a performance model based on measuring average contention for critical sections and the average time taken to acquire and release a lock under a given average contention. We empirically evaluated that our approach scales to typical module sizes of many real world concurrent programs such as device drivers and multithreaded servers, and that the performance predictions match reality. To the best of our knowledge, this is the first comprehensive approach for optimizing the placement of synthesized synchronization.
Developing a High Performance Software Library with MPI and CUDA for Matrix Computations
Venue: arXiv cs.DC 2015
Year: 2015

Nowadays, the paradigm of parallel computing is changing. CUDA is now a popular programming model for general purpose computations on GPUs and a great number of applications were ported to CUDA obtaining speedups of orders of magnitude comparing to optimized CPU implementations. Hybrid approaches that combine the message passing model with the shared memory model for parallel computing are a solution for very large applications. We considered a heterogeneous cluster that combines the CPU and GPU computations using MPI and CUDA for developing a high performance linear algebra library. Our library deals with large linear systems solvers because they are a common problem in the fields of science and engineering. Direct methods for computing the solution of such systems can be very expensive due to high memory requirements and computational cost. An efficient alternative are iterative methods which computes only an approximation of the solution. In this paper we present an implementation of a library that uses a hybrid model of computation using MPI and CUDA implementing both direct and iterative linear systems solvers. Our library implements LU and Cholesky factorization based solvers and some of the non-stationary iterative methods using the MPI/CUDA combination. We compared the performance of our MPI/CUDA implementation with classic programs written to be run on a single CPU.
Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization
Venue: arXiv cs.AI 2015
Year: 2015

We address the problem of maximizing an unknown submodular function that can only be accessed via noisy evaluations. Our work is motivated by the task of summarizing content, e.g., image collections, by leveraging users' feedback in form of clicks or ratings. For summarization tasks with the goal of maximizing coverage and diversity, submodular set functions are a natural choice. When the underlying submodular function is unknown, users' feedback can provide noisy evaluations of the function that we seek to maximize. We provide a generic algorithm -- \submM{} -- for maximizing an unknown submodular function under cardinality constraints. This algorithm makes use of a novel exploration module -- \blbox{} -- that proposes good elements based on adaptively sampling noisy function evaluations. \blbox{} is able to accommodate different kinds of observation models such as value queries and pairwise comparisons. We provide PAC-style guarantees on the quality and sampling cost of the solution obtained by \submM{}. We demonstrate the effectiveness of our approach in an interactive, crowdsourced image collection summarization application.
A Low-Complexity Detection Algorithm for the Primary Synchronization Signal in LTE
Venue: arXiv cs.IT 2015
Year: 2015

One of the challenging tasks in LTE baseband receiver design is synchronization, which determines the symbol boundary and transmitted frame start-time, and performs cell identification. Conventional algorithms are based on correlation methods that involve a large number of multiplications and thus lead to high receiver hardware complexity and power consumption. In this paper, a hardware-efficient synchronization algorithm for frame timing based on K-means clustering schemes is proposed. The algorithm reduces the complexity of the primary synchronization signal for LTE from 24 complex-multiplications, currently best known in the literature, to just 8. Simulation results demonstrate that the proposed algorithm has negligible performance degradation with reduced complexity relative to conventional techniques.
A Note on Flagg and Friedman's Epistemic and Intuitionistic Formal Systems
Venue: arXiv cs.LO 2015
Year: 2015

We report our findings on the properties of Flagg and Friedman's translation from Epistemic into Intuitionistic logic, which was proposed as the basis of a comprehensive proof method for the faithfulness of the Goodel translation. We focus on the propositional case and raise the issue of the admissibility of the translated necessitation rule. Then, we contribute to Flagg and Friedman's program by giving an explicit proof of the soundness of their translation.
Instantaneous Relaying for the 3-Way Relay Channel with Circular Message Exchanges
Venue: arXiv cs.IT 2015
Year: 2015

The 3-user discrete memoryless multi-way relay channel with circular message exchange and instantaneous relaying is investigated. We first show that this channel is effectively a 3-user interference channel with receiver message side information for every fixed (and instantaneous) relay mapping. Then, we extend the Han-Kobayashi coding scheme to this channel. Finally, we apply these results to Gaussian channels with amplify-and-forward relaying and present numerical results showing the gain of the proposed scheme compared to the state of the art.
Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search
Venue: arXiv cs.CG 2015
Year: 2015

We introduce a new variant of the nearest neighbor search problem, which allows for some coordinates of the dataset to be arbitrarily corrupted or unknown. Formally, given a dataset of $n$ points $P=\{ x_1,\ldots, x_n\}$ in high-dimensions, and a parameter $k$, the goal is to preprocess the dataset, such that given a query point $q$, one can compute quickly a point $x \in P$, such that the distance of the query to the point $x$ is minimized, when ignoring the "optimal" $k$ coordinates. Note, that the coordinates being ignored are a function of both the query point and the point returned. We present a general reduction from this problem to answering ANN queries, which is similar in spirit to LSH (locality sensitive hashing) [IM98]. Specifically, we give a sampling technique which achieves a bi-criterion approximation for this problem. If the distance to the nearest neighbor after ignoring $k$ coordinates is $r$, the data-structure returns a point that is within a distance of $O(r)$ after ignoring $O(k)$ coordinates. We also present other applications and further extensions and refinements of the above result. The new data-structures are simple and (arguably) elegant, and should be practical -- specifically, all bounds are polynomial in all relevant parameters (including the dimension of the space, and the robustness parameter $k$).
A review and evaluation of numerical tools for fractional calculus and fractional order control
Venue: arXiv cs.SY 2015
Year: 2015

In recent years, as fractional calculus becomes more and more broadly used in research across different academic disciplines, there are increasing demands for the numerical tools for the computation of fractional integration/differentiation, and the simulation of fractional order systems. Time to time, being asked about which tool is suitable for a specific application, the authors decide to carry out this survey to present recapitulative information of the available tools in the literature, in hope of benefiting researchers with different academic backgrounds. With this motivation, the present article collects the scattered tools into a dashboard view, briefly introduces their usage and algorithms, evaluates the accuracy, compares the performance, and provides informative comments for selection.
Simultaneous Wireless Information and Power Transfer in Cooperative Relay Networks with Rateless Codes
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the simultaneous wireless information and power transfer (SWIPT) in cooperative relay networks, where a relay harvests energy from the radio frequency (RF) signals transmitted by a source and then uses the harvested energy to assist the information transmission from the source to its destination. Both source and relay transmissions use rateless code, which allows the destination to employ any of the two information receiving strategies, i.e., the mutual information accumulation (IA) and the energy accumulation (EA). The SWIPT-enabled relay employs three different SWIPT receiver architectures, the ideal receiver and two practical receivers (i.e., the power splitting (PS) and the time switch (TS) receivers). Accordingly, three relaying protocols, namely, ideal protocol, PS protocol and TS protocol, are presented. In order to explore the system performance limits with these three protocols, optimization problems are formulated to maximize their achievable information rates. For the ideal protocol, explicit expressions of the optimal solutions are derived. For the PS protocol, a linear-search algorithm is designed to solve the non-convex problems. For the TS protocol, two solving methods are presented. Numerical experiments are carried out to validate our analysis and algorithms, which also show that, with the same SWIPT receiver, the IA-based system outperforms the EA-based system, while with the same information receiving strategy, PS protocol outperforms TS protocol. Moreover, compared with conventional non-SWIPT and non-rateless-coded systems, the proposed protocols exhibit considerable performance gains, especially in relatively low signal-to-noise ratio (SNR) regime. Besides, the effects of the source-destination direct link and the relay position on system performance are also discussed, which provides insights on SWIPT-enabled relay systems.