OpenRaiser/Intern-Atlas huggingface dataset:
k-Maximum Subarrays for Small k: Divide-and-Conquer made simpler
Venue: arXiv cs.DS 2018
Year: 2018

Given an array A of n real numbers, the maximum subarray problem is to find a contiguous subarray which has the largest sum. The k-maximum subarrays problem is to find k such subarrays with the largest sums. For the 1-maximum subarray the well known divide-and-conquer algorithm, presented in most textbooks, although suboptimal, is easy to implement and can be made optimal with a simple change that speeds up the combine phase. On the other hand, the only known divide-and-conquer algorithm for k > 1, that is efficient for small values of k, is difficult to implement, due to the intricacies of the combine phase. In this paper we give a divide- and-conquer solution for the k-maximum subarray problem that simplifies the combine phase considerably while preserving the overall running time. In the process of designing the combine phase of the algorithm we provide a simple, sublinear, O($k^{1/2} log^3 k$) time algorithm, for finding the k largest sums of X + Y, where X and Y are sorted arrays of size n and $k <= n^2$. The k largest sums are implicitly represented, and can be enumerated with an additional O(k) time. To our knowledge, this is the first sublinear time algorithm for this well studied problem. Unlike previous solutions, that are fairly complicated and sometimes difficult to implement, ours rely on simple operations such as merging sorted arrays, binary search, and selecting the $k^{th}$ smallest number in an array. We have implemented our algorithms and report excellent performance on test data.
Controlling the Charging of Electric Vehicles with Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

We propose and evaluate controllers for the coordination of the charging of electric vehicles. The controllers are based on neural networks and are completely de-centralized, in the sense that the charging current is completely decided by the controller itself. One of the versions of the controllers does not require any outside communication at all. We test controllers based on two different architectures of neural networks - the feed-forward networks and the echo state networks. The networks are optimized by either an evolutionary algorithm (CMA-ES) or by a gradient-based method. The results of the different architectures and the different optimization algorithms are compared in a realistic scenario. We show that the controllers are able to charge the cars while keeping the peak consumptions almost the same as when no charging is performed. Moreover, the controllers fill the valleys of the consumption thus reducing the difference between the maximum and minimum consumption in the grid.
Cross-Domain Adversarial Auto-Encoder
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose the Cross-Domain Adversarial Auto-Encoder (CDAAE) to address the problem of cross-domain image inference, generation and transformation. We make the assumption that images from different domains share the same latent code space for content, while having separate latent code space for style. The proposed framework can map cross-domain data to a latent code vector consisting of a content part and a style part. The latent code vector is matched with a prior distribution so that we can generate meaningful samples from any part of the prior space. Consequently, given a sample of one domain, our framework can generate various samples of the other domain with the same content of the input. This makes the proposed framework different from the current work of cross-domain transformation. Besides, the proposed framework can be trained with both labeled and unlabeled data, which makes it also suitable for domain adaptation. Experimental results on data sets SVHN, MNIST and CASIA show the proposed framework achieved visually appealing performance for image generation task. Besides, we also demonstrate the proposed method achieved superior results for domain adaptation. Code of our experiments is available in https://github.com/luckycallor/CDAAE.
A Hybrid High-Order method for incremental associative plasticity with small deformations
Venue: arXiv cs.CE 2018
Year: 2018

We devise and evaluate numerically a Hybrid High-Order (HHO) method for incremental associative plasticity with small deformations. The HHO method uses as discrete unknowns piecewise polynomials of order $k\ge1$ on the mesh skeleton, together with cell-based polynomials that can be eliminated locally by static condensation. The HHO method supports polyhedral meshes with non-matching interfaces, is free of volumetric-locking and the integration of the behavior law is performed only at cell-based quadrature nodes. Moreover, the principle of virtual work is satisfied locally with equilibrated tractions. Various two- and three-dimensional test cases from the literature are presented including comparison against known solutions and against results obtained with an industrial software using conforming and mixed finite elements.
Demystifying Deception Technology:A Survey
Venue: arXiv cs.CR 2018
Year: 2018

