OpenRaiser/Intern-Atlas huggingface dataset:
Mining Massive Hierarchical Data Using a Scalable Probabilistic Graphical Model
Venue: arXiv cs.AI 2015
Year: 2015

Probabilistic Graphical Models (PGM) are very useful in the fields of machine learning and data mining. The crucial limitation of those models,however, is the scalability. The Bayesian Network, which is one of the most common PGMs used in machine learning and data mining, demonstrates this limitation when the training data consists of random variables, each of them has a large set of possible values. In the big data era, one would expect new extensions to the existing PGMs to handle the massive amount of data produced these days by computers, sensors and other electronic devices. With hierarchical data - data that is arranged in a treelike structure with several levels - one would expect to see hundreds of thousands or millions of values distributed over even just a small number of levels. When modeling this kind of hierarchical data across large data sets, Bayesian Networks become infeasible for representing the probability distributions. In this paper we introduce an extension to Bayesian Networks to handle massive sets of hierarchical data in a reasonable amount of time and space. The proposed model achieves perfect precision of 1.0 and high recall of 0.93 when it is used as multi-label classifier for the annotation of mass spectrometry data. On another data set of 1.5 billion search logs provided by CareerBuilder.com the model was able to predict latent semantic relationships between search keywords with accuracy up to 0.80.
Sending a Bivariate Gaussian Source Over a Gaussian MAC with Unidirectional Conferencing Encoders
Venue: arXiv cs.IT 2015
Year: 2015

We consider the transmission of a memoryless bivariate Gaussian source over a two-user additive Gaussian multiple-access channel with unidirectional conferencing encoders. Here, prior to each transmission block, Encoder 1, which observes the first source component, is allowed to communicate with Encoder 2, which observes the second source component, via a unidirectional noise-free bit-pipe of given capacity. The main results of this work are sufficient conditions and a necessary condition for the achievability of a distortion pair expressed as a function of the channel SNR and of the source correlation. The main sufficient condition is obtained by an extension of the vector-quantizer scheme suggested by Lapidoth-Tinguely, for the case without conferencing, to the case with unidirectional conference. In the high-SNR regime, and when the capacity of the conference channel is unlimited, these necessary and sufficient conditions are shown to agree. We evaluate the precise high-SNR asymptotics for a subset of distortion pairs when the capacity of the conference channel is unlimited in which case we show that a separation based scheme attains these optimal distortion pairs. However, with symmetric average-power constraints and fixed conferencing capacity, at high-SNR the latter separation based scheme is shown to be suboptimal.
A Simple Baseline for Travel Time Estimation using Large-Scale Trip Data
Venue: arXiv cs.LG 2015
Year: 2015

The increased availability of large-scale trajectory data around the world provides rich information for the study of urban dynamics. For example, New York City Taxi Limousine Commission regularly releases source-destination information about trips in the taxis they regulate. Taxi data provide information about traffic patterns, and thus enable the study of urban flow -- what will traffic between two locations look like at a certain date and time in the future? Existing big data methods try to outdo each other in terms of complexity and algorithmic sophistication. In the spirit of "big data beats algorithms", we present a very simple baseline which outperforms state-of-the-art approaches, including Bing Maps and Baidu Maps (whose APIs permit large scale experimentation). Such a travel time estimation baseline has several important uses, such as navigation (fast travel time estimates can serve as approximate heuristics for A search variants for path finding) and trip planning (which uses operating hours for popular destinations along with travel time estimates to create an itinerary).
Improper Graceful and Odd-graceful Labellings of Graph Theory
Venue: arXiv cs.DM 2015
Year: 2015

In this paper we define some new labellings for trees, called the in-improper and out-improper odd-graceful labellings such that some trees labelled with the new labellings can induce graceful graphs having at least a cycle. We, next, apply the new labellings to construct large scale of graphs having improper graceful/odd-graceful labellings or having graceful/odd-graceful labellings.
On the Foundations of the Brussels Operational-Realistic Approach to Cognition
Venue: arXiv cs.AI 2015
Year: 2015

The scientific community is becoming more and more interested in the research that applies the mathematical formalism of quantum theory to model human decision-making. In this paper, we provide the theoretical foundations of the quantum approach to cognition that we developed in Brussels. These foundations rest on the results of two decade studies on the axiomatic and operational-realistic approaches to the foundations of quantum physics. The deep analogies between the foundations of physics and cognition lead us to investigate the validity of quantum theory as a general and unitary framework for cognitive processes, and the empirical success of the Hilbert space models derived by such investigation provides a strong theoretical confirmation of this validity. However, two situations in the cognitive realm, 'question order effects' and 'response replicability', indicate that even the Hilbert space framework could be insufficient to reproduce the collected data. This does not mean that the mentioned operational-realistic approach would be incorrect, but simply that a larger class of measurements would be in force in human cognition, so that an extended quantum formalism may be needed to deal with all of them. As we will explain, the recently derived 'extended Bloch representation' of quantum theory (and the associated 'general tension-reduction' model) precisely provides such extended formalism, while remaining within the same unitary interpretative framework.
Privacy Preservation in Distributed Subgradient Optimization Algorithms
Venue: arXiv cs.DC 2015
Year: 2015

