OpenRaiser/Intern-Atlas huggingface dataset:
Encoding Watermark Numbers as Reducible Permutation Graphs using Self-inverting Permutations
Venue: arXiv cs.DS 2017
Year: 2017

Several graph theoretic watermark methods have been proposed to encode numbers as graph structures in software watermarking environments. In this paper, we propose an efficient and easily implementable codec system for encoding watermark numbers as reducible permutation flow-graphs and, thus, we extend the class of graphs used in such a watermarking environment. More precisely, we present an algorithm for encoding a watermark number $w$ as a self-inverting permutation $π^*$, an algorithm for encoding the self-inverting permutation $π^*$ into a reducible permutation graph $F[π^*]$ whose structure resembles the structure of real program graphs, as well as decoding algorithms which extract the permutation $π^*$ from the reducible permutation graph $F[π^*]$ and the number $w$ from $π^*$. Both the encoding and the decoding process takes time and space linear in the length of the binary representation of $w$. The two main components of our proposed codec system, i.e., the self-inverting permutation $π^*$ and the reducible permutation graph $F[π^*]$, incorporate the binary representation of the watermark~$w$ in their structure and possess important structural properties, which make our system resilient to attacks; to this end, we experimentally evaluated our system under edge modification attacks on the graph $F[π^*]$ and the results show that we can detect such attacks with high probability.
Lattice-based Locality Sensitive Hashing is Optimal
Venue: arXiv cs.DS 2017
Year: 2017

Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (STOC `98) to give the first sublinear time algorithm for the c-approximate nearest neighbor (ANN) problem using only polynomial space. At a high level, an LSH family hashes "nearby" points to the same bucket and "far away" points to different buckets. The quality of measure of an LSH family is its LSH exponent, which helps determine both query time and space usage. In a seminal work, Andoni and Indyk (FOCS `06) constructed an LSH family based on random ball partitioning of space that achieves an LSH exponent of 1/c^2 for the l_2 norm, which was later shown to be optimal by Motwani, Naor and Panigrahy (SIDMA `07) and O'Donnell, Wu and Zhou (TOCT `14). Although optimal in the LSH exponent, the ball partitioning approach is computationally expensive. So, in the same work, Andoni and Indyk proposed a simpler and more practical hashing scheme based on Euclidean lattices and provided computational results using the 24-dimensional Leech lattice. However, no theoretical analysis of the scheme was given, thus leaving open the question of finding the exponent of lattice based LSH. In this work, we resolve this question by showing the existence of lattices achieving the optimal LSH exponent of 1/c^2 using techniques from the geometry of numbers. At a more conceptual level, our results show that optimal LSH space partitions can have periodic structure. Understanding the extent to which additional structure can be imposed on these partitions, e.g. to yield low space and query complexity, remains an important open problem.
Extended Product and Integrated Interleaved Codes
Venue: arXiv cs.IT 2017
Year: 2017

A new class of codes, Extended Product (EPC) Codes, consisting of a product code with a number of extra parities added, is presented and applications for erasure decoding are discussed. An upper bound on the minimum distance of EPC codes is given, as well as constructions meeting the bound for some relevant cases. A special case of EPC codes, Extended Integrated Interleaved (EII) codes, which naturally unify Integrated Interleaved (II) codes and product codes, is defined and studied in detail. It is shown that EII codes often improve the minimum distance of II codes with the same rate, and they enhance the decoding algorithm by allowing decoding on columns as well as on rows. It is also shown that EII codes allow for encoding II codes with an uniform distribution of the parity symbols.
Feature Extraction and Feature Selection: Reducing Data Complexity with Apache Spark
Venue: arXiv cs.DB 2017
Year: 2017

Feature extraction and feature selection are the first tasks in pre-processing of input logs in order to detect cyber security threats and attacks while utilizing machine learning. When it comes to the analysis of heterogeneous data derived from different sources, these tasks are found to be time-consuming and difficult to be managed efficiently. In this paper, we present an approach for handling feature extraction and feature selection for security analytics of heterogeneous data derived from different network sensors. The approach is implemented in Apache Spark, using its python API, named pyspark.
Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
Venue: arXiv cs.LG 2017
Year: 2017

