OpenRaiser/Intern-Atlas huggingface dataset:
Tabling with Sound Answer Subsumption
Venue: arXiv cs.PL 2016
Year: 2016

Tabling is a powerful resolution mechanism for logic programs that captures their least fixed point semantics more faithfully than plain Prolog. In many tabling applications, we are not interested in the set of all answers to a goal, but only require an aggregation of those answers. Several works have studied efficient techniques, such as lattice-based answer subsumption and mode-directed tabling, to do so for various forms of aggregation. While much attention has been paid to expressivity and efficient implementation of the different approaches, soundness has not been considered. This paper shows that the different implementations indeed fail to produce least fixed points for some programs. As a remedy, we provide a formal framework that generalises the existing approaches and we establish a soundness criterion that explains for which programs the approach is sound. This article is under consideration for acceptance in TPLP.
CUHK & ETHZ & SIAT Submission to ActivityNet Challenge 2016
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents the method that underlies our submission to the untrimmed video classification task of ActivityNet Challenge 2016. We follow the basic pipeline of temporal segment networks and further raise the performance via a number of other techniques. Specifically, we use the latest deep model architecture, e.g., ResNet and Inception V3, and introduce new aggregation schemes (top-k and attention-weighted pooling). Additionally, we incorporate the audio as a complementary channel, extracting relevant information via a CNN applied to the spectrograms. With these techniques, we derive an ensemble of deep models, which, together, attains a high classification accuracy (mAP $93.23\%$) on the testing set and secured the first place in the challenge.
Deriving Conclusions From Non-Monotonic Cause-Effect Relations
Venue: arXiv cs.LO 2016
Year: 2016

We present an extension of Logic Programming (under stable models semantics) that, not only allows concluding whether a true atom is a cause of another atom, but also deriving new conclusions from these causal-effect relations. This is expressive enough to capture informal rules like "if some agent's actions $\mathcal{A}$ have been necessary to cause an event $E$ then conclude atom $caused(\mathcal{A},E)$," something that, to the best of our knowledge, had not been formalised in the literature. To this aim, we start from a first attempt that proposed extending the syntax of logic programs with so-called causal literals. These causal literals are expressions that can be used in rule bodies and allow inspecting the derivation of some atom $A$ in the program with respect to some query function $ϕ$. Depending on how these query functions are defined, we can model different types of causal relations such as sufficient, necessary or contributory causes, for instance. The initial approach was specifically focused on monotonic query functions. This was enough to cover sufficient cause-effect relations but, unfortunately, necessary and contributory are essentially non-monotonic. In this work, we define a semantics for non-monotonic causal literals showing that, not only extends the stable model semantics for normal logic programs, but also preserves many of its usual desirable properties for the extended syntax. Using this new semantics, we provide precise definitions of necessary and contributory causal relations and briefly explain their behaviour on a pair of typical examples from the Knowledge Representation literature. (Under consideration for publication in Theory and Practice of Logic Programming)
Modeling Spatial and Temporal Cues for Multi-label Facial Action Unit Detection
Venue: arXiv cs.CV 2016
Year: 2016

Facial action units (AUs) are essential to decode human facial expressions. Researchers have focused on training AU detectors with a variety of features and classifiers. However, several issues remain. These are spatial representation, temporal modeling, and AU correlation. Unlike most studies that tackle these issues separately, we propose a hybrid network architecture to jointly address them. Specifically, spatial representations are extracted by a Convolutional Neural Network (CNN), which, as analyzed in this paper, is able to reduce person-specific biases caused by hand-crafted features (eg, SIFT and Gabor). To model temporal dependencies, Long Short-Term Memory (LSTMs) are stacked on top of these representations, regardless of the lengths of input videos. The outputs of CNNs and LSTMs are further aggregated into a fusion network to produce per-frame predictions of 12 AUs. Our network naturally addresses the three issues, and leads to superior performance compared to existing methods that consider these issues independently. Extensive experiments were conducted on two large spontaneous datasets, GFT and BP4D, containing more than 400,000 frames coded with 12 AUs. On both datasets, we report significant improvement over a standard multi-label CNN and feature-based state-of-the-art. Finally, we provide visualization of the learned AU models, which, to our best knowledge, reveal how machines see facial AUs for the first time.
Summarizing Large Query Logs in Ettu
Venue: arXiv cs.DB 2016
Year: 2016

