OpenRaiser/Intern-Atlas huggingface dataset:
NeuroPod: a real-time neuromorphic spiking CPG applied to robotics
Venue: arXiv cs.RO 2019
Year: 2019

Initially, robots were developed with the aim of making our life easier, carrying out repetitive or dangerous tasks for humans. Although they were able to perform these tasks, the latest generation of robots are being designed to take a step further, by performing more complex tasks that have been carried out by smart animals or humans up to date. To this end, inspiration needs to be taken from biological examples. For instance, insects are able to optimally solve complex environment navigation problems, and many researchers have started to mimic how these insects behave. Recent interest in neuromorphic engineering has motivated us to present a real-time, neuromorphic, spike-based Central Pattern Generator of application in neurorobotics, using an arthropod-like robot. A Spiking Neural Network was designed and implemented on SpiNNaker. The network models a complex, online-change capable Central Pattern Generator which generates three gaits for a hexapod robot locomotion. Reconfigurable hardware was used to manage both the motors of the robot and the real-time communication interface with the Spiking Neural Networks. Real-time measurements confirm the simulation results, and locomotion tests show that NeuroPod can perform the gaits without any balance loss or added delay.
Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
Venue: arXiv cs.DS 2019
Year: 2019

We present an algorithm that takes as input an $n$-vertex planar graph $G$ and a $k$-vertex pattern graph $P$, and computes the number of (induced) copies of $P$ in $G$ in $2^{O(k/\log k)}n^{O(1)}$ time. If $P$ is a matching, independent set, or connected bounded maximum degree graph, the runtime reduces to $2^{\tilde{O}(\sqrt{k})}n^{O(1)}$. While our algorithm counts all copies of $P$, it also improves the fastest algorithms that only detect copies of $P$. Before our work, no $2^{O(k/\log k)}n^{O(1)}$ time algorithms for detecting unrestricted patterns $P$ were known, and by a result of Bodlaender et al. [ICALP 2016] a $2^{o(k/\log k)}n^{O(1)}$ time algorithm would violate the Exponential Time Hypothesis (ETH). Furthermore, it was only known how to detect copies of a fixed connected bounded maximum degree pattern $P$ in $2^{\tilde{O}(\sqrt{k})}n^{O(1)}$ time probabilistically. For counting problems, it was a repeatedly asked open question whether $2^{o(k)}n^{O(1)}$ time algorithms exist that count even special patterns such as independent sets, matchings and paths in planar graphs. The above results resolve this question in a strong sense by giving algorithms for counting versions of problems with running times equal to the ETH lower bounds for their decision versions. Generally speaking, our algorithm counts copies of $P$ in time proportional to its number of non-isomorphic separations of order $\tilde{O}(\sqrt{k})$. The algorithm introduces a new recursive approach to construct families of balanced cycle separators in planar graphs that have limited overlap inspired by methods from Fomin et al. [FOCS 2016], a new `efficient' inclusion-exclusion based argument and uses methods from Bodlaender et al. [ICALP 2016].
A novel method for extracting interpretable knowledge from a spiking neural classifier with time-varying synaptic weights
Venue: arXiv cs.NE 2019
Year: 2019

This paper presents a novel method for information interpretability in an MC-SEFRON classifier. To develop a method to extract knowledge stored in a trained classifier, first, the binary-class SEFRON classifier developed earlier is extended to handle multi-class problems. MC-SEFRON uses the population encoding scheme to encode the real-valued input data into spike patterns. MC-SEFRON is trained using the same supervised learning rule used in the SEFRON. After training, the proposed method extracts the knowledge for a given class stored in the classifier by mapping the weighted postsynaptic potential in the time domain to the feature domain as Feature Strength Functions (FSFs). A set of FSFs corresponding to each output class represents the extracted knowledge from the classifier. This knowledge encoding method is derived to maintain consistency between the classification in the time domain and the feature domain. The correctness of the FSF is quantitatively measured by using FSF directly for classification tasks. For a given input, each FSF is sampled at the input value to obtain the corresponding feature strength value (FSV). Then the aggregated FSVs obtained for each class are used to determine the output class labels during classification. FSVs are also used to interpret the predictions during the classification task. Using ten UCI datasets and the MNIST dataset, the knowledge extraction method, interpretation and the reliability of the FSF are demonstrated. Based on the studies, it can be seen that on an average, the difference in the classification accuracies using the FSF directly and those obtained by MC-SEFRON is only around 0.9% & 0.1\% for the UCI datasets and the MNIST dataset respectively. This clearly shows that the knowledge represented by the FSFs has acceptable reliability and the interpretability of classification using the classifier's knowledge has been justified.
Identifying short-term interests from mobile app adoption pattern
Venue: arXiv cs.IR 2019
Year: 2019

With the increase in an average user's dependence on their mobile devices, the reliance on collecting his browsing history from mobile browsers has also increased. This browsing history is highly utilized in the advertising industry for providing targeted ads in the purview of inferring his short-term interests and pushing relevant ads. However, the major limitation of such an extraction from mobile browsers is that they reset when the browser is closed or when the device is shut down/restarted; thus rendering existing methods to identify the user's short-term interests on mobile devices users, ineffective. In this paper, we propose an alternative method to identify such short-term interests by analysing their mobile app adoption (installation/uninstallation) patterns over a period of time. Such a method can be highly effective in pinpointing the user's ephemeral inclinations like buying/renting an apartment, buying/selling a car or a sudden increased interest in shopping (possibly due to a recent salary bonus, he received). Subsequently, these derived interests are also used for targeted experiments. Our experiments result in up to 93.68% higher click-through rate in comparison to the ads shown without any user-interest knowledge. Also, up to 51% higher revenue in the long term is expected as a result of the application of our proposed algorithm.
Reward-Based Deception with Cognitive Bias
Venue: arXiv cs.AI 2019
Year: 2019

Deception plays a key role in adversarial or strategic interactions for the purpose of self-defence and survival. This paper introduces a general framework and solution to address deception. Most existing approaches for deception consider obfuscating crucial information to rational adversaries with abundant memory and computation resources. In this paper, we consider deceiving adversaries with bounded rationality and in terms of expected rewards. This problem is commonly encountered in many applications especially involving human adversaries. Leveraging the cognitive bias of humans in reward evaluation under stochastic outcomes, we introduce a framework to optimally assign resources of a limited quantity to optimally defend against human adversaries. Modeling such cognitive biases follows the so-called prospect theory from behavioral psychology literature. Then we formulate the resource allocation problem as a signomial program to minimize the defender's cost in an environment modeled as a Markov decision process. We use police patrol hour assignment as an illustrative example and provide detailed simulation results based on real-world data.
Terminologies augmented recurrent neural network model for clinical named entity recognition
Venue: arXiv cs.CL 2019
Year: 2019

We aimed to enhance the performance of a supervised model for clinical named-entity recognition (NER) using medical terminologies. In order to evaluate our system in French, we built a corpus for 5 types of clinical entities. We used a terminology-based system as baseline, built upon UMLS and SNOMED. Then, we evaluated a biGRU-CRF, and an hybrid system using the prediction of the terminology-based system as feature for the biGRU-CRF. In English, we evaluated the NER systems on the i2b2-2009 Medication Challenge for Drug name recognition, which contained 8,573 entities for 268 documents. In French, we built APcNER, a corpus of 147 documents annotated for 5 entities (drug name, sign or symptom, disease or disorder, diagnostic procedure or lab test and therapeutic procedure). We evaluated each NER systems using exact and partial match definition of F-measure for NER. The APcNER contains 4,837 entities which took 28 hours to annotate, the inter-annotator agreement was acceptable for Drug name in exact match (85%) and acceptable for other entity types in non-exact match (>70%). For drug name recognition on both i2b2-2009 and APcNER, the biGRU-CRF performed better that the terminology-based system, with an exact-match F-measure of 91.1% versus 73% and 81.9% versus 75% respectively. Moreover, the hybrid system outperformed the biGRU-CRF, with an exact-match F-measure of 92.2% versus 91.1% (i2b2-2009) and 88.4% versus 81.9% (APcNER). On APcNER corpus, the micro-average F-measure of the hybrid system on the 5 entities was 69.5% in exact match, and 84.1% in non-exact match. APcNER is a French corpus for clinical-NER of five type of entities which covers a large variety of document types. Extending supervised model with terminology allowed for an easy performance gain, especially in low regimes of entities, and established near state of the art results on the i2b2-2009 corpus.
Developing Secure Services for IoT with OP-TEE: A First Look at Performance and Usability
Venue: arXiv cs.DC 2019
Year: 2019

The implementation, deployment and testing of secure services for Internet of Things devices is nowadays still at an early stage. Several frameworks have recently emerged to help developers realize such services, abstracting the complexity of the many types of underlying hardware platforms and software libraries. Assessing the performance and usability of a given framework remains challenging, as they are largely influenced by the application and workload considered, as well as the target hardware. Since 15 years, ARM processors are providing support for TrustZone, a set of security instructions that realize a trusted execution environment inside the processor. OP-TEE is a free-software framework to implement trusted applications and services for TrustZone. In this short paper we show how one can leverage OP-TEE for implementing a secure service (i.e., a key-value store). We deploy and evaluate the performance of this trusted service on common Raspberry Pi hardware platforms. We report our experimental results with the data store and also compare it against OP-TEE's built-in secure storage.
Warm Up Cold-start Advertisements: Improving CTR Predictions via Learning to Learn ID Embeddings
Venue: arXiv cs.LG 2019
Year: 2019

Click-through rate (CTR) prediction has been one of the most central problems in computational advertising. Lately, embedding techniques that produce low-dimensional representations of ad IDs drastically improve CTR prediction accuracies. However, such learning techniques are data demanding and work poorly on new ads with little logging data, which is known as the cold-start problem. In this paper, we aim to improve CTR predictions during both the cold-start phase and the warm-up phase when a new ad is added to the candidate pool. We propose Meta-Embedding, a meta-learning-based approach that learns to generate desirable initial embeddings for new ad IDs. The proposed method trains an embedding generator for new ad IDs by making use of previously learned ads through gradient-based meta-learning. In other words, our method learns how to learn better embeddings. When a new ad comes, the trained generator initializes the embedding of its ID by feeding its contents and attributes. Next, the generated embedding can speed up the model fitting during the warm-up phase when a few labeled examples are available, compared to the existing initialization methods. Experimental results on three real-world datasets showed that Meta-Embedding can significantly improve both the cold-start and warm-up performances for six existing CTR prediction models, ranging from lightweight models such as Factorization Machines to complicated deep models such as PNN and DeepFM. All of the above apply to conversion rate (CVR) predictions as well.
The Roadmap to 6G -- AI Empowered Wireless Networks
Venue: arXiv cs.NI 2019
Year: 2019

The recent upsurge of diversified mobile applications, especially those supported by Artificial Intelligence (AI), is spurring heated discussions on the future evolution of wireless communications. While 5G is being deployed around the world, efforts from industry and academia have started to look beyond 5G and conceptualize 6G. We envision 6G to undergo an unprecedented transformation that will make it substantially different from the previous generations of wireless cellular systems. In particular, 6G will go beyond mobile Internet and will be required to support ubiquitous AI services from the core to the end devices of the network. Meanwhile, AI will play a critical role in designing and optimizing 6G architectures, protocols, and operations. In this article, we discuss potential technologies for 6G to enable mobile AI applications, as well as AI-enabled methodologies for 6G network design and optimization. Key trends in the evolution to 6G will also be discussed.
Are We Consistently Biased? Multidimensional Analysis of Biases in Distributional Word Vectors
Venue: arXiv cs.CL 2019
Year: 2019

Word embeddings have recently been shown to reflect many of the pronounced societal biases (e.g., gender bias or racial bias). Existing studies are, however, limited in scope and do not investigate the consistency of biases across relevant dimensions like embedding models, types of texts, and different languages. In this work, we present a systematic study of biases encoded in distributional word vector spaces: we analyze how consistent the bias effects are across languages, corpora, and embedding models. Furthermore, we analyze the cross-lingual biases encoded in bilingual embedding spaces, indicative of the effects of bias transfer encompassed in cross-lingual transfer of NLP models. Our study yields some unexpected findings, e.g., that biases can be emphasized or downplayed by different embedding models or that user-generated content may be less biased than encyclopedic text. We hope our work catalyzes bias research in NLP and informs the development of bias reduction techniques.
Will this Course Increase or Decrease Your GPA? Towards Grade-aware Course Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

In order to help undergraduate students towards successfully completing their degrees, developing tools that can assist students during the course selection process is a significant task in the education domain. The optimal set of courses for each student should include courses that help him/her graduate in a timely fashion and for which he/she is well-prepared for so as to get a good grade in. To this end, we propose two different grade-aware course recommendation approaches to recommend to each student his/her optimal set of courses. The first approach ranks the courses by using an objective function that differentiates between courses that are expected to increase or decrease a student's GPA. The second approach combines the grades predicted by grade prediction methods with the rankings produced by course recommendation methods to improve the final course rankings. To obtain the course rankings in the first approach, we adapt two widely-used representation learning techniques to learn the optimal temporal ordering between courses. Our experiments on a large dataset obtained from the University of Minnesota that includes students from 23 different majors show that the grade-aware course recommendation methods can do better on recommending more courses in which the students are expected to perform well and recommending fewer courses in which they are expected not to perform well in than grade-unaware course recommendation methods.
The $k$-path coloring problem in graphs with bounded treewidth: an application in integrated circuit manufacturing
Venue: arXiv cs.DM 2019
Year: 2019

In this paper, we investigate the $k$-path coloring problem, a variant of vertex coloring arising in the context of integrated circuit manufacturing. In this setting, typical industrial instances exhibit a `tree-like' structure. We exploit this property to design an efficient algorithm for our industrial problem: (i) on the methodological side, we show that the $k$-path coloring problem can be solved in polynomial time on graphs with bounded treewidth and we devise a simple polytime dynamic programming algorithm in this case (not relying on Courcelle's celebrated theorem); and (ii) on the empirical side, we provide computational evidences that the corresponding algorithm could be suitable for practice, by testing our algorithm on true instances obtained from an on-going collaboration with Mentor Graphics. We finally compare this approach with integer programming on some pseudo-industrial instances. It suggests that dynamic programming cannot compete with integer programming when the tree-width is greater than three. While all our industrial instances exhibit such a small tree-width, this is not for granted that all future instances will also do, and this tend to advocate for integer programming approaches.
AlphaClean: Automatic Generation of Data Cleaning Pipelines
Venue: arXiv cs.DB 2019
Year: 2019

