OpenRaiser/Intern-Atlas huggingface dataset:
Improved Algorithms for Fully Dynamic Maximal Independent Set
Venue: arXiv cs.DS 2018
Year: 2018

Maintaining maximal independent set in dynamic graph is a fundamental open problem in graph theory and the first sublinear time deterministic algorithm was came up by Assadi, Onak, Schieber and Solomon(STOC'18), which achieves $O(m^{3/4})$ amortized update time. We have two main contributions in this paper. We present a new simple deterministic algorithm with $O(m^{2/3}\sqrt{\log m})$ amortized update time, which improves the previous best result. And we also present the first randomized algorithm with expected $O(\sqrt{m}\log^{1.5}m)$ amortized time against an oblivious adversary.
Scheduled Multi-Task Learning: From Syntax to Translation
Venue: arXiv cs.CL 2018
Year: 2018

Neural encoder-decoder models of machine translation have achieved impressive results, while learning linguistic knowledge of both the source and target languages in an implicit end-to-end manner. We propose a framework in which our model begins learning syntax and translation interleaved, gradually putting more focus on translation. Using this approach, we achieve considerable improvements in terms of BLEU score on relatively large parallel corpus (WMT14 English to German) and a low-resource (WIT German to English) setup.
Mining Automatically Estimated Poses from Video Recordings of Top Athletes
Venue: arXiv cs.CV 2018
Year: 2018

Human pose detection systems based on state-of-the-art DNNs are on the go to be extended, adapted and re-trained to fit the application domain of specific sports. Therefore, plenty of noisy pose data will soon be available from videos recorded at a regular and frequent basis. This work is among the first to develop mining algorithms that can mine the expected abundance of noisy and annotation-free pose data from video recordings in individual sports. Using swimming as an example of a sport with dominant cyclic motion, we show how to determine unsupervised time-continuous cycle speeds and temporally striking poses as well as measure unsupervised cycle stability over time. Additionally, we use long jump as an example of a sport with a rigid phase-based motion to present a technique to automatically partition the temporally estimated pose sequences into their respective phases. This enables the extraction of performance relevant, pose-based metrics currently used by national professional sports associations. Experimental results prove the effectiveness of our mining algorithms, which can also be applied to other cycle-based or phase-based types of sport.
On M2M Micropayments : A Case Study of Electric Autonomous Vehicles
Venue: arXiv cs.CY 2018
Year: 2018

The proliferation of electric vehicles has spurred the research interest in technologies associated with it, for instance, batteries, and charging mechanisms. Moreover, the recent advancements in autonomous cars also encourage the enabling technologies to integrate and provide holistic applications. To this end, one key requirement for electric vehicles is to have an efficient, secure, and scalable infrastructure and framework for charging, billing, and auditing. However, the current manual charging systems for EVs may not be applicable to the autonomous cars that demand new, automatic, secure, efficient, and scalable billing and auditing mechanism. Owing to the distributed systems such as blockchain technology, in this paper, we propose a new charging and billing mechanism for electric vehicles that charge their batteries in a charging-on-the-move fashion. To meet the requirements of billing in electric vehicles, we leverage distributed ledger technology (DLT), a distributed peer-to-peer technology for micro-transactions. Our proof-of-concept implementation of the billing framework demonstrates the feasibility of such system in electric vehicles. It is also worth noting that the solution can easily be extended to the electric autonomous cars (EACs).
Connectors meet Choreographies
Venue: arXiv cs.PL 2018
Year: 2018

We present Cho-Reo-graphies (CR), a new language model that unites two powerful programming paradigms for concurrent software based on communicating processes: Choreographic Programming and Exogenous Coordination. In CR, programmers specify the desired communications among processes using a choreography, and define how communications should be concretely animated by connectors given as constraint automata (e.g., synchronous barriers and asynchronous multi-casts). CR is the first choreography calculus where different communication semantics (determined by connectors) can be freely mixed; since connectors are user-defined, CR also supports many communication semantics that were previously unavailable for choreographies. We develop a static analysis that guarantees that a choreography in CR and its user-defined connectors are compatible, define a compiler from choreographies to a process calculus based on connectors, and prove that compatibility guarantees deadlock-freedom of the compiled process implementations.
Principally Box-integer Polyhedra and Equimodular Matrices
Venue: arXiv cs.DM 2018
Year: 2018

A polyhedron is box-integer if its intersection with any integer box $\{\ell\leq x \leq u\}$ is integer. We define principally box-integer polyhedra to be the polyhedra $P$ such that $kP$ is box-integer whenever $kP$ is integer. We characterize them in several ways, involving equimodular matrices and box-total dual integral (box-TDI) systems. A rational $r\times n$ matrix is equimodular if it has full row rank and its nonzero $r\times r$ determinants all have the same absolute value. A face-defining matrix is a full row rank matrix describing the affine hull of a face of the polyhedron. Box-TDI systems are systems which yield strong min-max relations, and the underlying polyhedron is called a box-TDI polyhedron. Our main result is that the following statements are equivalent. - The polyhedron $P$ is principally box-integer. - The polyhedron $P$ is box-TDI. - Every face-defining matrix of $P$ is equimodular. - Every face of $P$ has an equimodular face-defining matrix. - Every face of $P$ has a totally unimodular face-defining matrix. - For every face $F$ of $P$, lin($F$) has a totally unimodular basis. Along our proof, we show that a cone $\{x:Ax\leq \mathbf{0}\}$ is box-TDI if and only if it is box-integer, and that these properties are passed on to its polar. We illustrate the use of these characterizations by reviewing well known results about box-TDI polyhedra. We also provide several applications. The first one is a new perspective on the equivalence between two results about binary clutters. Secondly, we refute a conjecture of Ding, Zang, and Zhao about box-perfect graphs. Thirdly, we discuss connections with an abstract class of polyhedra having the Integer Carathéodory Property. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph and provide a corresponding box-TDI system.
Resource Allocation and Interference Management in OFDMA-based VLC Networks
Venue: arXiv cs.IT 2018
Year: 2018

Resource allocation and interference management are two main issues that need to be carefully addressed in visible light communication (VLC) systems. In this paper, we propose a resource allocation scheme that can also handle the inter-cell interference in a multi-user VLC system that employs orthogonal frequency division multiple access (OFDMA). Particularly, we suggest dividing the cell coverage into two non-overlapping zones and performing a two-step resource allocation process, in which each step corresponds to a different level of allocating resources, i.e., zone and user levels. We initially define both zones in terms of the physical area and the amount of allocated resources and we investigate the impact of illumination requirements on defining both zones. Through simulations, we evaluate the performance of the proposed scheme in terms of the area spectral efficiency and the fairness level between the two zones. We show that both performance measures can be potentially enhanced by carefully setting a certain design parameter that reflects the priority level of the users located in the region around the cell center, denoted as Zone 0, in terms of the achievable rate. We further eventuate the system performance in a realistic transmission scenario using a simulation tool.
An Anchor-Free Region Proposal Network for Faster R-CNN based Text Detection Approaches
Venue: arXiv cs.CV 2018
Year: 2018

The anchor mechanism of Faster R-CNN and SSD framework is considered not effective enough to scene text detection, which can be attributed to its IoU based matching criterion between anchors and ground-truth boxes. In order to better enclose scene text instances of various shapes, it requires to design anchors of various scales, aspect ratios and even orientations manually, which makes anchor-based methods sophisticated and inefficient. In this paper, we propose a novel anchor-free region proposal network (AF-RPN) to replace the original anchor-based RPN in the Faster R-CNN framework to address the above problem. Compared with a vanilla RPN and FPN-RPN, AF-RPN can get rid of complicated anchor design and achieve higher recall rate on large-scale COCO-Text dataset. Owing to the high-quality text proposals, our Faster R-CNN based two-stage text detection approach achieves state-of-the-art results on ICDAR-2017 MLT, ICDAR-2015 and ICDAR-2013 text detection benchmarks when using single-scale and single-model (ResNet50) testing only.
Cubes3D: Neural Network based Optical Flow in Omnidirectional Image Scenes
Venue: arXiv cs.CV 2018
Year: 2018

Optical flow estimation with convolutional neural networks (CNNs) has recently solved various tasks of computer vision successfully. In this paper we adapt a state-of-the-art approach for optical flow estimation to omnidirectional images. We investigate CNN architectures to determine high motion variations caused by the geometry of fish-eye images. Further we determine the qualitative influence of texture on the non-rigid object to the motion vectors. For evaluation of the results we create ground truth motion fields synthetically. The ground truth contains cubes with static background. We test variations of pre-trained FlowNet 2.0 architectures by indicating common error metrics. We generate competitive results for the motion of the foreground with inhomogeneous texture on the moving object.
Room Recognition Using Discriminative Ensemble Learning with Hidden Markov Models for Smartphones
Venue: arXiv cs.NI 2018
Year: 2018

An accurate room localization system is a powerful tool for providing location-based services. Considering that people spend most of their time indoors, indoor localization systems are becoming increasingly important in designing smart environments. In this work, we propose an efficient ensemble learning method to provide room level localization in smart buildings. Our proposed localization method achieves high room-level localization accuracy by combining Hidden Markov Models with simple discriminative learning methods. The localization algorithms are designed for a terminal-based system, which consists of commercial smartphones and Wi-Fi access points. We conduct experimental studies to evaluate our system in an office-like indoor environment. Experiment results show that our system can overcome traditional individual machine learning and ensemble learning approaches.
Robust Decentralized Navigation of Multi-Agent Systems with Collision Avoidance and Connectivity Maintenance Using Model Predictive Controllers
Venue: arXiv cs.SY 2018
Year: 2018

This paper addresses the problem of navigation control of a general class of 2nd order uncertain nonlinear multi-agent systems in a bounded workspace, which is a subset of $R^3$ , with static obstacles. In particular, we propose a decentralized control protocol such that each agent reaches a predefined position at the workspace, while using local information based on a limited sensing radius. The proposed scheme guarantees that the initially connected agents remain always connected. In addition, by introducing certain distance constraints, we guarantee inter-agent collision avoidance as well as collision avoidance with the obstacles and the boundary of the workspace. The proposed controllers employ a class of Decentralized Nonlinear Model Predictive Controllers (DNMPC) under the presence of disturbances and uncertainties. Finally, simulation results verify the validity of the proposed framework.
A reaction network scheme which implements the EM algorithm
Venue: arXiv cs.ET 2018
Year: 2018

A detailed algorithmic explanation is required for how a network of chemical reactions can generate the sophisticated behavior displayed by living cells. Though several previous works have shown that reaction networks are computationally universal and can in principle implement any algorithm, there is scope for constructions that map well onto biological reality, make efficient use of the computational potential of the native dynamics of reaction networks, and make contact with statistical mechanics. We describe a new reaction network scheme for solving a large class of statistical problems including the problem of how a cell would infer its environment from receptor-ligand bindings. Specifically we show how reaction networks can implement information projection, and consequently a generalized Expectation-Maximization algorithm, to solve maximum likelihood estimation problems in partially-observed exponential families on categorical data. Our scheme can be thought of as an algorithmic interpretation of E. T. Jaynes's vision of statistical mechanics as statistical inference.
Automated Network Service Scaling in NFV: Concepts, Mechanisms and Scaling Workflow
Venue: arXiv cs.NI 2018
Year: 2018

Next-generation systems are anticipated to be digital platforms supporting innovative services with rapidly changing traffic patterns. To cope with this dynamicity in a cost-efficient manner, operators need advanced service management capabilities such as those provided by NFV. NFV enables operators to scale network services with higher granularity and agility than today. For this end, automation is key. In search of this automation, the European Telecommunications Standards Institute (ETSI) has defined a reference NFV framework that make use of model-driven templates called Network Service Descriptors (NSDs) to operate network services through their lifecycle. For the scaling operation, an NSD defines a discrete set of instantiation levels among which a network service instance can be resized throughout its lifecycle. Thus, the design of these levels is key for ensuring an effective scaling. In this article, we provide an overview of the automation of the network service scaling operation in NFV, addressing the options and boundaries introduced by ETSI normative specifications. We start by providing a description of the NSD structure, focusing on how instantiation levels are constructed. For illustrative purposes, we propose an NSD for a representative NS. This NSD includes different instantiation levels that enable different ways to automatically scale this NS. Then, we show the different scaling procedures the NFV framework has available, and how it may automate their triggering. Finally, we propose an ETSI-compliant workflow to describe in detail a representative scaling procedure. This workflow clarifies the interactions and information exchanges between the functional blocks in the NFV framework when performing the scaling operation.
Human-level Performance On Automatic Head Biometrics In Fetal Ultrasound Using Fully Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Measurement of head biometrics from fetal ultrasonography images is of key importance in monitoring the healthy development of fetuses. However, the accurate measurement of relevant anatomical structures is subject to large inter-observer variability in the clinic. To address this issue, an automated method utilizing Fully Convolutional Networks (FCN) is proposed to determine measurements of fetal head circumference (HC) and biparietal diameter (BPD). An FCN was trained on approximately 2000 2D ultrasound images of the head with annotations provided by 45 different sonographers during routine screening examinations to perform semantic segmentation of the head. An ellipse is fitted to the resulting segmentation contours to mimic the annotation typically produced by a sonographer. The model's performance was compared with inter-observer variability, where two experts manually annotated 100 test images. Mean absolute model-expert error was slightly better than inter-observer error for HC (1.99mm vs 2.16mm), and comparable for BPD (0.61mm vs 0.59mm), as well as Dice coefficient (0.980 vs 0.980). Our results demonstrate that the model performs at a level similar to a human expert, and learns to produce accurate predictions from a large dataset annotated by many sonographers. Additionally, measurements are generated in near real-time at 15fps on a GPU, which could speed up clinical workflow for both skilled and trainee sonographers.
A Duality-Based Approach for Distributed Optimization with Coupling Constraints
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we consider a distributed optimization scenario in which a set of agents has to solve a convex optimization problem with separable cost function, local constraint sets and a coupling inequality constraint. We propose a novel distributed algorithm based on a relaxation of the primal problem and an elegant exploration of duality theory. Despite its complex derivation based on several duality steps, the distributed algorithm has a very simple and intuitive structure. That is, each node solves a local version of the original problem relaxation, and updates suitable dual variables. We prove the algorithm correctness and show its effectiveness via numerical computations.
On Multilinear Forms: Bias, Correlation, and Tensor Rank
Venue: arXiv cs.CC 2018
Year: 2018

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors. 1. Correlation bounds : We show that a random $d$-linear form has exponentially low correlation with low-degree polynomials. More precisely, for $d \ll 2^{o(k)}$, we show that a random $d$-linear form $f(X_1,X_2, \dots, X_d) : \left(GF(2)^{k}\right)^d \rightarrow GF(2)$ has correlation $2^{-k(1-o(1))}$ with any polynomial of degree at most $d/10$. This result is proved by giving near-optimal bounds on the bias of random $d$-linear form, which is in turn proved by giving near-optimal bounds on the probability that a random rank-$t$ $d$-linear form is identically zero. 2. Tensor-rank vs Bias : We show that if a $d$-dimensional tensor has small rank, then the bias of the associated $d$-linear form is large. More precisely, given any $d$-dimensional tensor $$T :\underbrace{[k]\times \ldots [k]}_{\text{$d$ times}}\to GF(2)$$ of rank at most $t$, the bias of the associated $d$-linear form $$f_T(X_1,\ldots,X_d) := \sum_{(i_1,\dots,i_d) \in [k]^d} T(i_1,i_2,\ldots, i_d) X_{1,i_1}\cdot X_{1,i_2}\cdots X_{d,i_d}$$ is at least $\left(1-\frac1{2^{d-1}}\right)^t$. The above bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds for $d=3$. In particular, we use this approach to prove that the finite field multiplication tensor has tensor rank at least $3.52 k$ matching the best known lower bound for any explicit tensor in three dimensions over $GF(2)$.
A Report on the Complex Word Identification Shared Task 2018
Venue: arXiv cs.CL 2018
Year: 2018

We report the findings of the second Complex Word Identification (CWI) shared task organized as part of the BEA workshop co-located with NAACL-HLT'2018. The second CWI shared task featured multilingual and multi-genre datasets divided into four tracks: English monolingual, German monolingual, Spanish monolingual, and a multilingual track with a French test set, and two tasks: binary classification and probabilistic classification. A total of 12 teams submitted their results in different task/track combinations and 11 of them wrote system description papers that are referred to in this report and appear in the BEA workshop proceedings.
MaskFusion: Real-Time Recognition, Tracking and Reconstruction of Multiple Moving Objects
Venue: arXiv cs.CV 2018
Year: 2018

We present MaskFusion, a real-time, object-aware, semantic and dynamic RGB-D SLAM system that goes beyond traditional systems which output a purely geometric map of a static scene. MaskFusion recognizes, segments and assigns semantic class labels to different objects in the scene, while tracking and reconstructing them even when they move independently from the camera. As an RGB-D camera scans a cluttered scene, image-based instance-level semantic segmentation creates semantic object masks that enable real-time object recognition and the creation of an object-level representation for the world map. Unlike previous recognition-based SLAM systems, MaskFusion does not require known models of the objects it can recognize, and can deal with multiple independent motions. MaskFusion takes full advantage of using instance-level semantic segmentation to enable semantic labels to be fused into an object-aware map, unlike recent semantics enabled SLAM systems that perform voxel-level semantic segmentation. We show augmented-reality applications that demonstrate the unique features of the map output by MaskFusion: instance-aware, semantic and dynamic.
ImVerde: Vertex-Diminished Random Walk for Learning Network Representation from Imbalanced Data
Venue: arXiv cs.SI 2018
Year: 2018

Imbalanced data widely exists in many high-impact applications. An example is in air traffic control, where we aim to identify the leading indicators for each type of accident cause from historical records. Among all three types of accident causes, historical records with 'personnel issues' are much more than the other two types ('aircraft issues' and 'environmental issues') combined. Thus, the resulting dataset is highly imbalanced, and can be naturally modeled as a network. Up until now, most existing work on imbalanced data analysis focused on the classification setting, and very little is devoted to learning the node representation from imbalanced networks. To address this problem, in this paper, we propose Vertex-Diminished Random Walk (VDRW) for imbalanced network analysis. The key idea is to encourage the random particle to walk within the same class by adjusting the transition probabilities each step. It resembles the existing Vertex Reinforced Random Walk in terms of the dynamic nature of the transition probabilities, as well as some convergence properties. However, it is more suitable for analyzing imbalanced networks as it leads to more separable node representations in the embedding space. Then, based on VDRW, we propose a semi-supervised network representation learning framework named ImVerde for imbalanced networks, in which context sampling uses VDRW and the label information to create node-context pairs, and balanced-batch sampling adopts a simple under-sampling method to balance these pairs in different classes. Experimental results demonstrate that ImVerde based on VDRW outperforms state-of-the-art algorithms for learning network representation from imbalanced data.