Reinforcement learning (RL) has been successfully used to solve many continuous control tasks. Despite its impressive results however, fundamental questions regarding the sample complexity of RL on continuous problems remain open. We study the performance of RL in this setting by considering the behavior of the Least-Squares Temporal Difference (LSTD) estimator on the classic Linear Quadratic Regulator (LQR) problem from optimal control. We give the first finite-time analysis of the number of samples needed to estimate the value function for a fixed static state-feedback policy to within $\varepsilon$-relative error. In the process of deriving our result, we give a general characterization for when the minimum eigenvalue of the empirical covariance matrix formed along the sample path of a fast-mixing stochastic process concentrates above zero, extending a result by Koltchinskii and Mendelson in the independent covariates setting. Finally, we provide experimental evidence indicating that our analysis correctly captures the qualitative behavior of LSTD on several LQR instances.
Relevance Scoring of Triples Using Ordinal Logistic Classification - The Celosia Triple Scorer at WSDM Cup 2017
Venue: arXiv cs.IR 2017
Year: 2017

In this paper, we report our participation in the Task 2: Triple Scoring of WSDM Cup challenge 2017. In this task, we were provided with triples of "type-like" relations which were given human-annotated relevance scores ranging from 0 to 7, with 7 being the "most relevant" and 0 being the "least relevant". The task focuses on two such relations: profession and nationality. We built a system which could automatically predict the relevance scores for unseen triples. Our model is primarily a supervised machine learning based one in which we use well-designed features which are used to a make a Logistic Ordinal Regression based classification model. The proposed system achieves an overall accuracy score of 0.73 and Kendall's tau score of 0.36.
Query-limited Black-box Attacks to Classifiers
Venue: arXiv cs.CR 2017
Year: 2017

We study black-box attacks on machine learning classifiers where each query to the model incurs some cost or risk of detection to the adversary. We focus explicitly on minimizing the number of queries as a major objective. Specifically, we consider the problem of attacking machine learning classifiers subject to a budget of feature modification cost while minimizing the number of queries, where each query returns only a class and confidence score. We describe an approach that uses Bayesian optimization to minimize the number of queries, and find that the number of queries can be reduced to approximately one tenth of the number needed through a random strategy for scenarios where the feature modification cost budget is low.
Combining Weakly and Webly Supervised Learning for Classifying Food Images
Venue: arXiv cs.CV 2017
Year: 2017

Food classification from images is a fine-grained classification problem. Manual curation of food images is cost, time and scalability prohibitive. On the other hand, web data is available freely but contains noise. In this paper, we address the problem of classifying food images with minimal data curation. We also tackle a key problems with food images from the web where they often have multiple cooccuring food types but are weakly labeled with a single label. We first demonstrate that by sequentially adding a few manually curated samples to a larger uncurated dataset from two web sources, the top-1 classification accuracy increases from 50.3% to 72.8%. To tackle the issue of weak labels, we augment the deep model with Weakly Supervised learning (WSL) that results in an increase in performance to 76.2%. Finally, we show some qualitative results to provide insights into the performance improvements using the proposed ideas.
A Framework for Enriching Lexical Semantic Resources with Distributional Semantics
Venue: arXiv cs.CL 2017
Year: 2017

We present an approach to combining distributional semantic representations induced from text corpora with manually constructed lexical-semantic networks. While both kinds of semantic resources are available with high lexical coverage, our aligned resource combines the domain specificity and availability of contextual information from distributional models with the conciseness and high quality of manually crafted lexical networks. We start with a distributional representation of induced senses of vocabulary terms, which are accompanied with rich context information given by related lexical items. We then automatically disambiguate such representations to obtain a full-fledged proto-conceptualization, i.e. a typed graph of induced word senses. In a final step, this proto-conceptualization is aligned to a lexical ontology, resulting in a hybrid aligned resource. Moreover, unmapped induced senses are associated with a semantic type in order to connect them to the core resource. Manual evaluations against ground-truth judgments for different stages of our method as well as an extrinsic evaluation on a knowledge-based Word Sense Disambiguation benchmark all indicate the high quality of the new hybrid resource. Additionally, we show the benefits of enriching top-down lexical knowledge resources with bottom-up distributional information from text for addressing high-end knowledge acquisition tasks such as cleaning hypernym graphs and learning taxonomies from scratch.
How Intelligent is your Intelligent Robot?
Venue: arXiv cs.RO 2017
Year: 2017

How intelligent is robot A compared with robot B? And how intelligent are robots A and B compared with animals (or plants) X and Y? These are both interesting and deeply challenging questions. In this paper we address the question "how intelligent is your intelligent robot?" by proposing that embodied intelligence emerges from the interaction and integration of four different and distinct kinds of intelligence. We then suggest a simple diagrammatic representation on which these kinds of intelligence are shown as four axes in a star diagram. A crude qualitative comparison of the intelligence graphs of animals and robots both exposes and helps to explain the chronic intelligence deficit of intelligent robots. Finally we examine the options for determining numerical values for the four kinds of intelligence in an effort to move toward a quantifiable intelligence vector.
Comparative Opinion Mining: A Review
Venue: arXiv cs.IR 2017
Year: 2017

