OpenRaiser/Intern-Atlas huggingface dataset:
Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels
Venue: arXiv cs.DS 2017
Year: 2017

The CONNECTED VERTEX COVER problem asks for a vertex cover in a graph that induces a connected subgraph. The problem is known to be fixed-parameter tractable (FPT), and is unlikely to have a polynomial sized kernel (under complexity theoretic assumptions) when parameterized by the solution size. In a recent paper, Lokshtanov et al.[STOC 2017], have shown an $α$-approximate kernel for the problem for every $α> 1$, in the framework of approximate or lossy kernelization. In this work, we exhibit lossy kernels and FPT algorithms for CONNECTED VERTEX COVER for parameters that are more natural and functions of the input, and in some cases, smaller than the solution size. The parameters we consider are the sizes of a split deletion set, clique deletion set, clique cover, cluster deletion set and chordal deletion set.
Recover Missing Sensor Data with Iterative Imputing Network
Venue: arXiv cs.LG 2017
Year: 2017

Sensor data has been playing an important role in machine learning tasks, complementary to the human-annotated data that is usually rather costly. However, due to systematic or accidental mis-operations, sensor data comes very often with a variety of missing values, resulting in considerable difficulties in the follow-up analysis and visualization. Previous work imputes the missing values by interpolating in the observational feature space, without consulting any latent (hidden) dynamics. In contrast, our model captures the latent complex temporal dynamics by summarizing each observation's context with a novel Iterative Imputing Network, thus significantly outperforms previous work on the benchmark Beijing air quality and meteorological dataset. Our model also yields consistent superiority over other methods in cases of different missing rates.
Two-Archive Evolutionary Algorithm for Constrained Multi-Objective Optimization
Venue: arXiv cs.NE 2017
Year: 2017

When solving constrained multi-objective optimization problems, an important issue is how to balance convergence, diversity and feasibility simultaneously. To address this issue, this paper proposes a parameter-free constraint handling technique, two-archive evolutionary algorithm, for constrained multi-objective optimization. It maintains two co-evolving populations simultaneously: one, denoted as convergence archive, is the driving force to push the population toward the Pareto front; the other one, denoted as diversity archive, mainly tends to maintain the population diversity. In particular, to complement the behavior of the convergence archive and provide as much diversified information as possible, the diversity archive aims at exploring areas under-exploited by the convergence archive including the infeasible regions. To leverage the complementary effects of both archives, we develop a restricted mating selection mechanism that adaptively chooses appropriate mating parents from them according to their evolution status. Comprehensive experiments on a series of benchmark problems and a real-world case study fully demonstrate the competitiveness of our proposed algorithm, comparing to five state-of-the-art constrained evolutionary multi-objective optimizers.
10Sent: A Stable Sentiment Analysis Method Based on the Combination of Off-The-Shelf Approaches
Venue: arXiv cs.CL 2017
Year: 2017

Sentiment analysis has become a very important tool for analysis of social media data. There are several methods developed for this research field, many of them working very differently from each other, covering distinct aspects of the problem and disparate strategies. Despite the large number of existent techniques, there is no single one which fits well in all cases or for all data sources. Supervised approaches may be able to adapt to specific situations but they require manually labeled training, which is very cumbersome and expensive to acquire, mainly for a new application. In this context, in here, we propose to combine several very popular and effective state-of-the-practice sentiment analysis methods, by means of an unsupervised bootstrapped strategy for polarity classification. One of our main goals is to reduce the large variability (lack of stability) of the unsupervised methods across different domains (datasets). Our solution was thoroughly tested considering thirteen different datasets in several domains such as opinions, comments, and social media. The experimental results demonstrate that our combined method (aka, 10SENT) improves the effectiveness of the classification task, but more importantly, it solves a key problem in the field. It is consistently among the best methods in many data types, meaning that it can produce the best (or close to best) results in almost all considered contexts, without any additional costs (e.g., manual labeling). Our self-learning approach is also very independent of the base methods, which means that it is highly extensible to incorporate any new additional method that can be envisioned in the future. Finally, we also investigate a transfer learning approach for sentiment analysis as a means to gather additional (unsupervised) information for the proposed approach and we show the potential of this technique to improve our results.
A Directional Antenna based Leader-Follower Relay System for End-to-End Robot Communications
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we present a directional antenna-based leader-follower robotic relay system capable of building end-to-end communication in complicated and dynamically changing environments. The proposed system consists of multiple networked robots - one is a mobile end node and the others are leaders or followers acting as radio relays. Every follower uses directional antennas to relay a communication radio and to estimate the location of the leader robot as a sensory device. For bearing estimation, we employ a weight centroid algorithm (WCA) and present a theoretical analysis of the use of WCA for this work. Using a robotic convoy method, we develop online, distributed control strategies that satisfy the scalability requirements of robotic network systems and enable cooperating robots to work independently. The performance of the proposed system is evaluated by conducting extensive real-world experiments that successfully build actual communication between two end nodes.
The Riemannian Geometry of Deep Generative Models
Venue: arXiv cs.LG 2017
Year: 2017

