OpenRaiser/Intern-Atlas huggingface dataset:
Machine Learning for Vehicular Networks
Venue: arXiv cs.IT 2018
Year: 2018

The emerging vehicular networks are expected to make everyday vehicular operation safer, greener, and more efficient, and pave the path to autonomous driving in the advent of the fifth generation (5G) cellular system. Machine learning, as a major branch of artificial intelligence, has been recently applied to wireless networks to provide a data-driven approach to solve traditionally challenging problems. In this article, we review recent advances in applying machine learning in vehicular networks and attempt to bring more attention to this emerging area. After a brief overview of the major concept of machine learning, we present some application examples of machine learning in solving problems arising in vehicular networks. We finally discuss and highlight several open issues that warrant further research.
Calibrating Noise to Variance in Adaptive Data Analysis
Venue: arXiv cs.LG 2018
Year: 2018

Datasets are often used multiple times and each successive analysis may depend on the outcome of previous analyses. Standard techniques for ensuring generalization and statistical validity do not account for this adaptive dependence. A recent line of work studies the challenges that arise from such adaptive data reuse by considering the problem of answering a sequence of "queries" about the data distribution where each query may depend arbitrarily on answers to previous queries. The strongest results obtained for this problem rely on differential privacy -- a strong notion of algorithmic stability with the important property that it "composes" well when data is reused. However the notion is rather strict, as it requires stability under replacement of an arbitrary data element. The simplest algorithm is to add Gaussian (or Laplace) noise to distort the empirical answers. However, analysing this technique using differential privacy yields suboptimal accuracy guarantees when the queries have low variance. Here we propose a relaxed notion of stability that also composes adaptively. We demonstrate that a simple and natural algorithm based on adding noise scaled to the standard deviation of the query provides our notion of stability. This implies an algorithm that can answer statistical queries about the dataset with substantially improved accuracy guarantees for low-variance queries. The only previous approach that provides such accuracy guarantees is based on a more involved differentially private median-of-means algorithm and its analysis exploits stronger "group" stability of the algorithm.
Pseudorehearsal in actor-critic agents with neural network function approximation
Venue: arXiv cs.AI 2018
Year: 2018

Catastrophic forgetting has a significant negative impact in reinforcement learning. The purpose of this study is to investigate how pseudorehearsal can change performance of an actor-critic agent with neural-network function approximation. We tested agent in a pole balancing task and compared different pseudorehearsal approaches. We have found that pseudorehearsal can assist learning and decrease forgetting.
An Order Preserving Bilinear Model for Person Detection in Multi-Modal Data
Venue: arXiv cs.CV 2018
Year: 2018

We propose a new order preserving bilinear framework that exploits low-resolution video for person detection in a multi-modal setting using deep neural networks. In this setting cameras are strategically placed such that less robust sensors, e.g. geophones that monitor seismic activity, are located within the field of views (FOVs) of cameras. The primary challenge is being able to leverage sufficient information from videos where there are less than 40 pixels on targets, while also taking advantage of less discriminative information from other modalities, e.g. seismic. Unlike state-of-the-art methods, our bilinear framework retains spatio-temporal order when computing the vector outer products between pairs of features. Despite the high dimensionality of these outer products, we demonstrate that our order preserving bilinear framework yields better performance than recent orderless bilinear models and alternative fusion methods.
Note on Attacking Object Detectors with Adversarial Stickers
Venue: arXiv cs.CR 2018
Year: 2018