The analyst effort in data cleaning is gradually shifting away from the design of hand-written scripts to building and tuning complex pipelines of automated data cleaning libraries. Hyper-parameter tuning for data cleaning is very different than hyper-parameter tuning for machine learning since the pipeline components and objective functions have structure that tuning algorithms can exploit. This paper proposes a framework, called AlphaClean, that rethinks parameter tuning for data cleaning pipelines. AlphaClean provides users with a rich library to define data quality measures with weighted sums of SQL aggregate queries. AlphaClean applies generate-then-search framework where each pipelined cleaning operator contributes candidate transformations to a shared pool. Asynchronously, in separate threads, a search algorithm sequences them into cleaning pipelines that maximize the user-defined quality measures. This architecture allows AlphaClean to apply a number of optimizations including incremental evaluation of the quality measures and learning dynamic pruning rules to reduce the search space. Our experiments on real and synthetic benchmarks suggest that AlphaClean finds solutions of up-to 9x higher quality than naively applying state-of-the-art parameter tuning methods, is significantly more robust to straggling data cleaning methods and redundancy in the data cleaning library, and can incorporate state-of-the-art cleaning systems such as HoloClean as cleaning operators.
Evaluating Recurrent Neural Network Explanations
Venue: arXiv cs.LG 2019
Year: 2019

