OpenRaiser/Intern-Atlas huggingface dataset:
Generalizable Adversarial Examples Detection Based on Bi-model Decision Mismatch
Venue: arXiv cs.CV 2019
Year: 2019

Modern applications of artificial neural networks have yielded remarkable performance gains in a wide range of tasks. However, recent studies have discovered that such modelling strategy is vulnerable to Adversarial Examples, i.e. examples with subtle perturbations often too small and imperceptible to humans, but that can easily fool neural networks. Defense techniques against adversarial examples have been proposed, but ensuring robust performance against varying or novel types of attacks remains an open problem. In this work, we focus on the detection setting, in which case attackers become identifiable while models remain vulnerable. Particularly, we employ the decision layer of independently trained models as features for posterior detection. The proposed framework does not require any prior knowledge of adversarial examples generation techniques, and can be directly employed along with unmodified off-the-shelf models. Experiments on the standard MNIST and CIFAR10 datasets deliver empirical evidence that such detection approach generalizes well across not only different adversarial examples generation methods but also quality degradation attacks. Non-linear binary classifiers trained on top of our proposed features can achieve a high detection rate (>90%) in a set of white-box attacks and maintain such performance when tested against unseen attacks.
A Weighted Sparse Sampling and Smoothing Frame Transition Approach for Semantic Fast-Forward First-Person Videos
Venue: arXiv cs.CV 2019
Year: 2019

Thanks to the advances in the technology of low-cost digital cameras and the popularity of the self-recording culture, the amount of visual data on the Internet is going to the opposite side of the available time and patience of the users. Thus, most of the uploaded videos are doomed to be forgotten and unwatched in a computer folder or website. In this work, we address the problem of creating smooth fast-forward videos without losing the relevant content. We present a new adaptive frame selection formulated as a weighted minimum reconstruction problem, which combined with a smoothing frame transition method accelerates first-person videos emphasizing the relevant segments and avoids visual discontinuities. The experiments show that our method is able to fast-forward videos to retain as much relevant information and smoothness as the state-of-the-art techniques in less time. We also present a new 80-hour multimodal (RGB-D, IMU, and GPS) dataset of first-person videos with annotations for recorder profile, frame scene, activities, interaction, and attention.
Evaluating and Tuning n-fold Integer Programming
Venue: arXiv cs.DS 2019
Year: 2019

In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying the theory of so-called $n$-fold integer programming. An $n$-fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke, Onn, and Romanchuk [Math. Programming, 2013] showed an algorithm with runtime $a^{O(rst + r^2s)} n^3$, where $a$ is the largest coefficient, $r,s$, and $t$ are dimensions of blocks of the constraint matrix and $n$ is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and $n$-fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements which make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a "best" step, while finding only an "approximatelly best" step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on $n$ from $n^3$ to $n^2 \log n$. We show that decreasing the tuning parameter initially leads to an increased number of iterations needed for convergence and eventually to getting stuck in local optima, as expected. However, surprisingly small values of the parameter already exhibit good behavior. Second, our new strategy for finding "approximatelly best" steps wildly outperforms the original construction.
Robust Control for Renewable-Integrated Power Networks Considering Input Bound Constraints and Worst-Case Uncertainty Measure
Venue: arXiv cs.SY 2019
Year: 2019

Uncertainty from renewable energy and loads is one of the major challenges for stable grid operation. Various approaches have been explored to remedy these uncertainties. In this paper, we design centralized or decentralized state-feedback controllers for generators while considering worst-case uncertainty. Specifically, this paper introduces the notion of $\mathcal{L}_{\infty}$ robust control and stability for uncertain power networks. Uncertain and nonlinear differential algebraic equation model of the network is presented. The model includes unknown disturbances from renewables and loads. Given an operating point, the linearized state-space presentation is given. Then, the notion of $\mathcal{L}_{\infty}$ robust control and stability is discussed, resulting in a nonconvex optimization routine that yields a state feedback gain mitigating the impact of disturbances. The developed routine includes explicit input-bound constraints on generators' inputs and a measure of the worst-case disturbance. The feedback control architecture can be centralized, distributed, or decentralized. Algorithms based on successive convex approximations are then given to address the nonconvexity. Case studies are presented showcasing the performance of the $\mathcal{L}_{\infty}$ controllers in comparison with automatic generation control and $\mathcal{H}_{\infty}$ control methods.
Cloth Manipulation Using Random-Forest-Based Imitation Learning
Venue: arXiv cs.RO 2019
Year: 2019