Database access logs are large, unwieldy, and hard for humans to inspect and summarize. In spite of this, they remain the canonical go-to resource for tasks ranging from performance tuning to security auditing. In this paper, we address the challenge of compactly encoding large sequences of SQL queries for presentation to a human user. Our approach is based on the Weisfeiler-Lehman (WL) approximate graph isomorphism algorithm, which identifies salient features of a graph or in our case of an abstract syntax tree. Our generalization of WL allows us to define a distance metric for SQL queries, which in turn permits automated clustering of queries. We also present two techniques for visualizing query clusters, and an algorithm that allows these visualizations to be constructed at interactive speeds. Finally, we evaluate our algorithms in the context of a motivating example: insider threat detection at a large US bank. We show experimentally on real world query logs that (a) our distance metric captures a meaningful notion of similarity, and (b) the log summarization process is scalable and performant.
Empirical Evaluation of Real World Tournaments
Venue: arXiv cs.GT 2016
Year: 2016

Computational Social Choice (ComSoc) is a rapidly developing field at the intersection of computer science, economics, social choice, and political science. The study of tournaments is fundamental to ComSoc and many results have been published about tournament solution sets and reasoning in tournaments. Theoretical results in ComSoc tend to be worst case and tell us little about performance in practice. To this end we detail some experiments on tournaments using real wold data from soccer and tennis. We make three main contributions to the understanding of tournaments using real world data from English Premier League, the German Bundesliga, and the ATP World Tour: (1) we find that the NP-hard question of finding a seeding for which a given team can win a tournament is easily solvable in real world instances, (2) using detailed and principled methodology from statistical physics we show that our real world data obeys a log-normal distribution; and (3) leveraging our log-normal distribution result and using robust statistical methods, we show that the popular Condorcet Random (CR) tournament model does not generate realistic tournament data.
Ranking Entity Based on Both of Word Frequency and Word Sematic Features
Venue: arXiv cs.IR 2016
Year: 2016

Entity search is a new application meeting either precise or vague requirements from the search engines users. Baidu Cup 2016 Challenge just provided such a chance to tackle the problem of the entity search. We achieved the first place with the average MAP scores on 4 tasks including movie, tvShow, celebrity and restaurant. In this paper, we propose a series of similarity features based on both of the word frequency features and the word semantic features and describe our ranking architecture and experiment details.
Generation of Near-Optimal Solutions Using ILP-Guided Sampling
Venue: arXiv cs.AI 2016
Year: 2016

Our interest in this paper is in optimisation problems that are intractable to solve by direct numerical optimisation, but nevertheless have significant amounts of relevant domain-specific knowledge. The category of heuristic search techniques known as estimation of distribution algorithms (EDAs) seek to incrementally sample from probability distributions in which optimal (or near-optimal) solutions have increasingly higher probabilities. Can we use domain knowledge to assist the estimation of these distributions? To answer this in the affirmative, we need: (a)a general-purpose technique for the incorporation of domain knowledge when constructing models for optimal values; and (b)a way of using these models to generate new data samples. Here we investigate a combination of the use of Inductive Logic Programming (ILP) for (a), and standard logic-programming machinery to generate new samples for (b). Specifically, on each iteration of distribution estimation, an ILP engine is used to construct a model for good solutions. The resulting theory is then used to guide the generation of new data instances, which are now restricted to those derivable using the ILP model in conjunction with the background knowledge). We demonstrate the approach on two optimisation problems (predicting optimal depth-of-win for the KRK endgame, and job-shop scheduling). Our results are promising: (a)On each iteration of distribution estimation, samples obtained with an ILP theory have a substantially greater proportion of good solutions than samples without a theory; and (b)On termination of distribution estimation, samples obtained with an ILP theory contain more near-optimal samples than samples without a theory. Taken together, these results suggest that the use of ILP-constructed theories could be a useful technique for incorporating complex domain-knowledge into estimation distribution procedures.
Offloading traffic hotspots using moving small cells
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, the concept of moving small cells in mobile networks is presented and evaluated taking into account the dynamics of the system. We consider a small cell moving according to a Manhattan mobility model which is the case when the small cell is deployed on the top of a bus following a predefined trajectory in areas which are generally crowded. Taking into account the distribution of user locations, we study the dynamic level considering a queuing model composed of multi-class Processor Sharing queues. Macro and small cells are assumed to be operating in the same bandwidth. Consequently, they are coupled due to the mutual interferences generated by each cell to the other. Our results show that deploying moving small cells could be an efficient solution to offload traffic hotspots.
Hard Threshold Least Mean Squares Algorithm
Venue: arXiv cs.SY 2016
Year: 2016

