OpenRaiser/Intern-Atlas huggingface dataset:
Multimodal sparse representation learning and applications
Venue: arXiv cs.LG 2016
Year: 2016

Unsupervised methods have proven effective for discriminative tasks in a single-modality scenario. In this paper, we present a multimodal framework for learning sparse representations that can capture semantic correlation between modalities. The framework can model relationships at a higher level by forcing the shared sparse representation. In particular, we propose the use of joint dictionary learning technique for sparse coding and formulate the joint representation for concision, cross-modal representations (in case of a missing modality), and union of the cross-modal representations. Given the accelerated growth of multimodal data posted on the Web such as YouTube, Wikipedia, and Twitter, learning good multimodal features is becoming increasingly important. We show that the shared representations enabled by our framework substantially improve the classification performance under both unimodal and multimodal settings. We further show how deep architectures built on the proposed framework are effective for the case of highly nonlinear correlations between modalities. The effectiveness of our approach is demonstrated experimentally in image denoising, multimedia event detection and retrieval on the TRECVID dataset (audio-video), category classification on the Wikipedia dataset (image-text), and sentiment classification on PhotoTweet (image-text).
Asymmetrically Weighted CCA And Hierarchical Kernel Sentence Embedding For Image & Text Retrieval
Venue: arXiv cs.LG 2016
Year: 2016

Joint modeling of language and vision has been drawing increasing interest. A multimodal data representation allowing for bidirectional retrieval of images by sentences and vice versa is a key aspect. In this paper we present three contributions in canonical correlation analysis (CCA) based multimodal retrieval. Firstly, we show that an asymmetric weighting of the canonical weights, while achieving a cross view mapping from the search to the query space, improves the retrieval performance. Secondly, we devise a computationally efficient model selection, crucial to generalization and stability, in the framework of the Björk Golub algorithm for regularized CCA via spectral filtering. Finally, we introduce a Hierarchical Kernel Sentence Embedding (HKSE) that approximates Kernel CCA for a special similarity kernel between distribution of words embedded in a vector space. State of the art results are obtained on MSCOCO and Flickr benchmarks when these three techniques are used in conjunction.
Conditional Computation in Neural Networks for faster models
Venue: arXiv cs.LG 2016
Year: 2016

Deep learning has become the state-of-art tool in many applications, but the evaluation and training of deep models can be time-consuming and computationally expensive. The conditional computation approach has been proposed to tackle this problem (Bengio et al., 2013; Davis & Arel, 2013). It operates by selectively activating only parts of the network at a time. In this paper, we use reinforcement learning as a tool to optimize conditional computation policies. More specifically, we cast the problem of learning activation-dependent policies for dropping out blocks of units as a reinforcement learning problem. We propose a learning scheme motivated by computation speed, capturing the idea of wanting to have parsimonious activations while maintaining prediction accuracy. We apply a policy gradient algorithm for learning policies that optimize this loss function and propose a regularization mechanism that encourages diversification of the dropout policy. We present encouraging empirical results showing that this approach improves the speed of computation without impacting the quality of the approximation.
Communicating Semantics: Reference by Description
Venue: arXiv cs.CL 2016
Year: 2016

