OpenRaiser/Intern-Atlas huggingface dataset:
Encoding Data for HTM Systems
Venue: arXiv cs.NE 2016
Year: 2016

Hierarchical Temporal Memory (HTM) is a biologically inspired machine intelligence technology that mimics the architecture and processes of the neocortex. In this white paper we describe how to encode data as Sparse Distributed Representations (SDRs) for use in HTM systems. We explain several existing encoders, which are available through the open source project called NuPIC, and we discuss requirements for creating encoders for new types of data.
A Nonparametric Framework for Quantifying Generative Inference on Neuromorphic Systems
Venue: arXiv cs.NE 2016
Year: 2016

Restricted Boltzmann Machines and Deep Belief Networks have been successfully used in probabilistic generative model applications such as image occlusion removal, pattern completion and motion synthesis. Generative inference in such algorithms can be performed very efficiently on hardware using a Markov Chain Monte Carlo procedure called Gibbs sampling, where stochastic samples are drawn from noisy integrate and fire neurons implemented on neuromorphic substrates. Currently, no satisfactory metrics exist for evaluating the generative performance of such algorithms implemented on high-dimensional data for neuromorphic platforms. This paper demonstrates the application of nonparametric goodness-of-fit testing to both quantify the generative performance as well as provide decision-directed criteria for choosing the parameters of the neuromorphic Gibbs sampler and optimizing usage of hardware resources used during sampling.
On Training Bi-directional Neural Network Language Model with Noise Contrastive Estimation
Venue: arXiv cs.CL 2016
Year: 2016

We propose to train bi-directional neural network language model(NNLM) with noise contrastive estimation(NCE). Experiments are conducted on a rescore task on the PTB data set. It is shown that NCE-trained bi-directional NNLM outperformed the one trained by conventional maximum likelihood training. But still(regretfully), it did not out-perform the baseline uni-directional NNLM.
Ordonnancement d'entités pour la rencontre du web des documents et du web des données
Venue: arXiv cs.IR 2016
Year: 2016

The advances of the Linked Open Data (LOD) initiative are giving rise to a more structured web of data. Indeed, a few datasets act as hubs (e.g., DBpedia) connecting many other datasets. They also made possible new web services for entity detection inside plain text (e.g., DBpedia Spotlight), thus allowing for new applications that will benefit from a combination of the web of documents and the web of data. To ease the emergence of these new use-cases, we propose a query-biased algorithm for the ranking of entities detected inside a web page. Our algorithm combine link analysis with dimensionality reduction. We use crowdsourcing for building a publicly available and reusable dataset on which we compare our algorithm to the state of the art. Finally, we use this algorithm for the construction of semantic snippets for which we evaluate the usability and the usefulness with a crowdsourcing-based approach.
Contextual LSTM (CLSTM) models for Large scale NLP tasks
Venue: arXiv cs.CL 2016
Year: 2016

Documents exhibit sequential structure at multiple levels of abstraction (e.g., sentences, paragraphs, sections). These abstractions constitute a natural hierarchy for representing the context in which to infer the meaning of words and larger fragments of text. In this paper, we present CLSTM (Contextual LSTM), an extension of the recurrent neural network LSTM (Long-Short Term Memory) model, where we incorporate contextual features (e.g., topics) into the model. We evaluate CLSTM on three specific NLP tasks: word prediction, next sentence selection, and sentence topic prediction. Results from experiments run on two corpora, English documents in Wikipedia and a subset of articles from a recent snapshot of English Google News, indicate that using both words and topics as features improves performance of the CLSTM models over baseline LSTM models for these tasks. For example on the next sentence selection task, we get relative accuracy improvements of 21% for the Wikipedia dataset and 18% for the Google News dataset. This clearly demonstrates the significant benefit of using context appropriately in natural language (NL) tasks. This has implications for a wide variety of NL applications like question answering, sentence completion, paraphrase generation, and next utterance prediction in dialog systems.
Directly Coupled Observers for Quantum Harmonic Oscillators with Discounted Mean Square Cost Functionals and Penalized Back-action
Venue: arXiv cs.SY 2016
Year: 2016

This paper is concerned with quantum harmonic oscillators consisting of a quantum plant and a directly coupled coherent quantum observer. We employ discounted quadratic performance criteria in the form of exponentially weighted time averages of second-order moments of the system variables. A coherent quantum filtering (CQF) problem is formulated as the minimization of the discounted mean square of an estimation error, with which the dynamic variables of the observer approximate those of the plant. The cost functional also involves a quadratic penalty on the plant-observer coupling matrix in order to mitigate the back-action of the observer on the covariance dynamics of the plant. For the discounted mean square optimal CQF problem with penalized back-action, we establish first-order necessary conditions of optimality in the form of algebraic matrix equations. By using the Hamiltonian structure of the Heisenberg dynamics and related Lie-algebraic techniques, we represent this set of equations in a more explicit form in the case of equally dimensioned plant and observer.
Interactive Storytelling over Document Collections
Venue: arXiv cs.AI 2016
Year: 2016

