OpenRaiser/Intern-Atlas huggingface dataset:
A Factor Graph Approach to Multi-Camera Extrinsic Calibration on Legged Robots
Venue: arXiv cs.RO 2019
Year: 2019

Legged robots are becoming popular not only in research, but also in industry, where they can demonstrate their superiority over wheeled machines in a variety of applications. Either when acting as mobile manipulators or just as all-terrain ground vehicles, these machines need to precisely track the desired base and end-effector trajectories, perform Simultaneous Localization and Mapping (SLAM), and move in challenging environments, all while keeping balance. A crucial aspect for these tasks is that all onboard sensors must be properly calibrated and synchronized to provide consistent signals for all the software modules they feed. In this paper, we focus on the problem of calibrating the relative pose between a set of cameras and the base link of a quadruped robot. This pose is fundamental to successfully perform sensor fusion, state estimation, mapping, and any other task requiring visual feedback. To solve this problem, we propose an approach based on factor graphs that jointly optimizes the mutual position of the cameras and the robot base using kinematics and fiducial markers. We also quantitatively compare its performance with other state-of-the-art methods on the hydraulic quadruped robot HyQ. The proposed approach is simple, modular, and independent from external devices other than the fiducial marker.
Partitions of Matrix Spaces With an Application to $q$-Rook Polynomials
Venue: arXiv cs.IT 2019
Year: 2019

We study the row-space partition and the pivot partition on the matrix space $\mathbb{F}_q^{n \times m}$. We show that both these partitions are reflexive and that the row-space partition is self-dual. Moreover, using various combinatorial methods, we explicitly compute the Krawtchouk coefficients associated with these partitions. This establishes MacWilliams-type identities for the row-space and pivot enumerators of linear rank-metric codes. We then generalize the Singleton-like bound for rank-metric codes, and introduce two new concepts of code extremality. Both of them generalize the notion of MRD codes and are preserved by trace-duality. Moreover, codes that are extremal according to either notion satisfy strong rigidity properties analogous to those of MRD codes. As an application of our results to combinatorics, we give closed formulas for the $q$-rook polynomials associated with Ferrers diagram boards. Moreover, we exploit connections between matrices over finite fields and rook placements to prove that the number of matrices of rank $r$ over $\mathbb{F}_q$ supported on a Ferrers diagram is a polynomial in $q$, whose degree is strictly increasing in $r$. Finally, we investigate the natural analogues of the MacWilliams Extension Theorem for the rank, the row-space, and the pivot partitions.
Dynamic Representations Toward Efficient Inference on Deep Neural Networks by Decision Gates
Venue: arXiv cs.NE 2019
Year: 2019

While deep neural networks extract rich features from the input data, the current trade-off between depth and computational cost makes it difficult to adopt deep neural networks for many industrial applications, especially when computing power is limited. Here, we are inspired by the idea that, while deeper embeddings are needed to discriminate difficult samples (i.e., fine-grained discrimination), a large number of samples can be well discriminated via much shallower embeddings (i.e., coarse-grained discrimination). In this study, we introduce the simple yet effective concept of decision gates (d-gate), modules trained to decide whether a sample needs to be projected into a deeper embedding or if an early prediction can be made at the d-gate, thus enabling the computation of dynamic representations at different depths. The proposed d-gate modules can be integrated with any deep neural network and reduces the average computational cost of the deep neural networks while maintaining modeling accuracy. The proposed d-gate framework is examined via different network architectures and datasets, with experimental results showing that leveraging the proposed d-gate modules led to a ~43% speed-up and 44% FLOPs reduction on ResNet-101 and 55% speed-up and 39% FLOPs reduction on DenseNet-201 trained on the CIFAR10 dataset with only ~2% drop in accuracy. Furthermore, experiments where d-gate modules are integrated into ResNet-101 trained on the ImageNet dataset demonstrate that it is possible to reduce the computational cost of the network by 1.5 GFLOPs without any drop in the modeling accuracy.
Complexity Estimates for Fourier-Motzkin Elimination
Venue: arXiv cs.SC 2019
Year: 2019

In this paper, we propose a new method for removing all the redundant inequalities generated by Fourier-Motzkin elimination. This method is based on an improved version of Balas' work and can also be used to remove all the redundant inequalities in the input system. Moreover, our method only uses arithmetic operations on matrices and avoids resorting to linear programming techniques. Algebraic complexity estimates and experimental results show that our method outperforms alternative approaches, in particular those based on linear programming and simplex algorithm.
Incrementally Building Topology Graphs via Distance Maps
Venue: arXiv cs.RO 2019
Year: 2019

