OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Branching Cascaded Regression for Face Alignment under Significant Head Rotation
Venue: arXiv cs.CV 2016
Year: 2016

Despite much interest in face alignment in recent years, the large majority of work has focused on near-frontal faces. Algorithms typically break down on profile faces, or are too slow for real-time applications. In this work we propose an efficient approach to face alignment that can handle 180 degrees of head rotation in a unified way (e.g., without resorting to view-based models) using 2D training data. The foundation of our approach is cascaded shape regression (CSR), which has emerged recently as the leading strategy. We propose a generalization of conventional CSRs that we call branching cascaded regression (BCR). Conventional CSRs are single-track; that is, they progress from one cascade level to the next in a straight line, with each regressor attempting to fit the entire dataset. We instead split the regression problem into two or more simpler ones after each cascade level. Intuitively, each regressor can then operate on a simpler objective function (i.e., with fewer conflicting gradient directions). Within the BCR framework, we model and infer pose-related landmark visibility and face shape simultaneously using Structured Point Distribution Models (SPDMs). We propose to learn task-specific feature mapping functions that are adaptive to landmark visibility, and that use SPDM parameters as regression targets instead of 2D landmark coordinates. Additionally, we introduce a new in-the-wild dataset of profile faces to validate our approach.
Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs
Venue: arXiv cs.DM 2016
Year: 2016

We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by Lieberman et al.\ (Nature, 2005). In this process, individuals are the vertices of a connected graph $G$. Initially, there is a single mutant vertex, chosen uniformly at random. In each step, a random vertex is selected for reproduction with a probability proportional to its fitness: mutants have fitness $r>1$, while non-mutants have fitness 1. The vertex chosen to reproduce places a copy of itself to a uniformly random neighbor in $G$, replacing the individual that was there. The process ends when the mutation either reaches fixation (i.e., all vertices are mutants), or gets extinct. The principal quantity of interest is the probability with which each of the two outcomes occurs. A problem that has received significant attention recently concerns the existence of families of graphs, called strong amplifiers of selection, for which the fixation probability tends to 1 as the order $n$ of the graph increases, and the existence of strong suppressors of selection, for which this probability tends to 0. For the case of directed graphs, it is known that both strong amplifiers and suppressors exist. For the case of undirected graphs, however, the problem has remained open, and the general belief has been that neither strong amplifiers nor suppressors exist. In this paper we disprove this belief, by providing the first examples of such graphs. The strong amplifier we present has fixation probability $1-\tilde O(n^{-1/3})$, and the strong suppressor has fixation probability $\tilde O(n^{-1/4})$. Both graph constructions are surprisingly simple. We also prove a general upper bound of $1-\tilde Ω(n^{-1/3})$ on the fixation probability of any undirected graph. Hence, our strong amplifier is existentially optimal.
Learning to Play in a Day: Faster Deep Reinforcement Learning by Optimality Tightening
Venue: arXiv cs.LG 2016
Year: 2016

We propose a novel training algorithm for reinforcement learning which combines the strength of deep Q-learning with a constrained optimization approach to tighten optimality and encourage faster reward propagation. Our novel technique makes deep reinforcement learning more practical by drastically reducing the training time. We evaluate the performance of our approach on the 49 games of the challenging Arcade Learning Environment, and report significant improvements in both training time and accuracy.
What Is the Best Practice for CNNs Applied to Visual Instance Retrieval?
Venue: arXiv cs.CV 2016
Year: 2016

Previous work has shown that feature maps of deep convolutional neural networks (CNNs) can be interpreted as feature representation of a particular image region. Features aggregated from these feature maps have been exploited for image retrieval tasks and achieved state-of-the-art performances in recent years. The key to the success of such methods is the feature representation. However, the different factors that impact the effectiveness of features are still not explored thoroughly. There are much less discussion about the best combination of them. The main contribution of our paper is the thorough evaluations of the various factors that affect the discriminative ability of the features extracted from CNNs. Based on the evaluation results, we also identify the best choices for different factors and propose a new multi-scale image feature representation method to encode the image effectively. Finally, we show that the proposed method generalises well and outperforms the state-of-the-art methods on four typical datasets used for visual instance retrieval.
Boosting Image Captioning with Attributes
Venue: arXiv cs.CV 2016
Year: 2016