We present a novel approach for robust manipulation of high-DOF deformable objects such as cloth. Our approach uses a random forest-based controller that maps the observed visual features of the cloth to an optimal control action of the manipulator. The topological structure of this random forest-based controller is determined automatically based on the training data consisting visual features and optimal control actions. This enables us to integrate the overall process of training data classification and controller optimization into an imitation learning (IL) approach. Our approach enables learning of robust control policy for cloth manipulation with guarantees on convergence.We have evaluated our approach on different multi-task cloth manipulation benchmarks such as flattening, folding and twisting. In practice, our approach works well with different deformable features learned based on the specific task or deep learning. Moreover, our controller outperforms a simple or piecewise linear controller in terms of robustness to noise. In addition, our approach is easy to implement and does not require much parameter tuning.
Anticipation in Human-Robot Cooperation: A Recurrent Neural Network Approach for Multiple Action Sequences Prediction
Venue: arXiv cs.HC 2019
Year: 2019

Close human-robot cooperation is a key enabler for new developments in advanced manufacturing and assistive applications. Close cooperation require robots that can predict human actions and intent, and understand human non-verbal cues. Recent approaches based on neural networks have led to encouraging results in the human action prediction problem both in continuous and discrete spaces. Our approach extends the research in this direction. Our contributions are three-fold. First, we validate the use of gaze and body pose cues as a means of predicting human action through a feature selection method. Next, we address two shortcomings of existing literature: predicting multiple and variable-length action sequences. This is achieved by introducing an encoder-decoder recurrent neural network topology in the discrete action prediction problem. In addition, we theoretically demonstrate the importance of predicting multiple action sequences as a means of estimating the stochastic reward in a human robot cooperation scenario. Finally, we show the ability to effectively train the prediction model on a action prediction dataset, involving human motion data, and explore the influence of the model's parameters on its performance. Source code repository: https://github.com/pschydlo/ActionAnticipation
CLX: Towards verifiable PBE data transformation
Venue: arXiv cs.DB 2019
Year: 2019

Effective data analytics on data collected from the real world usually begins with a notoriously expensive pre-processing step of data transformation and wrangling. Programming By Example (PBE) systems have been proposed to automatically infer transformations using simple examples that users provide as hints. However, an important usability issue - verification - limits the effective use of such PBE data transformation systems, since the verification process is often effort-consuming and unreliable. We propose a data transformation paradigm design CLX (pronounced "clicks") with a focus on facilitating verification for end users in a PBE-like data transformation. CLX performs pattern clustering in both input and output data, which allows the user to verify at the pattern level, rather than the data instance level, without having to write any regular expressions, thereby significantly reducing user verification effort. Thereafter, CLX automatically generates transformation programs as regular-expression replace operations that are easy for average users to verify. We experimentally compared the CLX prototype with both FlashFill, a state-of-the-art PBE data transformation tool, and Trifacta, an influential system supporting interactive data transformation. The results show improvements over the state of the art tools in saving user verification effort, without loss of efficiency or expressive power. In a user effort study on data sets of various sizes, when the data size grew by a factor of 30, the user verification time required by the CLX prototype grew by 1.3x whereas that required by FlashFill grew by 11.4x. In another test assessing the users' understanding of the transformation logic - a key ingredient in effective verification - CLX users achieved a success rate about twice that of FlashFill users.
On the Relation of Strong Triadic Closure and Cluster Deletion
Venue: arXiv cs.DS 2019
Year: 2019

We study the parameterized and classical complexity of two related problems on undirected graphs $G=(V,E)$. In Strong Triadic Closure we aim to label the edges in $E$ as strong and weak such that at most~$k$ edges are weak and $G$ contains no induced $P_3$ with two strong edges. In Cluster Deletion, we aim to destroy all induced $P_3$s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a $4k$-vertex kernel. Then, we study parameterization by $\ell:=|E|-k$ and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to $\ell$. Finally, we give a dichotomy of the classical complexity of both problems on $H$-free graphs for all $H$ of order four.
On Extended Long Short-term Memory and Dependent Bidirectional Recurrent Neural Network
Venue: arXiv cs.LG 2019
Year: 2019