Storytelling algorithms aim to 'connect the dots' between disparate documents by linking starting and ending documents through a series of intermediate documents. Existing storytelling algorithms are based on notions of coherence and connectivity, and thus the primary way by which users can steer the story construction is via design of suitable similarity functions. We present an alternative approach to storytelling wherein the user can interactively and iteratively provide 'must use' constraints to preferentially support the construction of some stories over others. The three innovations in our approach are distance measures based on (inferred) topic distributions, the use of constraints to define sets of linear inequalities over paths, and the introduction of slack and surplus variables to condition the topic distribution to preferentially emphasize desired terms over others. We describe experimental results to illustrate the effectiveness of our interactive storytelling approach over multiple text datasets.
Mean Field Equilibria for Competitive Exploration in Resource Sharing Settings
Venue: arXiv cs.GT 2016
Year: 2016

We consider a model of nomadic agents exploring and competing for time-varying location-specific resources, arising in crowdsourced transportation services, online communities, and in traditional location based economic activity. This model comprises a group of agents, and a set of locations each endowed with a dynamic stochastic resource process. Each agent derives a periodic reward determined by the overall resource level at her location, and the number of other agents there. Each agent is strategic and free to move between locations, and at each time decides whether to stay at the same node or switch to another one. We study the equilibrium behavior of the agents as a function of dynamics of the stochastic resource process and the nature of the externality each agent imposes on others at the same location. In the asymptotic limit with the number of agents and locations increasing proportionally, we show that an equilibrium exists and has a threshold structure, where each agent decides to switch to a different location based only on their current location's resource level and the number of other agents at that location. This result provides insight into how system structure affects the agents' collective ability to explore their domain to find and effectively utilize resource-rich areas. It also allows assessing the impact of changing the reward structure through penalties or subsidies.
An Algebraic Topological Approach to Privacy: Numerical and Categorical Data
Venue: arXiv cs.DB 2016
Year: 2016

In this paper, we cast the classic problem of achieving k-anonymity for a given database as a problem in algebraic topology. Using techniques from this field of mathematics, we propose a framework for k-anonymity that brings new insights and algorithms to anonymize a database. We begin by addressing the simpler case when the data lies in a metric space. This case is instrumental to introduce the main ideas and notation. Specifically, by mapping a database to the Euclidean space and by considering the distance between datapoints, we introduce a simplicial representation of the data and show how concepts from algebraic topology, such as the nerve complex and persistent homology, can be applied to efficiently obtain the entire spectrum of k-anonymity of the database for various values of k and levels of generalization. For this representation, we provide an analytic characterization of conditions under which a given representation of the dataset is k-anonymous. We introduce a weighted barcode diagram which, in this context, becomes a computational tool to tradeoff data anonymity with data loss expressed as level of generalization. Some simulations results are used to illustrate the main idea of the paper. We conclude the paper with a discussion on how to extend this method to address the general case of a mix of categorical and metric data.
Planogram Compliance Checking Based on Detection of Recurring Patterns
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a novel method for automatic planogram compliance checking in retail chains is proposed without requiring product template images for training. Product layout is extracted from an input image by means of unsupervised recurring pattern detection and matched via graph matching with the expected product layout specified by a planogram to measure the level of compliance. A divide and conquer strategy is employed to improve the speed. Specifically, the input image is divided into several regions based on the planogram. Recurring patterns are detected in each region respectively and then merged together to estimate the product layout. Experimental results on real data have verified the efficacy of the proposed method. Compared with a template-based method, higher accuracies are achieved by the proposed method over a wide range of products.
Structured Learning of Binary Codes with Column Generation
Venue: arXiv cs.LG 2016
Year: 2016