Deep learning has proven to be a powerful tool for computer vision and has seen widespread adoption for numerous tasks. However, deep learning algorithms are known to be vulnerable to adversarial examples. These adversarial inputs are created such that, when provided to a deep learning algorithm, they are very likely to be mislabeled. This can be problematic when deep learning is used to assist in safety critical decisions. Recent research has shown that classifiers can be attacked by physical adversarial examples under various physical conditions. Given the fact that state-of-the-art objection detection algorithms are harder to be fooled by the same set of adversarial examples, here we show that these detectors can also be attacked by physical adversarial examples. In this note, we briefly show both static and dynamic test results. We design an algorithm that produces physical adversarial inputs, which can fool the YOLO object detector and can also attack Faster-RCNN with relatively high success rate based on transferability. Furthermore, our algorithm can compress the size of the adversarial inputs to stickers that, when attached to the targeted object, result in the detector either mislabeling or not detecting the object a high percentage of the time. This note provides a small set of results. Our upcoming paper will contain a thorough evaluation on other object detectors, and will present the algorithm.
Detection and Tracking of General Movable Objects in Large 3D Maps
Venue: arXiv cs.RO 2018
Year: 2018

This paper studies the problem of detection and tracking of general objects with long-term dynamics, observed by a mobile robot moving in a large environment. A key problem is that due to the environment scale, it can only observe a subset of the objects at any given time. Since some time passes between observations of objects in different places, the objects might be moved when the robot is not there. We propose a model for this movement in which the objects typically only move locally, but with some small probability they jump longer distances, through what we call global motion. For filtering, we decompose the posterior over local and global movements into two linked processes. The posterior over the global movements and measurement associations is sampled, while we track the local movement analytically using Kalman filters. This novel filter is evaluated on point cloud data gathered autonomously by a mobile robot over an extended period of time. We show that tracking jumping objects is feasible, and that the proposed probabilistic treatment outperforms previous methods when applied to real world data. The key to efficient probabilistic tracking in this scenario is focused sampling of the object posteriors.
Optimality program in segment and string graphs
Venue: arXiv cs.CG 2018
Year: 2018