Recently, several methods have been proposed to explain the predictions of recurrent neural networks (RNNs), in particular of LSTMs. The goal of these methods is to understand the network's decisions by assigning to each input variable, e.g., a word, a relevance indicating to which extent it contributed to a particular prediction. In previous works, some of these methods were not yet compared to one another, or were evaluated only qualitatively. We close this gap by systematically and quantitatively comparing these methods in different settings, namely (1) a toy arithmetic task which we use as a sanity check, (2) a five-class sentiment prediction of movie reviews, and besides (3) we explore the usefulness of word relevances to build sentence-level representations. Lastly, using the method that performed best in our experiments, we show how specific linguistic phenomena such as the negation in sentiment analysis reflect in terms of relevance patterns, and how the relevance visualization can help to understand the misclassification of individual samples.
AutoEncoders for Training Compact Deep Learning RF Classifiers for Wireless Protocols
Venue: arXiv cs.NI 2019
Year: 2019

We show that compact fully connected (FC) deep learning networks trained to classify wireless protocols using a hierarchy of multiple denoising autoencoders (AEs) outperform reference FC networks trained in a typical way, i.e., with a stochastic gradient based optimization of a given FC architecture. Not only is the complexity of such FC network, measured in number of trainable parameters and scalar multiplications, much lower than the reference FC and residual models, its accuracy also outperforms both models for nearly all tested SNR values (0 dB to 50dB). Such AE-trained networks are suited for in-situ protocol inference performed by simple mobile devices based on noisy signal measurements. Training is based on the data transmitted by real devices, and collected in a controlled environment, and systematically augmented by a policy-based data synthesis process by adding to the signal any subset of impairments commonly seen in a wireless receiver.
Parameterized algorithms for Partial vertex covers in bipartite graphs
Venue: arXiv cs.DM 2019
Year: 2019

In the weighted partial vertex cover problem (WPVC), we are given a graph $G=(V,E)$, cost function $c:V\rightarrow N$, profit function $p:E\rightarrow N$, and positive integers $R$ and $L$. The goal is to check whether there is a subset $V'\subseteq V$ of cost at most $R$, such that the total profit of edges covered by $V'$ is at least $L$. In this paper we study the fixed-parameter tractability of WPVC in bipartite graphs (WPVCB). By extending the methods of Amini et al., we show that WPVCB is FPT with respect to $R$ if $c\equiv 1$. On the negative side, it is $W[1]$-hard for arbitrary $c$, even when $p\equiv 1$. In particular, WPVCB is $W[1]$-hard parameterized by $R$. We complement this negative result by proving that for bounded-degree graphs WPVC is FPT with respect to $R$. The same result holds for the case of WPVCB when we allow to take only one fractional vertex. Additionally, we show that WPVC is FPT with respect to $L$. Finally, we discuss a variant of PVCB in which the edges covered are constrained to include a matching of prescribed size and derive a paramterized algorithm for the same.