OpenRaiser/Intern-Atlas huggingface dataset:
Fine-Grained Retrieval of Sports Plays using Tree-Based Alignment of Trajectories
Venue: arXiv cs.IR 2017
Year: 2017

We propose a novel method for effective retrieval of multi-agent spatiotemporal tracking data. Retrieval of spatiotemporal tracking data offers several unique challenges compared to conventional text-based retrieval settings. Most notably, the data is fine-grained meaning that the specific location of agents is important in describing behavior. Additionally, the data often contains tracks of multiple agents (e.g., multiple players in a sports game), which generally leads to a permutational alignment problem when performing relevance estimation. Due to the frequent position swap of agents, it is difficult to maintain the correspondence of agents, and such issues make the pairwise comparison problematic for multi-agent spatiotemporal data. To address this issue, we propose a tree-based method to estimate the relevance between multi-agent spatiotemporal tracks. It uses a hierarchical structure to perform multi-agent data alignment and partitioning in a coarse-to-fine fashion. We validate our approach via user studies with domain experts. Our results show that our method boosts performance in retrieving similar sports plays -- especially in interactive situations where the user selects a subset of trajectories compared to current state-of-the-art methods.
FPGA based Parallelized Architecture of Efficient Graph based Image Segmentation Algorithm
Venue: arXiv cs.CV 2017
Year: 2017

Efficient and real time segmentation of color images has a variety of importance in many fields of computer vision such as image compression, medical imaging, mapping and autonomous navigation. Being one of the most computationally expensive operation, it is usually done through software imple- mentation using high-performance processors. In robotic systems, however, with the constrained platform dimensions and the need for portability, low power consumption and simultaneously the need for real time image segmentation, we envision hardware parallelism as the way forward to achieve higher acceleration. Field-programmable gate arrays (FPGAs) are among the best suited for this task as they provide high computing power in a small physical area. They exceed the computing speed of software based implementations by breaking the paradigm of sequential execution and accomplishing more per clock cycle operations by enabling hardware level parallelization at an architectural level. In this paper, we propose three novel architectures of a well known Efficient Graph based Image Segmentation algorithm. These proposed implementations optimizes time and power consumption when compared to software implementations. The hybrid design proposed, has notable furtherance of acceleration capabilities delivering atleast 2X speed gain over other implemen- tations, which henceforth allows real time image segmentation that can be deployed on Mobile Robotic systems.
On the Closest Vector Problem for Lattices Constructed from Polynomials and Their Cryptographic Applications
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, we propose new classes of trapdoor functions to solve the closest vector problem in lattices. Specifically, we construct lattices based on properties of polynomials for which the closest vector problem is hard to solve unless some trapdoor information is revealed. We thoroughly analyze the security of our proposed functions using state-of-the-art attacks and results on lattice reductions. Finally, we describe how our functions can be used to design quantum-safe encryption schemes with reasonable public key sizes. In particular, our scheme can offer around $106$ bits of security with a public key size of around $6.4$ $\texttt{KB}$. Our encryption schemes are efficient with respect to key generation, encryption and decryption.
Efficient K-Shot Learning with Regularized Deep Networks
Venue: arXiv cs.CV 2017
Year: 2017

Feature representations from pre-trained deep neural networks have been known to exhibit excellent generalization and utility across a variety of related tasks. Fine-tuning is by far the simplest and most widely used approach that seeks to exploit and adapt these feature representations to novel tasks with limited data. Despite the effectiveness of fine-tuning, itis often sub-optimal and requires very careful optimization to prevent severe over-fitting to small datasets. The problem of sub-optimality and over-fitting, is due in part to the large number of parameters used in a typical deep convolutional neural network. To address these problems, we propose a simple yet effective regularization method for fine-tuning pre-trained deep networks for the task of k-shot learning. To prevent overfitting, our key strategy is to cluster the model parameters while ensuring intra-cluster similarity and inter-cluster diversity of the parameters, effectively regularizing the dimensionality of the parameter search space. In particular, we identify groups of neurons within each layer of a deep network that shares similar activation patterns. When the network is to be fine-tuned for a classification task using only k examples, we propagate a single gradient to all of the neuron parameters that belong to the same group. The grouping of neurons is non-trivial as neuron activations depend on the distribution of the input data. To efficiently search for optimal groupings conditioned on the input data, we propose a reinforcement learning search strategy using recurrent networks to learn the optimal group assignments for each network layer. Experimental results show that our method can be easily applied to several popular convolutional neural networks and improve upon other state-of-the-art fine-tuning based k-shot learning strategies by more than10%
Deep Convolutional Neural Networks as Generic Feature Extractors
Venue: arXiv cs.CV 2017
Year: 2017