Opinion mining refers to the use of natural language processing, text analysis and computational linguistics to identify and extract subjective information in textual material. Opinion mining, also known as sentiment analysis, has received a lot of attention in recent times, as it provides a number of tools to analyse the public opinion on a number of different topics. Comparative opinion mining is a subfield of opinion mining that deals with identifying and extracting information that is expressed in a comparative form (e.g.~"paper X is better than the Y"). Comparative opinion mining plays a very important role when ones tries to evaluate something, as it provides a reference point for the comparison. This paper provides a review of the area of comparative opinion mining. It is the first review that cover specifically this topic as all previous reviews dealt mostly with general opinion mining. This survey covers comparative opinion mining from two different angles. One from perspective of techniques and the other from perspective of comparative opinion elements. It also incorporates preprocessing tools as well as dataset that were used by the past researchers that can be useful to the future researchers in the field of comparative opinion mining.
Kernel Regression with Sparse Metric Learning
Venue: arXiv cs.LG 2017
Year: 2017

Kernel regression is a popular non-parametric fitting technique. It aims at learning a function which estimates the targets for test inputs as precise as possible. Generally, the function value for a test input is estimated by a weighted average of the surrounding training examples. The weights are typically computed by a distance-based kernel function and they strongly depend on the distances between examples. In this paper, we first review the latest developments of sparse metric learning and kernel regression. Then a novel kernel regression method involving sparse metric learning, which is called kernel regression with sparse metric learning (KR$\_$SML), is proposed. The sparse kernel regression model is established by enforcing a mixed $(2,1)$-norm regularization over the metric matrix. It learns a Mahalanobis distance metric by a gradient descent procedure, which can simultaneously conduct dimensionality reduction and lead to good prediction results. Our work is the first to combine kernel regression with sparse metric learning. To verify the effectiveness of the proposed method, it is evaluated on 19 data sets for regression. Furthermore, the new method is also applied to solving practical problems of forecasting short-term traffic flows. In the end, we compare the proposed method with other three related kernel regression methods on all test data sets under two criterions. Experimental results show that the proposed method is much more competitive.
Space-Efficient Algorithms for Longest Increasing Subsequence
Venue: arXiv cs.DS 2017
Year: 2017

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in $O(n \log n)$ time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For $\sqrt{n} \le s \le n$, we present algorithms that use $O(s \log n)$ bits and $O(\frac{1}{s} \cdot n^{2} \cdot \log n)$ time for computing the length of a longest increasing subsequence, and $O(\frac{1}{s} \cdot n^{2} \cdot \log^{2} n)$ time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.
An Extensible Ad Hoc Interface between Lean and Mathematica
Venue: arXiv cs.LO 2017
Year: 2017

We implement a user-extensible ad hoc connection between the Lean proof assistant and the computer algebra system Mathematica. By reflecting the syntax of each system in the other and providing a flexible interface for extending translation, our connection allows for the exchange of arbitrary information between the two systems. We show how to make use of the Lean metaprogramming framework to verify certain Mathematica computations, so that the rigor of the proof assistant is not compromised.
Learning Based on CC1 and CC4 Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

We propose that a general learning system should have three kinds of agents corresponding to sensory, short-term, and long-term memory that implicitly will facilitate context-free and context-sensitive aspects of learning. These three agents perform mututally complementary functions that capture aspects of the human cognition system. We investigate the use of CC1 and CC4 networks for use as models of short-term and sensory memory.
An Online Ride-Sharing Path Planning Strategy for Public Vehicle Systems
Venue: arXiv cs.AI 2017
Year: 2017

As efficient traffic-management platforms, public vehicle (PV) systems are envisioned to be a promising approach to solving traffic congestions and pollutions for future smart cities. PV systems provide online/dynamic peer-to-peer ride-sharing services with the goal of serving sufficient number of customers with minimum number of vehicles and lowest possible cost. A key component of the PV system is the online ride-sharing scheduling strategy. In this paper, we propose an efficient path planning strategy that focuses on a limited potential search area for each vehicle by filtering out the requests that violate passenger service quality level, so that the global search is reduced to local search. We analyze the performance of the proposed solution such as reduction ratio of computational complexity. Simulations based on the Manhattan taxi data set show that, the computing time is reduced by 22% compared with the exhaustive search method under the same service quality performance.
RaspiReader: Open Source Fingerprint Reader
Venue: arXiv cs.CV 2017
Year: 2017

