OpenRaiser/Intern-Atlas huggingface dataset:
A Mid-level Video Representation based on Binary Descriptors: A Case Study for Pornography Detection
Venue: arXiv cs.CV 2016
Year: 2016

With the growing amount of inappropriate content on the Internet, such as pornography, arises the need to detect and filter such material. The reason for this is given by the fact that such content is often prohibited in certain environments (e.g., schools and workplaces) or for certain publics (e.g., children). In recent years, many works have been mainly focused on detecting pornographic images and videos based on visual content, particularly on the detection of skin color. Although these approaches provide good results, they generally have the disadvantage of a high false positive rate since not all images with large areas of skin exposure are necessarily pornographic images, such as people wearing swimsuits or images related to sports. Local feature based approaches with Bag-of-Words models (BoW) have been successfully applied to visual recognition tasks in the context of pornography detection. Even though existing methods provide promising results, they use local feature descriptors that require a high computational processing time yielding high-dimensional vectors. In this work, we propose an approach for pornography detection based on local binary feature extraction and BossaNova image representation, a BoW model extension that preserves more richly the visual information. Moreover, we propose two approaches for video description based on the combination of mid-level representations namely BossaNova Video Descriptor (BNVD) and BoW Video Descriptor (BoW-VD). The proposed techniques are promising, achieving an accuracy of 92.40%, thus reducing the classification error by 16% over the current state-of-the-art local features approach on the Pornography dataset.
Which Learning Algorithms Can Generalize Identity-Based Rules to Novel Inputs?
Venue: arXiv cs.CL 2016
Year: 2016

We propose a novel framework for the analysis of learning algorithms that allows us to say when such algorithms can and cannot generalize certain patterns from training data to test data. In particular we focus on situations where the rule that must be learned concerns two components of a stimulus being identical. We call such a basis for discrimination an identity-based rule. Identity-based rules have proven to be difficult or impossible for certain types of learning algorithms to acquire from limited datasets. This is in contrast to human behaviour on similar tasks. Here we provide a framework for rigorously establishing which learning algorithms will fail at generalizing identity-based rules to novel stimuli. We use this framework to show that such algorithms are unable to generalize identity-based rules to novel inputs unless trained on virtually all possible inputs. We demonstrate these results computationally with a multilayer feedforward neural network.
Redundancy Elimination Might Be Overrated: A Quantitative Study on Real-World Wireless Traffic
Venue: arXiv cs.NI 2016
Year: 2016

With significant increases in mobile device traffic slated for the foreseeable future, numerous technologies must be embraced to satisfy such demand. Notably, one of the more intriguing approaches has been blending on-device caching and device-to-device (D2D) communications. While various past research has pointed to potentially significant gains (30%+) via redundancy elimination (RE), some skepticism has emerged to whether or not such gains are truly harnessable in practice. The premise of this paper is to explore whether or not significant potential for redundancy elimination exists and whether the rise of video and encryption might blunt said efforts. Critically, we find that absent significant synchronized interests of mobile users, the actual redundancy falls well short of the promising values from the literature. In our paper, we investigate the roots for said shortcomings by exploring RE savings with regards to cache hit characteristics and to what extent client and domain diversity contribute to the realized redundancy savings.
Robin Hood Hashing really has constant average search cost and variance in full tables
Venue: arXiv cs.DS 2016
Year: 2016

Thirty years ago, the Robin Hood collision resolution strategy was introduced for open addressing hash tables, and a recurrence equation was found for the distribution of its search cost. Although this recurrence could not be solved analytically, it allowed for numerical computations that, remarkably, suggested that the variance of the search cost approached a value of $1.883$ when the table was full. Furthermore, by using a non-standard mean-centered search algorithm, this would imply that searches could be performed in expected constant time even in a full table. In spite of the time elapsed since these observations were made, no progress has been made in proving them. In this paper we introduce a technique to work around the intractability of the recurrence equation by solving instead an associated differential equation. While this does not provide an exact solution, it is sufficiently powerful to prove a bound for the variance, and thus obtain a proof that the variance of Robin Hood is bounded by a small constant for load factors arbitrarily close to 1. As a corollary, this proves that the mean-centered search algorithm runs in expected constant time. We also use this technique to study the performance of Robin Hood hash tables under a long sequence of insertions and deletions, where deletions are implemented by marking elements as deleted. We prove that, in this case, the variance is bounded by $1/(1-α)+O(1)$, where $α$ is the load factor. To model the behavior of these hash tables, we use a unified approach that can be applied also to study the First-Come-First-Served and Last-Come-First-Served collision resolution disciplines, both with and without deletions.
Fast Semantic Image Segmentation with High Order Context and Guided Filtering
Venue: arXiv cs.CV 2016
Year: 2016