Deep generative models learn a mapping from a low dimensional latent space to a high-dimensional data space. Under certain regularity conditions, these models parameterize nonlinear manifolds in the data space. In this paper, we investigate the Riemannian geometry of these generated manifolds. First, we develop efficient algorithms for computing geodesic curves, which provide an intrinsic notion of distance between points on the manifold. Second, we develop an algorithm for parallel translation of a tangent vector along a path on the manifold. We show how parallel translation can be used to generate analogies, i.e., to transport a change in one data point into a semantically similar change of another data point. Our experiments on real image data show that the manifolds learned by deep generative models, while nonlinear, are surprisingly close to zero curvature. The practical implication is that linear paths in the latent space closely approximate geodesics on the generated manifold. However, further investigation into this phenomenon is warranted, to identify if there are other architectures or datasets where curvature plays a more prominent role. We believe that exploring the Riemannian geometry of deep generative models, using the tools developed in this paper, will be an important step in understanding the high-dimensional, nonlinear spaces these models learn.
Identifying Most Walkable Direction for Navigation in an Outdoor Environment
Venue: arXiv cs.CV 2017
Year: 2017

We present an approach for identifying the most walkable direction for navigation using a hand-held camera. Our approach extracts semantically rich contextual information from the scene using a custom encoder-decoder architecture for semantic segmentation and models the spatial and temporal behavior of objects in the scene using a spatio-temporal graph. The system learns to minimize a cost function over the spatial and temporal object attributes to identify the most walkable direction. We construct a new annotated navigation dataset collected using a hand-held mobile camera in an unconstrained outdoor environment, which includes challenging settings such as highly dynamic scenes, occlusion between objects, and distortions. Our system achieves an accuracy of 84% on predicting a safe direction. We also show that our custom segmentation network is both fast and accurate, achieving mIOU (mean intersection over union) scores of 81 and 44.7 on the PASCAL VOC and the PASCAL Context datasets, respectively, while running at about 21 frames per second.
Intrusion Detection and Ubiquitous Host to Host Encryption
Venue: arXiv cs.CR 2017
Year: 2017

Growing concern for individual privacy, driven by an increased public awareness of the degree to which many of our electronic activities are tracked by interested third parties (e.g. Google knows what I am thinking before I finish entering my search query), is driving the development anonymizing technologies (e.g. Tor). The coming mass migration to IPv6 as the primary transport of Internet traffic promises to make one such technology, end-to-end host based encryption, more readily available to the average user. In a world where end-to-end encryption is ubiquitous, what can replace the existing models for network intrusion detection? How can network administrators and operators, responsible for securing networks against hostile activity, protect a network they cannot see? In an encrypted world, signature based event detection is unlikely to prove useful. In order to secure a network in such an environment, without trampling the privacy afforded to users by end-to-end encryption, our threat detection model needs to evolve from signature based detection to a heuristic model that flags deviations from normal network-wide behavior for further investigation. In this paper we present such a heuristic model and test its effectiveness for detecting intrusions in an entirely encrypted network environment. Our results demonstrate the network intrusion detection system's ability to monitor a network carrying only host-to-host encrypted traffic. This work indicates that a broad perspective change is required. Network security models need to evolve from endeavoring to define attack signatures to describing what the network looks like under normal conditions and searching for deviations from the norm.
Learning Discrete Distributions from Untrusted Batches
Venue: arXiv cs.LG 2017
Year: 2017