Messages often refer to entities such as people, places and events. Correct identification of the intended reference is an essential part of communication. Lack of shared unique names often complicates entity reference. Shared knowledge can be used to construct uniquely identifying descriptive references for entities with ambiguous names. We introduce a mathematical model for `Reference by Description', derive results on the conditions under which, with high probability, programs can construct unambiguous references to most entities in the domain of discourse and provide empirical validation of these results.
Generating Sentences from a Continuous Space
Venue: arXiv cs.LG 2016
Year: 2016

The standard recurrent neural network language model (RNNLM) generates sentences one word at a time and does not work from an explicit global sentence representation. In this work, we introduce and study an RNN-based variational autoencoder generative model that incorporates distributed latent representations of entire sentences. This factorization allows it to explicitly model holistic properties of sentences such as style, topic, and high-level syntactic features. Samples from the prior over these sentence representations remarkably produce diverse and well-formed sentences through simple deterministic decoding. By examining paths through this latent space, we are able to generate coherent novel sentences that interpolate between known sentences. We present techniques for solving the difficult learning problem presented by this model, demonstrate its effectiveness in imputing missing words, explore many interesting properties of the model's latent sentence space, and present negative results on the use of the model in language modeling.
Patterns for Learning with Side Information
Venue: arXiv cs.LG 2016
Year: 2016

Supervised, semi-supervised, and unsupervised learning estimate a function given input/output samples. Generalization of the learned function to unseen data can be improved by incorporating side information into learning. Side information are data that are neither from the input space nor from the output space of the function, but include useful information for learning it. In this paper we show that learning with side information subsumes a variety of related approaches, e.g. multi-task learning, multi-view learning and learning using privileged information. Our main contributions are (i) a new perspective that connects these previously isolated approaches, (ii) insights about how these methods incorporate different types of prior knowledge, and hence implement different patterns, (iii) facilitating the application of these methods in novel tasks, as well as (iv) a systematic experimental evaluation of these patterns in two supervised learning tasks.
Tracklet Association by Online Target-Specific Metric Learning and Coherent Dynamics Estimation
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present a novel method based on online target-specific metric learning and coherent dynamics estimation for tracklet (track fragment) association by network flow optimization in long-term multi-person tracking. Our proposed framework aims to exploit appearance and motion cues to prevent identity switches during tracking and to recover missed detections. Furthermore, target-specific metrics (appearance cue) and motion dynamics (motion cue) are proposed to be learned and estimated online, i.e. during the tracking process. Our approach is effective even when such cues fail to identify or follow the target due to occlusions or object-to-object interactions. We also propose to learn the weights of these two tracking cues to handle the difficult situations, such as severe occlusions and object-to-object interactions effectively. Our method has been validated on several public datasets and the experimental results show that it outperforms several state-of-the-art tracking methods.
Conducting sparse feature selection on arbitrarily long phrases in text corpora with a focus on interpretability
Venue: arXiv cs.CL 2016
Year: 2016

We propose a general framework for topic-specific summarization of large text corpora, and illustrate how it can be used for analysis in two quite different contexts: an OSHA database of fatality and catastrophe reports (to facilitate surveillance for patterns in circumstances leading to injury or death) and legal decisions on workers' compensation claims (to explore relevant case law). Our summarization framework, built on sparse classification methods, is a compromise between simple word frequency based methods currently in wide use, and more heavyweight, model-intensive methods such as Latent Dirichlet Allocation (LDA). For a particular topic of interest (e.g., mental health disability, or chemical reactions), we regress a labeling of documents onto the high-dimensional counts of all the other words and phrases in the documents. The resulting small set of phrases found as predictive are then harvested as the summary. Using a branch-and-bound approach, this method can be extended to allow for phrases of arbitrary length, which allows for potentially rich summarization. We discuss how focus on the purpose of the summaries can inform choices of regularization parameters and model constraints. We evaluate this tool by comparing computational time and summary statistics of the resulting word lists to three other methods in the literature. We also present a new R package, textreg. Overall, we argue that sparse methods have much to offer text analysis, and is a branch of research that should be considered further in this context.
Quantum approach to Bertrand duopoly
Venue: arXiv cs.GT 2016
Year: 2016

The aim of the paper is to study the Bertrand duopoly example in the quantum domain. We use two ways to write the game in terms of quantum theory. The first one adapts the Li-Du-Massar scheme for the Cournot duopoly. The second one is a simplified model that exploits a two qubit entangled state. In both cases we focus on finding Nash equilibria in the resulting games.
MIMO Channel Modeling and Capacity Analysis for 5G Millimeter-Wave Wireless Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a 3-D statistical channel model of the impulse response with small-scale spatially correlated random coefficients for multi-element transmitter and receiver antenna arrays, derived using the physically-based time cluster - spatial lobe (TCSL) clustering scheme. The small-scale properties of multipath amplitudes are modeled based on 28 GHz outdoor millimeter-wave small-scale local area channel measurements. The wideband channel capacity is evaluated by considering measurement-based Rician-distributed voltage amplitudes, and the spatial autocorrelation of multipath amplitudes for each pair of transmitter and receiver antenna elements. Results indicate that Rician channels may exhibit equal or possibly greater capacity compared to Rayleigh channels, depending on the number of antennas.
Temporal Convolutional Neural Networks for Diagnosis from Lab Tests
Venue: arXiv cs.LG 2016
Year: 2016

Early diagnosis of treatable diseases is essential for improving healthcare, and many diseases' onsets are predictable from annual lab tests and their temporal trends. We introduce a multi-resolution convolutional neural network for early detection of multiple diseases from irregularly measured sparse lab values. Our novel architecture takes as input both an imputed version of the data and a binary observation matrix. For imputing the temporal sparse observations, we develop a flexible, fast to train method for differentiable multivariate kernel regression. Our experiments on data from 298K individuals over 8 years, 18 common lab measurements, and 171 diseases show that the temporal signatures learned via convolution are significantly more predictive than baselines commonly used for early disease diagnosis.
Maximum Weight Independent Sets for ($P_7$,Triangle)-Free Graphs in Polynomial Time
Venue: arXiv cs.DM 2016
Year: 2016

The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity was an open problem for $P_k$-free graphs, $k \ge 5$. Recently, Lokshtanov, Vatshelle, and Villanger proved that MWIS can be solved in polynomial time for $P_5$-free graphs, and Lokshtanov, Pilipczuk, and van Leeuwen proved that MWIS can be solved in quasi-polynomial time for $P_6$-free graphs. It still remains an open problem whether MWIS can be solved in polynomial time for $P_k$-free graphs, $k \geq 6$ or in quasi-polynomial time for $P_k$-free graphs, $k \geq 7$. Some characterizations of $P_k$-free graphs and some progress are known in the literature but so far did not solve the problem. In this paper, we show that MWIS can be solved in polynomial time for ($P_7$,triangle)-free graphs. This extends the corresponding result for ($P_6$,triangle)-free graphs and may provide some progress in the study of MWIS for $P_7$-free graphs.
A Roadmap towards Machine Intelligence
Venue: arXiv cs.AI 2016
Year: 2016

The development of intelligent machines is one of the biggest unsolved challenges in computer science. In this paper, we propose some fundamental properties these machines should have, focusing in particular on communication and learning. We discuss a simple environment that could be used to incrementally teach a machine the basics of natural-language-based communication, as a prerequisite to more complex interaction with human users. We also present some conjectures on the sort of algorithms the machine should support in order to profitably learn from the environment.
A Computational Model for Amodal Completion
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a computational model to recover the most likely interpretation of the 3D scene structure from a planar image, where some objects may occlude others. The estimated scene interpretation is obtained by integrating some global and local cues and provides both the complete disoccluded objects that form the scene and their ordering according to depth. Our method first computes several distal scenes which are compatible with the proximal planar image. To compute these different hypothesized scenes, we propose a perceptually inspired object disocclusion method, which works by minimizing the Euler's elastica as well as by incorporating the relatability of partially occluded contours and the convexity of the disoccluded objects. Then, to estimate the preferred scene we rely on a Bayesian model and define probabilities taking into account the global complexity of the objects in the hypothesized scenes as well as the effort of bringing these objects in their relative position in the planar image, which is also measured by an Euler's elastica-based quantity. The model is illustrated with numerical experiments on, both, synthetic and real images showing the ability of our model to reconstruct the occluded objects and the preferred perceptual order among them. We also present results on images of the Berkeley dataset with provided figure-ground ground-truth labeling.
Virtual World, Defined from a Technological Perspective, and Applied to Video Games, Mixed Reality and the Metaverse
Venue: arXiv cs.HC 2016
Year: 2016

There is no generally accepted definition for a virtual world, with many complimentary terms and acronyms having emerged implying a virtual world. Advances in systems architecture techniques such as, host migration of instances, mobile ad-hoc networking, and distributed computing, bring in to question whether those architectures can actually support a virtual world. Without a concrete definition, controversy ensues and it is problematic to design an architecture for a virtual world. Several researchers provided a definition but aspects of each definition are still problematic and simply can not be applied to contemporary technologies. The approach of this article is to sample technologies using grounded theory, and obtain a definition for a `virtual world' that is directly applicable to technology. The obtained definition is compared with related work and used to classify advanced technologies, such as: a pseudo-persistent video game, a MANet, virtual and mixed reality, and the Metaverse. The results of this article include: a break down of which properties set apart the various technologies; a definition that is validated by comparing it with other definitions; an ontology showing the relation of the different complimentary terms and acronyms; and, the usage of pseudo-persistence to categories those technologies which only mimic persistence.
Incremental Truncated LSTD
Venue: arXiv cs.LG 2016
Year: 2016