This paper describes a fast and accurate semantic image segmentation approach that encodes not only the discriminative features from deep neural networks, but also the high-order context compatibility among adjacent objects as well as low level image features. We formulate the underlying problem as the conditional random field that embeds local feature extraction, clique potential construction, and guided filtering within the same framework, and provide an efficient coarse-to-fine solver. At the coarse level, we combine local feature representation and context interaction using a deep convolutional network, and directly learn the interaction from high order cliques with a message passing routine, avoiding time-consuming explicit graph inference for joint probability distribution. At the fine level, we introduce a guided filtering interpretation for the mean field algorithm, and achieve accurate object boundaries with 100+ faster than classic learning methods. The two parts are connected and jointly trained in an end-to-end fashion. Experimental results on Pascal VOC 2012 dataset have shown that the proposed algorithm outperforms the state-of-the-art, and that it achieves the rank 1 performance at the time of submission, both of which prove the effectiveness of this unified framework for semantic image segmentation.
A Reinforcement Learning System to Encourage Physical Activity in Diabetes Patients
Venue: arXiv cs.CY 2016
Year: 2016

Regular physical activity is known to be beneficial to people suffering from diabetes type 2. Nevertheless, most such people are sedentary. Smartphones create new possibilities for helping people to adhere to their physical activity goals, through continuous monitoring and communication, coupled with personalized feedback. We provided 27 sedentary diabetes type 2 patients with a smartphone-based pedometer and a personal plan for physical activity. Patients were sent SMS messages to encourage physical activity between once a day and once per week. Messages were personalized through a Reinforcement Learning (RL) algorithm which optimized messages to improve each participant's compliance with the activity regimen. The RL algorithm was compared to a static policy for sending messages and to weekly reminders. Our results show that participants who received messages generated by the RL algorithm increased the amount of activity and pace of walking, while the control group patients did not. Patients assigned to the RL algorithm group experienced a superior reduction in blood glucose levels (HbA1c) compared to control policies, and longer participation caused greater reductions in blood glucose levels. The learning algorithm improved gradually in predicting which messages would lead participants to exercise. Our results suggest that a mobile phone application coupled with a learning algorithm can improve adherence to exercise in diabetic patients. As a learning algorithm is automated, and delivers personalized messages, it could be used in large populations of diabetic patients to improve health and glycemic control. Our results can be expanded to other areas where computer-led health coaching of humans may have a positive impact.
Towards Empathetic Human-Robot Interactions
Venue: arXiv cs.CL 2016
Year: 2016

Since the late 1990s when speech companies began providing their customer-service software in the market, people have gotten used to speaking to machines. As people interact more often with voice and gesture controlled machines, they expect the machines to recognize different emotions, and understand other high level communication features such as humor, sarcasm and intention. In order to make such communication possible, the machines need an empathy module in them which can extract emotions from human speech and behavior and can decide the correct response of the robot. Although research on empathetic robots is still in the early stage, we described our approach using signal processing techniques, sentiment analysis and machine learning algorithms to make robots that can "understand" human emotion. We propose Zara the Supergirl as a prototype system of empathetic robots. It is a software based virtual android, with an animated cartoon character to present itself on the screen. She will get "smarter" and more empathetic through its deep learning algorithms, and by gathering more data and learning from it. In this paper, we present our work so far in the areas of deep learning of emotion and sentiment recognition, as well as humor recognition. We hope to explore the future direction of android development and how it can help improve people's lives.
Semantic Spaces
Venue: arXiv cs.CL 2016
Year: 2016

Any natural language can be considered as a tool for producing large databases (consisting of texts, written, or discursive). This tool for its description in turn requires other large databases (dictionaries, grammars etc.). Nowadays, the notion of database is associated with computer processing and computer memory. However, a natural language resides also in human brains and functions in human communication, from interpersonal to intergenerational one. We discuss in this survey/research paper mathematical, in particular geometric, constructions, which help to bridge these two worlds. In particular, in this paper we consider the Vector Space Model of semantics based on frequency matrices, as used in Natural Language Processing. We investigate underlying geometries, formulated in terms of Grassmannians, projective spaces, and flag varieties. We formulate the relation between vector space models and semantic spaces based on semic axes in terms of projectability of subvarieties in Grassmannians and projective spaces. We interpret Latent Semantics as a geometric flow on Grassmannians. We also discuss how to formulate Gärdenfors' notion of "meeting of minds" in our geometric setting.
The Maximum Block Size of Critical Random Graphs
Venue: arXiv cs.DM 2016
Year: 2016