We consider the problem of learning a discrete distribution in the presence of an $ε$ fraction of malicious data sources. Specifically, we consider the setting where there is some underlying distribution, $p$, and each data source provides a batch of $\ge k$ samples, with the guarantee that at least a $(1-ε)$ fraction of the sources draw their samples from a distribution with total variation distance at most $η$ from $p$. We make no assumptions on the data provided by the remaining $ε$ fraction of sources--this data can even be chosen as an adversarial function of the $(1-ε)$ fraction of "good" batches. We provide two algorithms: one with runtime exponential in the support size, $n$, but polynomial in $k$, $1/ε$ and $1/η$ that takes $O((n+k)/ε^2)$ batches and recovers $p$ to error $O(η+ε/\sqrt{k})$. This recovery accuracy is information theoretically optimal, to constant factors, even given an infinite number of data sources. Our second algorithm applies to the $η= 0$ setting and also achieves an $O(ε/\sqrt{k})$ recover guarantee, though it runs in $\mathrm{poly}((nk)^k)$ time. This second algorithm, which approximates a certain tensor via a rank-1 tensor minimizing $\ell_1$ distance, is surprising in light of the hardness of many low-rank tensor approximation problems, and may be of independent interest.
Triangulated Surface Denoising using High Order Regularization with Dynamic Weights
Venue: arXiv cs.CG 2017
Year: 2017

Recovering high quality surfaces from noisy triangulated surfaces is a fundamental important problem in geometry processing. Sharp features including edges and corners can not be well preserved in most existing denoising methods except the recent total variation (TV) and $\ell_0$ regularization methods. However, these two methods have suffered producing staircase artifacts in smooth regions. In this paper, we first introduce a second order regularization method for restoring a surface normal vector field, and then propose a new vertex updating scheme to recover the desired surface according to the restored surface normal field. The proposed model can preserve sharp features and simultaneously suppress the staircase effects in smooth regions which overcomes the drawback of the first order models. In addition, the new vertex updating scheme can prevent ambiguities introduced in existing vertex updating methods. Numerically, the proposed high order model is solved by the augmented Lagrangian method with a dynamic weighting strategy. Intensive numerical experiments on a variety of surfaces demonstrate the superiority of our method by visually and quantitatively.
Implementation of an Android Framework for USB storage access without root rights
Venue: arXiv cs.OS 2017
Year: 2017

This bachelor thesis describes the implementation of an Android framework to access mass storage devices over the USB interface of a smartphone. First the basics of USB (i.e. interfaces, endpoints and USB On the go) and accessing USB devices via the official Android API are discussed. Next the USB mass storage class is explained, which was de- signed by the USB-IF to access mobile mass storage like USB pen drives or external HDDs. For communication with mass storage devices, most important are the bulk-only transfer and the SCSI transparent command set. Furthermore file systems, for accessing directo- ries and files, are described. This thesis focuses on the FAT32 file system from Microsoft, because it is the most commonly used file system on such devices. After the theory part it is time to look at the implementation of the framework. In this section, the first concern is the purpose in general. Then the architecture of the framework and the actual implementation are presented. Important parts are discussed in detail. The thesis finishes with an overview of the test results on various Android devices, a short conclusion and an outlook to future developments. Moreover the current status of the developed framework is visualized.
Shift: A Zero FLOP, Zero Parameter Alternative to Spatial Convolutions
Venue: arXiv cs.CV 2017
Year: 2017

Neural networks rely on convolutions to aggregate spatial information. However, spatial convolutions are expensive in terms of model size and computation, both of which grow quadratically with respect to kernel size. In this paper, we present a parameter-free, FLOP-free "shift" operation as an alternative to spatial convolutions. We fuse shifts and point-wise convolutions to construct end-to-end trainable shift-based modules, with a hyperparameter characterizing the tradeoff between accuracy and efficiency. To demonstrate the operation's efficacy, we replace ResNet's 3x3 convolutions with shift-based modules for improved CIFAR10 and CIFAR100 accuracy using 60% fewer parameters; we additionally demonstrate the operation's resilience to parameter reduction on ImageNet, outperforming ResNet family members. We finally show the shift operation's applicability across domains, achieving strong performance with fewer parameters on classification, face verification and style transfer.
A Face Fairness Framework for 3D Meshes
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we present a face fairness framework for 3D meshes that preserves the regular shape of faces and is applicable to a variety of 3D mesh restoration tasks. Specifically, we present a number of desirable properties for any mesh restoration method and show that our framework satisfies them. We then apply our framework to two different tasks --- mesh-denoising and mesh-refinement, and present comparative results for these two tasks showing improvement over other relevant methods in the literature.
Video Semantic Object Segmentation by Self-Adaptation of DCNN
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a new framework for semantic segmentation of objects in videos. We address the label inconsistency problem of deep convolutional neural networks (DCNNs) by exploiting the fact that videos have multiple frames; in a few frames the object is confidently-estimated (CE) and we use the information in them to improve labels of the other frames. Given the semantic segmentation results of each frame obtained from DCNN, we sample several CE frames to adapt the DCNN model to the input video by focusing on specific instances in the video rather than general objects in various circumstances. We propose offline and online approaches under different supervision levels. In experiments our method achieved great improvement over the original model and previous state-of-the-art methods.
Post-hoc labeling of arbitrary EEG recordings for data-efficient evaluation of neural decoding methods
Venue: arXiv cs.LG 2017
Year: 2017