Automatically describing an image with a natural language has been an emerging challenge in both fields of computer vision and natural language processing. In this paper, we present Long Short-Term Memory with Attributes (LSTM-A) - a novel architecture that integrates attributes into the successful Convolutional Neural Networks (CNNs) plus Recurrent Neural Networks (RNNs) image captioning framework, by training them in an end-to-end manner. To incorporate attributes, we construct variants of architectures by feeding image representations and attributes into RNNs in different ways to explore the mutual but also fuzzy relationship between them. Extensive experiments are conducted on COCO image captioning dataset and our framework achieves superior results when compared to state-of-the-art deep models. Most remarkably, we obtain METEOR/CIDEr-D of 25.2%/98.6% on testing data of widely used and publicly available splits in (Karpathy & Fei-Fei, 2015) when extracting image representations by GoogleNet and achieve to date top-1 performance on COCO captioning Leaderboard.
Analytical Derivation of Downlink Data Rate Distribution for 5G HetNets with Cell-Edge Located Small Cells
Venue: arXiv cs.NI 2016
Year: 2016

In HetNets, time/frequency resources should be partitioned intelligently in order to minimize the interference among the users. In this paper, the probability distributions of per user downlink Data Rate, Spectral Efficiency (SE) and Energy Efficiency (EE) are analytically derived for a HetNet model with cell-edge located small cells. The high accuracy of analytically derived CDFs have been verified by the distributions obtained via simulations. CDF expressions have then been employed in order to optimize Key Parameter Indicators (KPI) which are selected here as $10^{th}$ percentile downlink user Data Rate ($R_{10}$), Spectral Efficiency ($SE_{10}$) and Energy Efficiency ($EE_{10}$). In addition to optimizing KPIs separately, employing the analytically derived distributions, we have also investigated the variation of the KPIs with respect to each other. The results have shown that the resource allocation parameter values maximizing $R_{10}$ is very close to the values that maximize $SE_{10}$. However, the values that are optimal for $SE_{10}$ and $R_{10}$, are not optimal for $EE_{10}$, which demonstrates the EE and SE trade-off in HetNets. We have also proposed a metric, $θ$, aiming to jointly optimize SE and EE. The results have shown the value of resource sharing parameter optimizing $θ$ is closer to the value that maximizes SE. This result shows that SE is more critical in SE-EE trade-off.
A Compare-Aggregate Model for Matching Text Sequences
Venue: arXiv cs.CL 2016
Year: 2016

Many NLP tasks including machine comprehension, answer selection and text entailment require the comparison between sequences. Matching the important units between sequences is a key to solve these problems. In this paper, we present a general "compare-aggregate" framework that performs word-level matching followed by aggregation using Convolutional Neural Networks. We particularly focus on the different comparison functions we can use to match two vectors. We use four different datasets to evaluate the model. We find that some simple comparison functions based on element-wise operations can work better than standard neural network and neural tensor network.
Forensics in Industrial Control System: A Case Study
Venue: arXiv cs.CR 2016
Year: 2016

Industrial Control Systems (ICS) are used worldwide in critical infrastructures. An ICS system can be a single embedded system working stand-alone for controlling a simple process or ICS can also be a very complex Distributed Control System (DCS) connected to Supervisory Control And Data Acquisition (SCADA) system(s) in a nuclear power plant. Although ICS are widely used to-day, there are very little research on the forensic acquisition and analyze ICS artefacts. In this paper we present a case study of forensics in ICS where we de-scribe a method of safeguarding important volatile artefacts from an embedded industrial control system and several other sources
A Comparison of the Triangle Algorithm and SMO for Solving the Hard Margin Problem
Venue: arXiv cs.CG 2016
Year: 2016

