OpenRaiser/Intern-Atlas huggingface dataset:
Robust Online Matrix Factorization for Dynamic Background Subtraction
Venue: arXiv cs.CV 2017
Year: 2017

We propose an effective online background subtraction method, which can be robustly applied to practical videos that have variations in both foreground and background. Different from previous methods which often model the foreground as Gaussian or Laplacian distributions, we model the foreground for each frame with a specific mixture of Gaussians (MoG) distribution, which is updated online frame by frame. Particularly, our MoG model in each frame is regularized by the learned foreground/background knowledge in previous frames. This makes our online MoG model highly robust, stable and adaptive to practical foreground and background variations. The proposed model can be formulated as a concise probabilistic MAP model, which can be readily solved by EM algorithm. We further embed an affine transformation operator into the proposed model, which can be automatically adjusted to fit a wide range of video background transformations and make the method more robust to camera movements. With using the sub-sampling technique, the proposed method can be accelerated to execute more than 250 frames per second on average, meeting the requirement of real-time background subtraction for practical video processing tasks. The superiority of the proposed method is substantiated by extensive experiments implemented on synthetic and real videos, as compared with state-of-the-art online and offline background subtraction methods.
Supervised Complementary Entity Recognition with Augmented Key-value Pairs of Knowledge
Venue: arXiv cs.CL 2017
Year: 2017

Extracting opinion targets is an important task in sentiment analysis on product reviews and complementary entities (products) are one important type of opinion targets that may work together with the reviewed product. In this paper, we address the problem of Complementary Entity Recognition (CER) as a supervised sequence labeling with the capability of expanding domain knowledge as key-value pairs from unlabeled reviews, by automatically learning and enhancing knowledge-based features. We use Conditional Random Field (CRF) as the base learner and augment CRF with knowledge-based features (called the Knowledge-based CRF or KCRF for short). We conduct experiments to show that KCRF effectively improves the performance of supervised CER task.
Learning Network Structures from Contagion
Venue: arXiv cs.LG 2017
Year: 2017

In 2014, Amin, Heidari, and Kearns proved that tree networks can be learned by observing only the infected set of vertices of the contagion process under the independent cascade model, in both the active and passive query models. They also showed empirically that simple extensions of their algorithms work on sparse networks. In this work, we focus on the active model. We prove that a simple modification of Amin et al.'s algorithm works on more general classes of networks, namely (i) networks with large girth and low path growth rate, and (ii) networks with bounded degree. This also provides partial theoretical explanation for Amin et al.'s experiments on sparse networks.
Role Playing Learning for Socially Concomitant Mobile Robot Navigation
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we present the Role Playing Learning (RPL) scheme for a mobile robot to navigate socially with its human companion in populated environments. Neural networks (NN) are constructed to parameterize a stochastic policy that directly maps sensory data collected by the robot to its velocity outputs, while respecting a set of social norms. An efficient simulative learning environment is built with maps and pedestrians trajectories collected from a number of real-world crowd data sets. In each learning iteration, a robot equipped with the NN policy is created virtually in the learning environment to play itself as a companied pedestrian and navigate towards a goal in a socially concomitant manner. Thus, we call this process Role Playing Learning, which is formulated under a reinforcement learning (RL) framework. The NN policy is optimized end-to-end using Trust Region Policy Optimization (TRPO), with consideration of the imperfectness of robot's sensor measurements. Simulative and experimental results are provided to demonstrate the efficacy and superiority of our method.
Machine Learned Learning Machines
Venue: arXiv cs.AI 2017
Year: 2017

There are two common approaches for optimizing the performance of a machine: genetic algorithms and machine learning. A genetic algorithm is applied over many generations whereas machine learning works by applying feedback until the system meets a performance threshold. Though these are methods that typically operate separately, we combine evolutionary adaptation and machine learning into one approach. Our focus is on machines that can learn during their lifetime, but instead of equipping them with a machine learning algorithm we aim to let them evolve their ability to learn by themselves. We use evolvable networks of probabilistic and deterministic logic gates, known as Markov Brains, as our computational model organism. The ability of Markov Brains to learn is augmented by a novel adaptive component that can change its computational behavior based on feedback. We show that Markov Brains can indeed evolve to incorporate these feedback gates to improve their adaptability to variable environments. By combining these two methods, we now also implemented a computational model that can be used to study the evolution of learning.
Increasing the Efficiency of Sparse Matrix-Matrix Multiplication with a 2.5D Algorithm and One-Sided MPI
Venue: arXiv cs.DC 2017
Year: 2017