Recognizing objects in natural images is an intricate problem involving multiple conflicting objectives. Deep convolutional neural networks, trained on large datasets, achieve convincing results and are currently the state-of-the-art approach for this task. However, the long time needed to train such deep networks is a major drawback. We tackled this problem by reusing a previously trained network. For this purpose, we first trained a deep convolutional network on the ILSVRC2012 dataset. We then maintained the learned convolution kernels and only retrained the classification part on different datasets. Using this approach, we achieved an accuracy of 67.68 % on CIFAR-100, compared to the previous state-of-the-art result of 65.43 %. Furthermore, our findings indicate that convolutional networks are able to learn generic feature extractors that can be used for different tasks.
Covering vectors by spaces: Regular matroids
Venue: arXiv cs.DS 2017
Year: 2017

Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theorem can be used in the design of parameterized algorithms on regular matroids. We consider the problem of covering a set of vectors of a given finite dimensional linear space (vector space) by a subspace generated by a set of vectors of minimum size. Specifically, in the Space Cover problem, we are given a matrix M and a subset of its columns T; the task is to find a minimum set F of columns of M disjoint with T such that that the linear span of F contains all vectors of T. For graphic matroids this problem is essentially Stainer Forest and for cographic matroids this is a generalization of Multiway Cut. Our main result is the algorithm with running time 2^{O(k)}||M|| ^{O(1)} solving Space Cover in the case when M is a totally unimodular matrix over rationals, where k is the size of F. In other words, we show that on regular matroids the problem is fixed-parameter tractable parameterized by the rank of the covering subspace.
An Integrated Research Infrastructure for Validating Cyber-Physical Energy Systems
Venue: arXiv cs.SY 2017
Year: 2017

Renewables are key enablers in the plight to reduce greenhouse gas emissions and cope with anthropogenic global warming. The intermittent nature and limited storage capabilities of renewables culminate in new challenges that power system operators have to deal with in order to regulate power quality and ensure security of supply. At the same time, the increased availability of advanced automation and communication technologies provides new opportunities for the derivation of intelligent solutions to tackle the challenges. Previous work has shown various new methods of operating highly interconnected power grids, and their corresponding components, in a more effective way. As a consequence of these developments, the traditional power system is being transformed into a cyber-physical energy system, a smart grid. Previous and ongoing research have tended to mainly focus on how specific aspects of smart grids can be validated, but until there exists no integrated approach for the analysis and evaluation of complex cyber-physical systems configurations. This paper introduces integrated research infrastructure that provides methods and tools for validating smart grid systems in a holistic, cyber-physical manner. The corresponding concepts are currently being developed further in the European project ERIGrid.
Five-Nines Reliable Downward Routing in RPL
Venue: arXiv cs.NI 2017
Year: 2017

After a decade of research in low-power data collection, reaching arbitrary nodes has received comparatively little attention. The leading protocol for low-power IPv6 routing, RPL, is no exception, as it is often studied in multipoint-to-point scenarios. As a result, downward routing (from root to node) is still notoriously difficult, holding back the emergence of Internet of Things applications that involve actuation. In this paper, we focus on achieving industrial-grade reliability levels (1e-5 failure rate) in downward routing with RPL. We make every packet count, and classify the different causes of packet loss. We show how to mitigate each source of packet loss, by (1) introducing a gradient metric that favors reliable links, (2) increasing neighborhood awareness for accurate link selection, and (3) ensuring a robust routing state maintenance and packet forwarding. We demonstrate RPL downward routing with loss rates in the order of 1e-5 in four different testbeds up to 352 nodes, in both sparse and dense settings. We also validate our solution on top of a low-power TSCH scheduler, and achieve sub-percent low duty cycles and a channel utilization of 0.07% at every node, spread over 16 channels.
Projection Based Weight Normalization for Deep Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Optimizing deep neural networks (DNNs) often suffers from the ill-conditioned problem. We observe that the scaling-based weight space symmetry property in rectified nonlinear network will cause this negative effect. Therefore, we propose to constrain the incoming weights of each neuron to be unit-norm, which is formulated as an optimization problem over Oblique manifold. A simple yet efficient method referred to as projection based weight normalization (PBWN) is also developed to solve this problem. PBWN executes standard gradient updates, followed by projecting the updated weight back to Oblique manifold. This proposed method has the property of regularization and collaborates well with the commonly used batch normalization technique. We conduct comprehensive experiments on several widely-used image datasets including CIFAR-10, CIFAR-100, SVHN and ImageNet for supervised learning over the state-of-the-art convolutional neural networks, such as Inception, VGG and residual networks. The results show that our method is able to improve the performance of DNNs with different architectures consistently. We also apply our method to Ladder network for semi-supervised learning on permutation invariant MNIST dataset, and our method outperforms the state-of-the-art methods: we obtain test errors as 2.52%, 1.06%, and 0.91% with only 20, 50, and 100 labeled samples, respectively.
Food for Thought: Analyzing Public Opinion on the Supplemental Nutrition Assistance Program
Venue: arXiv cs.CY 2017
Year: 2017