In this article we consider the problem of testing, for two finite sets of points in the Euclidean space, if their convex hulls are disjoint and computing an optimal supporting hyperplane if so. This is a fundamental problem of classification in machine learning known as the hard-margin SVM. The problem can be formulated as a quadratic programming problem. The SMO algorithm is the current state of art algorithm for solving it, but it does not answer the question of separability. An alternative to solving both problems is the Triangle Algorithm, a geometrically inspired algorithm, initially described for the convex hull membership problem, a fundamental problem in linear programming. First, we describe the experimental performance of the Triangle Algorithm for testing the intersection of two convex hulls. Next, we compare the performance of Triangle Algorithm with SMO for finding the optimal supporting hyperplane. Based on experimental results ranging up to 5000 points in each set in dimensions up to 10000, the Triangle Algorithm outperforms SMO.
Truth Discovery with Memory Network
Venue: arXiv cs.CL 2016
Year: 2016

Truth discovery is to resolve conflicts and find the truth from multiple-source statements. Conventional methods mostly research based on the mutual effect between the reliability of sources and the credibility of statements, however, pay no attention to the mutual effect among the credibility of statements about the same object. We propose memory network based models to incorporate these two ideas to do the truth discovery. We use feedforward memory network and feedback memory network to learn the representation of the credibility of statements which are about the same object. Specially, we adopt memory mechanism to learn source reliability and use it through truth prediction. During learning models, we use multiple types of data (categorical data and continuous data) by assigning different weights automatically in the loss function based on their own effect on truth discovery prediction. The experiment results show that the memory network based models much outperform the state-of-the-art method and other baseline methods.
Neural Machine Translation with Reconstruction
Venue: arXiv cs.CL 2016
Year: 2016

Although end-to-end Neural Machine Translation (NMT) has achieved remarkable progress in the past two years, it suffers from a major drawback: translations generated by NMT systems often lack of adequacy. It has been widely observed that NMT tends to repeatedly translate some source words while mistakenly ignoring other words. To alleviate this problem, we propose a novel encoder-decoder-reconstructor framework for NMT. The reconstructor, incorporated into the NMT model, manages to reconstruct the input source sentence from the hidden layer of the output target sentence, to ensure that the information in the source side is transformed to the target side as much as possible. Experiments show that the proposed framework significantly improves the adequacy of NMT output and achieves superior translation result over state-of-the-art NMT and statistical MT systems.
Challenges of Feature Selection for Big Data Analytics
Venue: arXiv cs.LG 2016
Year: 2016

We are surrounded by huge amounts of large-scale high dimensional data. It is desirable to reduce the dimensionality of data for many learning tasks due to the curse of dimensionality. Feature selection has shown its effectiveness in many applications by building simpler and more comprehensive model, improving learning performance, and preparing clean, understandable data. Recently, some unique characteristics of big data such as data velocity and data variety present challenges to the feature selection problem. In this paper, we envision these challenges of feature selection for big data analytics. In particular, we first give a brief introduction about feature selection and then detail the challenges of feature selection for structured, heterogeneous and streaming data as well as its scalability and stability issues. At last, to facilitate and promote the feature selection research, we present an open-source feature selection repository (scikit-feature), which consists of most of current popular feature selection algorithms.
Me, Myself and My Killfie: Characterizing and Preventing Selfie Deaths
Venue: arXiv cs.SI 2016
Year: 2016