Matrix-matrix multiplication is a basic operation in linear algebra and an essential building block for a wide range of algorithms in various scientific fields. Theory and implementation for the dense, square matrix case are well-developed. If matrices are sparse, with application-specific sparsity patterns, the optimal implementation remains an open question. Here, we explore the performance of communication reducing 2.5D algorithms and one-sided MPI communication in the context of linear scaling electronic structure theory. In particular, we extend the DBCSR sparse matrix library, which is the basic building block for linear scaling electronic structure theory and low scaling correlated methods in CP2K. The library is specifically designed to efficiently perform block-sparse matrix-matrix multiplication of matrices with a relatively large occupation. Here, we compare the performance of the original implementation based on Cannon's algorithm and MPI point-to-point communication, with an implementation based on MPI one-sided communications (RMA), in both a 2D and a 2.5D approach. The 2.5D approach trades memory and auxiliary operations for reduced communication, which can lead to a speedup if communication is dominant. The 2.5D algorithm is somewhat easier to implement with one-sided communications. A detailed description of the implementation is provided, also for non ideal processor topologies, since this is important for actual applications. Given the importance of the precise sparsity pattern, and even the actual matrix data, which decides the effective fill-in upon multiplication, the tests are performed within the CP2K package with application benchmarks. Results show a substantial boost in performance for the RMA based 2.5D algorithm, up to 1.80x, which is observed to increase with the number of involved processes in the parallelization.
Learning Belief Network Structure From Data under Causal Insufficiency
Venue: arXiv cs.AI 2017
Year: 2017

Though a belief network (a representation of the joint probability distribution, see [3]) and a causal network (a representation of causal relationships [14]) are intended to mean different things, they are closely related. Both assume an underlying dag (directed acyclic graph) structure of relations among variables and if Markov condition and faithfulness condition [15] are met, then a causal network is in fact a belief network. The difference comes to appearance when we recover belief network and causal network structure from data. A causal network structure may be impossible to recover completely from data as not all directions of causal links may be uniquely determined [15]. Fortunately, if we deal with causally sufficient sets of variables (that is whenever significant influence variables are not omitted from observation), then there exists the possibility to identify the family of belief networks a causal network belongs to [16]. Regrettably, to our knowledge, a similar result is not directly known for causally insufficient sets of variables. Spirtes, Glymour and Scheines developed a CI algorithm to handle this situation, but it leaves some important questions open. The big open question is whether or not the bidirectional edges (that is indications of a common cause) are the only ones necessary to develop a belief network out of the product of CI, or must there be some other hidden variables added (e.g. by guessing). This paper is devoted to settling this question.
Deep Learning for Ontology Reasoning
Venue: arXiv cs.AI 2017
Year: 2017

In this work, we present a novel approach to ontology reasoning that is based on deep learning rather than logic-based formal reasoning. To this end, we introduce a new model for statistical relational learning that is built upon deep recursive neural networks, and give experimental evidence that it can easily compete with, or even outperform, existing logic-based reasoners on the task of ontology reasoning. More precisely, we compared our implemented system with one of the best logic-based ontology reasoners at present, RDFox, on a number of large standard benchmark datasets, and found that our system attained high reasoning quality, while being up to two orders of magnitude faster.
DNN-based uncertainty estimation for weighted DNN-HMM ASR
Venue: arXiv cs.SD 2017
Year: 2017

In this paper, the uncertainty is defined as the mean square error between a given enhanced noisy observation vector and the corresponding clean one. Then, a DNN is trained by using enhanced noisy observation vectors as input and the uncertainty as output with a training database. In testing, the DNN receives an enhanced noisy observation vector and delivers the estimated uncertainty. This uncertainty in employed in combination with a weighted DNN-HMM based speech recognition system and compared with an existing estimation of the noise cancelling uncertainty variance based on an additive noise model. Experiments were carried out with Aurora-4 task. Results with clean, multi-noise and multi-condition training are presented.
Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We pursue a study of the Generalized Demand Matching problem, a common generalization of the $b$-Matching and Knapsack problems. Here, we are given a graph with vertex capacities, edge profits, and asymmetric demands on the edges. The goal is to find a maximum-profit subset of edges so the demands of chosen edges do not violate vertex capacities. This problem is APX-hard and constant-factor approximations are known. Our results fall into two categories. First, using iterated relaxation and various filtering strategies, we show with an efficient rounding algorithm if an additional matroid structure $\mathcal M$ is given and we further only allow sets $F \subseteq E$ that are independent in $\mathcal M$, the natural LP relaxation has an integrality gap of at most $\frac{25}{3} \approx 8.333$. This can be improved in various special cases, for example we improve over the 15-approximation for the previously-studied Coupled Placement problem [Korupolu et al. 2014] by giving a $7$-approximation. Using similar techniques, we show the problem of computing a minimum-cost base in $\mathcal M$ satisfying vertex capacities admits a $(1,3)$-bicriteria approximation. This improves over the previous $(1,4)$-approximation in the special case that $\mathcal M$ is the graphic matroid over the given graph [Fukanaga and Nagamochi, 2009]. Second, we show Demand Matching admits a polynomial-time approximation scheme in graphs that exclude a fixed minor. If all demands are polynomially-bounded integers, this is somewhat easy using dynamic programming in bounded-treewidth graphs. Our main technical contribution is a sparsification lemma allowing us to scale the demands to be used in a more intricate dynamic programming algorithm, followed by randomized rounding to filter our scaled-demand solution to a feasible solution.
On the Fundamental Limits of Random Non-orthogonal Multiple Access in Cellular Massive IoT
Venue: arXiv cs.IT 2017
Year: 2017

