OpenRaiser/Intern-Atlas huggingface dataset:
Triangle packing in (sparse) tournaments: approximation and kernelization
Venue: arXiv cs.DS 2017
Year: 2017

Given a tournament T and a positive integer k, the C_3-Pakcing-T problem asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C_3-Pakcing-T did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a (1+6/(c-1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have "length" at least c. Concerning kernelization, we show that C_3-Pakcing-T admits a kernel with O(m) vertices, where m is the size of a given feedback arc set. In particular, we derive a O(k) vertices kernel for C_3-Pakcing-T when restricted to sparse instances. On the negative size, we show that C_3-Pakcing-T does not admit a kernel of (total bit) size O(k^{2-ε}) unless NP is a subset of coNP / Poly. The existence of a kernel in O(k) vertices for C_3-Pakcing-T remains an open question.
Lithium NLP: A System for Rich Information Extraction from Noisy User Generated Text on Social Media
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, we describe the Lithium Natural Language Processing (NLP) system - a resource-constrained, high- throughput and language-agnostic system for information extraction from noisy user generated text on social media. Lithium NLP extracts a rich set of information including entities, topics, hashtags and sentiment from text. We discuss several real world applications of the system currently incorporated in Lithium products. We also compare our system with existing commercial and academic NLP systems in terms of performance, information extracted and languages supported. We show that Lithium NLP is at par with and in some cases, outperforms state- of-the-art commercial NLP systems.
Sparse Impulse Noise Minimization in UWB Communication using Signal Characteristics
Venue: arXiv cs.IT 2017
Year: 2017

In many applications, ultra-wide band (UWB) system experiences impulse noise due to surrounding physical noise sources. Therefore, a conventional receiver (correlator or matched filter) designed for additive Gaussian noise system is not optimum for an impulse noise affected communication channel. In this paper, we propose a new robust receiver design that utilizes the received UWB signal cluster sparsity to mitigate impulse noise. Further, multipath channel diversity enhances the signal-to-noise ratio, as compared to the single path after impulse noise removal in the proposed receiver design. The proposed receiver is analyzed in time hopping binary phase shift keying UWB system and is compared with popular blanking non-linearity based receiver in Bernoulli-Gaussian impulse noise over both single and multipath IEEE 802.15.4a channels. Unlike existing designs, the proposed receiver does not require any training sequence. The proposed receiver is observed to be robust with improved bit error rate performance as compared to a blanking receiver in the presence of impulse noise.
Predicting Abandonment in Online Coding Tutorials
Venue: arXiv cs.LG 2017
Year: 2017

Learners regularly abandon online coding tutorials when they get bored or frustrated, but there are few techniques for anticipating this abandonment to intervene. In this paper, we examine the feasibility of predicting abandonment with machine-learned classifiers. Using interaction logs from an online programming game, we extracted a collection of features that are potentially related to learner abandonment and engagement, then developed classifiers for each level. Across the first five levels of the game, our classifiers successfully predicted 61% to 76% of learners who did not complete the next level, achieving an average AUC of 0.68. In these classifiers, features negatively associated with abandonment included account activation and help-seeking behaviors, whereas features positively associated with abandonment included features indicating difficulty and disengagement. These findings highlight the feasibility of providing timely intervention to learners likely to quit.
Tensor-Based Backpropagation in Neural Networks with Non-Sequential Input
Venue: arXiv cs.LG 2017
Year: 2017

Neural networks have been able to achieve groundbreaking accuracy at tasks conventionally considered only doable by humans. Using stochastic gradient descent, optimization in many dimensions is made possible, albeit at a relatively high computational cost. By splitting training data into batches, networks can be distributed and trained vastly more efficiently and with minimal accuracy loss. We have explored the mathematics behind efficiently implementing tensor-based batch backpropagation algorithms. A common approach to batch training is iterating over batch items individually. Explicitly using tensor operations to backpropagate allows training to be performed non-linearly, increasing computational efficiency.
Non-locality of the meet levels of the Trotter-Weil Hierarchy
Venue: arXiv cs.FL 2017
Year: 2017

We prove that the meet level $m$ of the Trotter-Weil, $\mathsf{V}_m$ is not local for all $m \geq 1$, as conjectured in a paper by Kufleitner and Lauser. In order to show this, we explicitly provide a language whose syntactic semigroup is in $L \mathsf{V}_m$ and not in $\mathsf{V}_m*\mathsf{D}$.
Optimal Asynchronous Rendezvous for Mobile Robots with Lights
Venue: arXiv cs.DC 2017
Year: 2017

We study a Rendezvous problem for 2 autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible when robots have no lights in basic common models, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights with a constant number of colors in several types lights. In asynchronous settings, Rendezvous can be solved by robots with 4 colors of lights in non-rigid movement, if robots can use not only own light but also other robot's light (full-light), where non-rigid movement means robots may be stopped before reaching the computed destination but can move a minimum distance δ> 0 and rigid movement means robots can reach the computed destination. In semi-synchronous settings, Rendezvous can be solved with 2 colors of full-lights in non-rigid movement. In this paper, we show that in asynchronous settings, Rendezvous can be solved with 2 colors of full-lights in rigid movement and in non-rigid movement if robots know the value of the minimum distance δ. We also show that Rendezvous can be solved with 2 colors of full-lights in general non-rigid movement if we consider some reasonable restricted class of asynchronous settings.
LIUM-CVC Submissions for WMT17 Multimodal Translation Task
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the monomodal and multimodal Neural Machine Translation systems developed by LIUM and CVC for WMT17 Shared Task on Multimodal Translation. We mainly explored two multimodal architectures where either global visual features or convolutional feature maps are integrated in order to benefit from visual context. Our final systems ranked first for both En-De and En-Fr language pairs according to the automatic evaluation metrics METEOR and BLEU.
Guiding InfoGAN with Semi-Supervision
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we propose a new semi-supervised GAN architecture (ss-InfoGAN) for image synthesis that leverages information from few labels (as little as 0.22%, max. 10% of the dataset) to learn semantically meaningful and controllable data representations where latent variables correspond to label categories. The architecture builds on Information Maximizing Generative Adversarial Networks (InfoGAN) and is shown to learn both continuous and categorical codes and achieves higher quality of synthetic samples compared to fully unsupervised settings. Furthermore, we show that using small amounts of labeled data speeds-up training convergence. The architecture maintains the ability to disentangle latent variables for which no labels are available. Finally, we contribute an information-theoretic reasoning on how introducing semi-supervision increases mutual information between synthetic and real data.
An Efficient Approach to Communication-aware Path Planning for Long-range Surveillance Missions undertaken by UAVs
Venue: arXiv cs.RO 2017
Year: 2017

While using drones for remote surveillance missions, it is mandatory to do path planning of the vehicle since these are pilot-less vehicles. Path planning, whether offline or online, entails setting up the path as a sequence of locations in the 3D Euclidean space, whose coordinates happen to be latitude, longitude and altitude. For the specific application of remote surveillance of long linear infrastructures in non-urban terrain, the continuous 3D-ESP problem practically entails two important scalar costs. The first scalar cost is the distance traveled along the planned path. Since drones are battery operated, hence it is needed that the path length between fixed start and goal locations of a mission should be minimal at all costs. The other scalar cost is the cost of transmitting the acquired video during the mission of remote surveillance, via a camera mounted in the drone's belly. Because of the length of surveillance target which is long linear infrastructure, the amount of video generated is very high and cannot be generally stored in its entirety, on board. If the connectivity is poor along certain segments of a naive path, to boost video transmission rate, the transmission power of the signal is kept high, which in turn dissipates more battery energy. Hence a path is desired that simultaneously also betters what is known as communication cost. These two costs trade-off, and hence Pareto optimization is needed for this 3D bi-objective Euclidean shortest path problem. In this report, we study the mono-objective offline path planning problem, based on the distance cost, while posing the communication cost as an upper-bounded constraint. The bi-objective path planning solution is sketched out towards the end.
Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
Venue: arXiv cs.SI 2017
Year: 2017

Detection of overlapping communities in real-world networks is a generally challenging task. Upon recognizing that a network is in fact the union of its egonets, a novel network representation using multi-way data structures is advocated in this contribution. The introduced sparse tensor-based representation exhibits richer structure compared to its matrix counterpart, and thus enables a more robust approach to community detection. To leverage this structure, a constrained tensor approximation framework is introduced using PARAFAC decomposition. The arising constrained trilinear optimization is handled via alternating minimization, where intermediate subproblems are solved using the alternating direction method of multipliers (ADMM) to ensure convergence. The factors obtained provide soft community memberships, which can further be exploited for crisp, and possibly-overlapping community assignments. The framework is further broadened to include time-varying graphs, where the edgeset as well as the underlying communities evolve through time. Performance of the proposed approach is assessed via tests on benchmark synthetic graphs as well as real-world networks. As corroborated by numerical tests, the proposed tensor-based representation captures multi-hop nodal connections, that is, connectivity patterns within single-hop neighbors, whose exploitation yields a more robust community identification in the presence of mixing as well as overlapping communities.
Simplified Long Short-term Memory Recurrent Neural Networks: part I
Venue: arXiv cs.NE 2017
Year: 2017

We present five variants of the standard Long Short-term Memory (LSTM) recurrent neural networks by uniformly reducing blocks of adaptive parameters in the gating mechanisms. For simplicity, we refer to these models as LSTM1, LSTM2, LSTM3, LSTM4, and LSTM5, respectively. Such parameter-reduced variants enable speeding up data training computations and would be more suitable for implementations onto constrained embedded platforms. We comparatively evaluate and verify our five variant models on the classical MNIST dataset and demonstrate that these variant models are comparable to a standard implementation of the LSTM model while using less number of parameters. Moreover, we observe that in some cases the standard LSTM's accuracy performance will drop after a number of epochs when using the ReLU nonlinearity; in contrast, however, LSTM3, LSTM4 and LSTM5 will retain their performance.
UAV Air-to-Ground Channel Characterization for mmWave Systems
Venue: arXiv cs.IT 2017
Year: 2017

Communication at mmWave bands carries critical importance for 5G wireless networks. In this paper, we study the characterization of mmWave air-to-ground (AG) channels for unmanned aerial vehicle (UAV) communications. In particular, we use ray tracing simulations using Remcom Wireless InSite software to study the behavior of AG mmWave bands at two different frequencies: 28~GHz and 60~GHz. Received signal strength (RSS) and root mean square delay spread (RMS-DS) of multipath components (MPCs) are analyzed for different UAV heights considering four different environments: urban, suburban, rural, and over sea. It is observed that the RSS mostly follows the two ray propagation model along the UAV flight path for higher altitudes. This two ray propagation model is affected by the presence of high rise scatterers in urban scenario. Moreover, we present details of a universal serial radio peripheral (USRP) based channel sounder that can be used for AG channel measurements for mmWave (60 GHz) UAV communications.
Simplified Long Short-term Memory Recurrent Neural Networks: part II
Venue: arXiv cs.NE 2017
Year: 2017

This is part II of three-part work. Here, we present a second set of inter-related five variants of simplified Long Short-term Memory (LSTM) recurrent neural networks by further reducing adaptive parameters. Two of these models have been introduced in part I of this work. We evaluate and verify our model variants on the benchmark MNIST dataset and assert that these models are comparable to the base LSTM model while use progressively less number of parameters. Moreover, we observe that in case of using the ReLU activation, the test accuracy performance of the standard LSTM will drop after a number of epochs when learning parameter become larger. However all of the new model variants sustain their performance.
EmojiNet: An Open Service and API for Emoji Sense Discovery
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents the release of EmojiNet, the largest machine-readable emoji sense inventory that links Unicode emoji representations to their English meanings extracted from the Web. EmojiNet is a dataset consisting of: (i) 12,904 sense labels over 2,389 emoji, which were extracted from the web and linked to machine-readable sense definitions seen in BabelNet, (ii) context words associated with each emoji sense, which are inferred through word embedding models trained over Google News corpus and a Twitter message corpus for each emoji sense definition, and (iii) recognizing discrepancies in the presentation of emoji on different platforms, specification of the most likely platform-based emoji sense for a selected set of emoji. The dataset is hosted as an open service with a REST API and is available at http://emojinet.knoesis.org/. The development of this dataset, evaluation of its quality, and its applications including emoji sense disambiguation and emoji sense similarity are discussed.
Ternary Residual Networks
Venue: arXiv cs.IT 2017
Year: 2017

Sub-8-bit representation of DNNs incur some discernible loss of accuracy despite rigorous (re)training at low-precision. Such loss of accuracy essentially makes them equivalent to a much shallower counterpart, diminishing the power of being deep networks. To address this problem of accuracy drop we introduce the notion of \textit{residual networks} where we add more low-precision edges to sensitive branches of the sub-8-bit network to compensate for the lost accuracy. Further, we present a perturbation theory to identify such sensitive edges. Aided by such an elegant trade-off between accuracy and compute, the 8-2 model (8-bit activations, ternary weights), enhanced by ternary residual edges, turns out to be sophisticated enough to achieve very high accuracy ($\sim 1\%$ drop from our FP-32 baseline), despite $\sim 1.6\times$ reduction in model size, $\sim 26\times$ reduction in number of multiplications, and potentially $\sim 2\times$ power-performance gain comparing to 8-8 representation, on the state-of-the-art deep network ResNet-101 pre-trained on ImageNet dataset. Moreover, depending on the varying accuracy requirements in a dynamic environment, the deployed low-precision model can be upgraded/downgraded on-the-fly by partially enabling/disabling residual connections. For example, disabling the least important residual connections in the above enhanced network, the accuracy drop is $\sim 2\%$ (from FP32), despite $\sim 1.9\times$ reduction in model size, $\sim 32\times$ reduction in number of multiplications, and potentially $\sim 2.3\times$ power-performance gain comparing to 8-8 representation. Finally, all the ternary connections are sparse in nature, and the ternary residual conversion can be done in a resource-constraint setting with no low-precision (re)training.
$Θ_S-$cyclic codes over $A_k$
Venue: arXiv cs.IT 2017
Year: 2017

We study $Θ_S-$cyclic codes over the family of rings $A_k.$ We characterize $Θ_S-$cyclic codes in terms of their binary images. A family of Hermitian inner-products is defined and we prove that if a code is $Θ_S-$cyclic then its Hermitian dual is also $Θ_S-$cyclic. Finally, we give constructions of $Θ_S-$cyclic codes.
A new NS3 Implementation of CCNx 1.0 Protocol
Venue: arXiv cs.NI 2017
Year: 2017

The ccns3Sim project is an open source implementation of the CCNx 1.0 protocols for the NS3 simulator. We describe the implementation and several important features including modularity and process delay simulation. The ccns3Sim implementation is a fresh NS3-specific implementation. Like NS3 itself, it uses C++98 standard, NS3 code style, NS3 smart pointers, NS3 xUnit, and integrates with the NS3 documentation and manual. A user or developer does not need to learn two systems. If one knows NS3, one should be able to get started with the CCNx code right away. A developer can easily use their own implementation of the layer 3 protocol, layer 4 protocol, forwarder, routing protocol, Pending Interest Table (PIT) or Forwarding Information Base (FIB) or Content Store (CS). A user may configure or specify a new implementation for any of these features at runtime in the simulation script. In this paper, we describe the software architecture and give examples of using the simulator. We evaluate the implementation with several example experiments on ICN caching.
Abstracting Definitional Interpreters
Venue: arXiv cs.PL 2017
Year: 2017

In this functional pearl, we examine the use of definitional interpreters as a basis for abstract interpretation of higher-order programming languages. As it turns out, definitional interpreters, especially those written in monadic style, can provide a nice basis for a wide variety of collecting semantics, abstract interpretations, symbolic executions, and their intermixings. But the real insight of this story is a replaying of an insight from Reynold's landmark paper, Definitional Interpreters for Higher-Order Programming Languages, in which he observes definitional interpreters enable the defined-language to inherit properties of the defining-language. We show the same holds true for definitional abstract interpreters. Remarkably, we observe that abstract definitional interpreters can inherit the so-called "pushdown control flow" property, wherein function calls and returns are precisely matched in the abstract semantics, simply by virtue of the function call mechanism of the defining-language. The first approaches to achieve this property for higher-order languages appeared within the last ten years, and have since been the subject of many papers. These approaches start from a state-machine semantics and uniformly involve significant technical engineering to recover the precision of pushdown control flow. In contrast, starting from a definitional interpreter, the pushdown control flow property is inherent in the meta-language and requires no further technical mechanism to achieve.
AI Challenges in Human-Robot Cognitive Teaming
Venue: arXiv cs.AI 2017
Year: 2017

Among the many anticipated roles for robots in the future is that of being a human teammate. Aside from all the technological hurdles that have to be overcome with respect to hardware and control to make robots fit to work with humans, the added complication here is that humans have many conscious and subconscious expectations of their teammates - indeed, we argue that teaming is mostly a cognitive rather than physical coordination activity. This introduces new challenges for the AI and robotics community and requires fundamental changes to the traditional approach to the design of autonomy. With this in mind, we propose an update to the classical view of the intelligent agent architecture, highlighting the requirements for mental modeling of the human in the deliberative process of the autonomous agent. In this article, we outline briefly the recent efforts of ours, and others in the community, towards developing cognitive teammates along these guidelines.
Automatic Identification of Non-Meaningful Body-Movements and What It Reveals About Humans
Venue: arXiv cs.HC 2017
Year: 2017

We present a framework to identify whether a public speaker's body movements are meaningful or non-meaningful ("Mannerisms") in the context of their speeches. In a dataset of 84 public speaking videos from 28 individuals, we extract 314 unique body movement patterns (e.g. pacing, gesturing, shifting body weights, etc.). Online workers and the speakers themselves annotated the meaningfulness of the patterns. We extracted five types of features from the audio-video recordings: disfluency, prosody, body movements, facial, and lexical. We use linear classifiers to predict the annotations with AUC up to 0.82. Analysis of the classifier weights reveals that it puts larger weights on the lexical features while predicting self-annotations. Contrastingly, it puts a larger weight on prosody features while predicting audience annotations. This analysis might provide subtle hint that public speakers tend to focus more on the verbal features while evaluating self-performances. The audience, on the other hand, tends to focus more on the non-verbal aspects of the speech. The dataset and code associated with this work has been released for peer review and further analysis.
Android Malware Clustering through Malicious Payload Mining
Venue: arXiv cs.CR 2017
Year: 2017

Clustering has been well studied for desktop malware analysis as an effective triage method. Conventional similarity-based clustering techniques, however, cannot be immediately applied to Android malware analysis due to the excessive use of third-party libraries in Android application development and the widespread use of repackaging in malware development. We design and implement an Android malware clustering system through iterative mining of malicious payload and checking whether malware samples share the same version of malicious payload. Our system utilizes a hierarchical clustering technique and an efficient bit-vector format to represent Android apps. Experimental results demonstrate that our clustering approach achieves precision of 0.90 and recall of 0.75 for Android Genome malware dataset, and average precision of 0.98 and recall of 0.96 with respect to manually verified ground-truth.