This project explores public opinion on the Supplemental Nutrition Assistance Program (SNAP) in news and social media outlets, and tracks elected representatives' voting records on issues relating to SNAP and food insecurity. We used machine learning, sentiment analysis, and text mining to analyze national and state level coverage of SNAP in order to gauge perceptions of the program over time across these outlets. Results indicate that the majority of news coverage has negative sentiment, more partisan news outlets have more extreme sentiment, and that clustering of negative reporting on SNAP occurs in the Midwest. Our final results and tools will be displayed in an on-line application that the ACFB Advocacy team can use to inform their communication to relevant stakeholders.
Data science for urban equity: Making gentrification an accessible topic for data scientists, policymakers, and the community
Venue: arXiv cs.CY 2017
Year: 2017

The University of Washington eScience Institute runs an annual Data Science for Social Good (DSSG) program that selects four projects each year to train students from a wide range of disciplines while helping community members execute social good projects, often with an urban focus. We present observations and deliberations of one such project, the DSSG 2017 'Equitable Futures' project, which investigates the ongoing gentrification process and the increasingly inequitable access to opportunities in Seattle. Similar processes can be observed in many major cities. The project connects issues usually analyzed in the disciplines of the built environment, geography, sociology, economics, social work and city governments with data science methodologies and visualizations.
Model Predictive Path-Following for Constrained Differentially Flat Systems
Venue: arXiv cs.RO 2017
Year: 2017

For many tasks, predictive path-following control can significantly improve the performance and robustness of autonomous robots over traditional trajectory tracking control. It does this by prioritizing closeness to the path over timed progress along the path and by looking ahead to account for changes in the path. We propose a novel predictive path-following approach that couples feedforward linearization with path-based model predictive control. Our approach has a few key advantages. By utilizing the differential flatness property, we reduce the path-based model predictive control problem from a nonlinear to a convex optimization problem. Robustness to disturbances is achieved by a dynamic path reference, which adjusts its speed based on the robot's progress. We also account for key system constraints. We demonstrate these advantages in experiment on a quadrotor. We show improved performance over a baseline trajectory tracking controller by keeping the quadrotor closer to the desired path under nominal conditions, with an initial offset and under a wind disturbance.
Bag-Level Aggregation for Multiple Instance Active Learning in Instance Classification Problems
Venue: arXiv cs.CV 2017
Year: 2017

A growing number of applications, e.g. video surveillance and medical image analysis, require training recognition systems from large amounts of weakly annotated data while some targeted interactions with a domain expert are allowed to improve the training process. In such cases, active learning (AL) can reduce labeling costs for training a classifier by querying the expert to provide the labels of most informative instances. This paper focuses on AL methods for instance classification problems in multiple instance learning (MIL), where data is arranged into sets, called bags, that are weakly labeled. Most AL methods focus on single instance learning problems. These methods are not suitable for MIL problems because they cannot account for the bag structure of data. In this paper, new methods for bag-level aggregation of instance informativeness are proposed for multiple instance active learning (MIAL). The \textit{aggregated informativeness} method identifies the most informative instances based on classifier uncertainty, and queries bags incorporating the most information. The other proposed method, called \textit{cluster-based aggregative sampling}, clusters data hierarchically in the instance space. The informativeness of instances is assessed by considering bag labels, inferred instance labels, and the proportion of labels that remain to be discovered in clusters. Both proposed methods significantly outperform reference methods in extensive experiments using benchmark data from several application domains. Results indicate that using an appropriate strategy to address MIAL problems yields a significant reduction in the number of queries needed to achieve the same level of performance as single instance AL methods.
Intelligent Pothole Detection and Road Condition Assessment
Venue: arXiv cs.CY 2017
Year: 2017