In this work, we first analyze the memory behavior in three recurrent neural networks (RNN) cells; namely, the simple RNN (SRN), the long short-term memory (LSTM) and the gated recurrent unit (GRU), where the memory is defined as a function that maps previous elements in a sequence to the current output. Our study shows that all three of them suffer rapid memory decay. Then, to alleviate this effect, we introduce trainable scaling factors that act like an attention mechanism to adjust memory decay adaptively. The new design is called the extended LSTM (ELSTM). Finally, to design a system that is robust to previous erroneous predictions, we propose a dependent bidirectional recurrent neural network (DBRNN). Extensive experiments are conducted on different language tasks to demonstrate the superiority of the proposed ELSTM and DBRNN solutions. The ELTSM has achieved up to 30% increase in the labeled attachment score (LAS) as compared to LSTM and GRU in the dependency parsing (DP) task. Our models also outperform other state-of-the-art models such as bi-attention and convolutional sequence to sequence (convseq2seq) by close to 10% in the LAS. The code is released as an open source (https://github.com/yuanhangsu/ELSTM-DBRNN)
Analysis of Decimation on Finite Frames with Sigma-Delta Quantization
Venue: arXiv cs.IT 2019
Year: 2019

In Analog-to-digital (A/D) conversion, signal decimation has been proven to greatly improve the efficiency of data storage while maintaining high accuracy. When one couples signal decimation with the $ΣΔ$ quantization scheme, the reconstruction error decays exponentially with respect to the bit-rate. In this study, similar results have been proven for finite unitarily generated frames. We have devised a process called alternative decimation on finite frames that is compatible with $ΣΔ$ quantization up to the second order. In both cases, decimation results in exponential error decay with respect to the bit usage.
Insights into the robustness of control point configurations for homography and planar pose estimation
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we investigate the influence of the spatial configuration of a number of $n \geq 4$ control points on the accuracy and robustness of space resection methods, e.g. used by a fiducial marker for pose estimation. We find robust configurations of control points by minimizing the first order perturbed solution of the DLT algorithm which is equivalent to minimizing the condition number of the data matrix. An empirical statistical evaluation is presented verifying that these optimized control point configurations not only increase the performance of the DLT homography estimation but also improve the performance of planar pose estimation methods like IPPE and EPnP, including the iterative minimization of the reprojection error which is the most accurate algorithm. We provide the characteristics of stable control point configurations for real-world noisy camera data that are practically independent on the camera pose and form certain symmetric patterns dependent on the number of points. Finally, we present a comparison of optimized configuration versus the number of control points.
Dynamic IoT Choreographies
Venue: arXiv cs.DC 2019
Year: 2019

The Internet of Things is growing at a dramatic rate and extending into various application domains. We have designed, implemented and evaluated a resilient and decentralized system using IoT concepts. We applied it to maintaining the functionality of building automation systems, so that new devices can appear and vanish on-the-fly.
Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time
Venue: arXiv cs.GT 2019
Year: 2019

We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in [Faigle, Kern, Fekete, Hochstättler, Mathematical Programming, 1998].
The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups
Venue: arXiv cs.IT 2019
Year: 2019

In Group Synchronization, one attempts to find a collection of unknown group elements from noisy measurements of their pairwise differences. Several important problems in vision and data analysis reduce to group synchronization over various compact groups. Spectral Group Synchronization is a commonly used, robust algorithm for solving group synchronization problems, which relies on diagonalization of a block matrix whose blocks are matrix representations of the measured pairwise differences. Assuming uniformly distributed measurement errors, we present a rigorous analysis of the accuracy and noise sensitivity of spectral group synchronization algorithms over any compact group, up to the rounding error. We identify a Baik-Ben Arous-Péché type phase transition in the noise level, beyond which spectral group synchronization necessarily fails. Below the phase transition, spectral group synchronization succeeds in recovering the unknown group elements, but its performance deteriorates with the noise level. We provide asymptotically exact formulas for the accuracy of spectral group synchronization below the phase transition, up to the rounding error. We also provide a consistent risk estimate, allowing practitioners to estimate the method's accuracy from available measurements.
Indoor Scene Understanding in 2.5/3D for Autonomous Agents: A Survey
Venue: arXiv cs.CV 2019
Year: 2019

With the availability of low-cost and compact 2.5/3D visual sensing devices, computer vision community is experiencing a growing interest in visual scene understanding of indoor environments. This survey paper provides a comprehensive background to this research topic. We begin with a historical perspective, followed by popular 3D data representations and a comparative analysis of available datasets. Before delving into the application specific details, this survey provides a succinct introduction to the core technologies that are the underlying methods extensively used in the literature. Afterwards, we review the developed techniques according to a taxonomy based on the scene understanding tasks. This covers holistic indoor scene understanding as well as subtasks such as scene classification, object detection, pose estimation, semantic segmentation, 3D reconstruction, saliency detection, physics-based reasoning and affordance prediction. Later on, we summarize the performance metrics used for evaluation in different tasks and a quantitative comparison among the recent state-of-the-art techniques. We conclude this review with the current challenges and an outlook towards the open research problems requiring further investigation.
Precision and Recall for Time Series
Venue: arXiv cs.LG 2019
Year: 2019

Classical anomaly detection is principally concerned with point-based anomalies, those anomalies that occur at a single point in time. Yet, many real-world anomalies are range-based, meaning they occur over a period of time. Motivated by this observation, we present a new mathematical model to evaluate the accuracy of time series classification algorithms. Our model expands the well-known Precision and Recall metrics to measure ranges, while simultaneously enabling customization support for domain-specific preferences.
Partitioning a graph into degenerate subgraphs
Venue: arXiv cs.DM 2019
Year: 2019

Let $G = (V, E)$ be a connected graph with maximum degree $k\geq 3$ distinct from $K_{k+1}$. Given integers $s \geq 2$ and $p_1,\ldots,p_s\geq 0$, $G$ is said to be $(p_1, \dots, p_s)$-partitionable if there exists a partition of $V$ into sets~$V_1,\ldots,V_s$ such that $G[V_i]$ is $p_i$-degenerate for $i\in\{1,\ldots,s\}$. In this paper, we prove that we can find a $(p_1, \dots, p_s)$-partition of $G$ in $O(|V| + |E|)$-time whenever $1\geq p_1, \dots, p_s \geq 0$ and $p_1 + \dots + p_s \geq k - s$. This generalizes a result of Bonamy et al. (MFCS, 2017) and can be viewed as an algorithmic extension of Brooks' theorem and several results on vertex arboricity of graphs of bounded maximum degree. We also prove that deciding whether $G$ is $(p, q)$-partitionable is $\mathbb{NP}$-complete for every $k \geq 5$ and pairs of non-negative integers $(p, q)$ such that $(p, q) \not = (1, 1)$ and $p + q = k - 3$. This resolves an open problem of Bonamy et al. (manuscript, 2017). Combined with results of Borodin, Kostochka and Toft (\emph{Discrete Mathematics}, 2000), Yang and Yuan (\emph{Discrete Mathematics}, 2006) and Wu, Yuan and Zhao (\emph{Journal of Mathematical Study}, 1996), it also settles the complexity of deciding whether a graph with bounded maximum degree can be partitioned into two subgraphs of prescribed degeneracy.
Categorizing Variants of Goodhart's Law
Venue: arXiv cs.AI 2019
Year: 2019

There are several distinct failure modes for overoptimization of systems on the basis of metrics. This occurs when a metric which can be used to improve a system is used to an extent that further optimization is ineffective or harmful, and is sometimes termed Goodhart's Law. This class of failure is often poorly understood, partly because terminology for discussing them is ambiguous, and partly because discussion using this ambiguous terminology ignores distinctions between different failure modes of this general type. This paper expands on an earlier discussion by Garrabrant, which notes there are "(at least) four different mechanisms" that relate to Goodhart's Law. This paper is intended to explore these mechanisms further, and specify more clearly how they occur. This discussion should be helpful in better understanding these types of failures in economic regulation, in public policy, in machine learning, and in Artificial Intelligence alignment. The importance of Goodhart effects depends on the amount of power directed towards optimizing the proxy, and so the increased optimization power offered by artificial intelligence makes it especially critical for that field.
Robust Contrast Enhancement Forensics Using Pixel and Histogram Domain CNNs
Venue: arXiv cs.MM 2019
Year: 2019

Contrast enhancement (CE) forensics has always been ofconcern to image forensics community. It can provide aneffective tool for recovering image history and identifyingtampered images. Although several CE forensic algorithmshave been proposed, their robustness against some processingis still unsatisfactory, such as JPEG compression and anti-forensic attacks. In order to attenuate such deficiency, inthis paper we first present a discriminability analysis of CEforensics in pixel and gray level histogram domains. Then, insuch two domains, two end-to-end methods based on convo-lutional neural networks (P-CNN, H-CNN) are proposed toachieve robust CE forensics against pre-JPEG compressionand anti-forensics attacks. Experimental results show that theproposed methods achieve much better performance than thestate-of-the-art schemes for CE detection in the case of noother operation and comparable performance when pre-JPEGcompression and anti-foresics attacks is used.