Deception boosts security for systems and components by denial, deceit, misinformation, camouflage and obfuscation. In this work an extensive overview of the deception technology environment is presented. Taxonomies, theoretical backgrounds, psychological aspects as well as concepts, implementations, legal aspects and ethics are discussed and compared.
IGCV$2$: Interleaved Structured Sparse Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we study the problem of designing efficient convolutional neural network architectures with the interest in eliminating the redundancy in convolution kernels. In addition to structured sparse kernels, low-rank kernels and the product of low-rank kernels, the product of structured sparse kernels, which is a framework for interpreting the recently-developed interleaved group convolutions (IGC) and its variants (e.g., Xception), has been attracting increasing interests. Motivated by the observation that the convolutions contained in a group convolution in IGC can be further decomposed in the same manner, we present a modularized building block, {IGCV$2$:} interleaved structured sparse convolutions. It generalizes interleaved group convolutions, which is composed of two structured sparse kernels, to the product of more structured sparse kernels, further eliminating the redundancy. We present the complementary condition and the balance condition to guide the design of structured sparse kernels, obtaining a balance among three aspects: model size, computation complexity and classification accuracy. Experimental results demonstrate the advantage on the balance among these three aspects compared to interleaved group convolutions and Xception, and competitive performance compared to other state-of-the-art architecture design methods.
Vortex Pooling: Improving Context Representation in Semantic Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Semantic segmentation is a fundamental task in computer vision, which can be considered as a per-pixel classification problem. Recently, although fully convolutional neural network (FCN) based approaches have made remarkable progress in such task, aggregating local and contextual information in convolutional feature maps is still a challenging problem. In this paper, we argue that, when predicting the category of a given pixel, the regions close to the target are more important than those far from it. To tackle this problem, we then propose an effective yet efficient approach named Vortex Pooling to effectively utilize contextual information. Empirical studies are also provided to validate the effectiveness of the proposed method. To be specific, our approach outperforms the previous state-of-the-art model named DeepLab v3 by 1.5% on the PASCAL VOC 2012 val set and 0.6% on the test set by replacing the Atrous Spatial Pyramid Pooling (ASPP) module in DeepLab v3 with the proposed Vortex Pooling. Moreover, our model (10.13FPS) shares similar computation cost with DeepLab v3 (10.37 FPS).
Structured networks and coarse-grained descriptions: a dynamical perspective
Venue: arXiv cs.SI 2018
Year: 2018

This chapter discusses the interplay between structure and dynamics in complex networks. Given a particular network with an endowed dynamics, our goal is to find partitions aligned with the dynamical process acting on top of the network. We thus aim to gain a reduced description of the system that takes into account both its structure and dynamics. In the first part, we introduce the general mathematical setup for the types of dynamics we consider throughout the chapter. We provide two guiding examples, namely consensus dynamics and diffusion processes (random walks), motivating their connection to social network analysis, and provide a brief discussion on the general dynamical framework and its possible extensions. In the second part, we focus on the influence of graph structure on the dynamics taking place on the network, focusing on three concepts that allow us to gain insight into this notion. First, we describe how time scale separation can appear in the dynamics on a network as a consequence of graph structure. Second, we discuss how the presence of particular symmetries in the network give rise to invariant dynamical subspaces that can be precisely described by graph partitions. Third, we show how this dynamical viewpoint can be extended to study dynamics on networks with signed edges, which allow us to discuss connections to concepts in social network analysis, such as structural balance. In the third part, we discuss how to use dynamical processes unfolding on the network to detect meaningful network substructures. We then show how such dynamical measures can be related to seemingly different algorithm for community detection and coarse-graining proposed in the literature. We conclude with a brief summary and highlight interesting open future directions.
Network Signatures from Image Representation of Adjacency Matrices: Deep/Transfer Learning for Subgraph Classification
Venue: arXiv cs.CV 2018
Year: 2018