Poor road conditions are a public nuisance, causing passenger discomfort, damage to vehicles, and accidents. In the U.S., road-related conditions are a factor in 22,000 of the 42,000 traffic fatalities each year. Although we often complain about bad roads, we have no way to detect or report them at scale. To address this issue, we developed a system to detect potholes and assess road conditions in real-time. Our solution is a mobile application that captures data on a car's movement from gyroscope and accelerometer sensors in the phone. To assess roads using this sensor data, we trained SVM models to classify road conditions with 93% accuracy and potholes with 92% accuracy, beating the base rate for both problems. As the user drives, the models use the sensor data to classify whether the road is good or bad, and whether it contains potholes. Then, the classification results are used to create data-rich maps that illustrate road conditions across the city. Our system will empower civic officials to identify and repair damaged roads which inconvenience passengers and cause accidents. This paper details our data science process for collecting training data on real roads, transforming noisy sensor data into useful signals, training and evaluating machine learning models, and deploying those models to production through a real-time classification app. It also highlights how cities can use our system to crowdsource data and deliver road repair resources to areas in need.
Rotation Blurring: Use of Artificial Blurring to Reduce Cybersickness in Virtual Reality First Person Shooters
Venue: arXiv cs.HC 2017
Year: 2017

Users of Virtual Reality (VR) systems often experience vection, the perception of self-motion in the absence of any physical movement. While vection helps to improve presence in VR, it often leads to a form of motion sickness called cybersickness. Cybersickness is a major deterrent to large scale adoption of VR. Prior work has discovered that changing vection (changing the perceived speed or moving direction) causes more severe cybersickness than steady vection (walking at a constant speed or in a constant direction). Based on this idea, we try to reduce the cybersickness caused by character movements in a First Person Shooter (FPS) game in VR. We propose Rotation Blurring (RB), uniformly blurring the screen during rotational movements to reduce cybersickness. We performed a user study to evaluate the impact of RB in reducing cybersickness. We found that the blurring technique led to an overall reduction in sickness levels of the participants and delayed its onset. Participants who experienced acute levels of cybersickness benefited significantly from this technique.
Pattern-based Modeling of High-Performance Computing Resilience
Venue: arXiv cs.DC 2017
Year: 2017

With the growing scale and complexity of high-performance computing (HPC) systems, resilience solutions that ensure continuity of service despite frequent errors and component failures must be methodically designed to balance the reliability requirements with the overheads to performance and power. Design patterns enable a structured approach to the development of resilience solutions, providing hardware and software designers with the building block elements for the rapid development of novel solutions and for adapting existing technologies for emerging, extreme-scale HPC environments. In this paper, we develop analytical models that enable designers to evaluate the reliability and performance characteristics of the design patterns. These models are particularly useful in building a unified framework that analyzes and compares various resilience solutions built using a combination of patterns.
Rudder Augmented Trajectory Correction for Small UAV to Minimize Lateral Image Errors
Venue: arXiv cs.SY 2017
Year: 2017

Civil applications for unmanned aerial vehicles (UAVs) have increased rapidly over the last few years. In the realm of civil applications, many aircraft carry cameras that are physically fixed to the airframe. While this yields a simple and robust remote sensing platform, the imagery quality diminishes with increasing attitude errors. A rudder augmented trajectory correction method for small unmanned aerial vehicles is discussed in this paper. The goal of this type of controller is to minimize the lateral image errors of body fixed non-gimbaled cameras. We present a comparison to current aileron only trajectory correction autopilots. Simulation and flight test results are presented that show significant reduction in the roll angle present during trajectory correction resulting in a large effect on total flight line image deviations.
A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
Venue: arXiv cs.CG 2017
Year: 2017

Given a triangulation of a point set in the plane, a \emph{flip} deletes an edge $e$ whose removal leaves a convex quadrilateral, and replaces $e$ by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips. We characterize when this is possible by proving the \emph{Orbit Conjecture} of Bose, Lubiw, Pathak and Verdonschot which states that \emph{all} labels can be simultaneously mapped to their destination if and only if \emph{each} label individually can be mapped to its destination. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of $O(n^7)$ on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the \emph{flip complex}, has the usual flip graph as its $1$-skeleton. We use properties of the $2$-skeleton of the flip complex to prove the Orbit Conjecture.