This work presents a new variation of the commonly used Least Mean Squares Algorithm (LMS) for the identification of sparse signals with an a-priori known sparsity using a hard threshold operator in every iteration. It examines some useful properties of the algorithm and compares it with the traditional LMS and other sparsity aware variations of the same algorithm. It goes on to examine the application of the algorithm in the problem of spectrum estimation for cognitive radio devices.
Ensemble-driven support vector clustering: From ensemble learning to automatic parameter estimation
Venue: arXiv cs.LG 2016
Year: 2016

Support vector clustering (SVC) is a versatile clustering technique that is able to identify clusters of arbitrary shapes by exploiting the kernel trick. However, one hurdle that restricts the application of SVC lies in its sensitivity to the kernel parameter and the trade-off parameter. Although many extensions of SVC have been developed, to the best of our knowledge, there is still no algorithm that is able to effectively estimate the two crucial parameters in SVC without supervision. In this paper, we propose a novel support vector clustering approach termed ensemble-driven support vector clustering (EDSVC), which for the first time tackles the automatic parameter estimation problem for SVC based on ensemble learning, and is capable of producing robust clustering results in a purely unsupervised manner. Experimental results on multiple real-world datasets demonstrate the effectiveness of our approach.
Few paths, fewer words: model selection with automatic structure functions
Venue: arXiv cs.FL 2016
Year: 2016

We consider the problem of finding an optimal statistical model for a given binary string. Following Kolmogorov, we use structure functions. In order to get concrete results, we replace Turing machines by finite automata and Kolmogorov complexity by Shallit and Wang's automatic complexity. The $p$-value of a model for given data $x$ is the probability that there exists a model with as few states, accepting as few words, fitting uniformly randomly selected data $y$. Deterministic and nondeterministic automata can give different optimal models. For $x=011\, 110\, 110\, 11$, the best deterministic model has $p$-value $0.3$, whereas the best nondeterministic model has $p$-value $0.04$. In the nondeterministic case, counting paths and counting words can give different optimal models. For $x=01100\, 01000$, the best path-counting model has $p$-value $0.79$, whereas the best word-counting model has $p$-value $0.60$.
Solving General Arithmetic Word Problems
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents a novel approach to automatically solving arithmetic word problems. This is the first algorithmic approach that can handle arithmetic problems with multiple steps and operations, without depending on additional annotations or predefined templates. We develop a theory for expression trees that can be used to represent and evaluate the target arithmetic expressions; we use it to uniquely decompose the target arithmetic problem to multiple classification problems; we then compose an expression tree, combining these with world knowledge through a constrained inference framework. Our classifiers gain from the use of {\em quantity schemas} that supports better extraction of features. Experimental results show that our method outperforms existing systems, achieving state of the art performance on benchmark datasets of arithmetic word problems.
Full Duplex Joint Sensing for Opportunistic Access in Spectrum-Heterogeneous Cognitive Radio Networks
Venue: arXiv cs.NI 2016
Year: 2016

