OpenRaiser/Intern-Atlas huggingface dataset:
Towards Cereceda's conjecture for planar graphs
Venue: arXiv cs.DM 2018
Year: 2018

The reconfiguration graph $R_k(G)$ of the $k$-colourings of a graph $G$ has as vertex set the set of all possible $k$-colourings of $G$ and two colourings are adjacent if they differ on the colour of exactly one vertex. Cereceda conjectured ten years ago that, for every $k$-degenerate graph $G$ on $n$ vertices, $R_{k+2}(G)$ has diameter $\mathcal{O}({n^2})$. The conjecture is wide open, with a best known bound of $\mathcal{O}({k^n})$, even for planar graphs. We improve this bound for planar graphs to $2^{\mathcal{O}({\sqrt{n}})}$. Our proof can be transformed into an algorithm that runs in $2^{\mathcal{O}({\sqrt{n}})}$ time.
Graph Diffusion-Embedding Networks
Venue: arXiv cs.CV 2018
Year: 2018

We present a novel graph diffusion-embedding networks (GDEN) for graph structured data. GDEN is motivated by our closed-form formulation on regularized feature diffusion on graph. GDEN integrates both regularized feature diffusion and low-dimensional embedding simultaneously in a unified network model. Moreover, based on GDEN, we can naturally deal with structured data with multiple graph structures. Experiments on semi-supervised learning tasks on several benchmark datasets demonstrate the better performance of the proposed GDEN when comparing with the traditional GCN models.
Adaptive Game-Theoretic Decision Making for Autonomous Vehicle Control at Roundabouts
Venue: arXiv cs.GT 2018
Year: 2018

In this paper, we propose a decision making algorithm for autonomous vehicle control at a roundabout intersection. The algorithm is based on a game-theoretic model representing the interactions between the ego vehicle and an opponent vehicle, and adapts to an online estimated driver type of the opponent vehicle. Simulation results are reported.
Training Machine Learning Models by Regularizing their Explanations
Venue: arXiv cs.LG 2018
Year: 2018

Neural networks are among the most accurate supervised learning methods in use today. However, their opacity makes them difficult to trust in critical applications, especially when conditions in training may differ from those in practice. Recent efforts to develop explanations for neural networks and machine learning models more generally have produced tools to shed light on the implicit rules behind predictions. These tools can help us identify when models are right for the wrong reasons. However, they do not always scale to explaining predictions for entire datasets, are not always at the right level of abstraction, and most importantly cannot correct the problems they reveal. In this thesis, we explore the possibility of training machine learning models (with a particular focus on neural networks) using explanations themselves. We consider approaches where models are penalized not only for making incorrect predictions but also for providing explanations that are either inconsistent with domain knowledge or overly complex. These methods let us train models which can not only provide more interpretable rationales for their predictions but also generalize better when training data is confounded or meaningfully different from test data (even adversarially so).
Graph Isomorphism by Conversion to Chordal (6, 3) Graphs
Venue: arXiv cs.CC 2018
Year: 2018

Babel has shown that for an extended class of chordal (6, 3) graphs the coarsest regular simplicial partition is equivalent to the graph's automorphism partition. We give a reversible transformation for any graph to one of these graph by using Booth's reduction of a graph to a chordal graph and elimination of Babel's forbidden subgraphs for these graphs by adding edges to them.
Codestitcher: Inter-Procedural Basic Block Layout Optimization
Venue: arXiv cs.PL 2018
Year: 2018

Modern software executes a large amount of code. Previous techniques of code layout optimization were developed one or two decades ago and have become inadequate to cope with the scale and complexity of new types of applications such as compilers, browsers, interpreters, language VMs and shared libraries. This paper presents Codestitcher, an inter-procedural basic block code layout optimizer which reorders basic blocks in an executable to benefit from better cache and TLB performance. Codestitcher provides a hierarchical framework which can be used to improve locality in various layers of the memory hierarchy. Our evaluation shows that Codestitcher improves the performance of the original program by 3\% to 25\% (on average, by 10\%) on 5 widely used applications with large code sizes: MySQL, Clang, Firefox, Apache, and Python. It gives an additional improvement of 4\% over LLVM's PGO and 3\% over PGO combined with the best function reordering technique.
First International HARTING Open Source Prize Winner: The igus Humanoid Open Platform
Venue: arXiv cs.RO 2018
Year: 2018