Mapping is an essential task for mobile robots and topological representation often works as a basis for the various applications. In this paper, a novel framework that can build topological maps incrementally is proposed. The algorithm is using a distance map, and in our framework the topological map can grow as we append more sensor data to the map. To demonstrate our algorithm, we show the result of the distance map based method on several popular maps and run the incremental framework with raw sensor data to have a growing topological map, as an example of a robot exploring the environment.
On a generalization of iterated and randomized rounding
Venue: arXiv cs.DS 2019
Year: 2019

We give a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems where iterated rounding has been useful.
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Venue: arXiv cs.DS 2019
Year: 2019

Given an $n$-bit array $A$, the succinct rank data structure problem asks to construct a data structure using space $n+r$ bits for $r\ll n$, supporting rank queries of form $\mathtt{rank}(x)=\sum_{i=0}^{x-1} A[i]$. In this paper, we design a new succinct rank data structure with $r=n/(\log n)^{Ω(t)}+n^{1-c}$ and query time $O(t)$ for some constant $c>0$, improving the previous best-known by Patrascu [Pat08], which has $r=n/(\frac{\log n}{t})^{Ω(t)}+\tilde{O}(n^{3/4})$ bits of redundancy. For $r>n^{1-c}$, our space-time tradeoff matches the cell-probe lower bound by Patrascu and Viola [PV10], which asserts that $r$ must be at least $n/(\log n)^{O(t)}$. Moreover, one can avoid an $n^{1-c}$-bit lookup table when the data structure is implemented in the cell-probe model, achieving $r=\lceil n/(\log n)^{Ω(t)}\rceil$. It matches the lower bound for the full range of parameters. En route to our new data structure design, we establish an interesting connection between succinct data structures and approximate nonnegative tensor decomposition. Our connection shows that for specific problems, to construct a space-efficient data structure, it suffices to approximate a particular tensor by a sum of (few) nonnegative rank-$1$ tensors. For the rank problem, we explicitly construct such an approximation, which yields an explicit construction of the data structure.
Micro-Attention for Micro-Expression recognition
Venue: arXiv cs.CV 2019
Year: 2019

Micro-expression, for its high objectivity in emotion detection, has emerged to be a promising modality in affective computing. Recently, deep learning methods have been successfully introduced into the micro-expression recognition area. Whilst the higher recognition accuracy achieved, substantial challenges in micro-expression recognition remain. The existence of micro expression in small-local areas on face and limited size of available databases still constrain the recognition accuracy on such emotional facial behavior. In this work, to tackle such challenges, we propose a novel attention mechanism called micro-attention cooperating with residual network. Micro-attention enables the network to learn to focus on facial areas of interest covering different action units. Moreover, coping with small datasets, the micro-attention is designed without adding noticeable parameters while a simple yet efficient transfer learning approach is together utilized to alleviate the overfitting risk. With extensive experimental evaluations on three benchmarks (CASMEII, SAMM and SMIC) and post-hoc feature visualizations, we demonstrate the effectiveness of the proposed micro-attention and push the boundary of automatic recognition of micro-expression.
Effective Subword Segmentation for Text Comprehension
Venue: arXiv cs.CL 2019
Year: 2019

Representation learning is the foundation of machine reading comprehension and inference. In state-of-the-art models, character-level representations have been broadly adopted to alleviate the problem of effectively representing rare or complex words. However, character itself is not a natural minimal linguistic unit for representation or word embedding composing due to ignoring the linguistic coherence of consecutive characters inside word. This paper presents a general subword-augmented embedding framework for learning and composing computationally-derived subword-level representations. We survey a series of unsupervised segmentation methods for subword acquisition and different subword-augmented strategies for text understanding, showing that subword-augmented embedding significantly improves our baselines in various types of text understanding tasks on both English and Chinese benchmarks.
A Description Logic Framework for Commonsense Conceptual Combination Integrating Typicality, Probabilities and Cognitive Heuristics
Venue: arXiv cs.AI 2019
Year: 2019

We propose a nonmonotonic Description Logic of typicality able to account for the phenomenon of concept combination of prototypical concepts. The proposed logic relies on the logic of typicality ALC TR, whose semantics is based on the notion of rational closure, as well as on the distributed semantics of probabilistic Description Logics, and is equipped with a cognitive heuristic used by humans for concept composition. We first extend the logic of typicality ALC TR by typicality inclusions whose intuitive meaning is that "there is probability p about the fact that typical Cs are Ds". As in the distributed semantics, we define different scenarios containing only some typicality inclusions, each one having a suitable probability. We then focus on those scenarios whose probabilities belong to a given and fixed range, and we exploit such scenarios in order to ascribe typical properties to a concept C obtained as the combination of two prototypical concepts. We also show that reasoning in the proposed Description Logic is EXPTIME-complete as for the underlying ALC.
Low-Rank Tensor Modeling for Hyperspectral Unmixing Accounting for Spectral Variability
Venue: arXiv cs.CV 2019
Year: 2019

