OpenRaiser/Intern-Atlas huggingface dataset:
Cross-Lingual Dependency Parsing with Late Decoding for Truly Low-Resource Languages
Venue: arXiv cs.CL 2017
Year: 2017

In cross-lingual dependency annotation projection, information is often lost during transfer because of early decoding. We present an end-to-end graph-based neural network dependency parser that can be trained to reproduce matrices of edge scores, which can be directly projected across word alignments. We show that our approach to cross-lingual dependency parsing is not only simpler, but also achieves an absolute improvement of 2.25% averaged across 10 languages compared to the previous state of the art.
The next-to-minimal weights of binary projective Reed-Muller codes
Venue: arXiv cs.IT 2017
Year: 2017

Projective Reed-Muller codes were introduced by Lachaud, in 1988 and their dimension and minimum distance were determined by Serre and Sørensen in 1991. In coding theory one is also interested in the higher Hamming weights, to study the code performance. Yet, not many values of the higher Hamming weights are known for these codes, not even the second lowest weight (also known as next-to-minimal weight) is completely determined. In this paper we determine all the values of the next-to-minimal weight for the binary projective Reed-Muller codes, which we show to be equal to the next-to-minimal weight of Reed-Muller codes in most, but not all, cases.
DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
Venue: arXiv cs.AI 2017
Year: 2017

Artificial intelligence has seen several breakthroughs in recent years, with games often serving as milestones. A common feature of these games is that players have perfect information. Poker is the quintessential game of imperfect information, and a longstanding challenge problem in artificial intelligence. We introduce DeepStack, an algorithm for imperfect information settings. It combines recursive reasoning to handle information asymmetry, decomposition to focus computation on the relevant decision, and a form of intuition that is automatically learned from self-play using deep learning. In a study involving 44,000 hands of poker, DeepStack defeated with statistical significance professional poker players in heads-up no-limit Texas hold'em. The approach is theoretically sound and is shown to produce more difficult to exploit strategies than prior approaches.
Cyclotomic Construction of Strong External Difference Families in Finite Fields
Venue: arXiv cs.IT 2017
Year: 2017

Strong external difference family (SEDF) and its generalizations GSEDF, BGSEDF in a finite abelian group $G$ are combinatorial designs raised by Paterson and Stinson [7] in 2016 and have applications in communication theory to construct optimal strong algebraic manipulation detection codes. In this paper we firstly present some general constructions of these combinatorial designs by using difference sets and partial difference sets in $G$. Then, as applications of the general constructions, we construct series of SEDF, GSEDF and BGSEDF in finite fields by using cyclotomic classes.
A Simulation System for Energy Harvesting Networked Tags (EnHANTs)
Venue: arXiv cs.NI 2017
Year: 2017

This project is about EnHANTs networks. These networks have self-sustainable energy devices and the communication is performed over wireless links between neighboring devices. Since the devices are very limited in terms of energy, sending the data in these networks has to be as effective as possible and must take into consideration the available amount of energy. Therefore, it is necessary to use algorithms that are specifically designed for this type of networks. In this book we propose strategies for a specific case of these networks. The main part of this project is a MATLAB simulation built in order to examine the behavior of such networks. In the last section of this book, we describe a set of runs of different topologies, in order to test the influence of certain strategy parameters on the behavior of the system.
Sentence-level dialects identification in the greater China region
Venue: arXiv cs.CL 2017
Year: 2017

Identifying the different varieties of the same language is more challenging than unrelated languages identification. In this paper, we propose an approach to discriminate language varieties or dialects of Mandarin Chinese for the Mainland China, Hong Kong, Taiwan, Macao, Malaysia and Singapore, a.k.a., the Greater China Region (GCR). When applied to the dialects identification of the GCR, we find that the commonly used character-level or word-level uni-gram feature is not very efficient since there exist several specific problems such as the ambiguity and context-dependent characteristic of words in the dialects of the GCR. To overcome these challenges, we use not only the general features like character-level n-gram, but also many new word-level features, including PMI-based and word alignment-based features. A series of evaluation results on both the news and open-domain dataset from Wikipedia show the effectiveness of the proposed approach.
On the Complexity of Restoring Corrupted Colorings
Venue: arXiv cs.CC 2017
Year: 2017