The use of standard platforms in the field of humanoid robotics can lower the entry barrier for new research groups, and accelerate research by the facilitation of code sharing. Numerous humanoid standard platforms exist in the lower size ranges of up to 60cm, but beyond that humanoid robots scale up quickly in weight and price, becoming less affordable and more difficult to operate, maintain and modify. The igus Humanoid Open Platform is an affordable, fully open-source platform for humanoid research. At 92cm, the robot is capable of acting in an environment meant for humans, and is equipped with enough sensors, actuators and computing power to support researchers in many fields. The structure of the robot is entirely 3D printed, leading to a lightweight and visually appealing design. This paper covers the mechanical and electrical aspects of the robot, as well as the main features of the corresponding open-source ROS software. At RoboCup 2016, the platform was awarded the first International HARTING Open Source Prize.
Natural measures of alignment
Venue: arXiv cs.CV 2018
Year: 2018

Natural coordinate system will be proposed. In this coordinate system alignment procedure of a device and a detector can be easily performed. This approach is generalization of previous specific formulas in the field of calibration and provide top level description of the procedure. A basic example application to linac therapy plan is also provided.
Distributional Semantics Approach to Detect Intent in Twitter Conversations on Sexual Assaults
Venue: arXiv cs.SI 2018
Year: 2018