In cognitive radio networks (CRN), secondary users (SUs) can share spectrum with licensed primary users (PUs). Because an SU receiver (SU-Rx) does not always share the same view of spectrum availability as the corresponding SU transmitter (SU-Tx), spectrum sensing conducted only by an SU transmitter tends to be overly sensitive to guarantee safe spectrum access at the price of SU inefficiency. In this letter, we propose a joint spectrum sensing mechanism, named Full-Duplex Joint Sensing (FJDS), to relax sensitivity of SU detection and improve SU throughput. FDJS employs instantaneous feedback enabled by in-band full duplex communication to facilitate the sharing of spectral information from SU-Rx to SU-Tx. The joint detection problem in FDJS is modeled as non-linear optimization and solved by a binary searching algorithm. Simulation results show that FDJS could improve SU throughput as well as meeting PU interruption constraints in a wide range of parameter settings.
Security Monitoring of the Cyber Space
Venue: arXiv cs.CR 2016
Year: 2016

Adversaries are abusing Internet security and privacy services to execute cyber attacks. To cope with these threats, network operators utilize various security tools and techniques to monitor the cyber space. An efficient way to infer Internet threat activities is to collect information from trap-based monitoring sensors. As such, this chapter primarily defines the cyberspace trap-based monitoring systems and their taxonomies. Moreover, it presents the state-of-the-art in terms of research contributions and techniques, tools and technologies. Furthermore, it identifies gaps in terms of science and technology. Additionally, it presents some case studies and practical approaches corresponding to large-scale cyber monitoring systems such as Nicter. We further present some related security policies and legal issues for network monitoring. This chapter provides an overview on Internet monitoring and offers a guideline for readers to help them understand the concepts of observing, detecting and analyzing cyber attacks through computer network traps.
UnitBox: An Advanced Object Detection Network
Venue: arXiv cs.CV 2016
Year: 2016

In present object detection systems, the deep convolutional neural networks (CNNs) are utilized to predict bounding boxes of object candidates, and have gained performance advantages over the traditional region proposal methods. However, existing deep CNN methods assume the object bounds to be four independent variables, which could be regressed by the $\ell_2$ loss separately. Such an oversimplified assumption is contrary to the well-received observation, that those variables are correlated, resulting to less accurate localization. To address the issue, we firstly introduce a novel Intersection over Union ($IoU$) loss function for bounding box prediction, which regresses the four bounds of a predicted box as a whole unit. By taking the advantages of $IoU$ loss and deep fully convolutional networks, the UnitBox is introduced, which performs accurate and efficient localization, shows robust to objects of varied shapes and scales, and converges fast. We apply UnitBox on face detection task and achieve the best performance among all published methods on the FDDB benchmark.
Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
Venue: arXiv cs.DS 2016
Year: 2016

We consider clustering problems with {\em non-uniform lower bounds and outliers}, and obtain the {\em first approximation guarantees} for these problems. We have a set $\F$ of facilities with lower bounds $\{L_i\}_{i\in\F}$ and a set $\D$ of clients located in a common metric space $\{c(i,j)\}_{i,j\in\F\cup\D}$, and bounds $k$, $m$. A feasible solution is a pair $\bigl(S\sse\F,σ:\D\mapsto S\cup\{\mathsf{out}\}\bigr)$, where $σ$ specifies the client assignments, such that $|S|\leq k$, $|σ^{-1}(i)|\geq L_i$ for all $i\in S$, and $|σ^{-1}(\mathsf{out})|\leq m$. In the {\em lower-bounded min-sum-of-radii with outliers} (\lbksro) problem, the objective is to minimize $\sum_{i\in S}\max_{j\inσ^{-1}(i)}c(i,j)$, and in the {\em lower-bounded $k$-supplier with outliers} (\lbkso) problem, the objective is to minimize $\max_{i\in S}\max_{j\inσ^{-1}(i)}c(i,j)$. We obtain an approximation factor of $12.365$ for \lbksro, which improves to $3.83$ for the non-outlier version (i.e., $m=0$). These also constitute the {\em first} approximation bounds for the min-sum-of-radii objective when we consider lower bounds and outliers {\em separately}. We apply the primal-dual method to the relaxation where we Lagrangify the $|S|\leq k$ constraint. The chief technical contribution and novelty of our algorithm is that, departing from the standard paradigm used for such constrained problems, we obtain an $O(1)$-approximation {\em despite the fact that we do not obtain a Lagrangian-multiplier-preserving algorithm for the Lagrangian relaxation}. We believe that our ideas have {broader applicability to other clustering problems with outliers as well.} We obtain approximation factors of $5$ and $3$ respectively for \lbkso and its non-outlier version. These are the {\em first} approximation results for $k$-supplier with {\em non-uniform} lower bounds.
A Note on Secure Minimum Storage Regenerating Codes
Venue: arXiv cs.IT 2016
Year: 2016