Balancing between computational efficiency and sample efficiency is an important goal in reinforcement learning. Temporal difference (TD) learning algorithms stochastically update the value function, with a linear time complexity in the number of features, whereas least-squares temporal difference (LSTD) algorithms are sample efficient but can be quadratic in the number of features. In this work, we develop an efficient incremental low-rank LSTD(λ) algorithm that progresses towards the goal of better balancing computation and sample efficiency. The algorithm reduces the computation and storage complexity to the number of features times the chosen rank parameter while summarizing past samples efficiently to nearly obtain the sample complexity of LSTD. We derive a simulation bound on the solution given by truncated low-rank approximation, illustrating a bias- variance trade-off dependent on the choice of rank. We demonstrate that the algorithm effectively balances computational complexity and sample efficiency for policy evaluation in a benchmark task and a high-dimensional energy allocation domain.
Distortion Limited Amplify-and-forward Relay Networks and the $ε$-critical Phase Transition
Venue: arXiv cs.IT 2016
Year: 2016

We study amplify-and-forward (AF) relay networks operating with source and relay amplifier distortion, where the distortion dominates the noise power. The diversity order is shown to be $0$ for fixed-gain (FG) and $1$ for variable-gain (VG) if distortion occurs at the relay; if distortion occurs only at the source, the diversity order will be $1$ for both. With $ε_β=N_0/η_β$ ($N_0$ the noise power, $η_β$ the distortion power at node $β\in\{S,R\}$, the source or relay), we demonstrate the emergence of what we call an $ε$-critical signal-to-noise plus distortion ratio (SNDR) threshold (a threshold that emerges when $\min\{ε_β\}$ becomes small) for both forwarding protocols. We show that crossing this threshold in distortion limited regions will cause a phase transition (a dramatic drop) in the network's outage probability. Thus, small reductions in the required end-to-end transmission rate can have significant reductions in the network's outage probability.
The Algebra of Recursive Graph Transformation Language UnCAL: Complete Axiomatisation and Iteration Categorical Semantics
Venue: arXiv cs.LO 2016
Year: 2016