Hashing methods aim to learn a set of hash functions which map the original features to compact binary codes with similarity preserving in the Hamming space. Hashing has proven a valuable tool for large-scale information retrieval. We propose a column generation based binary code learning framework for data-dependent hash function learning. Given a set of triplets that encode the pairwise similarity comparison information, our column generation based method learns hash functions that preserve the relative comparison relations within the large-margin learning framework. Our method iteratively learns the best hash functions during the column generation procedure. Existing hashing methods optimize over simple objectives such as the reconstruction error or graph Laplacian related loss functions, instead of the performance evaluation criteria of interest---multivariate performance measures such as the AUC and NDCG. Our column generation based method can be further generalized from the triplet loss to a general structured learning based framework that allows one to directly optimize multivariate performance measures. For optimizing general ranking measures, the resulting optimization problem can involve exponentially or infinitely many variables and constraints, which is more challenging than standard structured output learning. We use a combination of column generation and cutting-plane techniques to solve the optimization problem. To speed-up the training we further explore stage-wise training and propose to use a simplified NDCG loss for efficient inference. We demonstrate the generality of our method by applying it to ranking prediction and image retrieval, and show that it outperforms a few state-of-the-art hashing methods.
Designing a Disaster-resilient Network with Software Defined Networking
Venue: arXiv cs.NI 2016
Year: 2016

With the wide deployment of network facilities and the increasing requirement of network reliability, the disruptive event like natural disaster, power outage or malicious attack has become a non-negligible threat to the current communication network. Such disruptive event can simultaneously destroy all devices in a specific geographical area and affect many network based applications for a long time. Hence, it is essential to build disaster-resilient network for future highly survivable communication services. In this paper, we consider the problem of designing a highly resilient network through the technique of SDN (Software Defined Networking). In contrast to the conventional idea of handling all the failures on the control plane (the controller), we focus on an integrated design to mitigate disaster risks by adding some redundant functions on the data plane. Our design consists of a sub-graph based proactive protection approach on the data plane and a splicing approach at the controller for effective restoration on the control plane. Such a systematic design is implemented in the OpenFlow framework through the Mininet emulator and Nox controller. Numerical results show that our approach can achieve high robustness with low control overhead.
Cognitive Architecture for Mutual Modelling
Venue: arXiv cs.RO 2016
Year: 2016