Privacy preservation is becoming an increasingly important issue in data mining and machine learning. In this paper, we consider the privacy preserving features of distributed subgradient optimization algorithms. We first show that a well-known distributed subgradient synchronous optimization algorithm, in which all agents make their optimization updates simultaneously at all times, is not privacy preserving in the sense that the malicious agent can learn other agents' subgradients asymptotically. Then we propose a distributed subgradient projection asynchronous optimization algorithm without relying on any existing privacy preservation technique, where agents can exchange data between neighbors directly. In contrast to synchronous algorithms, in the new asynchronous algorithm agents make their optimization updates asynchronously. The introduced projection operation and asynchronous optimization mechanism can guarantee that the proposed asynchronous optimization algorithm is privacy preserving. Moreover, we also establish the optimal convergence of the newly proposed algorithm. The proposed privacy preservation techniques shed light on developing other privacy preserving distributed optimization algorithms.
Sequence Numbers Do Not Guarantee Loop Freedom; AODV Can Yield Routing Loops
Venue: arXiv cs.NI 2015
Year: 2015

In the area of mobile ad-hoc networks and wireless mesh networks, sequence numbers are often used in routing protocols to avoid routing loops. It is commonly stated in protocol specifications that sequence numbers are sufficient to guarantee loop freedom if they are monotonically increased over time. A classical example for the use of sequence numbers is the popular Ad hoc On-Demand Distance Vector (AODV) routing protocol. The loop freedom of AODV is not only a common belief, it has been claimed in the abstract of its RFC and at least two proofs have been proposed. AODV-based protocols such as AODVv2 (DYMO) and HWMP also claim loop freedom due to the same use of sequence numbers. In this paper we show that AODV is not a priori loop free; by this we counter the proposed proofs in the literature. In fact, loop freedom hinges on non-evident assumptions to be made when resolving ambiguities occurring in the RFC. Thus, monotonically increasing sequence numbers, by themselves, do not guarantee loop freedom.
Metric Temporal Logic with Counting
Venue: arXiv cs.LO 2015
Year: 2015

Ability to count number of occurrences of events within a specified time interval is very useful in specification of resource bounded real time computation. In this paper, we study an extension of Metric Temporal Logic ($\mathsf{MTL}$) with two different counting modalities called $\mathsf{C}$ and $\mathsf{UT}$ (until with threshold), which enhance the expressive power of $\mathsf{MTL}$ in orthogonal fashion. We confine ourselves only to the future fragment of $\mathsf{MTL}$ interpreted in a pointwise manner over finite timed words. We provide a comprehensive study of the expressive power of logic $\mathsf{CTMTL}$ and its fragments using the technique of EF games extended with suitable counting moves. Finally, as our main result, we establish the decidability of $\mathsf{CTMTL}$ by giving an equisatisfiable reduction from $\mathsf{CTMTL}$ to $\mathsf{MTL}$. The reduction provides one more example of the use of temporal projections with oversampling introduced earlier for proving decidability. Our reduction also implies that $\mathsf{MITL}$ extended with $\mathsf{C}$ and $\mathsf{UT}$ modalities is elementarily decidable.
Actor-Action Semantic Segmentation with Grouping Process Models
Venue: arXiv cs.CV 2015
Year: 2015

Actor-action semantic segmentation made an important step toward advanced video understanding problems: what action is happening; who is performing the action; and where is the action in space-time. Current models for this problem are local, based on layered CRFs, and are unable to capture long-ranging interaction of video parts. We propose a new model that combines these local labeling CRFs with a hierarchical supervoxel decomposition. The supervoxels provide cues for possible groupings of nodes, at various scales, in the CRFs to encourage adaptive, high-order groups for more effective labeling. Our model is dynamic and continuously exchanges information during inference: the local CRFs influence what supervoxels in the hierarchy are active, and these active nodes influence the connectivity in the CRF; we hence call it a grouping process model. The experimental results on a recent large-scale video dataset show a large margin of 60% relative improvement over the state of the art, which demonstrates the effectiveness of the dynamic, bidirectional flow between labeling and grouping.
Around Context-Free Grammars -- a Normal Form, a Representation Theorem, and a Regular Approximation
Venue: arXiv cs.FL 2015
Year: 2015