The aim of this paper is to provide mathematical foundations of a graph transformation language, called UnCAL, using categorical semantics of type theory and fixed points. About twenty years ago, Buneman et al. developed a graph database query language UnQL on the top of a functional meta-language UnCAL for describing and manipulating graphs. Recently, the functional programming community has shown renewed interest in UnCAL, because it provides an efficient graph transformation language which is useful for various applications, such as bidirectional computation. In order to make UnCAL more flexible and fruitful for further extensions and applications, in this paper, we give a more conceptual understanding of UnCAL using categorical semantics. Our general interest of this paper is to clarify what is the algebra of UnCAL. Thus, we give an equational axiomatisation and categorical semantics of UnCAL, both of which are new. We show that the axiomatisation is complete for the original bisimulation semantics of UnCAL. Moreover, we provide a clean characterisation of the computation mechanism of UnCAL called "structural recursion on graphs" using our categorical semantics. We show a concrete model of UnCAL given by the lambdaG-calculus, which shows an interesting connection to lazy functional programming.
Column-Oriented Datalog Materialization for Large Knowledge Graphs (Extended Technical Report)
Venue: arXiv cs.DB 2016
Year: 2016

The evaluation of Datalog rules over large Knowledge Graphs (KGs) is essential for many applications. In this paper, we present a new method of materializing Datalog inferences, which combines a column-based memory layout with novel optimization methods that avoid redundant inferences at runtime. The pro-active caching of certain subqueries further increases efficiency. Our empirical evaluation shows that this approach can often match or even surpass the performance of state-of-the-art systems, especially under restricted resources.
Position Estimation of Robotic Mobile Nodes in Wireless Testbed using GENI
Venue: arXiv cs.NI 2016
Year: 2016

We present a low complexity experimental RF-based indoor localization system based on the collection and processing of WiFi RSSI signals and processing using a RSS-based multi-lateration algorithm to determine a robotic mobile node's location. We use a real indoor wireless testbed called w-iLab.t that is deployed in Zwijnaarde, Ghent, Belgium. One of the unique attributes of this testbed is that it provides tools and interfaces using Global Environment for Network Innovations (GENI) project to easily create reproducible wireless network experiments in a controlled environment. We provide a low complexity algorithm to estimate the location of the mobile robots in the indoor environment. In addition, we provide a comparison between some of our collected measurements with their corresponding location estimation and the actual robot location. The comparison shows an accuracy between 0.65 and 5 meters.
Wikipedia Ranking of World Universities
Venue: arXiv cs.SI 2016
Year: 2016

We use the directed networks between articles of 24 Wikipedia language editions for producing the Wikipedia Ranking of World Universities (WRWU) using PageRank, 2DRank and CheiRank algorithms. This approach allows to incorporate various cultural views on world universities using the mathematical statistical analysis independent of cultural preferences. The Wikipedia ranking of top 100 universities provides about 60 percent overlap with the Shanghai university ranking demonstrating the reliable features of this approach. At the same time WRWU incorporates all knowledge accumulated at 24 Wikipedia editions giving stronger highlights for historically important universities leading to a different estimation of efficiency of world countries in university education. The historical development of university ranking is analyzed during ten centuries of their history.