Let $G(n,\, M)$ be the uniform random graph with $n$ vertices and $M$ edges. Let $B_n$ be the maximum block-size of $G(n,\, M)$ or the maximum size of its maximal $2$-connected induced subgraphs. We determine the expectation of $B_n$ near the critical point $M=n/2$. As $n-2M \gg n^{2/3}$, we find a constant $c_1$ such that \[ c_1 = \lim_{n \rightarrow \infty} \left(1 - \frac{2M}{n} \right) \, E B_n \, . \] Inside the window of transition of $G(n,\, M)$ with $M=\frac{n}{2}(1+λn^{-1/3})$, where $λ$ is any real number, we find an exact analytic expression for \[ c_2(λ) = \lim_{n \rightarrow \infty} \frac{E B_n} {n^{1/3}} \, . \] This study relies on the symbolic method and analytic tools coming from generating function theory which enable us to describe the evolution of $n^{-1/3} \, E B_n $ as a function of $λ$.
Occurrence Statistics of Entities, Relations and Types on the Web
Venue: arXiv cs.CL 2016
Year: 2016

The problem of collecting reliable estimates of occurrence of entities on the open web forms the premise for this report. The models learned for tagging entities cannot be expected to perform well when deployed on the web. This is owing to the severe mismatch in the distributions of such entities on the web and in the relatively diminutive training data. In this report, we build up the case for maximum mean discrepancy for estimation of occurrence statistics of entities on the web, taking a review of named entity disambiguation techniques and related concepts along the way.
Neural Dataset Generality
Venue: arXiv cs.CV 2016
Year: 2016

Often the filters learned by Convolutional Neural Networks (CNNs) from different datasets appear similar. This is prominent in the first few layers. This similarity of filters is being exploited for the purposes of transfer learning and some studies have been made to analyse such transferability of features. This is also being used as an initialization technique for different tasks in the same dataset or for the same task in similar datasets. Off-the-shelf CNN features have capitalized on this idea to promote their networks as best transferable and most general and are used in a cavalier manner in day-to-day computer vision tasks. It is curious that while the filters learned by these CNNs are related to the atomic structures of the images from which they are learnt, all datasets learn similar looking low-level filters. With the understanding that a dataset that contains many such atomic structures learn general filters and are therefore useful to initialize other networks with, we propose a way to analyse and quantify generality among datasets from their accuracies on transferred filters. We applied this metric on several popular character recognition, natural image and a medical image dataset, and arrived at some interesting conclusions. On further experimentation we also discovered that particular classes in a dataset themselves are more general than others.
Sparsity-Based Error Detection in DC Power Flow State Estimation
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a new approach for identifying the measurement error in the DC power flow state estimation problem. The proposed algorithm exploits the singularity of the impedance matrix and the sparsity of the error vector by posing the DC power flow problem as a sparse vector recovery problem that leverages the structure of the power system and uses $l_1$-norm minimization for state estimation. This approach can provably compute the measurement errors exactly, and its performance is robust to the arbitrary magnitudes of the measurement errors. Hence, the proposed approach can detect the noisy elements if the measurements are contaminated with additive white Gaussian noise plus sparse noise with large magnitude. The effectiveness of the proposed sparsity-based decomposition-DC power flow approach is demonstrated on the IEEE 118-bus and 300-bus test systems.
Measuring satisfaction in societies with opinion leaders and mediators
Venue: arXiv cs.GT 2016
Year: 2016

An opinion leader-follower model (OLF) is a two-action collective decision-making model for societies, in which three kinds of actors are considered: "opinion leaders", "followers", and "independent actors". In OLF the initial decision of the followers can be modified by the influence of the leaders. Once the final decision is set, a collective decision is taken applying the simple majority rule. We consider a generalization of \OLF, the gOLF models which allow collective decision taken by rules different from the single majority rule. Inspired in this model we define two new families of collective decision-making models associated with cooperative influence games. We define the "oblivious" and "non-oblivious" influence models. We show that gOLF models are non-oblivious influence models played on a two layered bipartite influence graph. Together with OLF models, the Satisfaction measure was introduced and studied. We analyze the computational complexity of the satisfaction measure for gOLF models and the other collective decision-making models introduced in the paper. We show that computing the satisfaction measure is #P-hard in all the considered models except for the basic OLF inwhich the complexity remains open. On the other hand, we provide two subfamilies of decision models in which the satisfaction measure can be computed in polynomial time. Exploiting the relationship with influence games, we can relate the satisfaction measure with the Rae index of an associated simple game. The Rae index is closely related to the Banzhaf value. Thus, our results also extend the families of simple games for which computing the Rae index and the Banzhaf value is computationally hard.
Establishing Multiple Survivable Connections (Extended Version)
Venue: arXiv cs.NI 2016
Year: 2016