We open source an easy to assemble, spoof resistant, high resolution, optical fingerprint reader, called RaspiReader, using ubiquitous components. By using our open source STL files and software, RaspiReader can be built in under one hour for only US $175. As such, RaspiReader provides the fingerprint research community a seamless and simple method for quickly prototyping new ideas involving fingerprint reader hardware. In particular, we posit that this open source fingerprint reader will facilitate the exploration of novel fingerprint spoof detection techniques involving both hardware and software. We demonstrate one such spoof detection technique by specially customizing RaspiReader with two cameras for fingerprint image acquisition. One camera provides high contrast, frustrated total internal reflection (FTIR) fingerprint images, and the other outputs direct images of the finger in contact with the platen. Using both of these image streams, we extract complementary information which, when fused together and used for spoof detection, results in marked performance improvement over previous methods relying only on grayscale FTIR images provided by COTS optical readers. Finally, fingerprint matching experiments between images acquired from the FTIR output of RaspiReader and images acquired from a COTS reader verify the interoperability of the RaspiReader with existing COTS optical readers.
Horn-ICE Learning for Synthesizing Invariants and Contracts
Venue: arXiv cs.LO 2017
Year: 2017

We design learning algorithms for synthesizing invariants using Horn implication counterexamples (Horn-ICE), extending the ICE-learning model. In particular, we describe a decision-tree learning algorithm that learns from Horn-ICE samples, works in polynomial time, and uses statistical heuristics to learn small trees that satisfy the samples. Since most verification proofs can be modeled using Horn clauses, Horn-ICE learning is a more robust technique to learn inductive annotations that prove programs correct. Our experiments show that an implementation of our algorithm is able to learn adequate inductive invariants and contracts efficiently for a variety of sequential and concurrent programs.
Timely Feedback in Unstructured Cybersecurity Exercises
Venue: arXiv cs.CR 2017
Year: 2017

Cyber defence exercises are intensive, hands-on learning events for teams of professionals who gain or develop their skills to successfully prevent and respond to cyber attacks. The exercises mimic the real-life, routine operation of an organization which is being attacked by an unknown offender. Teams of learners receive very limited immediate feedback from the instructors during the exercise; they can usually see only a scoreboard showing the aggregated gain or loss of points for particular tasks. An in-depth analysis of learners' actions requires considerable human effort, which results in days or weeks of delay. The intensive experience is thus not followed by proper feedback facilitating actual learning, and this diminishes the effect of the exercise. In this initial work, we investigate how to provide valuable feedback to learners right after the exercise without any unnecessary delay. Based on the scoring system of a cyber defence exercise, we have developed a new feedback tool that presents an interactive, personalized timeline of exercise events. We deployed this tool during an international exercise, where we monitored participants' interactions and gathered their reflections. The results show that learners did use the new tool and rated it positively. Since this new feature is not bound to a particular defence exercise, it can be applied to all exercises that employ scoring based on the evaluation of individual exercise objectives. As a result, it enables the learner to immediately reflect on the experience gained.
Closed-Form Coverage Probability for Downlink Poisson Network with Double Shadowed Fading
Venue: arXiv cs.IT 2017
Year: 2017

Performances of cellular networks over κ-μ shadowed fading with long-term shadowing has been studied in the existing literature. However, the impact of κ-μ shadowed fading with instantaneous shadowing on performances of cellular networks is unknown. Therefore, this letter analyzes the downlink coverage probability of a Poisson network with double shadowed fading which is composed of a large-scale fading of lognormal distribution and κ-μ shadowed fading with integer fading parameters. The closest base station association rule without shadowing is considered. For analytical tractability, the double shadowed fading is approximated as a weighted sum of κ-μ shadowed distributions based on the Gaussian-Hermit quadrature. As a main theoretical result, a closed-form expression for the downlink coverage probability of a Poisson network under double shadowed fading for the desired signal and arbitrary fading for the interfering signals is successfully derived. Numerical simulations reveal that the double shadowed fading provides a pessimistic coverage on a Poisson network compared with the long-term shadowing which is incorporated into cell selection.
Sketching for Kronecker Product Regression and P-splines
Venue: arXiv cs.DS 2017
Year: 2017

TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was shown in Avron, Nguyen, Woodruff'14 that TensorSketch provides a subspace embedding, and therefore can be used for canonical correlation analysis, low rank approximation, and principal component regression for the polynomial kernel. We take TensorSketch outside of the context of polynomials kernels, and show its utility in applications in which the underlying design matrix is a Kronecker product of smaller matrices. This allows us to solve Kronecker product regression and non-negative Kronecker product regression, as well as regularized spline regression. Our main technical result is then in extending TensorSketch to other norms. That is, TensorSketch only provides input sparsity time for Kronecker product regression with respect to the $2$-norm. We show how to solve Kronecker product regression with respect to the $1$-norm in time sublinear in the time required for computing the Kronecker product, as well as for more general $p$-norms.