We propose a novel subgraph image representation for classification of network fragments with the targets being their parent networks. The graph image representation is based on 2D image embeddings of adjacency matrices. We use this image representation in two modes. First, as the input to a machine learning algorithm. Second, as the input to a pure transfer learner. Our conclusions from several datasets are that (a) deep learning using our structured image features performs the best compared to benchmark graph kernel and classical features based methods; and, (b) pure transfer learning works effectively with minimum interference from the user and is robust against small data.
Lightweight Cryptography for Distributed PKI Based MANETS
Venue: arXiv cs.CR 2018
Year: 2018

Because of lack of infrastructure and Central Authority(CA), secure communication is a challenging job in MANETs. A lightweight security solution is needed in MANET to balance its nodes resource tightness and mobility feature. The role of CA should be decentralized in MANET because the network is managed by the nodes themselves without any fixed infrastructure and centralized authority. In this paper, we created a distributed Public Key Infrastructure (PKI) using Shamir secret sharing mechanism which allows the nodes of the MANET to have a share of its private key. The traditional PKI protocols require centralized authority and heavy computing power to manage public and private keys, thus making them not suitable for MANETs. To establish a secure communication for the MANET nodes, we proposed a lightweight crypto protocol which requires limited resources, making it suitable for MANETs.
Similarity between Learning Outcomes from Course Objectives using Semantic Analysis, Blooms taxonomy and Corpus statistics
Venue: arXiv cs.CL 2018
Year: 2018

The course description provided by instructors is an essential piece of information as it defines what is expected from the instructor and what he/she is going to deliver during a particular course. One of the key components of a course description is the Learning Objectives section. The contents of this section are used by program managers who are tasked to compare and match two different courses during the development of Transfer Agreements between various institutions. This research introduces the development of semantic similarity algorithms to calculate the similarity between two learning objectives of the same domain. We present a novel methodology which deals with the semantic similarity by using a previously established algorithm and integrating it with the domain corpus utilizing domain statistics. The disambiguated domain serves as a supervised learning data for the algorithm. We also introduce Bloom Index to calculate the similarity between action verbs in the Learning Objectives referring to the Blooms taxonomy.
On $f$-Divergences: Integral Representations, Local Behavior, and Inequalities
Venue: arXiv cs.IT 2018
Year: 2018

This paper is focused on $f$-divergences, consisting of three main contributions. The first one introduces integral representations of a general $f$-divergence by means of the relative information spectrum. The second part provides a new approach for the derivation of $f$-divergence inequalities, and it exemplifies their utility in the setup of Bayesian binary hypothesis testing. The last part of this paper further studies the local behavior of $f$-divergences.
Effects of Interruptibility-Aware Robot Behavior
Venue: arXiv cs.RO 2018
Year: 2018

As robots become increasingly prevalent in human environments, there will inevitably be times when a robot needs to interrupt a human to initiate an interaction. Our work introduces the first interruptibility-aware mobile robot system, and evaluates the effects of interruptibility-awareness on human task performance, robot task performance, and on human interpretation of the robot's social aptitude. Our results show that our robot is effective at predicting interruptibility at high accuracy, allowing it to interrupt at more appropriate times. Results of a large-scale user study show that while participants are able to maintain task performance even in the presence of interruptions, interruptibility-awareness improves the robot's task performance and improves participant social perception of the robot.
Review of Mobile Apps Permissions and Associated Intrusive Privacy Threats
Venue: arXiv cs.CY 2018
Year: 2018