In the \probrFix problem, we are given a graph $G$, a (non-proper) vertex-coloring $c : V(G) \to [r]$, and a positive integer $k$. The goal is to decide whether a proper $r$-coloring $c'$ is obtainable from $c$ by recoloring at most $k$ vertices of $G$. Recently, Junosza-Szaniawski, Liedloff, and Rz{ą}{ż}ewski [SOFSEM 2015] asked whether the problem has a polynomial kernel parameterized by the number of recolorings $k$. In a full version of the manuscript, the authors together with Garnero and Montealegre, answered the question in the negative: for every $r \geq 3$, the problem \probrFix does not admit a polynomial kernel unless $\NP \subseteq \coNP / \poly$. Independently of their work, we give an alternative proof of the theorem. Furthermore, we study the complexity of \probrFixSwap, where the only difference from \probrFix is that instead of $k$ recolorings we have a budget of $k$ color swaps. We show that for every $r \geq 3$, the problem \probrFixSwap is $\W[1]$-hard whereas \probrFix is known to be FPT. Moreover, when $r$ is part of the input, we observe both \probFix and \probFixSwap are $\W[1]$-hard parameterized by treewidth. We also study promise variants of the problems, where we are guaranteed that a proper $r$-coloring $c'$ is indeed obtainable from $c$ by some finite number of swaps. For instance, we prove that for $r=3$, the problems \probrFixPromise and \probrFixSwapPromise are $\NP$-hard for planar graphs. As a consequence of our reduction, the problems cannot be solved in $2^{o(\sqrt{n})}$ time unless the Exponential Time Hypothesis (ETH) fails.
Automated Linear-Time Detection and Quality Assessment of Superpixels in Uncalibrated True- or False-Color RGB Images
Venue: arXiv cs.CV 2017
Year: 2017

Capable of automated near real time superpixel detection and quality assessment in an uncalibrated monitor typical red green blue (RGB) image, depicted in either true or false colors, an original low level computer vision (CV) lightweight computer program, called RGB Image Automatic Mapper (RGBIAM), is designed and implemented. Constrained by the Calibration Validation (CalVal) requirements of the Quality Assurance Framework for Earth Observation (QA4EO) guidelines, RGBIAM requires as mandatory an uncalibrated RGB image pre processing first stage, consisting of an automated statistical model based color constancy algorithm. The RGBIAM hybrid inference pipeline comprises: (I) a direct quantitative to nominal (QN) RGB variable transform, where RGB pixel values are mapped onto a prior dictionary of color names, equivalent to a static polyhedralization of the RGB cube. Prior color naming is the deductive counterpart of inductive vector quantization (VQ), whose typical VQ error function to minimize is a root mean square error (RMSE). In the output multi level color map domain, superpixels are automatically detected in linear time as connected sets of pixels featuring the same color label. (II) An inverse nominal to quantitative (NQ) RGB variable transform, where a superpixelwise constant RGB image approximation is generated in linear time to assess a VQ error image. The hybrid direct and inverse RGBIAM QNQ transform is: (i) general purpose, data and application independent. (ii) Automated, i.e., it requires no user machine interaction. (iii) Near real time, with a computational complexity increasing linearly with the image size. (iv) Implemented in tile streaming mode, to cope with massive images. Collected outcome and process quality indicators, including degree of automation, computational efficiency, VQ rate and VQ error, are consistent with theoretical expectations.
Multi-Objective Software Suite of Two-Dimensional Shape Descriptors for Object-Based Image Analysis
Venue: arXiv cs.CV 2017
Year: 2017