Machine-to-machine (M2M) constitutes the communication paradigm at the basis of Internet of Things (IoT) vision. M2M solutions allow billions of multi-role devices to communicate with each other or with the underlying data transport infrastructure without, or with minimal, human intervention. Current solutions for wireless transmissions originally designed for human-based applications thus require a substantial shift to cope with the capacity issues in managing a huge amount of M2M devices. In this paper, we consider the multiple access techniques as promising solutions to support a large number of devices in cellular systems with limited radio resources. We focus on non-orthogonal multiple access (NOMA) where, with the aim to increase the channel efficiency, the devices share the same radio resources for their data transmission. This has been shown to provide optimal throughput from an information theoretic point of view.We consider a realistic system model and characterise the system performance in terms of throughput and energy efficiency in a NOMA scenario with a random packet arrival model, where we also derive the stability condition for the system to guarantee the performance.
Towards Psychometrics-based Friend Recommendations in Social Networking Services
Venue: arXiv cs.SI 2017
Year: 2017

Two of the defining elements of Social Networking Services are the social profile, containing information about the user, and the social graph, containing information about the connections between users. Social Networking Services are used to connect to known people as well as to discover new contacts. Current friend recommendation mechanisms typically utilize the social graph. In this paper, we argue that psychometrics, the field of measuring personality traits, can help make meaningful friend recommendations based on an extended social profile containing collected smartphone sensor data. This will support the development of highly distributed Social Networking Services without central knowledge of the social graph.
Secret sharing on large girth graphs
Venue: arXiv cs.IT 2017
Year: 2017

We investigate graph based secret sharing schemes and its information ratio, also called complexity, measuring the maximal amount of information the vertices has to store. It was conjectured that in large girth graphs, where the interaction between far away nodes is restricted to a single path, this ratio is bounded. This conjecture was supported by several result, most notably by a result of Csirmaz and Ligeti saying that the complexity of graphs with girth at least six and no neighboring high degree vertices is strictly below 2. In this paper we refute the above conjecture. First, a family of $d$-regular graphs is defined iteratively such that the complexity of these graphs is the largest possible $(d+1)/2$ allowed by Stinson's bound. This part extends earlier results of van Dijk and Blundo et al, and uses the so-called entropy method. Second, using combinatorial arguments, we show that this family contains graphs with arbitrary large girth. In particular, we obtain the following purely combinatorial result, which might be interesting on its own: there are $d$-regular graphs with arbitrary large girth such that any fractional edge-cover by stars (or by complete multipartite graphs) must cover some vertex $(d+1)/2$ times.
On the effectiveness of the truth-spreading/rumor-blocking strategy for restraining rumors
Venue: arXiv cs.SI 2017
Year: 2017

Spreading truths and blocking rumors are two typical strategies for inhibiting rumors. In practice, a tradeoff between the two strategies, which is known as the TSRB strategy, may achieve a better cost-effectiveness. This paper is devoted to assessing the effectiveness of the TSRB strategy. For that purpose, an individual-level spreading model (the generic URQT model) capturing the interaction between a rumor and the truth is established. Under the model, a set of criteria for the dying out of a rumor is presented. These criteria capture the combined influence of the basic parameters and the network structures on the effectiveness of the TSRB strategy. Experimental results show that, when the rumor dies out, the dynamics of a simplified URQT model (the linear URQT model) fits well with the actual rumor-truth interacting process. Therefore, the generic URQT model and sometimes the linear URQT model provide a proper basis for assessing the effectiveness of the TSRB strategy.
Approximation of LRU Caches Miss Rate: Application to Power-law Popularities
Venue: arXiv cs.PF 2017
Year: 2017

