OpenRaiser/Intern-Atlas huggingface dataset:
CAp 2017 challenge: Twitter Named Entity Recognition
Venue: arXiv cs.CL 2017
Year: 2017

The paper describes the CAp 2017 challenge. The challenge concerns the problem of Named Entity Recognition (NER) for tweets written in French. We first present the data preparation steps we followed for constructing the dataset released in the framework of the challenge. We begin by demonstrating why NER for tweets is a challenging problem especially when the number of entities increases. We detail the annotation process and the necessary decisions we made. We provide statistics on the inter-annotator agreement, and we conclude the data description part with examples and statistics for the data. We, then, describe the participation in the challenge, where 8 teams participated, with a focus on the methods employed by the challenge participants and the scores achieved in terms of F$_1$ measure. Importantly, the constructed dataset comprising $\sim$6,000 tweets annotated for 13 types of entities, which to the best of our knowledge is the first such dataset in French, is publicly available at \url{http://cap2017.imag.fr/competition.html} .
Transition-Based Generation from Abstract Meaning Representations
Venue: arXiv cs.CL 2017
Year: 2017

This work addresses the task of generating English sentences from Abstract Meaning Representation (AMR) graphs. To cope with this task, we transform each input AMR graph into a structure similar to a dependency tree and annotate it with syntactic information by applying various predefined actions to it. Subsequently, a sentence is obtained from this tree structure by visiting its nodes in a specific order. We train maximum entropy models to estimate the probability of each individual action and devise an algorithm that efficiently approximates the best sequence of actions to be applied. Using a substandard language model, our generator achieves a Bleu score of 27.4 on the LDC2014T12 test set, the best result reported so far without using silver standard annotations from another corpus as additional training data.
Reliable Beamspace Channel Estimation for Millimeter-Wave Massive MIMO Systems with Lens Antenna Array
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter-wave massive MIMO with lens antenna array can considerably reduce the number of required radio-frequency (RF) chains by beam selection. However, beam selection requires the base station to acquire the accurate information of beamspace channel. This is a challenging task, as the size of beamspace channel is large while the number of RF chains is limited. In this paper, we investigate the beamspace channel estimation problem in mmWave massive MIMO systems with lens antenna array. Specifically, we first design an adaptive selecting network for mmWave massive MIMO systems with lens antenna array, and based on this network, we further formulate the beamspace channel estimation problem as a sparse signal recovery problem. Then, by fully utilizing the structural characteristics of mmWave beamspace channel, we propose a support detection (SD)-based channel estimation scheme with reliable performance and low pilot overhead. Finally, the performance and complexity analyses are provided to prove that the proposed SD-based channel estimation scheme can estimate the support of sparse beamspace channel with comparable or higher accuracy than conventional schemes. Simulation results verify that the proposed SD-based channel estimation scheme outperforms conventional schemes and enjoys satisfying accuracy, even in the low SNR region as the structural characteristics of beamspace channel can be exploited.
Improve Lexicon-based Word Embeddings By Word Sense Disambiguation
Venue: arXiv cs.CL 2017
Year: 2017

There have been some works that learn a lexicon together with the corpus to improve the word embeddings. However, they either model the lexicon separately but update the neural networks for both the corpus and the lexicon by the same likelihood, or minimize the distance between all of the synonym pairs in the lexicon. Such methods do not consider the relatedness and difference of the corpus and the lexicon, and may not be the best optimized. In this paper, we propose a novel method that considers the relatedness and difference of the corpus and the lexicon. It trains word embeddings by learning the corpus to predicate a word and its corresponding synonym under the context at the same time. For polysemous words, we use a word sense disambiguation filter to eliminate the synonyms that have different meanings for the context. To evaluate the proposed method, we compare the performance of the word embeddings trained by our proposed model, the control groups without the filter or the lexicon, and the prior works in the word similarity tasks and text classification task. The experimental results show that the proposed model provides better embeddings for polysemous words and improves the performance for text classification.
Detection of curved lines with B-COSFIRE filters: A case study on crack delineation
Venue: arXiv cs.CV 2017
Year: 2017

The detection of curvilinear structures is an important step for various computer vision applications, ranging from medical image analysis for segmentation of blood vessels, to remote sensing for the identification of roads and rivers, and to biometrics and robotics, among others. %The visual system of the brain has remarkable abilities to detect curvilinear structures in noisy images. This is a nontrivial task especially for the detection of thin or incomplete curvilinear structures surrounded with noise. We propose a general purpose curvilinear structure detector that uses the brain-inspired trainable B-COSFIRE filters. It consists of four main steps, namely nonlinear filtering with B-COSFIRE, thinning with non-maximum suppression, hysteresis thresholding and morphological closing. We demonstrate its effectiveness on a data set of noisy images with cracked pavements, where we achieve state-of-the-art results (F-measure=0.865). The proposed method can be employed in any computer vision methodology that requires the delineation of curvilinear and elongated structures.
Stochastic Coalitional Games for Cooperative Random Access in M2M Communications
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, the problem of random access contention between machine type devices (MTDs) in the uplink of a wireless cellular network is studied. In particular, the possibility of forming cooperative groups to coordinate the MTDs' requests for the random access channel (RACH) is analyzed. The problem is formulated as a stochastic coalition formation game in which the MTDs are the players that seek to form cooperative coalitions to optimize a utility function that captures each MTD's energy consumption and time-varying queue length. Within each coalition, an MTD acts as a coalition head that sends the access requests of the coalition members over the RACH. One key feature of this game is its ability to cope with stochastic environments in which the arrival requests of MTDs and the packet success rate over RACH are dynamically time-varying. The proposed stochastic coalitional is composed of multiple stages, each of which corresponds to a coalitional game in stochastic characteristic form that is played by the MTDs at each time step. To solve this game, a novel distributed coalition formation algorithm is proposed and shown to converge to a stable MTD partition. Simulation results show that, on the average, the proposed stochastic coalition formation algorithm can reduce the average fail ratio and energy consumption of up to 36% and 31% for a cluster-based distribution of MTDs, respectively, compared with a noncooperative case. Moreover, when the MTDs are more sensitive to the energy consumption (queue length), the coalitions' size will increase (decrease).
A Framework for Wireless Broadband Network for Connecting the Unconnected
Venue: arXiv cs.NI 2017
Year: 2017

A significant barrier in providing affordable rural broadband is to connect the rural and remote places to the optical Point of Presence (PoP) over distances of few kilometers. A lot of work has been done in the area of long distance Wi-Fi networks. However, these networks require tall towers and high gain (directional) antennas. Also, they work in the unlicensed band which has Effective Isotropically Radiated Power (EIRP) limit (e.g. 1 W in India) which restricts the network design. In this work, we propose a Long Term Evolution-Advanced (LTE-A) network operating in TV UHF to connect the remote areas to the optical PoP. In India, around 100 MHz of TV UHF band IV (470-585 MHz) is unused at any location and can be put to an effective use in these areas. We explore the idea of multi-hop topology for the proposed network. We also compare the performance of the multi-hop network with the Point to Multipoint (PMP) topology. The results show that multi-hop network performs much better than the PMP network. We then formulate a Linear Programming (LP) problem of generating optimal topology and compare its performance with the multi-hop network. Overall, the analysis implies that an optimally planned LTE-A network in TV UHF band can be a potential solution for affordable rural broadband.
Towards Semantic Query Segmentation
Venue: arXiv cs.IR 2017
Year: 2017

Query Segmentation is one of the critical components for understanding users' search intent in Information Retrieval tasks. It involves grouping tokens in the search query into meaningful phrases which help downstream tasks like search relevance and query understanding. In this paper, we propose a novel approach to segment user queries using distributed query embeddings. Our key contribution is a supervised approach to the segmentation task using low-dimensional feature vectors for queries, getting rid of traditional hand tuned and heuristic NLP features which are quite expensive. We benchmark on a 50,000 human-annotated web search engine query corpus achieving comparable accuracy to state-of-the-art techniques. The advantage of our technique is its fast and does not use external knowledge-base like Wikipedia for score boosting. This helps us generalize our approach to other domains like eCommerce without any fine-tuning. We demonstrate the effectiveness of this method on another 50,000 human-annotated eCommerce query corpus from eBay search logs. Our approach is easy to implement and generalizes well across different search domains proving the power of low-dimensional embeddings in query segmentation task, opening up a new direction of research for this problem.
HornDroid: Practical and Sound Static Analysis of Android Applications by SMT Solving
Venue: arXiv cs.CR 2017
Year: 2017

We present HornDroid, a new tool for the static analysis of information flow properties in Android applications. The core idea underlying HornDroid is to use Horn clauses for soundly abstracting the semantics of Android applications and to express security properties as a set of proof obligations that are automatically discharged by an off-the-shelf SMT solver. This approach makes it possible to fine-tune the analysis in order to achieve a high degree of precision while still using off-the-shelf verification tools, thereby leveraging the recent advances in this field. As a matter of fact, HornDroid outperforms state-of-the-art Android static analysis tools on benchmarks proposed by the community. Moreover, HornDroid is the first static analysis tool for Android to come with a formal proof of soundness, which covers the core of the analysis technique: besides yielding correctness assurances, this proof allowed us to identify some critical corner-cases that affect the soundness guarantees provided by some of the previous static analysis tools for Android.
An Executable Specification of Typing Rules for Extensible Records based on Row Polymorphism
Venue: arXiv cs.PL 2017
Year: 2017

Type inference is an application domain that is a natural fit for logic programming (LP). LP systems natively support unification, which serves as a basic building block of typical type inference algorithms. In particular, polymorphic type inference in the Hindley--Milner type system (HM) can be succinctly specified and executed in Prolog. In our previous work, we have demonstrated that more advanced features of parametric polymorphism beyond HM, such as type-constructor polymorphism and kind polymorphism, can be similarly specified in Prolog. Here, we demonstrate a specification for records, which is one of the most widely supported compound data structures in real-world programming languages, and discuss the advantages and limitations of Prolog as a specification language for type systems. Record types are specified as order-irrelevant collections of named fields mapped to their corresponding types. In addition, an open-ended collection is used to support row polymorphism for record types to be extensible.
Structural Regularities in Text-based Entity Vector Spaces
Venue: arXiv cs.IR 2017
Year: 2017

Entity retrieval is the task of finding entities such as people or products in response to a query, based solely on the textual documents they are associated with. Recent semantic entity retrieval algorithms represent queries and experts in finite-dimensional vector spaces, where both are constructed from text sequences. We investigate entity vector spaces and the degree to which they capture structural regularities. Such vector spaces are constructed in an unsupervised manner without explicit information about structural aspects. For concreteness, we address these questions for a specific type of entity: experts in the context of expert finding. We discover how clusterings of experts correspond to committees in organizations, the ability of expert representations to encode the co-author graph, and the degree to which they encode academic rank. We compare latent, continuous representations created using methods based on distributional semantics (LSI), topic models (LDA) and neural networks (word2vec, doc2vec, SERT). Vector spaces created using neural methods, such as doc2vec and SERT, systematically perform better at clustering than LSI, LDA and word2vec. When it comes to encoding entity relations, SERT performs best.
A generic framework for adaptive EEG-based BCI training and operation
Venue: arXiv cs.HC 2017
Year: 2017

There are numerous possibilities and motivations for an adaptive BCI, which may not be easy to clarify and organize for a newcomer to the field. To our knowledge, there has not been any work done in classifying the literature on adaptive BCI in a comprehensive and structured way. We propose a conceptual framework, a taxonomy of adaptive BCI methods which encompasses most important approaches to fit them in such a way that a reader can clearly visualize which elements are being adapted and for what reason. In the interest of having a clear review of existing adaptive BCIs, this framework considers adaptation approaches for both the user and the machine, i.e., using instructional design observations as well as the usual machine learning techniques. This framework not only provides a coherent review of such extensive literature but also enables the reader to perceive gaps and flaws in the current BCI systems, which would hopefully bring novel solutions for an overall improvement.
Residual Conv-Deconv Grid Network for Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents GridNet, a new Convolutional Neural Network (CNN) architecture for semantic image segmentation (full scene labelling). Classical neural networks are implemented as one stream from the input to the output with subsampling operators applied in the stream in order to reduce the feature maps size and to increase the receptive field for the final prediction. However, for semantic image segmentation, where the task consists in providing a semantic class to each pixel of an image, feature maps reduction is harmful because it leads to a resolution loss in the output prediction. To tackle this problem, our GridNet follows a grid pattern allowing multiple interconnected streams to work at different resolutions. We show that our network generalizes many well known networks such as conv-deconv, residual or U-Net networks. GridNet is trained from scratch and achieves competitive results on the Cityscapes dataset.
Automatic Liver Segmentation Using an Adversarial Image-to-Image Network
Venue: arXiv cs.CV 2017
Year: 2017

Automatic liver segmentation in 3D medical images is essential in many clinical applications, such as pathological diagnosis of hepatic diseases, surgical planning, and postoperative assessment. However, it is still a very challenging task due to the complex background, fuzzy boundary, and various appearance of liver. In this paper, we propose an automatic and efficient algorithm to segment liver from 3D CT volumes. A deep image-to-image network (DI2IN) is first deployed to generate the liver segmentation, employing a convolutional encoder-decoder architecture combined with multi-level feature concatenation and deep supervision. Then an adversarial network is utilized during training process to discriminate the output of DI2IN from ground truth, which further boosts the performance of DI2IN. The proposed method is trained on an annotated dataset of 1000 CT volumes with various different scanning protocols (e.g., contrast and non-contrast, various resolution and position) and large variations in populations (e.g., ages and pathology). Our approach outperforms the state-of-the-art solutions in terms of segmentation accuracy and computing efficiency.
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
Venue: arXiv cs.DS 2017
Year: 2017

We study approximation algorithms for scheduling problems with the objective of minimizing total weighted completion time, under identical and related machine models with job precedence constraints. We give algorithms that improve upon many previous 15 to 20-year-old state-of-art results. A major theme in these results is the use of time-indexed linear programming relaxations. These are natural relaxations for their respective problems, but surprisingly are not studied in the literature. We also consider the scheduling problem of minimizing total weighted completion time on unrelated machines. The recent breakthrough result of [Bansal-Srinivasan-Svensson, STOC 2016] gave a $(1.5-c)$-approximation for the problem, based on some lift-and-project SDP relaxation. Our main result is that a $(1.5 - c)$-approximation can also be achieved using a natural and considerably simpler time-indexed LP relaxation for the problem. We hope this relaxation can provide new insights into the problem.
Synthesising Sign Language from semantics, approaching "from the target and back"
Venue: arXiv cs.CL 2017
Year: 2017

We present a Sign Language modelling approach allowing to build grammars and create linguistic input for Sign synthesis through avatars. We comment on the type of grammar it allows to build, and observe a resemblance between the resulting expressions and traditional semantic representations. Comparing the ways in which the paradigms are designed, we name and contrast two essentially different strategies for building higher-level linguistic input: "source-and-forward" vs. "target-and-back". We conclude by favouring the latter, acknowledging the power of being able to automatically generate output from semantically relevant input straight into articulations of the target language.
Line-Circle: A Geometric Filter for Single Camera Edge-Based Object Detection
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents a state-of-the-art approach in object detection for being applied in future SLAM problems. Although, many SLAM methods are proposed to create suitable autonomy for mobile robots namely ground vehicles, they still face overconfidence and large computations during entrance to immense spaces with many landmarks. In particular, they suffer from impractical applications via sole reliance on the limited sensors like camera. Proposed method claims that unmanned ground vehicles without having huge amount of database for object definition and highly advance prediction parameters can deal with incoming objects during straight motion of camera in real-time. Line-Circle (LC) filter tries to apply detection, tracking and learning to each defined experts to obtain more information for judging scene without over-calculation. In this filter, circle expert let us summarize edges in groups. The Interactive feedback learning between each expert creates minimal error that fights against overwhelming landmark signs in crowded scenes without mapping. Our experts basically are dependent on trust factors' covariance with geometric definitions to ignore, emerge and compare detected landmarks. The experiment for validating the model is taken place utilizing a camera beside an IMU sensor for location estimation.
The RepEval 2017 Shared Task: Multi-Genre Natural Language Inference with Sentence Representations
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents the results of the RepEval 2017 Shared Task, which evaluated neural network sentence representation learning models on the Multi-Genre Natural Language Inference corpus (MultiNLI) recently introduced by Williams et al. (2017). All of the five participating teams beat the bidirectional LSTM (BiLSTM) and continuous bag of words baselines reported in Williams et al.. The best single model used stacked BiLSTMs with residual connections to extract sentence features and reached 74.5% accuracy on the genre-matched test set. Surprisingly, the results of the competition were fairly consistent across the genre-matched and genre-mismatched test sets, and across subsets of the test data representing a variety of linguistic phenomena, suggesting that all of the submitted systems learned reasonably domain-independent representations for sentence meaning.
Persistent Cache-oblivious Streaming Indexes
Venue: arXiv cs.DS 2017
Year: 2017

In [SPAA2007], Bender et al. define a streaming B-tree (or index) as one that supports updates in amortized $o(1)$ IOs, and present a structure achieving amortized $O((\log N)/B)$ IOs and queries in $O(\log N)$ IOs. We extend their result to the partially-persistent case. For a version $v$, let $N_v$ be the number of keys accessible at $v$ and $N$ be the total number of updates. We give a data structure using space $O(N)$, supporting updates to a leaf version $v$ with $O((\log N_{v})/B)$ amortized IOs and answering range queries returning $Z$ elements with $O(\log N_{v} + Z/B)$ IOs on average (where the average is over all queries covering disjoint key ranges at a given version). This is the first persistent `streaming' index we are aware of, i.e. that supports updates in $o(1)$ IOs and supports efficient range queries.
A bijection for essentially 4-connected toroidal triangulations
Venue: arXiv cs.DM 2017
Year: 2017

Transversal structures (also known as regular edge labelings) are combinatorial structures defined over 4-connected plane triangulations with quadrangular outer-face. They have been intensively studied and used for many applications (drawing algorithm, random generation, enumeration ...). In this paper we introduce and study a generalization of these objects for the toroidal case. Contrary to what happens in the plane, the set of toroidal transversal structures of a given toroidal triangulation is partitioned into several distributive lattices. We exhibit a subset of toroidal transversal structures, called balanced, and show that it forms a single distributive lattice. Then, using the minimal element of the lattice, we are able to enumerate bijectively essentially 4-connected toroidal triangulations.