In recent years two sets of planar (2D) shape attributes, provided with an intuitive physical meaning, were proposed to the remote sensing community by, respectively, Nagao & Matsuyama and Shackelford & Davis in their seminal works on the increasingly popular geographic object based image analysis (GEOBIA) paradigm. These two published sets of intuitive geometric features were selected as initial conditions by the present R&D software project, whose multi-objective goal was to accomplish: (i) a minimally dependent and maximally informative design (knowledge/information representation) of a general purpose, user and application independent dictionary of 2D shape terms provided with a physical meaning intuitive to understand by human end users and (ii) an effective (accurate, scale invariant, easy to use) and efficient implementation of 2D shape descriptors. To comply with the Quality Assurance Framework for Earth Observation guidelines, the proposed suite of geometric functions is validated by means of a novel quantitative quality assurance policy, centered on inter feature dependence (causality) assessment. This innovative multivariate feature validation strategy is alternative to traditional feature selection procedures based on either inductive data learning classification accuracy estimation, which is inherently case specific, or cross correlation estimation, because statistical cross correlation does not imply causation. The project deliverable is an original general purpose software suite of seven validated off the shelf 2D shape descriptors intuitive to use. Alternative to existing commercial or open source software libraries of tens of planar shape functions whose informativeness remains unknown, it is eligible for use in (GE)OBIA systems in operating mode, expected to mimic human reasoning based on a convergence of evidence approach.
Resource Management in Cloud Networking Using Economic Analysis and Pricing Models: A Survey
Venue: arXiv cs.GT 2017
Year: 2017

This paper presents a comprehensive literature review on applications of economic and pricing models for resource management in cloud networking. To achieve sustainable profit advantage, cost reduction, and flexibility in provisioning of cloud resources, resource management in cloud networking requires adaptive and robust designs to address many issues, e.g., resource allocation, bandwidth reservation, request allocation, and workload allocation. Economic and pricing models have received a lot of attention as they can lead to desirable performance in terms of social welfare, fairness, truthfulness, profit, user satisfaction, and resource utilization. This paper reviews applications of the economic and pricing models to develop adaptive algorithms and protocols for resource management in cloud networking. Besides, we survey a variety of incentive mechanisms using the pricing strategies in sharing resources in edge computing. In addition, we consider using pricing models in cloud-based Software Defined Wireless Networking (cloud-based SDWN). Finally, we highlight important challenges, open issues and future research directions of applying economic and pricing models to cloud networking
Guessing Attacks on Distributed-Storage Systems
Venue: arXiv cs.IT 2017
Year: 2017

The secrecy of a distributed-storage system for passwords is studied. The encoder, Alice, observes a length-n password and describes it using two hints, which she stores in different locations. The legitimate receiver, Bob, observes both hints. In one scenario the requirement is that the expected number of guesses it takes Bob to guess the password approach one as n tends to infinity, and in the other that the expected size of the shortest list that Bob must form to guarantee that it contain the password approach one. The eavesdropper, Eve, sees only one of the hints. Assuming that Alice cannot control which hints Eve observes, the largest normalized (by n) exponent that can be guaranteed for the expected number of guesses it takes Eve to guess the password is characterized for each scenario. Key to the proof are new results on Arikan's guessing and Bunte and Lapidoth's task-encoding problem; in particular, the paper establishes a close relation between the two problems. A rate-distortion version of the model is also discussed, as is a generalization that allows for Alice to produce δ (not necessarily two) hints, for Bob to observe ν (not necessarily two) of the hints, and for Eve to observe η (not necessarily one) of the hints. The generalized model is robust against δ - ν disk failures.
A Joint Resource Allocation Scheme for Multi-User Full-Duplex OFDMA Systems
Venue: arXiv cs.IT 2017
Year: 2017