Building on the 1977 pioneering work of R. Fagin, we give a closed-form expression for the approximated Miss Rate (MR) of LRU Caches assuming a power-law popularity. Asymptotic behavior of this expression is an already known result when power-law parameter is above 1. It is extended to any value of the parameter. In addition, we bring a new analysis of the conditions (cache relative size, popularity parameter) under which the ratio of LRU MR to Static MR is worst-case.
Tracking System Behaviour from Resource Usage Data
Venue: arXiv cs.PF 2017
Year: 2017

Resource usage data, collected using tools such as TACC Stats, capture the resource utilization by nodes within a high performance computing system. We present methods to analyze the resource usage data to understand the system performance and identify performance anomalies. The core idea is to model the data as a three-way tensor corresponding to the compute nodes, usage metrics, and time. Using the reconstruction error between the original tensor and the tensor reconstructed from a low rank tensor decomposition, as a scalar performance metric, enables us to monitor the performance of the system in an online fashion. This error statistic is then used for anomaly detection that relies on the assumption that the normal/routine behavior of the system can be captured using a low rank approx- imation of the original tensor. We evaluate the performance of the algorithm using information gathered from system logs and show that the performance anomalies identified by the proposed method correlates with critical errors reported in the system logs. Results are shown for data collected for 2013 from the Lonestar4 system at the Texas Advanced Computing Center (TACC)
On The Limitation of Some Fully Observable Multiple Session Resilient Shoulder Surfing Defense Mechanisms
Venue: arXiv cs.CR 2017
Year: 2017

Using password based authentication technique, a system maintains the login credentials (username, password) of the users in a password file. Once the password file is compromised, an adversary obtains both the login credentials. With the advancement of technology, even if a password is maintained in hashed format, then also the adversary can invert the hashed password to get the original one. To mitigate this threat, most of the systems nowadays store some system generated fake passwords (also known as honeywords) along with the original password of a user. This type of setup confuses an adversary while selecting the original password. If the adversary chooses any of these honeywords and submits that as a login credential, then system detects the attack. A large number of significant work have been done on designing methodologies (identified as $\text{M}^{\text{DS}}_{\text{OA}}$) that can protect password against observation or, shoulder surfing attack. Under this attack scenario, an adversary observes (or records) the login information entered by a user and later uses those credentials to impersonate the genuine user. In this paper, we have shown that because of their design principle, a large subset of $\text{M}^{\text{DS}}_{\text{OA}}$ (identified as $\text{M}^{\text{FODS}}_{\text{SOA}}$) cannot afford to store honeywords in password file. Thus these methods, belonging to $\text{M}^{\text{FODS}}_{\text{SOA}}$, are unable to provide any kind of security once password file gets compromised. Through our contribution in this paper, by still using the concept of honeywords, we have proposed few generic principles to mask the original password of $\text{M}^{\text{FODS}}_{\text{SOA}}$ category methods. We also consider few well-established methods like S3PAS, CHC, PAS and COP belonging to $\text{M}^{\text{FODS}}_{\text{SOA}}$, to show that proposed idea is implementable in practice.
Towards Learned Clauses Database Reduction Strategies Based on Dominance Relationship
Venue: arXiv cs.AI 2017
Year: 2017

Clause Learning is one of the most important components of a conflict driven clause learning (CDCL) SAT solver that is effective on industrial instances. Since the number of learned clauses is proved to be exponential in the worse case, it is necessary to identify the most relevant clauses to maintain and delete the irrelevant ones. As reported in the literature, several learned clauses deletion strategies have been proposed. However the diversity in both the number of clauses to be removed at each step of reduction and the results obtained with each strategy creates confusion to determine which criterion is better. Thus, the problem to select which learned clauses are to be removed during the search step remains very challenging. In this paper, we propose a novel approach to identify the most relevant learned clauses without favoring or excluding any of the proposed measures, but by adopting the notion of dominance relationship among those measures. Our approach bypasses the problem of the diversity of results and reaches a compromise between the assessments of these measures. Furthermore, the proposed approach also avoids another non-trivial problem which is the amount of clauses to be deleted at each reduction of the learned clause database.
Generating Witness of Non-Bisimilarity for the pi-Calculus
Venue: arXiv cs.LO 2017
Year: 2017

In the logic programming paradigm, it is difficult to develop an elegant solution for generating distinguishing formulae that witness the failure of open-bisimilarity between two pi-calculus processes; this was unexpected because the semantics of the pi-calculus and open bisimulation have already been elegantly specified in higher-order logic programming systems. Our solution using Haskell defines the formulae generation as a tree transformation from the forest of all nondeterministic bisimulation steps to a pair of distinguishing formulae. Thanks to laziness in Haskell, only the necessary paths demanded by the tree transformation function are generated. Our work demonstrates that Haskell and its libraries provide an attractive platform for symbolically analyzing equivalence properties of labeled transition systems in an environment sensitive setting.