Traditional hyperspectral unmixing methods neglect the underlying variability of spectral signatures often observed in typical hyperspectral images (HI), propagating these missmodeling errors throughout the whole unmixing process. Attempts to model material spectra as members of sets or as random variables tend to lead to severely ill-posed unmixing problems. Although parametric models have been proposed to overcome this drawback by handling endmember variability through generalizations of the mixing model, the success of these techniques depend on employing appropriate regularization strategies. Moreover, the existing approaches fail to adequately explore the natural multidimensinal representation of HIs. Recently, tensor-based strategies considered low-rank decompositions of hyperspectral images as an alternative to impose low-dimensional structures on the solutions of standard and multitemporal unmixing problems. These strategies, however, present two main drawbacks: 1) they confine the solutions to low-rank tensors, which often cannot represent the complexity of real-world scenarios; and 2) they lack guarantees that endmembers and abundances will be correctly factorized in their respective tensors. In this work, we propose a more flexible approach, called ULTRA-V, that imposes low-rank structures through regularizations whose strictness is controlled by scalar parameters. Simulations attest the superior accuracy of the method when compared with state-of-the-art unmixing algorithms that account for spectral variability.
New MDS Self-dual Codes over Finite Fields of Odd Characteristic
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we produce new classes of MDS self-dual codes via (extended) generalized Reed-Solomon codes over finite fields of odd characteristic. Among our constructions, there are many MDS self-dual codes with new parameters which have never been reported. For odd prime power $q$ with $q$ square, the total number of lengths for MDS self-dual codes over $\mathbb{F}_q$ presented in this paper is much more than those in all the previous results.
Supervisor Obfuscation Against Actuator Enablement Attack
Venue: arXiv cs.SY 2019
Year: 2019

In this paper, we propose and address the problem of supervisor obfuscation against actuator enablement attack, in a common setting where the actuator attacker can eavesdrop the control commands issued by the supervisor. We propose a method to obfuscate an (insecure) supervisor to make it resilient against actuator enablement attack in such a way that the behavior of the original closed-loop system is preserved. An additional feature of the obfuscated supervisor, if it exists, is that it has exactly the minimum number of states among the set of all the resilient and behavior-preserving supervisors. Our approach involves a simple combination of two basic ideas: 1) a formulation of the problem of computing behavior-preserving supervisors as the problem of computing separating finite state automata under controllability and observability constraints, which can be efficiently tackled by using modern SAT solvers, and 2) the use of a recently proposed technique for the verification of attackability in our setting, with a normality assumption imposed on both the actuator attackers and supervisors.
A Tight Analysis of Bethe Approximation for Permanent
Venue: arXiv cs.DS 2019
Year: 2019

We prove that the permanent of nonnegative matrices can be deterministically approximated within a factor of $\sqrt{2}^n$ in polynomial time, improving upon the previous deterministic approximations. We show this by proving that the Bethe approximation of the permanent, a quantity computable in polynomial time, is at least as large as the permanent divided by $\sqrt{2}^{n}$. This resolves a conjecture of Gurvits. Our bound is tight, and when combined with previously known inequalities lower bounding the permanent, fully resolves the quality of Bethe approximation for permanent. As an additional corollary of our methods, we resolve a conjecture of Chertkov and Yedidia, proving that fractional belief propagation with fractional parameter $γ=-1/2$ yields an upper bound on the permanent.
On the Complexity of Reconnaissance Blind Chess
Venue: arXiv cs.AI 2019
Year: 2019

This paper provides a complexity analysis for the game of reconnaissance blind chess (RBC), a recently-introduced variant of chess where each player does not know the positions of the opponent's pieces a priori but may reveal a subset of them through chosen, private sensing actions. In contrast to many commonly studied imperfect information games like poker, an RBC player does not know what the opponent knows or has chosen to learn, exponentially expanding the size of the game's information sets (i.e., the number of possible game states that are consistent with what a player has observed). Effective RBC sensing and moving strategies must account for the uncertainty of both players, an essential element of many real-world decision-making problems. Here we evaluate RBC from a game theoretic perspective, tracking the proliferation of information sets from the perspective of selected canonical bot players in tournament play. We show that, even for effective sensing strategies, the game sizes of RBC compare to those of Go while the average size of a player's information set throughout an RBC game is much greater than that of a player in Heads-up Limit Hold 'Em. We compare these measures of complexity among different playing algorithms and provide cursory assessments of the various sensing and moving strategies.
High Speed Tracking With A Fourier Domain Kernelized Correlation Filter
Venue: arXiv cs.CV 2019
Year: 2019