Full-duplex is a promising technology and great system performance enhancement can be achieved especially when we apply it to base stations. In this paper, we consider a Multi-User OFDMA network consisting of one Full-duplex base station, several uplink users, and a number of downlink users. A joint subcarrier, downlink user and uplink user mapping and power allocation optimization problem is investigated. In detail, we first decompose the 3-dimensional mapping problem into three 2-dimensional sub-problems and solve them by iteratively using classical Hungarian Method. Then, based on the dual method, we sequentially solve the power allocation and 3-dimensional mapping problem at each dual point. And the optimal solution to the dual problem is derived by using sub-gradient method. Unlike existing methods that only solve one sub-problem but with a high computation complexity, we tackle both of them and successfully reducing computation complexity from exponential to polynomial order. Numerical simulations are conducted to verify the proposed system.
Toward Active Learning in Cross-domain Recommender Systems
Venue: arXiv cs.IR 2017
Year: 2017

One of the main challenges in Recommender Systems (RSs) is the New User problem which happens when the system has to generate personalised recommendations for a new user whom the system has no information about. Active Learning tries to solve this problem by acquiring user preference data with the maximum quality, and with the minimum acquisition cost. Although there are variety of works in active learning for RSs research area, almost all of them have focused only on the single-domain recommendation scenario. However, several real-world RSs operate in the cross-domain scenario, where the system generates recommendations in the target domain by exploiting user preferences in both the target and auxiliary domains. In such a scenario, the performance of active learning strategies can be significantly influenced and typical active learning strategies may fail to perform properly. In this paper, we address this limitation, by evaluating active learning strategies in a novel evaluation framework, explicitly suited for the cross-domain recommendation scenario. We show that having access to the preferences of the users in the auxiliary domain may have a huge impact on the performance of active learning strategies w.r.t. the classical, single-domain scenario.
Macro diversity in Cellular Networks with Random Blockages
Venue: arXiv cs.IT 2017
Year: 2017

Blocking objects (blockages) between a transmitter and receiver cause wireless communication links to transition from line-of-sight (LOS) to non-line-of-sight (NLOS) propagation, which can greatly reduce the received power, particularly at higher frequencies such as millimeter wave (mmWave). We consider a cellular network in which a mobile user attempts to connect to two or more base stations (BSs) simultaneously, to increase the probability of at least one LOS link, which is a form of macrodiversity. We develop a framework for determining the LOS probability as a function of the number of BSs, when taking into account the correlation between blockages: for example, a single blockage close to the device -- including the user's own body -- could block multiple BSs. We consider the impact of the size of blocking objects on the system reliability probability and show that macrodiversity gains are higher when the blocking objects are small. We also show that the BS density must scale as the square of the blockage density to maintain a given level of reliability.
Personalised Query Suggestion for Intranet Search with Temporal User Profiling
Venue: arXiv cs.IR 2017
Year: 2017

Recent research has shown the usefulness of using collective user interaction data (e.g., query logs) to recommend query modification suggestions for Intranet search. However, most of the query suggestion approaches for Intranet search follow an "one size fits all" strategy, whereby different users who submit an identical query would get the same query suggestion list. This is problematic, as even with the same query, different users may have different topics of interest, which may change over time in response to the user's interaction with the system. We address the problem by proposing a personalised query suggestion framework for Intranet search. For each search session, we construct two temporal user profiles: a click user profile using the user's clicked documents and a query user profile using the user's submitted queries. We then use the two profiles to re-rank the non-personalised query suggestion list returned by a state-of-the-art query suggestion method for Intranet search. Experimental results on a large-scale query logs collection show that our personalised framework significantly improves the quality of suggested queries.
A Decentralized Optimization Framework for Energy Harvesting Devices
Venue: arXiv cs.IT 2017
Year: 2017