Over the past couple of years, clicking and posting selfies has become a popular trend. However, since March 2014, 127 people have died and many have been injured while trying to click a selfie. Researchers have studied selfies for understanding the psychology of the authors, and understanding its effect on social media platforms. In this work, we perform a comprehensive analysis of the selfie-related casualties and infer various reasons behind these deaths. We use inferences from incidents and from our understanding of the features, we create a system to make people more aware of the dangerous situations in which these selfies are taken. We use a combination of text-based, image-based and location-based features to classify a particular selfie as dangerous or not. Our method ran on 3,155 annotated selfies collected on Twitter gave 73% accuracy. Individually the image-based features were the most informative for the prediction task. The combination of image-based and location-based features resulted in the best accuracy. We have made our code and dataset available at http://labs.precog.iiitd.edu.in/killfie.
Extending Two-Variable Logic on Trees
Venue: arXiv cs.LO 2016
Year: 2016

The finite satisfiability problem for the two-variable fragment of first-order logic interpreted over trees was recently shown to be ExpSpace-complete. We consider two extensions of this logic. We show that adding either additional binary symbols or counting quantifiers to the logic does not affect the complexity of the finite satisfiability problem. However, combining the two extensions and adding both binary symbols and counting quantifiers leads to an explosion of this complexity. We also compare the expressive power of the two-variable fragment over trees with its extension with counting quantifiers. It turns out that the two logics are equally expressive, although counting quantifiers do add expressive power in the restricted case of unordered trees.
The Bufferbloat Problem over Intermittent Multi-Gbps mmWave Links
Venue: arXiv cs.NI 2016
Year: 2016

Due to massive available spectrum in the millimeter wave (mmWave) bands, cellular systems in these frequencies may provides orders of magnitude greater capacity than networks in conventional lower frequency bands. However, due to high susceptibility to blocking, mmWave links can be extremely intermittent in quality. This combination of high peak throughputs and intermittency can cause significant challenges in end-to-end transport-layer mechanisms such as TCP. This paper studies the particularly challenging problem of bufferbloat. Specifically, with current buffering and congestion control mechanisms, high throughput-high variable links can lead to excessive buffers incurring long latency. In this paper, we capture the performance trends obtained while adopting two potential solutions that have been proposed in the literature: Active queue management (AQM) and dynamic receive window. We show that, over mmWave links, AQM mitigates the latency but cannot deliver high throughput. The main reason relies on the fact that the current congestion control was not designed to cope with high data rates with sudden change. Conversely, the dynamic receive window approach is more responsive and therefore supports higher channel utilization while mitigating the delay, thus representing a viable solution.
Bayesian Non-parametric model to Target Gamification Notifications Using Big Data
Venue: arXiv cs.AI 2016
Year: 2016

I suggest an approach that helps the online marketers to target their Gamification elements to users by modifying the order of the list of tasks that they send to users. It is more realistic and flexible as it allows the model to learn more parameters when the online marketers collect more data. The targeting approach is scalable and quick, and it can be used over streaming data.
Convergence Analysis of Iterated Best Response for a Trusted Computation Game
Venue: arXiv cs.GT 2016
Year: 2016

We introduce a game of trusted computation in which a sensor equipped with limited computing power leverages a central node to evaluate a specified function over a large dataset, collected over time. We assume that the central computer can be under attack and we propose a strategy where the sensor retains a limited amount of the data to counteract the effect of attack. We formulate the problem as a two player game in which the sensor (defender) chooses an optimal fusion strategy using both the non-trusted output from the central computer and locally stored trusted data. The attacker seeks to compromise the computation by influencing the fused value through malicious manipulation of the data stored on the central node. We first characterize all Nash equilibria of this game, which turn out to be dependent on parameters known to both players. Next we adopt an Iterated Best Response (IBR) scheme in which, at each iteration, the central computer reveals its output to the sensor, who then computes its best response based on a linear combination of its private local estimate and the untrusted third-party output. We characterize necessary and sufficient conditions for convergence of the IBR along with numerical results which show that the convergence conditions are relatively tight.
Chain Reduction Preserves the Unrooted Subtree Prune-and-Regraft Distance
Venue: arXiv cs.DM 2016
Year: 2016