We introduce a normal form for context-free grammars, called Dyck normal form. This is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals. This pairwise property allows to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. We prove that for each context-free language L, there exist an integer K and a homomorphism h such that L=h(D'_K), where D'_K is a subset of the one-sided Dyck language over K letters. Through a transition-like diagram for a context-free grammar in Dyck normal form, we effectively build a regular language R that satisfies the Chomsky-Schutzenberger theorem. Using graphical approaches we refine R such that the Chomsky-Schutzenberger theorem still holds. Based on this readjustment we sketch a transition diagram for a regular grammar that generates a regular superset approximation for the initial context-free language.
Load Balancing Congestion Games and their Asymptotic Behavior
Venue: arXiv cs.GT 2015
Year: 2015

A central question in routing games has been to establish conditions for the uniqueness of the equilibrium, either in terms of network topology or in terms of costs. This question is well understood in two classes of routing games. The first is the non-atomic routing introduced by Wardrop on 1952 in the context of road traffic in which each player (car) is infinitesimally small; a single car has a negligible impact on the congestion. Each car wishes to minimize its expected delay. Under arbitrary topology, such games are known to have a convex potential and thus a unique equilibrium. The second framework is splitable atomic games: there are finitely many players, each controlling the route of a population of individuals (let them be cars in road traffic or packets in the communication networks). In this paper, we study two other frameworks of routing games in which each of several players has an integer number of connections (which are population of packets) to route and where there is a constraint that a connection cannot be split. Through a particular game with a simple three link topology, we identify various novel and surprising properties of games within these frameworks. We show in particular that equilibria are non unique even in the potential game setting of Rosenthal with strictly convex link costs. We further show that non-symmetric equilibria arise in symmetric networks. I. INTRODUCTION A central question in routing games has been to establish conditions for the uniqueness of the equilibria, either in terms of the network topology or in terms of the costs. A survey on these issues is given in [1]. The question of uniqueness of equilibria has been studied in two different frameworks. The first, which we call F1, is the non-atomic routing introduced by Wardrop on 1952 in the context of road traffic in which each player (car) is infinitesimally small; a single car has a negligible impact on the congestion. Each car wishes to minimize its expected delay. Under arbitrary topology, such games are known to have a convex potential and thus have a unique equilibrium [2]. The second framework, denoted by F2, is splitable atomic games. There are finitely many players, each controlling the route of a population of individuals. This type of games have already been studied in the context of road traffic by Haurie and Marcotte [3] but have become central in the telecom community to model routing decisions of Internet Service Providers that can decide how to split the traffic of their subscribers among various routes so as to minimize network congestion [4]. In this paper we study properties of equilibria in two other frameworks of routing games which exhibit surprising
On the security of a class of diffusion mechanisms for image encryption
Venue: arXiv cs.CR 2015
Year: 2015

The need for fast and strong image cryptosystems motivates researchers to develop new techniques to apply traditional cryptographic primitives in order to exploit the intrinsic features of digital images. One of the most popular and mature technique is the use of complex ynamic phenomena, including chaotic orbits and quantum walks, to generate the required key stream. In this paper, under the assumption of plaintext attacks we investigate the security of a classic diffusion mechanism (and of its variants) used as the core cryptographic rimitive in some image cryptosystems based on the aforementioned complex dynamic phenomena. We have theoretically found that regardless of the key schedule process, the data complexity for recovering each element of the equivalent secret key from these diffusion mechanisms is only O(1). The proposed analysis is validated by means of numerical examples. Some additional cryptographic applications of our work are also discussed.
Faster Maximium Priority Matchings in Bipartite Graphs
Venue: arXiv cs.DS 2015
Year: 2015

A maximum priority matching is a matching in an undirected graph that maximizes a priority score defined with respect to given vertex priorities. An earlier paper showed how to find maximum priority matchings in unweighted graphs. This paper describes an algorithm for bipartite graphs that is faster when the number of distinct priority classes is limited. For graphs with $k$ distinct priority classes it runs in $O(kmn^{1/2})$ time, where $n$ is the number of vertices in the graph and $m$ is the number of edges.
Disambiguation of Patent Inventors and Assignees Using High-Resolution Geolocation Data
Venue: arXiv cs.DL 2015
Year: 2015

Patent data represent a significant source of information on innovation and the evolution of technology through networks of citations, co-invention and co-assignment of new patents. A major obstacle to extracting useful information from this data is the problem of name disambiguation: linking alternate spellings of individuals or institutions to a single identifier to uniquely determine the parties involved in the creation of a technology. In this paper, we describe a new algorithm that uses high-resolution geolocation to disambiguate both inventor and assignees on more than 3.6 million patents found in the European Patent Office (EPO), under the Patent Cooperation treaty (PCT), and in the US Patent and Trademark Office (USPTO). We show that our algorithm has both high precision and recall in comparison to a manual disambiguation of EPO assignee names in Boston and Paris, and show it performs well for a benchmark of USPTO inventor names that can be linked to a high-resolution address (but poorly for inventors that never provided a high quality address). The most significant benefit of this work is the high quality assignee disambiguation with worldwide coverage coupled with an inventor disambiguation that is competitive with other state of the art approaches. To our knowledge this is the broadest and most accurate simultaneous disambiguation and cross-linking of the inventor and assignee names for a significant fraction of patents in these three major patent collections.
Online Model Estimation for Predictive Thermal Control of Buildings
Venue: arXiv cs.SY 2015
Year: 2015

This study proposes a general, scalable method to learn control-oriented thermal models of buildings that could enable wide-scale deployment of cost-effective predictive controls. An Unscented Kalman Filter augmented for parameter and disturbance estimation is shown to accurately learn and predict a building's thermal response. Recent studies of heating, ventilating, and air conditioning (HVAC) systems have shown significant energy savings with advanced model predictive control (MPC). A scalable cost-effective method to readily acquire accurate, robust models of individual buildings' unique thermal envelopes has historically been elusive and hindered the widespread deployment of prediction-based control systems. Continuous commissioning and lifetime performance of these thermal models requires deployment of on-line data-driven system identification and parameter estimation routines. We propose a novel gray-box approach using an Unscented Kalman Filter based on a multi-zone thermal network and validate it with EnergyPlus simulation data. The filter quickly learns parameters of a thermal network during periods of known or constrained loads and then characterizes unknown loads in order to provide accurate 24+ hour energy predictions. This study extends our initial investigation by formalizing parameter and disturbance estimation routines and demonstrating results across a year-long study.
Deep Learning Applied to Image and Text Matching
Venue: arXiv cs.LG 2015
Year: 2015

The ability to describe images with natural language sentences is the hallmark for image and language understanding. Such a system has wide ranging applications such as annotating images and using natural sentences to search for images.In this project we focus on the task of bidirectional image retrieval: such asystem is capable of retrieving an image based on a sentence (image search) andretrieve sentence based on an image query (image annotation). We present asystem based on a global ranking objective function which uses a combinationof convolutional neural networks (CNN) and multi layer perceptrons (MLP).It takes a pair of image and sentence and processes them in different channels,finally embedding it into a common multimodal vector space. These embeddingsencode abstract semantic information about the two inputs and can be comparedusing traditional information retrieval approaches. For each such pair, the modelreturns a score which is interpretted as a similarity metric. If this score is high,the image and sentence are likely to convey similar meaning, and if the score is low then they are likely not to. The visual input is modeled via deep convolutional neural network. On theother hand we explore three models for the textual module. The first one isbag of words with an MLP. The second one uses n-grams (bigram, trigrams,and a combination of trigram & skip-grams) with an MLP. The third is morespecialized deep network specific for modeling variable length sequences (SSE).We report comparable performance to recent work in the field, even though ouroverall model is simpler. We also show that the training time choice of how wecan generate our negative samples has a significant impact on performance, and can be used to specialize the bi-directional system in one particular task.
Artificial neural network approach for condition-based maintenance
Venue: arXiv cs.NE 2015
Year: 2015

In this research, computerized maintenance management will be investigated. The rise of maintenance cost forced the research community to look for more effective ways to schedule maintenance operations. Using computerized models to come up with optimal maintenance policy has led to better equipment utilization and lower costs. This research adopts Condition-Based Maintenance model where the maintenance decision is generated based on equipment conditions. Artificial Neural Network technique is proposed to capture and analyze equipment condition signals which lead to higher level of knowledge gathering. This knowledge is used to accurately estimate equipment failure time. Based on these estimations, an optimal maintenance management policy can be achieved.
Predictive and statistical analyses for academic advisory support
Venue: arXiv cs.OH 2015
Year: 2015

The ability to recognize weakness of students and solving any problem may confront them in timely fashion is always a target of all educational institutions. This study was designed to explore how can predictive and statistical analysis support the academic work of adviser mainly in analysis progress of students . The sample consisted of a total of 249 undergraduate students: 46 % of them were Female and 54% Male. A one-way analysis of variance and t-test were conducted to analysis if there was different behavior in registering courses. Predictive data mining is used for support adviser in decision making. Several classification techniques with 10-fold Cross validation were applied. Among of them, C 4.5 constitutes the best agreement among the finding results.