Designing decentralized policies for wireless communication networks is a crucial problem, which has only been partially solved in the literature so far. In this paper, we propose the Decentralized Markov Decision Process (Dec-MDP) framework to analyze a wireless sensor network with multiple users which access a common wireless channel. We consider devices with energy harvesting capabilities, so that they aim at balancing the energy arrivals with the data departures and with the probability of colliding with other nodes. Randomly over time, an access point triggers a SYNC slot, wherein it recomputes the optimal transmission parameters of the whole network, and distributes this information. Every node receives its own policy, which specifies how it should access the channel in the future, and, thereafter, proceeds in a fully decentralized fashion, without interacting with other entities in the network. We propose a multi-layer Markov model, where an external MDP manages the jumps between SYNC slots, and an internal Dec-MDP computes the optimal policy in the near future. We numerically show that, because of the harvesting, a fully orthogonal scheme (e.g., TDMA-like) is suboptimal in energy harvesting scenarios, and the optimal trade-off lies between an orthogonal and a random access system.
Design and Implementation of a Wireless OBD II Fleet Management System
Venue: arXiv cs.NI 2017
Year: 2017

This paper describes the work that has been done in the design and development of a wireless OBD II fleet management system. The system aims to measure speed, distance and fuel consumption of vehicles for tracking and analysis purposes. An OBD II reader is designed to measure speed and mass air flow, from which distance and fuel consumption are also computed. This data is then transmitted via WiFi to a remote server. The system also implements GPS tracking to determine the location of the vehicle. A database management system is implemented at the remote server for the storage and management of transmitted data and a graphical user interface (GUI) is developed for analysing the transmitted data . Various qualification tests are conducted to verify the functionality of the system. The results demonstrate that the system is capable of reading the various parameters, and can successfully process, transmit and display the readings.
Games with Costs and Delays
Venue: arXiv cs.GT 2017
Year: 2017

We demonstrate the usefulness of adding delay to infinite games with quantitative winning conditions. In a delay game, one of the players may delay her moves to obtain a lookahead on her opponent's moves. We show that determining the winner of delay games with winning conditions given by parity automata with costs is EXPTIME-complete and that exponential bounded lookahead is both sufficient and in general necessary. Thus, although the parity condition with costs is a quantitative extension of the parity condition, our results show that adding costs does not increase the complexity of delay games with parity conditions. Furthermore, we study a new phenomenon that appears in quantitative delay games: lookahead can be traded for the quality of winning strategies and vice versa. We determine the extent of this tradeoff. In particular, even the smallest lookahead allows to improve the quality of an optimal strategy from the worst possible value to almost the smallest possible one. Thus, the benefit of introducing lookahead is twofold: not only does it allow the delaying player to win games she would lose without, but lookahead also allows her to improve the quality of her winning strategies in games she wins even without lookahead.
Bounding a global red-blue proportion using local conditions
Venue: arXiv cs.CG 2017
Year: 2017

We study the following local-to-global phenomenon: Let $B$ and $R$ be two finite sets of (blue and red) points in the Euclidean plane $\mathbb{R}^2$. Suppose that in each "neighborhood" of a red point, the number of blue points is at least as large as the number of red points. We show that in this case the total number of blue points is at least one fifth of the total number of red points. We also show that this bound is optimal and we generalize the result to arbitrary dimension and arbitrary norm using results from Minkowski arrangements.
Bounded time computation on metric spaces and Banach spaces
Venue: arXiv cs.LO 2017
Year: 2017

We extend the framework by Kawamura and Cook for investigating computational complexity for operators occurring in analysis. This model is based on second-order complexity theory for functions on the Baire space, which is lifted to metric spaces by means of representations. Time is measured in terms of the length of the input encodings and the required output precision. We propose the notions of a complete representation and of a regular representation. We show that complete representations ensure that any computable function has a time bound. Regular representations generalize Kawamura and Cook's more restrictive notion of a second-order representation, while still guaranteeing fast computability of the length of the encodings. Applying these notions, we investigate the relationship between purely metric properties of a metric space and the existence of a representation such that the metric is computable within bounded time. We show that a bound on the running time of the metric can be straightforwardly translated into size bounds of compact subsets of the metric space. Conversely, for compact spaces and for Banach spaces we construct a family of admissible, complete, regular representations that allow for fast computation of the metric and provide short encodings. Here it is necessary to trade the time bound off against the length of encodings.