In social robotics, robots needs to be able to be understood by humans. Especially in collaborative tasks where they have to share mutual knowledge. For instance, in an educative scenario, learners share their knowledge and they must adapt their behaviour in order to make sure they are understood by others. Learners display behaviours in order to show their understanding and teachers adapt in order to make sure that the learners' knowledge is the required one. This ability requires a model of their own mental states perceived by others: \textit{"has the human understood that I(robot) need this object for the task or should I explain it once again ?"} In this paper, we discuss the importance of a cognitive architecture enabling second-order Mutual Modelling for Human-Robot Interaction in educative contexts.
On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
Venue: arXiv cs.DS 2016
Year: 2016

Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bounds often imply worst-case bounds for the partially dynamic setting, it seems much more difficult to prove amortized bounds for incremental and decremental algorithms. In this paper we consider partially dynamic versions of three classic problems in graph theory. Based on popular conjectures we show that: -- No algorithm with amortized update time $O(n^{1-\varepsilon})$ exists for incremental or decremental maximum cardinality bipartite matching. This significantly improves on the $O(m^{1/2-\varepsilon})$ bound for sparse graphs of Henzinger et al. [STOC'15] and $O(n^{1/3-\varepsilon})$ bound of Kopelowitz, Pettie and Porat. Our linear bound also appears more natural. In addition, the result we present separates the node-addition model from the edge insertion model, as an algorithm with total update time $O(m\sqrt{n})$ exists for the former by Bosek et al. [FOCS'14]. -- No algorithm with amortized update time $O(m^{1-\varepsilon})$ exists for incremental or decremental maximum flow in directed and weighted sparse graphs. No such lower bound was known for partially dynamic maximum flow previously. Furthermore no algorithm with amortized update time $O(n^{1-\varepsilon})$ exists for directed and unweighted graphs or undirected and weighted graphs. -- No algorithm with amortized update time $O(n^{1/2 - \varepsilon})$ exists for incremental or decremental $(4/3-\varepsilon')$-approximating the diameter of an unweighted graph. We also show a slightly stronger bound if node additions are allowed. [...]
Decentralised Norm Monitoring in Open Multi-Agent Systems
Venue: arXiv cs.MA 2016
Year: 2016

We consider the problem of detecting norm violations in open multi-agent systems (MAS). We show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations. The cost of providing the incentives is not borne by the MAS and does not come from fines charged for norm violations (fines may be impossible to levy in a system where agents are free to leave and rejoin again under a different identity). Instead, monitoring incentives come from (scrip) fees for accessing the services provided by the MAS. In some cases, perfect monitoring (and hence enforcement) can be achieved: no norms will be violated in equilibrium. In other cases, we show that, while it is impossible to achieve perfect enforcement, we can get arbitrarily close; we can make the probability of a norm violation in equilibrium arbitrarily small. We show using simulations that our theoretical results hold for multi-agent systems with as few as 1000 agents---the system rapidly converges to the steady-state distribution of scrip tokens necessary to ensure monitoring and then remains close to the steady state.
Preventive and Reactive Cyber Defense Dynamics Is Globally Stable
Venue: arXiv cs.CR 2016
Year: 2016

The recently proposed {\em cybersecurity dynamics} approach aims to understand cybersecurity from a holistic perspective by modeling the evolution of the global cybersecurity state. These models describe the interactions between the various kinds of cyber defenses and the various kinds of cyber attacks. We study a particular kind of cybersecurity dynamics caused by the interactions between preventive and reactive defenses (e.g., filtering and malware detection) against push- and pull-based cyber attacks (e.g., malware spreading and "drive-by download" attacks). The dynamics was previously shown to be globally stable in a {\em special} regime of the parameter universe, but little is known beyond this special regime. In this paper, we resolve an open problem in this domain by proving that the dynamics is globally stable in the {\em entire} parameter universe (i.e., the dynamics always converges to a unique equilibrium). We discuss the cybersecurity meanings and implications of this theoretic result. We also prove that the dynamics converges {\em exponentially} to the equilibrium except for a special parameter regime, in which case the dynamics converges {\em polynomially}. Since it is often difficult to compute the equilibrium, we propose new bounds of the equilibrium and numerically show that these bounds are tighter than those proposed in the literature.
Refinement types in Jolie
Venue: arXiv cs.SE 2016
Year: 2016

Jolie is the first language for microservices and it is currently dynamically type checked. This paper considers the opportunity to integrate dynamic and static type checking with the introduction of refinement types, verified via SMT solver. The integration of the two aspects allows a scenario where the static verification of internal services and the dynamic verification of (potentially malicious) external services cooperates in order to reduce testing effort and enhancing security.
Generating Realistic Synthetic Population Datasets
Venue: arXiv cs.DB 2016
Year: 2016

Modern studies of societal phenomena rely on the availability of large datasets capturing attributes and activities of synthetic, city-level, populations. For instance, in epidemiology, synthetic population datasets are necessary to study disease propagation and intervention measures before implementation. In social science, synthetic population datasets are needed to understand how policy decisions might affect preferences and behaviors of individuals. In public health, synthetic population datasets are necessary to capture diagnostic and procedural characteristics of patient records without violating confidentialities of individuals. To generate such datasets over a large set of categorical variables, we propose the use of the maximum entropy principle to formalize a generative model such that in a statistically well-founded way we can optimally utilize given prior information about the data, and are unbiased otherwise. An efficient inference algorithm is designed to estimate the maximum entropy model, and we demonstrate how our approach is adept at estimating underlying data distributions. We evaluate this approach against both simulated data and on US census datasets, and demonstrate its feasibility using an epidemic simulation application.
Forecasting the Flu: Designing Social Network Sensors for Epidemics
Venue: arXiv cs.SI 2016
Year: 2016

Early detection and modeling of a contagious epidemic can provide important guidance about quelling the contagion, controlling its spread, or the effective design of countermeasures. A topic of recent interest has been to design social network sensors, i.e., identifying a small set of people who can be monitored to provide insight into the emergence of an epidemic in a larger population. We formally pose the problem of designing social network sensors for flu epidemics and identify two different objectives that could be targeted in such sensor design problems. Using the graph theoretic notion of dominators we develop an efficient and effective heuristic for forecasting epidemics at lead time. Using six city-scale datasets generated by extensive microscopic epidemiological simulations involving millions of individuals, we illustrate the practical applicability of our methods and show significant benefits (up to twenty-two days more lead time) compared to other competitors. Most importantly, we demonstrate the use of surrogates or proxies for policy makers for designing social network sensors that require from nonintrusive knowledge of people to more information on the relationship among people. The results show that the more intrusive information we obtain, the longer lead time to predict the flu outbreak up to nine days.
Application Location Based Service (LBS) Location Search Palembang Nature-Based Android
Venue: arXiv cs.CY 2016
Year: 2016

With the development of information systems to make the operating system more diverse mobile devices, the emergence of the Android operating system that is open allows users to search for and acquire various information easily and quickly. Application Search Nature Places is an application that can help bring information on nearby Places Nature is all around. Can be used in the Android Operating System and Global Positioning System (GPS). To be able to use this application, users must be connected to the Internet because it requires data taken from Google Maps. The main facilities contained in this application is a feature that makes it Map and Route users in finding the intended location. With the LBS application is expected to provide information that is accurate, clear and precise to determine location points Nature Palembang, and can facilitate local and foreign tourists and the public, especially the city of Palembang.