This short note revisits the problem of designing secure minimum storage regenerating (MSR) codes for distributed storage systems. A secure MSR code ensures that a distributed storage system does not reveal the stored information to a passive eavesdropper. The eavesdropper is assumed to have access to the content stored on $\ell_1$ number of storage nodes in the system and the data downloaded during the bandwidth efficient repair of an additional $\ell_2$ number of storage nodes. This note combines the Gabidulin codes based precoding [18] and a new construction of MSR codes (without security requirements) by Ye and Barg [27] in order to obtain secure MSR codes. Such optimal secure MSR codes were previously known in the setting where the eavesdropper was only allowed to observe the repair of $\ell_2$ nodes among a specific subset of $k$ nodes [7, 18]. The secure coding scheme presented in this note allows the eavesdropper to observe repair of any $\ell_2$ ouf of $n$ nodes in the system and characterizes the secrecy capacity of linear repairable MSR codes.
Linear Network Coding over Rings, Part II: Vector Codes and Non-Commutative Alphabets
Venue: arXiv cs.IT 2016
Year: 2016

We prove the following results regarding the linear solvability of networks over various alphabets. For any network, the following are equivalent: (i) vector linear solvability over some finite field, (ii) scalar linear solvability over some ring, (iii) linear solvability over some module. Analogously, the following are equivalent: (a) scalar linear solvability over some finite field, (b) scalar linear solvability over some commutative ring, (c) linear solvability over some module whose ring is commutative. Whenever any network is linearly solvable over a module, a smallest such module arises in a vector linear solution for that network over a field. If a network is linearly solvable over some non-commutative ring but not over any commutative ring, then such a non-commutative ring must have size at least $16$, and for some networks, this bound is achieved. An infinite family of networks is demonstrated, each of which is scalar linearly solvable over some non-commutative ring but not over any commutative ring. Whenever $p$ is prime and $2 \le k \le 6$, if a network is scalar linearly solvable over some ring of size $p^k$, then it is also $k$-dimensional vector linearly solvable over the field $GF(p)$, but the converse does not necessarily hold. This result is extended to all $k\ge 2$ when the ring is commutative.
Play and Learn: Using Video Games to Train Computer Vision Models
Venue: arXiv cs.CV 2016
Year: 2016

Video games are a compelling source of annotated data as they can readily provide fine-grained groundtruth for diverse tasks. However, it is not clear whether the synthetically generated data has enough resemblance to the real-world images to improve the performance of computer vision models in practice. We present experiments assessing the effectiveness on real-world data of systems trained on synthetic RGB images that are extracted from a video game. We collected over 60000 synthetic samples from a modern video game with similar conditions to the real-world CamVid and Cityscapes datasets. We provide several experiments to demonstrate that the synthetically generated RGB images can be used to improve the performance of deep neural networks on both image segmentation and depth estimation. These results show that a convolutional network trained on synthetic data achieves a similar test error to a network that is trained on real-world data for dense image classification. Furthermore, the synthetically generated RGB images can provide similar or better results compared to the real-world datasets if a simple domain adaptation technique is applied. Our results suggest that collaboration with game developers for an accessible interface to gather data is potentially a fruitful direction for future work in computer vision.