The recent surge in women reporting sexual assault and harassment (e.g., #metoo campaign) has highlighted a longstanding societal crisis. This injustice is partly due to a culture of discrediting women who report such crimes and also, rape myths (e.g., 'women lie about rape'). Social web can facilitate the further proliferation of deceptive beliefs and culture of rape myths through intentional messaging by malicious actors. This multidisciplinary study investigates Twitter posts related to sexual assaults and rape myths for characterizing the types of malicious intent, which leads to the beliefs on discrediting women and rape myths. Specifically, we first propose a novel malicious intent typology for social media using the guidance of social construction theory from policy literature that includes Accusational, Validational, or Sensational intent categories. We then present and evaluate a malicious intent classification model for a Twitter post using semantic features of the intent senses learned with the help of convolutional neural networks. Lastly, we analyze a Twitter dataset of four months using the intent classification model to study narrative contexts in which malicious intents are expressed and discuss their implications for gender violence policy design.
AI for Trustworthiness! Credible User Identification on Social Web for Disaster Response Agencies
Venue: arXiv cs.SI 2018
Year: 2018

Although social media provides a vibrant platform to discuss real-world events, the quantity of information generated can overwhelm decision making based on that information. By better understanding who is participating in information sharing, we can more effectively filter information as the event unfolds. Fine-grained understanding of credible sources can even help develop a trusted network of users for specific events or situations. Given the culture of relying on trusted actors for work practices in the humanitarian and disaster response domain, we propose to identify potential credible users as organizational and organizational-affiliated user accounts on social media in realtime for effective information collection and dissemination. Therefore, we examine social media using AI and Machine Learning methods during three types of humanitarian or disaster events and identify key actors responding to social media conversations as organization (business, group, or institution), organization-affiliated (individual with an organizational affiliation), and non-affiliated (individual without organizational affiliation) identities. We propose a credible user classification approach using a diverse set of social, activity, and descriptive representation features extracted from user profile metadata. Our extensive experiments showed a contrasting participation behavior of the user identities by their content practices, such as the use of higher authoritative content sharing by organization and organization-affiliated users. This study provides a direction for designing realtime credible content analytics systems for humanitarian and disaster response agencies.
Convergence Rates for Empirical Estimation of Binary Classification Bounds
Venue: arXiv cs.IT 2018
Year: 2018

Bounding the best achievable error probability for binary classification problems is relevant to many applications including machine learning, signal processing, and information theory. Many bounds on the Bayes binary classification error rate depend on information divergences between the pair of class distributions. Recently, the Henze-Penrose (HP) divergence has been proposed for bounding classification error probability. We consider the problem of empirically estimating the HP-divergence from random samples. We derive a bound on the convergence rate for the Friedman-Rafsky (FR) estimator of the HP-divergence, which is related to a multivariate runs statistic for testing between two distributions. The FR estimator is derived from a multicolored Euclidean minimal spanning tree (MST) that spans the merged samples. We obtain a concentration inequality for the Friedman-Rafsky estimator of the Henze-Penrose divergence. We validate our results experimentally and illustrate their application to real datasets.
Simultaneously Optimizing Weight and Quantizer of Ternary Neural Network using Truncated Gaussian Approximation
Venue: arXiv cs.LG 2018
Year: 2018

In the past years, Deep convolution neural network has achieved great success in many artificial intelligence applications. However, its enormous model size and massive computation cost have become the main obstacle for deployment of such powerful algorithm in the low power and resource-limited mobile systems. As the countermeasure to this problem, deep neural networks with ternarized weights (i.e. -1, 0, +1) have been widely explored to greatly reduce the model size and computational cost, with limited accuracy degradation. In this work, we propose a novel ternarized neural network training method which simultaneously optimizes both weights and quantizer during training, differentiating from prior works. Instead of fixed and uniform weight ternarization, we are the first to incorporate the thresholds of weight ternarization into a closed-form representation using the truncated Gaussian approximation, enabling simultaneous optimization of weights and quantizer through back-propagation training. With both of the first and last layer ternarized, the experiments on the ImageNet classification task show that our ternarized ResNet-18/34/50 only has 3.9/2.52/2.16% accuracy degradation in comparison to the full-precision counterparts.
PhotoSafer: Content-Based and Context-Aware Private Photo Protection for Smartphones
Venue: arXiv cs.CR 2018
Year: 2018

Nowadays many people store photos in smartphones. Many of the photos contain sensitive, private information, such as a photocopy of driver's license and credit card. An arising privacy concern is with the unauthorized accesses to such private photos by installed apps. Coarse-grained access control systems such as the Android permission system offer all-or-nothing access to photos stored on smartphones, and users are unaware of the exact behavior of installed apps. Our analysis finds that 82% of the top 200 free apps in a popular Android app store have complete access to stored photos and network on a user's smartphone, which indicates possible private photo leakage. In addition, our user survey reveals that 87.5% of the 112 respondents are not aware that certain apps can access their photos without informing users, and all the respondents believe that the stored photos on their smartphones contain different types of private information. Hence, we propose PhotoSafer, a content-based, context-aware private photo protection system for Android phones. PhotoSafer can detect private photos based on photo content with a well-trained deep convolutional neural network, and control access to photos based on system status (e.g., screen locked or not) and app-running status (e.g., app in the background). Evaluations demonstrate that PhotoSafer can accurately identify private photos in real time. The efficacy and efficiency of the implemented prototype system show the potential for practical use.
Improved Parallel Rabin-Karp Algorithm Using Compute Unified Device Architecture
Venue: arXiv cs.DC 2018
Year: 2018

String matching algorithms are among one of the most widely used algorithms in computer science. Traditional string matching algorithms efficiency of underlaying string matching algorithm will greatly increase the efficiency of any application. In recent years, Graphics processing units are emerged as highly parallel processor. They out perform best of the central processing units in scientific computation power. By combining recent advancement in graphics processing units with string matching algorithms will allows to speed up process of string matching. In this paper we proposed modified parallel version of Rabin-Karp algorithm using graphics processing unit. Based on that, result of CPU as well as parallel GPU implementations are compared for evaluating effect of varying number of threads, cores, file size as well as pattern size.
The Dreaming Variational Autoencoder for Reinforcement Learning Environments
Venue: arXiv cs.LG 2018
Year: 2018

Reinforcement learning has shown great potential in generalizing over raw sensory data using only a single neural network for value optimization. There are several challenges in the current state-of-the-art reinforcement learning algorithms that prevent them from converging towards the global optima. It is likely that the solution to these problems lies in short- and long-term planning, exploration and memory management for reinforcement learning algorithms. Games are often used to benchmark reinforcement learning algorithms as they provide a flexible, reproducible, and easy to control environment. Regardless, few games feature a state-space where results in exploration, memory, and planning are easily perceived. This paper presents The Dreaming Variational Autoencoder (DVAE), a neural network based generative modeling architecture for exploration in environments with sparse feedback. We further present Deep Maze, a novel and flexible maze engine that challenges DVAE in partial and fully-observable state-spaces, long-horizon tasks, and deterministic and stochastic problems. We show initial findings and encourage further work in reinforcement learning driven by generative exploration.
Robust Optimization through Neuroevolution
Venue: arXiv cs.NE 2018
Year: 2018

We propose a method for evolving solutions that are robust with respect to variations of the environmental conditions (i.e. that can operate effectively in new conditions immediately, without the need to adapt to variations). The obtained results show how the method proposed is effective and computational tractable. It permits to improve performance on an extended version of the double-pole balancing problem, to outperform the best available human-designed controllers on a car racing problem, and to generate rather effective solutions for a swarm robotic problem. The comparison of different algorithms indicates that the CMA-ES and xNES methods, that operate by optimizing a distribution of parameters, represent the best options for the evolution of robust neural network controllers.
Avoiding Burst-like Error Patterns in Windowed Decoding of Spatially Coupled LDPC Codes
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we analyze efficient window shift schemes for windowed decoding of spatially coupled low-density parity-check (SC-LDPC) codes, which is known to yield close-tooptimal decoding results when compared to full belief propagation (BP) decoding. However, a drawback of windowed decoding is that either a significant amount of window updates are required leading to unnecessary high decoding complexity or the decoder suffers from sporadic burst-like error patterns, causing a decoder stall. To tackle this effect and, thus, to reduce the average decoding complexity, the basic idea is to enable adaptive window shifts based on a bit error rate (BER) prediction, which reduces the amount of unnecessary updates. As the decoder stall does not occur in analytical investigations such as the density evolution (DE), we examine different schemes on a fixed test-set and exhaustive monte-carlo simulations based on our graphic processing unit (GPU) simulation framework. As a result, we can reduce the average decoding complexity of the naive windowed decoder while improving the BER performance when compared to a non-adaptive windowed decoding scheme. Furthermore, we show that a foresightful stall prediction does not significantly outperform a retrospective stall detection which is much easier to implement in practice.
Retrofit Control with Approximate Environment Modeling
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we develop a retrofit control method with approximate environment modeling. Retrofit control is a modular control approach for a general stable network system whose subsystems are supposed to be managed by their corresponding subsystem operators. From the standpoint of a single subsystem operator who performs the design of a retrofit controller, the subsystems managed by all other operators can be regarded as an environment, the complete system model of which is assumed not to be available. The proposed retrofit control with approximate environment modeling has an advantage that the stability of the resultant control system is robustly assured regardless of not only the stability of approximate environment models, but also the magnitude of modeling errors, provided that the network system before implementing retrofit control is originally stable. This robustness property is practically significant to incorporate existing identification methods of unknown environments, because the accuracy of identified models may neither be reliable nor assurable in reality. Furthermore, we conduct a control performance analysis to show that the resultant performance can be regulated by adjusting the accuracy of approximate environment modeling. The efficiency of the proposed retrofit control is shown by numerical experiments on a network of second-order oscillators.
An Entropic Optimal Transport Loss for Learning Deep Neural Networks under Label Noise in Remote Sensing Images
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks have established as a powerful tool for large scale supervised classification tasks. The state-of-the-art performances of deep neural networks are conditioned to the availability of large number of accurately labeled samples. In practice, collecting large scale accurately labeled datasets is a challenging and tedious task in most scenarios of remote sensing image analysis, thus cheap surrogate procedures are employed to label the dataset. Training deep neural networks on such datasets with inaccurate labels easily overfits to the noisy training labels and degrades the performance of the classification tasks drastically. To mitigate this effect, we propose an original solution with entropic optimal transportation. It allows to learn in an end-to-end fashion deep neural networks that are, to some extent, robust to inaccurately labeled samples. We empirically demonstrate on several remote sensing datasets, where both scene and pixel-based hyperspectral images are considered for classification. Our method proves to be highly tolerant to significant amounts of label noise and achieves favorable results against state-of-the-art methods.
Towards Mobility-Aware Proactive Caching for Vehicular Ad hoc Networks
Venue: arXiv cs.NI 2018
Year: 2018

Harnessing information about the user mobility pattern and daily demand can enhance the network capability to improve the quality of experience (QoE) at Vehicular Ad-Hoc Networks (VANETs). Proactive caching, as one of the key features offered by 5G networks, has lately received much interest. However, more research is still needed to convey large-sized multimedia content including video, audio and pictures to the high speed moving vehicles. In this paper, we study the gains achieved by proactive caching in Roadside Units (RSUs) where we take into consideration the effect of the vehicle velocity on the optimal caching decision. Information about the user demand and mobility is harnessed to cache some files in RSUs, which will communicate with vehicles traversing along the visited roads before the actual demand. Our main objective is to minimize the total network latency. Towards this objective, we formulate two optimization problems for non-cooperative and cooperative caching schemes to find the optimal caching policy to decide which files to be cached by the RSUs. Due to the complexity of these problems, we propose a sub-optimal caching policy for each scheme. We compare the performance of the optimal caching policy to that of the sub-optimal caching policy. Numerical results show that proactive caching has a significant performance gain when compared to the baseline reactive scenario. Moreover, results reveal that the cooperative caching scheme is more efficient than the non-cooperative scheme.
Combinatorial Algorithms for General Linear Arrow-Debreu Markets
Venue: arXiv cs.GT 2018
Year: 2018

We present a combinatorial algorithm for determining the market clearing prices of a general linear Arrow-Debreu market, where every agent can own multiple goods. The existing combinatorial algorithms for linear Arrow-Debreu markets consider the case where each agent can own all of one good only. We present an $\tilde{\mathcal{O}}((n+m)^7 \log^3(UW))$ algorithm where $n$, $m$, $U$ and $W$ refer to the number of agents, the number of goods, the maximal integral utility and the maximum quantity of any good in the market respectively. The algorithm refines the iterative algorithm of Duan, Garg and Mehlhorn using several new ideas. We also identify the hard instances for existing combinatorial algorithms for linear Arrow-Debreu markets. In particular we find instances where the ratio of the maximum to the minimum equilibrium price of a good is $U^{Ω(n)}$ and the number of iterations required by the existing iterative combinatorial algorithms of Duan, and Mehlhorn and Duan, Garg, and Mehlhorn are high. Our instances also separate the two algorithms.