The age of technology has created a huge market for smartphones and Apps usage and a new generation has been created based on knowledge sharing. Now knowledge has been made easily accessible by Apps but; are users even aware of the permissions that these Apps require and the privacy issues involved? The study was conducted on the basis of how users make use of Apps. It was conducted through the assessment of permissions required by various Apps through carefully selected third-party Apps and the devices settings and also a review of existing literature that has been conducted in fields within Apps and privacy. It will be unearthed that a many different but exhaustive lists of permission are sought by each App installed and the device it is installed on can quite give the user the information. Also not all permissions sought were found to be risky but some just created a path or a vulnerable point for other malicious programs to take advantage of.
Deep Probabilistic Programming Languages: A Qualitative Study
Venue: arXiv cs.AI 2018
Year: 2018

Deep probabilistic programming languages try to combine the advantages of deep learning with those of probabilistic programming languages. If successful, this would be a big step forward in machine learning and programming languages. Unfortunately, as of now, this new crop of languages is hard to use and understand. This paper addresses this problem directly by explaining deep probabilistic programming languages and indirectly by characterizing their current strengths and weaknesses.
An Adaptive Clipping Approach for Proximal Policy Optimization
Venue: arXiv cs.LG 2018
Year: 2018

Very recently proximal policy optimization (PPO) algorithms have been proposed as first-order optimization methods for effective reinforcement learning. While PPO is inspired by the same learning theory that justifies trust region policy optimization (TRPO), PPO substantially simplifies algorithm design and improves data efficiency by performing multiple epochs of \emph{clipped policy optimization} from sampled data. Although clipping in PPO stands for an important new mechanism for efficient and reliable policy update, it may fail to adaptively improve learning performance in accordance with the importance of each sampled state. To address this issue, a new surrogate learning objective featuring an adaptive clipping mechanism is proposed in this paper, enabling us to develop a new algorithm, known as PPO-$λ$. PPO-$λ$ optimizes policies repeatedly based on a theoretical target for adaptive policy improvement. Meanwhile, destructively large policy update can be effectively prevented through both clipping and adaptive control of a hyperparameter $λ$ in PPO-$λ$, ensuring high learning reliability. PPO-$λ$ enjoys the same simple and efficient design as PPO. Empirically on several Atari game playing tasks and benchmark control tasks, PPO-$λ$ also achieved clearly better performance than PPO.
Simplex Queues for Hot-Data Download
Venue: arXiv cs.IT 2018
Year: 2018

In cloud storage systems, hot data is usually replicated over multiple nodes in order to accommodate simultaneous access by multiple users as well as increase the fault tolerance of the system. Recent cloud storage research has proposed using availability codes, which is a special class of erasure codes, as a more storage efficient way to store hot data. These codes enable data recovery from multiple, small disjoint groups of servers. The number of the recovery groups is referred to as the availability and the size of each group as the locality of the code. Until now, we have very limited knowledge on how code locality and availability affect data access time. Data download from these systems involves multiple fork-join queues operating in-parallel, making the analysis of access time a very challenging problem. In this paper, we present an approximate analysis of data access time in storage systems that employ simplex codes, which are an important and in certain sense optimal class of availability codes. We consider and compare three strategies in assigning download requests to servers; first one aggressively exploits the storage availability for faster download, second one implements only load balancing, and the last one employs storage availability only for hot data download without incurring any negative impact on the cold data download.
Faster Evaluation of Subtraction Games
Venue: arXiv cs.DS 2018
Year: 2018

Subtraction games are played with one or more heaps of tokens, with players taking turns removing from a single heap a number of tokens belonging to a specified subtraction set; the last player to move wins. We describe how to compute the set of winning heap sizes in single-heap subtraction games (for an input consisting of the subtraction set and maximum heap size $n$), in time $\tilde O(n)$, where the $\tilde O$ elides logarithmic factors. For multi-heap games, the optimal game play is determined by the nim-value of each heap; we describe how to compute the nim-values of all heaps of size up to~$n$ in time $\tilde O(mn)$, where $m$ is the maximum nim-value occurring among these heap sizes. These time bounds improve naive dynamic programming algorithms with time $O(n|S|)$, because $m\le|S|$ for all such games. We apply these results to the game of subtract-a-square, whose set of winning positions is a maximal square-difference-free set of a type studied in number theory in connection with the Furstenberg-Sárközy theorem. We provide experimental evidence that, for this game, the set of winning positions has a density comparable to that of the densest known square-difference-free sets, and has a modular structure related to the known constructions for these dense sets. Additionally, this game's nim-values are (experimentally) significantly smaller than the size of its subtraction set, implying that our algorithm achieves a polynomial speedup over dynamic programming.
Aspect Level Sentiment Classification with Attention-over-Attention Neural Networks
Venue: arXiv cs.CL 2018
Year: 2018