Many cognitive, sensory and motor processes have correlates in oscillatory neural sources, which are embedded as a subspace into the recorded brain signals. Decoding such processes from noisy magnetoencephalogram/electroencephalogram (M/EEG) signals usually requires the use of data-driven analysis methods. The objective evaluation of such decoding algorithms on experimental raw signals, however, is a challenge: the amount of available M/EEG data typically is limited, labels can be unreliable, and raw signals often are contaminated with artifacts. The latter is specifically problematic, if the artifacts stem from behavioral confounds of the oscillatory neural processes of interest. To overcome some of these problems, simulation frameworks have been introduced for benchmarking decoding methods. Generating artificial brain signals, however, most simulation frameworks make strong and partially unrealistic assumptions about brain activity, which limits the generalization of obtained results to real-world conditions. In the present contribution, we thrive to remove many shortcomings of current simulation frameworks and propose a versatile alternative, that allows for objective evaluation and benchmarking of novel data-driven decoding methods for neural signals. Its central idea is to utilize post-hoc labelings of arbitrary M/EEG recordings. This strategy makes it paradigm-agnostic and allows to generate comparatively large datasets with noiseless labels. Source code and data of the novel simulation approach are made available for facilitating its adoption.
Solving Graph Isomorphism Problem for a Special case
Venue: arXiv cs.DM 2017
Year: 2017

Graph isomorphism is an important computer science problem. The problem for the general case is unknown to be in polynomial time. The base algorithm for the general case works in quasi-polynomial time. The solutions in polynomial time for some special type of classes are known. In this work, we have worked with a special type of graphs. We have proposed a method to represent these graphs and finding isomorphism between these graphs. The method uses a modified version of the degree list of a graph and neighbourhood degree list. These special type of graphs have a property that neighbourhood degree list of any two immediate neighbours is different for every vertex.The representation becomes invariant to the order in which the node was selected for giving the representation making the isomorphism problem trivial for this case. The algorithm works in $O(n^4)$ time, where n is the number of vertices present in the graph. The proposed algorithm runs faster than quasi-polynomial time for the graphs used in the study.
Proportionally Representative Participatory Budgeting: Axioms and Algorithms
Venue: arXiv cs.GT 2017
Year: 2017

Participatory budgeting is one of the exciting developments in deliberative grassroots democracy. We concentrate on approval elections and propose proportional representation axioms in participatory budgeting, by generalizing relevant axioms for approval-based multi-winner elections. We observe a rich landscape with respect to the computational complexity of identifying proportional budgets and computing such, and present budgeting methods that satisfy these axioms by identifying budgets that are representative to the demands of vast segments of the voters.
Engineering Resilient Collective Adaptive Systems by Self-Stabilisation
Venue: arXiv cs.DC 2017
Year: 2017

Collective adaptive systems are an emerging class of networked computational systems, particularly suited in application domains such as smart cities, complex sensor networks, and the Internet of Things. These systems tend to feature large scale, heterogeneity of communication model (including opportunistic peer-to-peer wireless interaction), and require inherent self-adaptiveness properties to address unforeseen changes in operating conditions. In this context, it is extremely difficult (if not seemingly intractable) to engineer reusable pieces of distributed behaviour so as to make them provably correct and smoothly composable. Building on the field calculus, a computational model (and associated toolchain) capturing the notion of aggregate network-level computation, we address this problem with an engineering methodology coupling formal theory and computer simulation. On the one hand, functional properties are addressed by identifying the largest-to-date field calculus fragment generating self-stabilising behaviour, guaranteed to eventually attain a correct and stable final state despite any transient perturbation in state or topology, and including highly reusable building blocks for information spreading, aggregation, and time evolution. On the other hand, dynamical properties are addressed by simulation, empirically evaluating the different performances that can be obtained by switching between implementations of building blocks with provably equivalent functional properties. Overall, our methodology sheds light on how to identify core building blocks of collective behaviour, and how to select implementations that improve system performance while leaving overall system function and resiliency properties unchanged.
Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources
Venue: arXiv cs.AI 2017
Year: 2017

Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1/2 - eps for any given eps greater than 0. We also show that no non-adaptive algorithm can achieve a ratio of 1/2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ride-sharing systems. We also present heuristics that perform well in practice.