It is challenging to design a high speed tracking approach using l1-norm due to its non-differentiability. In this paper, a new kernelized correlation filter is introduced by leveraging the sparsity attribute of l1-norm based regularization to design a high speed tracker. We combine the l1-norm and l2-norm based regularizations in one Huber-type loss function, and then formulate an optimization problem in the Fourier Domain for fast computation, which enables the tracker to adaptively ignore the noisy features produced from occlusion and illumination variation, while keep the advantages of l2-norm based regression. This is achieved due to the attribute of Convolution Theorem that the correlation in spatial domain corresponds to an element-wise product in the Fourier domain, resulting in that the l1-norm optimization problem could be decomposed into multiple sub-optimization spaces in the Fourier domain. But the optimized variables in the Fourier domain are complex, which makes using the l1-norm impossible if the real and imaginary parts of the variables cannot be separated. However, our proposed optimization problem is formulated in such a way that their real part and imaginary parts are indeed well separated. As such, the proposed optimization problem can be solved efficiently to obtain their optimal values independently with closed-form solutions. Extensive experiments on two large benchmark datasets demonstrate that the proposed tracking algorithm significantly improves the tracking accuracy of the original kernelized correlation filter (KCF) while with little sacrifice on tracking speed. Moreover, it outperforms the state-of-the-art approaches in terms of accuracy, efficiency, and robustness.
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Venue: arXiv cs.DC 2019
Year: 2019

In the {\em distributed all-pairs shortest paths} problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called {\em time complexity}). The problem admits $(1+o(1))$-approximation $\tildeΘ(n)$-time algorithm and a nearly-tight $\tilde Ω(n)$ lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15]\footnote{$\tilde Θ$, $\tilde O$ and $\tilde Ω$ hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios~\cite{LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14}.}. For the exact case, Elkin [STOC'17] presented an $O(n^{5/3} \log^{2/3} n)$ time bound, which was later improved to $\tilde O(n^{5/4})$ [Huang, Nanongkai, Saranurak FOCS'17]. It was shown that any super-linear lower bound (in $n$) requires a new technique [Censor-Hillel, Khoury, Paz, DISC'17], but otherwise it remained widely open whether there exists a $\tilde O(n)$-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) $\tilde O(n)$-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous $\tilde O(n^{5/4})$ bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous $\tilde O(n^{5/4})$ bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, ... poly(n)}). ...
Are the Dead Taking Over Facebook? A Big Data Approach to the Future of Death Online
Venue: arXiv cs.CY 2019
Year: 2019

We project the future accumulation of profiles belonging to deceased Facebook users. Our analysis suggests that a minimum of 1.4 billion users will pass away before 2100 if Facebook ceases to attract new users as of 2018. If the network continues expanding at current rates, however, this number will exceed 4.9 billion. In both cases, a majority of the profiles will belong to non-Western users. In discussing our findings, we draw on the emerging scholarship on digital preservation and stress the challenges arising from curating the profiles of the deceased. We argue that an exclusively commercial approach to data preservation poses important ethical and political risks that demand urgent consideration. We call for a scalable, sustainable, and dignified curation model that incorporates the interests of multiple stakeholders.
Integrative Biological Simulation, Neuropsychology, and AI Safety
Venue: arXiv cs.AI 2019
Year: 2019

We describe a biologically-inspired research agenda with parallel tracks aimed at AI and AI safety. The bottom-up component consists of building a sequence of biophysically realistic simulations of simple organisms such as the nematode $Caenorhabditis$ $elegans$, the fruit fly $Drosophila$ $melanogaster$, and the zebrafish $Danio$ $rerio$ to serve as platforms for research into AI algorithms and system architectures. The top-down component consists of an approach to value alignment that grounds AI goal structures in neuropsychology, broadly considered. Our belief is that parallel pursuit of these tracks will inform the development of value-aligned AI systems that have been inspired by embodied organisms with sensorimotor integration. An important set of side benefits is that the research trajectories we describe here are grounded in long-standing intellectual traditions within existing research communities and funding structures. In addition, these research programs overlap with significant contemporary themes in the biological and psychological sciences such as data/model integration and reproducibility.