Aspect-level sentiment classification aims to identify the sentiment expressed towards some aspects given context sentences. In this paper, we introduce an attention-over-attention (AOA) neural network for aspect level sentiment classification. Our approach models aspects and sentences in a joint way and explicitly captures the interaction between aspects and context sentences. With the AOA module, our model jointly learns the representations for aspects and sentences, and automatically focuses on the important parts in sentences. Our experiments on laptop and restaurant datasets demonstrate our approach outperforms previous LSTM-based architectures.
On bounds on bend number of split and cocomparability graphs
Venue: arXiv cs.DM 2018
Year: 2018

A path is a simple, piecewise linear curve made up of alternating horizontal and vertical line segments in the plane. A $k$-bend path is a path made up of at most $k + 1$ line segments. A $B_k$-VPG representation of a graph is a collection of $k$-bend paths such that each path in the collection represents a vertex of the graph and two such paths intersect if and only if the vertices they represent are adjacent in the graph. The graphs that have a $B_k$-VPG representation are called $B_k$-VPG graphs. It is known that the poset dimension $dim(G)$ of a cocomparability graph $G$ is greater than or equal to its bend number $bend(G)$. Cohen et al. ({\textsc{order 2015}}) asked for examples of cocomparability graphs with low bend number and high poset dimension. We answer this question by proving that for each $m, t \in \mathbb{N}$, there exists a cocomparability graph $G_{t,m}$ with $t < bend(G_{t,m}) \leq 4t+29$ and $dim(G_{t,m})-bend(G_{t,m})>m$. Techniques used to prove the above result, allows us to partially address the open question posed by Chaplick et al. ({\textsc{wg 2012}}) who asked whether $B_k$-VPG-chordal $\subsetneq$ $B_{k+1}$-VPG-chordal for all $k \in \mathbb{N}$. We address this by proving that there are infinitely many $m \in \mathbb{N}$ such that $B_m$-VPG-split $\subsetneq$ $B_{m+1}$-VPG-split which provides infinitely many positive examples. We use the same techniques to prove that, for all $t \in \mathbb{N}$, $B_t$-VPG-$Forb(C_{\geq 5})$ $\subsetneq$ $B_{4t+29}$-VPG-$Forb(C_{\geq 5})$, where $Forb(C_{\geq 5})$ denotes the family of graphs that does not contain induced cycles of length greater than 4. Furthermore, we show that for all $t \in \mathbb{N}$, $PB_t$-VPG-split $\subsetneq PB_{36t+80}$-VPG-split, where $PB_t$-VPG denotes the class of graphs with proper bend number at most $t$.
Mathematical Models of Specific Elements of Wind Energy Conversion Systems Based on Induction Generator
Venue: arXiv cs.SY 2018
Year: 2018

In the complex case of wind energy conversion systems (WECS) analysis and synthesis, the mathematical models of each component element are required. In the paper are presented some contributions to preset values establishing strategies and models of specific elements: rotation speed and voltage preset values establishing strategies, a simplified fixed blade wind turbine model, the induction generator squirrel rotor induction generator Park mathematical model, specific to current frequency converter supplier use, current frequency converter inverter model. The presented models are used for WECS analysis in its specific transient regimes as well for its controller design.