We consider the establishment of connections in survivable networks, where each connection is allocated with a working (primary) path and a protection (backup) path. While many optimal solutions have been found for the establishment of a single connection, only heuristics have been proposed for the multi-connection case. We investigate the algorithmic tractability of multi-connection establishment problems, both in online and offline frameworks. First, we focus on the special case of two connections, and study the tractability of three variants of the problem. We show that only one variant is tractable, for which we establish an optimal solution of polynomial complexity. For the other variants, which are shown to be NP-hard, heuristic schemes are proposed. These heuristics are designed based on the insight gained from our study. Through simulations, we indicate the advantages of these heuristics over more straightforward alternatives. We extend our study to K connections, for a fixed K that is larger than 2. We prove the tractability of online and offline variants of the problem, in which sharing links along backup paths is allowed, and we establish corresponding optimal solutions. On the other hand, we show that, if the number of connections is not fixed (i.e., K is not O(1)), then the problem is, in general, NP-hard.
Learning Relevant Features for Manipulation Skills using Meta-Level Priors
Venue: arXiv cs.RO 2016
Year: 2016

Robots can generalize manipulation skills between different scenarios by adapting to the features of the objects being manipulated. Selecting the set of relevant features for generalizing skills has usually been performed manually by a human. Alternatively, a robot can learn to select relevant features autonomously. However, feature selection usually requires a large amount of training data, which would require many demonstrations. In order to learn the relevant features more efficiently, we propose using a meta-level prior to transfer the relevance of features from previously learned skills. The experiments show that the meta-level prior more than doubles the average precision and recall of the feature selection when compared to a standard uniform prior. The proposed approach was used to learn a variety of manipulation skills, including pushing, cutting, and pouring.
A New Method for Parallel Monte Carlo Tree Search
Venue: arXiv cs.DC 2016
Year: 2016

In recent years there has been much interest in the Monte Carlo tree search algorithm, a new, adaptive, randomized optimization algorithm. In fields as diverse as Artificial Intelligence, Operations Research, and High Energy Physics, research has established that Monte Carlo tree search can find good solutions without domain dependent heuristics. However, practice shows that reaching high performance on large parallel machines is not so successful as expected. This paper proposes a new method for parallel Monte Carlo tree search based on the pipeline computation pattern.
Capturing divergence in dependency trees to improve syntactic projection
Venue: arXiv cs.CL 2016
Year: 2016

Obtaining syntactic parses is a crucial part of many NLP pipelines. However, most of the world's languages do not have large amounts of syntactically annotated corpora available for building parsers. Syntactic projection techniques attempt to address this issue by using parallel corpora consisting of resource-poor and resource-rich language pairs, taking advantage of a parser for the resource-rich language and word alignment between the languages to project the parses onto the data for the resource-poor language. These projection methods can suffer, however, when the two languages are divergent. In this paper, we investigate the possibility of using small, parallel, annotated corpora to automatically detect divergent structural patterns between two languages. These patterns can then be used to improve structural projection algorithms, allowing for better performing NLP tools for resource-poor languages, in particular those that may not have large amounts of annotated data necessary for traditional, fully-supervised methods. While this detection process is not exhaustive, we demonstrate that common patterns of divergence can be identified automatically without prior knowledge of a given language pair, and the patterns can be used to improve performance of projection algorithms.
Probabilistic Deep Spiking Neural Systems Enabled by Magnetic Tunnel Junction
Venue: arXiv cs.ET 2016
Year: 2016

Deep Spiking Neural Networks are becoming increasingly powerful tools for cognitive computing platforms. However, most of the existing literature on such computing models are developed with limited insights on the underlying hardware implementation, resulting in area and power expensive designs. Although several neuromimetic devices emulating neural operations have been proposed recently, their functionality has been limited to very simple neural models that may prove to be inefficient at complex recognition tasks. In this work, we venture into the relatively unexplored area of utilizing the inherent device stochasticity of such neuromimetic devices to model complex neural functionalities in a probabilistic framework in the time domain. We consider the implementation of a Deep Spiking Neural Network capable of performing high accuracy and low latency classification tasks where the neural computing unit is enabled by the stochastic switching behavior of a Magnetic Tunnel Junction. Simulation studies indicate an energy improvement of $20\times$ over a baseline CMOS design in $45nm$ technology.