Planar graphs are known to allow subexponential algorithms running in time $2^{O(\sqrt n)}$ or $2^{O(\sqrt n \log n)}$ for most of the paradigmatic problems, while the brute-force time $2^{Θ(n)}$ is very likely to be asymptotically best on general graphs. Intrigued by an algorithm packing curves in $2^{O(n^{2/3}\log n)}$ by Fox and Pach [SODA'11], we investigate which problems have subexponential algorithms on the intersection graphs of curves (string graphs) or segments (segment intersection graphs) and which problems have no such algorithms under the ETH (Exponential Time Hypothesis). Among our results, we show that, quite surprisingly, 3-Coloring can also be solved in time $2^{O(n^{2/3}\log^{O(1)}n)}$ on string graphs while an algorithm running in time $2^{o(n)}$ for 4-Coloring even on axis-parallel segments (of unbounded length) would disprove the ETH. For 4-Coloring of unit segments, we show a weaker ETH lower bound of $2^{o(n^{2/3})}$ which exploits the celebrated Erdős-Szekeres theorem. The subexponential running time also carries over to Min Feedback Vertex Set but not to Min Dominating Set and Min Independent Dominating Set.
Largest and Smallest Area Triangles on Imprecise Points
Venue: arXiv cs.CG 2018
Year: 2018

Assume we are given a set of parallel line segments in the plane, and we wish to place a point on each line segment such that the resulting point set maximizes or minimizes the area of the largest or smallest triangle in the set. We analyze the complexity of the four resulting computational problems, and we show that three of them admit polynomial-time algorithms, while the fourth is NP-hard. Specifically, we show that maximizing the largest triangle can be done in $O(n^2)$ time (or in $O(n \log n)$ time for unit segments); minimizing the largest triangle can be done in $O(n^2 \log n)$ time; maximizing the smallest triangle is NP-hard; but minimizing the smallest triangle can be done in $O(n^2)$ time. We also discuss to what extent our results can be generalized to polygons with $k>3$ sides.
Domain Adaptation Meets Disentangled Representation Learning and Style Transfer
Venue: arXiv cs.CV 2018
Year: 2018

Many methods have been proposed to solve the domain adaptation problem recently. However, the success of them implicitly funds on the assumption that the information of domains are fully transferrable. If the assumption is not satisfied, the effect of negative transfer may degrade domain adaptation. In this paper, a better learning network has been proposed by considering three tasks - domain adaptation, disentangled representation, and style transfer simultaneously. Firstly, the learned features are disentangled into common parts and specific parts. The common parts represent the transferrable features, which are suitable for domain adaptation with less negative transfer. Conversely, the specific parts characterize the unique style of each individual domain. Based on this, the new concept of feature exchange across domains, which can not only enhance the transferability of common features but also be useful for image style transfer, is introduced. These designs allow us to introduce five types of training objectives to realize the three challenging tasks at the same time. The experimental results show that our architecture can be adaptive well to full transfer learning and partial transfer learning upon a well-learned disentangled representation. Besides, the trained network also demonstrates high potential to generate style-transferred images.
Two Datasets of Questions and Answers for Studying the Development of Cross-platform Mobile Applications using Xamarin Framework
Venue: arXiv cs.SE 2018
Year: 2018

A cross-platform mobile application is an application that runs on multiple mobile platforms (Android, iOS). Several frameworks, have been proposed to simplify the development of cross-platform mobile applications and, therefore, to reduce development and maintenance costs. Between them, the cross-compiler mobile development frameworks, such as Xamarin from Microsoft, transform the application's code written in intermediate (aka non native) language to native code for each desired platform. However, to our best knowledge, there is no much research about the advantages and disadvantages of the use of those frameworks during the development and maintenance phases of mobile applications. The objective of this paper is twofold. Firstly, to present two datasets of questions and answers (Q&A) related to the development of mobile applications using Xamarin. Secondly, to show their usefulness, we present a replication study for discovering the main discussion topics of Xamarin development. We created the two datasets by mining two Q&A sites: Xamarin Forum and Stack Overflow. Then, for discovering the main topics of the questions from both datasets, we replicated a study that applies Latent Dirichlet Allocation (LDA). Finally, we compared the discovered topics with those topics about general mobile development reported by a previous study. Our datasets have 85,908 questions mined from the Xamarin Forum and 44,434 from Stack Overflow. Between the main topics discovered from those questions, we found that some of them are exclusively related to Xamarin and Microsoft technologies such as the design pattern "MVVM". Both datasets with Xamarin-related Q&A can be used by the research community for understanding the main concerns about developing cross-platform mobile applications using Xamarin. In this paper, we used it for replicating a studying about topic discovering.
Tensor network complexity of multilinear maps
Venue: arXiv cs.CC 2018
Year: 2018

We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. These capture any algorithm based on low border rank tensor decompositions, such as $O(n^{ω+ε})$ time matrix multiplication, and in addition many other algorithms such as $O(n \log n)$ time discrete Fourier transform and $O^*(2^n)$ time for computing the permanent of a matrix. However tensor networks sometimes yield faster algorithms than those that follow from low-rank decompositions. For instance the fastest known $O(n^{(ω+ε)t})$ time algorithms for counting $3t$-cliques can be implemented with tensor networks, even though the underlying tensor has border rank $n^{3t}$ for all $t \ge 2$. For counting homomorphisms of a general pattern graph $P$ into a host graph on $n$ vertices we obtain an upper bound of $O(n^{(ω+ε)\operatorname{bw}(P)/2})$ where $\operatorname{bw}(P)$ is the branchwidth of $P$. This essentially matches the bound for counting cliques, and yields small improvements over previous algorithms for many choices of $P$. While powerful, the model still has limitations, and we are able to show a number of unconditional lower bounds for various multilinear maps, including: (a) an $Ω(n^{\operatorname{bw}(P)})$ time lower bound for counting homomorphisms from $P$ to an $n$-vertex graph, matching the upper bound if $ω= 2$. In particular for $P$ a $v$-clique this yields an $Ω(n^{\lceil 2v/3 \rceil})$ time lower bound for counting $v$-cliques, and for $P$ a $k$-uniform $v$-hyperclique we obtain an $Ω(n^v)$ time lower bound for $k \ge 3$, ruling out tensor networks as an approach to obtaining non-trivial algorithms for hyperclique counting and the Max-$3$-CSP problem. (b) an $Ω(2^{0.918n})$ time lower bound for the permanent of an $n \times n$ matrix.
Learning More Universal Representations for Transfer-Learning
Venue: arXiv cs.CV 2018
Year: 2018

A representation is supposed universal if it encodes any element of the visual world (e.g., objects, scenes) in any configuration (e.g., scale, context). While not expecting pure universal representations, the goal in the literature is to improve the universality level, starting from a representation with a certain level. To do so, the state-of-the-art consists in learning CNN-based representations on a diversified training problem (e.g., ImageNet modified by adding annotated data). While it effectively increases universality, such approach still requires a large amount of efforts to satisfy the needs in annotated data. In this work, we propose two methods to improve universality, but pay special attention to limit the need of annotated data. We also propose a unified framework of the methods based on the diversifying of the training problem. Finally, to better match Atkinson's cognitive study about universal human representations, we proposed to rely on the transfer-learning scheme as well as a new metric to evaluate universality. This latter, aims us to demonstrates the interest of our methods on 10 target-problems, relating to the classification task and a variety of visual domains.
A linear programming approach for designing multilevel PWM waveforms
Venue: arXiv cs.SY 2018
Year: 2018

This paper considers the problem of designing a multilevel pulse width modulated waveform (PWM) with a prescribed harmonic content. Multilevel PWM design plays a major role in many diverse engineering disciplines. In power electronics, multilevel PWM design corresponds to determining the inverter switching times and levels for selective harmonic elimination and harmonic compensation. In mechatronics, the same design corresponds to shaping input signals to damp residual vibrations in flexible structures. More generally, in most applications, the aim of PWM design is to minimize the total harmonic distortion while adhering to a prescribed harmonic content. The solution approach presented in this paper is based on linear programming with the objective of minimizing the total harmonic distortion. This objective is achieved within an arbitrarily small bound of the optimal solution. In addition, the linear programming formulation makes the design of such switching waveforms computationally tractable and efficient. Simulations are provided for corroboration.
Gradient Regularization Improves Accuracy of Discriminative Models
Venue: arXiv cs.LG 2018
Year: 2018

Regularizing the gradient norm of the output of a neural network with respect to its inputs is a powerful technique, rediscovered several times. This paper presents evidence that gradient regularization can consistently improve classification accuracy on vision tasks, using modern deep neural networks, especially when the amount of training data is small. We introduce our regularizers as members of a broader class of Jacobian-based regularizers. We demonstrate empirically on real and synthetic data that the learning process leads to gradients controlled beyond the training points, and results in solutions that generalize well.
Subquadratic time encodable codes beating the Gilbert-Varshamov bound
Venue: arXiv cs.IT 2018
Year: 2018

We construct explicit algebraic geometry codes built from the Garcia-Stichtenoth function field tower beating the Gilbert-Varshamov bound for alphabet sizes at least 192. Messages are identied with functions in certain Riemann-Roch spaces associated with divisors supported on multiple places. Encoding amounts to evaluating these functions at degree one places. By exploiting algebraic structures particular to the Garcia-Stichtenoth tower, we devise an intricate deterministic ω/2 < 1.19 runtime exponent encoding and 1+ω/2 < 2.19 expected runtime exponent randomized (unique and list) decoding algorithms. Here ω< 2.373 is the matrix multiplication exponent. If ω= 2, as widely believed, the encoding and decoding runtimes are respectively nearly linear and nearly quadratic. Prior to this work, encoding (resp. decoding) time of code families beating the Gilbert-Varshamov bound were quadratic (resp. cubic) or worse.
A Class of Automatic Sequences
Venue: arXiv cs.FL 2018
Year: 2018

Let $k\ge 2$. We prove that the characteristic sequence of a regular language over a $k$-letter alphabet is $k$-automatic. More generally, if $t\ge 2$ and $t,k$ are multiplicatively dependent, we show that the characteristic sequence of a regular language over a $t$-letter alphabet is $k$-automatic.
Improved Online Algorithm for Weighted Flow Time
Venue: arXiv cs.DS 2018
Year: 2018

We discuss one of the most fundamental scheduling problem of processing jobs on a single machine to minimize the weighted flow time (weighted response time). Our main result is a $O(\log P)$-competitive algorithm, where $P$ is the maximum-to-minimum processing time ratio, improving upon the $O(\log^{2}P)$-competitive algorithm of Chekuri, Khanna and Zhu (STOC 2001). We also design a $O(\log D)$-competitive algorithm, where $D$ is the maximum-to-minimum density ratio of jobs. Finally, we show how to combine these results with the result of Bansal and Dhamdhere (SODA 2003) to achieve a $O(\log(\min(P,D,W)))$-competitive algorithm (where $W$ is the maximum-to-minimum weight ratio), without knowing $P,D,W$ in advance. As shown by Bansal and Chan (SODA 2009), no constant-competitive algorithm is achievable for this problem.
Personal Names in Modern Turkey
Venue: arXiv cs.CL 2018
Year: 2018

We analyzed the most common 5000 male and 5000 female Turkish names based on their etymological, morphological, and semantic attributes. The name statistics are based on all Turkish citizens who were alive in 2014 and they cover 90% of all population. To the best of our knowledge, this study is the most comprehensive data-driven analysis of Turkish personal names. Female names have a greater diversity than male names (e.g., top 15 male names cover 25% of the male population, whereas top 28 female names cover 25% of the female population). Despite their diversity, female names exhibit predictable patterns. For example, certain roots such as gül and nar (rose and pomegranate/red, respectively) are used to generate hundreds of unique female names. Turkish personal names have their origins mainly in Arabic, followed by Turkish and Persian. We computed overall frequencies of names according to broad semantic themes that were identified in previous studies. We found that foreign-origin names such as olga and khaled, pastoral names such as yağmur and deniz (rain and sea, respectively), and names based on fruits and plants such as filiz and menekşe (sprout and violet, respectively) are more frequently observed among females. Among males, names based on animals such as arslan and yunus (lion and dolphin, respectively) and names based on famous and/or historical figures such as mustafa kemal and oğuz kağan (founder of the Turkish Republic and the founder of the Turks in Turkish mythology, respectively) are observed more frequently.
The CAPIO 2017 Conversational Speech Recognition System
Venue: arXiv cs.CL 2018
Year: 2018

In this paper we show how we have achieved the state-of-the-art performance on the industry-standard NIST 2000 Hub5 English evaluation set. We explore densely connected LSTMs, inspired by the densely connected convolutional networks recently introduced for image classification tasks. We also propose an acoustic model adaptation scheme that simply averages the parameters of a seed neural network acoustic model and its adapted version. This method was applied with the CallHome training corpus and improved individual system performances by on average 6.1% (relative) against the CallHome portion of the evaluation set with no performance loss on the Switchboard portion. With RNN-LM rescoring and lattice combination on the 5 systems trained across three different phone sets, our 2017 speech recognition system has obtained 5.0% and 9.1% on Switchboard and CallHome, respectively, both of which are the best word error rates reported thus far. According to IBM in their latest work to compare human and machine transcriptions, our reported Switchboard word error rate can be considered to surpass the human parity (5.1%) of transcribing conversational telephone speech.
PAC-Bayesian Margin Bounds for Convolutional Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Recently the generalization error of deep neural networks has been analyzed through the PAC-Bayesian framework, for the case of fully connected layers. We adapt this approach to the convolutional setting.