The subtree prune-and-regraft (SPR) distance metric is a fundamental way of comparing evolutionary trees. It has wide-ranging applications, such as to study lateral genetic transfer, viral recombination, and Markov chain Monte Carlo phylogenetic inference. Although the rooted version of SPR distance can be com puted relatively efficiently between rooted trees using fixed-parameter-tractable algorithms, in the unrooted case previous algorithms are unable to compute distances larger than 7. One important tool for efficient computation in the rooted case is called chain reduction, which replaces an arbitrary chain of subtrees identical in both trees with a chain of three leaves. Whether chain reduction preserves SPR distance in the unrooted case has remained an open question since it was conjectured in 2001 by Allen and Steel, and was presented as a challenge question at the 2007 Isaac Newton Institute for Mathematical Sciences program on phylogenetics. In this paper we prove that chain reduction preserves the unrooted SPR distance. We do so by introducing a structure called a socket agreement forest that restricts edge modification to predetermined socket vertices, permitting detailed analysis and modification of SPR move sequences. This new chain reduction theorem reduces the unrooted distance problem to a linear size problem kernel, substantially improving on the previous best quadratic size kernel.
Combining observational and experimental data to find heterogeneous treatment effects
Venue: arXiv cs.AI 2016
Year: 2016

Every design choice will have different effects on different units. However traditional A/B tests are often underpowered to identify these heterogeneous effects. This is especially true when the set of unit-level attributes is high-dimensional and our priors are weak about which particular covariates are important. However, there are often observational data sets available that are orders of magnitude larger. We propose a method to combine these two data sources to estimate heterogeneous treatment effects. First, we use observational time series data to estimate a mapping from covariates to unit-level effects. These estimates are likely biased but under some conditions the bias preserves unit-level relative rank orderings. If these conditions hold, we only need sufficient experimental data to identify a monotonic, one-dimensional transformation from observationally predicted treatment effects to real treatment effects. This reduces power demands greatly and makes the detection of heterogeneous effects much easier. As an application, we show how our method can be used to improve Facebook page recommendations.
Using cognitive agent-based simulation for the evaluation of indoor wayfinding systems
Venue: arXiv cs.HC 2016
Year: 2016

This paper presents a novel approach to simulate human wayfinding behaviour incorporating visual cognition into a software agent for a computer aided evaluation of wayfinding systems in large infrastructures. The proposed approach follows the Sense-Plan-Act paradigm comprised of a model for visual attention, navigation behaviour and pedestrian movement. Stochastic features of perception are incorporated to enhance generality and diversity of the developed wayfinding simulation to reflect a variety of behaviours. The validity of the proposed approach was evaluated based on empirical data collected through wayfinding experiments with 20 participants in an immersive virtual reality environment using a life-sized 3D replica of Vienna's new central railway station. The results show that the developed cognitive agent-based simulation provides a further contribution to the simulation of human wayfinding and subsequently a further step to an effective evaluation tool for the planning of wayfinding and signage.
A Novel Framework for Modeling and Mitigating Distributed Link Flooding Attacks
Venue: arXiv cs.NI 2016
Year: 2016

Distributed link-flooding attacks constitute a new class of attacks with the potential to segment large areas of the Internet. Their distributed nature makes detection and mitigation very hard. This work proposes a novel framework for the analytical modeling and optimal mitigation of such attacks. The detection is modeled as a problem of relational algebra, representing the association of potential attackers (bots) to potential targets. The analysis seeks to optimally dissolve all but the malevolent associations. The framework is implemented at the level of online Traffic Engineering (TE), which is naturally triggered on link-flooding events. The key idea is to continuously re-route traffic in a manner that makes persistent participation to link-flooding events highly improbable for any benign source. Thus, bots are forced to adopt a suspicious behavior to remain effective, revealing their presence. The load-balancing objective of TE is not affected at all. Extensive simulations on various topologies validate our analytical findings.