OpenRaiser/Intern-Atlas huggingface dataset:
Monocular Object and Plane SLAM in Structured Environments
Venue: arXiv cs.RO 2019
Year: 2019

In this paper, we present a monocular Simultaneous Localization and Mapping (SLAM) algorithm using high-level object and plane landmarks. The built map is denser, more compact and semantic meaningful compared to feature point based SLAM. We first propose a high order graphical model to jointly infer the 3D object and layout planes from single images considering occlusions and semantic constraints. The extracted objects and planes are further optimized with camera poses in a unified SLAM framework. Objects and planes can provide more semantic constraints such as Manhattan plane and object supporting relationships compared to points. Experiments on various public and collected datasets including ICL NUIM and TUM Mono show that our algorithm can improve camera localization accuracy compared to state-of-the-art SLAM especially when there is no loop closure, and also generate dense maps robustly in many structured environments.
Unicyclic Strong Permutations
Venue: arXiv cs.CR 2019
Year: 2019

In this paper, we study some properties of a certain kind of permutation $σ$ over $\mathbb{F}_{2}^{n}$, where $n$ is a positive integer. The desired properties for $σ$ are: (1) the algebraic degree of each component function is $n-1$; (2) the permutation is unicyclic; (3) the number of terms of the algebraic normal form of each component is at least $2^{n-1}$. We call permutations that satisfy these three properties simultaneously unicyclic strong permutations. We prove that our permutations $σ$ always have high algebraic degree and that the average number of terms of each component function tends to $2^{n-1}$. We also give a condition on the cycle structure of $σ$. We observe empirically that for $n$ even, our construction does not provide unicylic permutations. For $n$ odd, $n \leq 11$, we conduct an exhaustive search of all $σ$ given our construction for specific examples of unicylic strong permutations. We also present some empirical results on the difference tables and linear approximation tables of $σ$.
SAI, a Sensible Artificial Intelligence that plays Go
Venue: arXiv cs.AI 2019
Year: 2019

We propose a multiple-komi modification of the AlphaGo Zero/Leela Zero paradigm. The winrate as a function of the komi is modeled with a two-parameters sigmoid function, so that the neural network must predict just one more variable to assess the winrate for all komi values. A second novel feature is that training is based on self-play games that occasionally branch -- with changed komi -- when the position is uneven. With this setting, reinforcement learning is showed to work on 7x7 Go, obtaining very strong playing agents. As a useful byproduct, the sigmoid parameters given by the network allow to estimate the score difference on the board, and to evaluate how much the game is decided.
Hubless keypoint-based 3D deformable groupwise registration
Venue: arXiv cs.CV 2019
Year: 2019

We present a novel algorithm for Fast Registration Of image Groups (FROG), applied to large 3D image groups. Our approach extracts 3D SURF keypoints from images, computes matched pairs of keypoints and registers the group by minimizing pair distances in a hubless way i.e. without computing any central mean image. Using keypoints significantly reduces the problem complexity compared to voxel-based approaches, and enables us to provide an in-core global optimization, similar to the Bundle Adjustment for 3D reconstruction. As we aim to register images of different patients, the matching step yields many outliers. Then we propose a new EM-weighting algorithm which efficiently discards outliers. Global optimization is carried out with a fast gradient descent algorithm. This allows our approach to robustly register large datasets. The result is a set of diffeomorphic half transforms which link the volumes together and can be subsequently exploited for computational anatomy and landmark detection. We show experimental results on whole-body CT scans, with groups of up to 103 volumes. On a benchmark based on anatomical landmarks, our algorithm compares favorably with the star-groupwise voxel-based ANTs and NiftyReg approaches while being much faster. We also discuss the limitations of our approach for lower resolution images such as brain MRI.
A Fixed-Depth Size-Hierarchy Theorem for AC$^0[\oplus]$ via the Coin Problem
Venue: arXiv cs.CC 2019
Year: 2019

We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC$^0[\oplus]$ circuits; in particular, for fixed $d$, the class $\mathcal{C}_{d,k}$ of uniform AC$^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. For this, we find the first class of explicit functions giving (up to polynomial factor) matching upper and lower bounds for AC$^0[\oplus]$ formulas, derived from the $δ$-Coin Problem, the computational problem of distinguishing between coins that are heads with probability $(1+δ)/2$ or $(1-δ)/2,$ where $δ$ is a parameter going to $0$. We study this problem's complexity and make progress on both upper bounds and lower bounds. Upper bounds. We find explicit monotone AC$^0$ formulas solving the $δ$-coin problem, having depth $d$, size $\exp(O(d(1/δ)^{1/(d-1)}))$, and sample complexity poly$(1/δ)$, for constant $d\ge2$. This matches previous upper bounds of O'Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size and improves the sample complexity. Lower bounds. The upper bounds are nearly tight even for the stronger model of AC$^0[\oplus]$ formulas (which allow NOT and Parity gates): any AC$^0[\oplus]$ formula solving the $δ$-coin problem must have size $\exp(Ω(d(1/δ)^{1/(d-1)})).$ This strengthens a result of Cohen, Ganor and Raz (APPROX-RANDOM 2014), who prove a similar result for AC$^0$, and a result of Shaltiel and Viola (SICOMP 2010), who give a superpolynomially weaker (still exponential) lower bound. The upper bound is a derandomization involving a use of Janson's inequality (as far as we know, the first such use of the inequality) and classical combinatorial designs. For the lower bound, we prove an optimal (up to constant factor) degree lower bound for multivariate polynomials over $\mathbb{F}_2$ solving the $δ$-coin problem, which may be of independent interest.
Trajectory Generation for Multiagent Point-To-Point Transitions via Distributed Model Predictive Control
Venue: arXiv cs.RO 2019
Year: 2019

This paper introduces a novel algorithm for multiagent offline trajectory generation based on distributed model predictive control. Central to the algorithm's scalability and success is the development of an on-demand collision avoidance strategy. By predicting future states and sharing this information with their neighbors, the agents are able to detect and avoid collisions while moving toward their goals. The proposed algorithm can be implemented in a distributed fashion and reduces the computation time by more than 85% compared to previous optimization approaches based on sequential convex programming, while only having a small impact on the optimality of the plans. The approach was validated both through extensive simulations and experimentally with teams of up to 25 quadrotors flying in confined indoor spaces.
The Curse and Blessing of Not-All-Equal in k-Satisfiability
Venue: arXiv cs.CC 2019
Year: 2019

As a natural variant of the $k$-SAT problem, NAE-$k$-SAT additionally requires the literals in each clause to take not-all-equal (NAE) truth values. In this paper, we study the worst-case time complexities of solving NAE-$k$-SAT and MAX-NAE-$k$-SAT approximation, as functions of $k$, the number of variables $n$, and the performance ratio $δ$. The latter problem asks for a solution of at least $δ$ times the optimal. Our main results include: (1) A deterministic algorithm for NAE-$k$-SAT that is faster than the best deterministic algorithm for $k$-SAT on all $k \ge 3$. Previously, no NAE-$k$-SAT algorithm is known to be faster than $k$-SAT algorithms. For $k = 3$, we achieve an upper bound of $1.326^n$. The corresponding bound for $3$-SAT is $1.328^n$. (2) A randomized algorithm for MAX-NAE-$k$-SAT approximation, with upper bound $(2 - ε_k(δ))^n$ where $ε_k(δ) > 0$ only depends on $k$ and $δ$. Previously, no upper bound better than the trivial $2^n$ is known for MAX-NAE-$k$-SAT approximation on $k \ge 4$. For $δ= 0.9$ and $k = 4$, we achieve an upper bound of $1.947^n$. (3) A deterministic algorithm for MAX-NAE-$k$-SAT approximation. For $δ= 0.9$ and $k = 3$, we achieve an upper bound of $1.698^n$, which is better than the upper bound $1.731^n$ of the exact algorithm for MAX-NAE-$3$-SAT. Our finding sheds new light on the following question: Is NAE-$k$-SAT easier than $k$-SAT? The answer might be affirmative at least on solving the problems exactly and deterministically, while approximately solving MAX-NAE-$k$-SAT might be harder than MAX-$k$-SAT on $k \ge 4$.
Compact Optimization Algorithms with Re-sampled Inheritance
Venue: arXiv cs.AI 2019
Year: 2019

Compact optimization algorithms are a class of Estimation of Distribution Algorithms (EDAs) characterized by extremely limited memory requirements (hence they are called "compact"). As all EDAs, compact algorithms build and update a probabilistic model of the distribution of solutions within the search space, as opposed to population-based algorithms that instead make use of an explicit population of solutions. In addition to that, to keep their memory consumption low, compact algorithms purposely employ simple probabilistic models that can be described with a small number of parameters. Despite their simplicity, compact algorithms have shown good performances on a broad range of benchmark functions and real-world problems. However, compact algorithms also come with some drawbacks, i.e. they tend to premature convergence and show poorer performance on non-separable problems. To overcome these limitations, here we investigate a possible algorithmic scheme obtained by combining compact algorithms with a non-disruptive restart mechanism taken from the literature, named Re-Sampled Inheritance (RI). The resulting compact algorithms with RI are tested on the CEC 2014 benchmark functions. The numerical results show on the one hand that the use of RI consistently enhances the performances of compact algorithms, still keeping a limited usage of memory. On the other hand, our experiments show that among the tested algorithms, the best performance is obtained by compact Differential Evolution with RI.
Predicting citation counts based on deep neural network learning techniques
Venue: arXiv cs.DL 2019
Year: 2019

With the growing number of published scientific papers world-wide, the need to evaluation and quality assessment methods for research papers is increasing. Scientific fields such as scientometrics, informetrics and bibliometrics establish quantified analysis methods and measurements for scientific papers. In this area, an important problem is to predict the future influence of a published paper. Particularly, early discrimination between influential papers and insignificant papers may find important applications. In this regard, one of the most important metrics is the number of citations to the paper, since this metric is widely utilized in the evaluation of scientific publications and moreover, it serves as the basis for many other metrics such as h-index. In this paper, we propose a novel method for predicting long-term citations of a paper based on the number of its citations in the first few years after publication. In order to train a citations prediction model, we employed artificial neural networks which is a powerful machine learning tool with recently growing applications in many domains including image and text processing. The empirical experiments show that our proposed method out-performs state-of-the-art methods with respect to the prediction accuracy in both yearly and total prediction of the number of citations.
But How Does It Work in Theory? Linear SVM with Random Features
Venue: arXiv cs.LG 2019
Year: 2019

We prove that, under low noise assumptions, the support vector machine with $N\ll m$ random features (RFSVM) can achieve the learning rate faster than $O(1/\sqrt{m})$ on a training set with $m$ samples when an optimized feature map is used. Our work extends the previous fast rate analysis of random features method from least square loss to 0-1 loss. We also show that the reweighted feature selection method, which approximates the optimized feature map, helps improve the performance of RFSVM in experiments on a synthetic data set.
Frequency-Aware Model Predictive Control
Venue: arXiv cs.RO 2019
Year: 2019

Transferring solutions found by trajectory optimization to robotic hardware remains a challenging task. When the optimization fully exploits the provided model to perform dynamic tasks, the presence of unmodeled dynamics renders the motion infeasible on the real system. Model errors can be a result of model simplifications, but also naturally arise when deploying the robot in unstructured and nondeterministic environments. Predominantly, compliant contacts and actuator dynamics lead to bandwidth limitations. While classical control methods provide tools to synthesize controllers that are robust to a class of model errors, such a notion is missing in modern trajectory optimization, which is solved in the time domain. We propose frequency-shaped cost functions to achieve robust solutions in the context of optimal control for legged robots. Through simulation and hardware experiments we show that motion plans can be made compatible with bandwidth limits set by actuators and contact dynamics. The smoothness of the model predictive solutions can be continuously tuned without compromising the feasibility of the problem. Experiments with the quadrupedal robot ANYmal, which is driven by highly-compliant series elastic actuators, showed significantly improved tracking performance of the planned motion, torque, and force trajectories and enabled the machine to walk robustly on terrain with unmodeled compliance.
Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability
Venue: arXiv cs.LG 2019
Year: 2019

Algorithms are increasingly used to aid, or in some cases supplant, human decision-making, particularly for decisions that hinge on predictions. As a result, two additional features in addition to prediction quality have generated interest: (i) to facilitate human interaction and understanding with these algorithms, we desire prediction functions that are in some fashion simple or interpretable; and (ii) because they influence consequential decisions, we also want them to produce equitable allocations. We develop a formal model to explore the relationship between the demands of simplicity and equity. Although the two concepts appear to be motivated by qualitatively distinct goals, we show a fundamental inconsistency between them. Specifically, we formalize a general framework for producing simple prediction functions, and in this framework we establish two basic results. First, every simple prediction function is strictly improvable: there exists a more complex prediction function that is both strictly more efficient and also strictly more equitable. Put another way, using a simple prediction function both reduces utility for disadvantaged groups and reduces overall welfare relative to other options. Second, we show that simple prediction functions necessarily create incentives to use information about individuals' membership in a disadvantaged group --- incentives that weren't present before simplification, and that work against these individuals. Thus, simplicity transforms disadvantage into bias against the disadvantaged group. Our results are not only about algorithms but about any process that produces simple models, and as such they connect to the psychology of stereotypes and to an earlier economics literature on statistical discrimination.
The closed loop between opinion formation and personalised recommendations
Venue: arXiv cs.SI 2019
Year: 2019

In online platforms, recommender systems are responsible for directing users to relevant contents. In order to enhance the users' engagement, recommender systems adapt their output to the reactions of the users, who are in turn affected by the recommended contents. In this work, we study a tractable analytical model of a user that interacts with an online news aggregator, with the purpose of making explicit the feedback loop between the evolution of the user's opinion and the personalised recommendation of contents. More specifically, we assume that the user is endowed with a scalar opinion about a certain issue and seeks news about it on a news aggregator: this opinion is influenced by all received news, which are characterized by a binary position on the issue at hand. The user is affected by a confirmation bias, that is, a preference for news that confirm her current opinion. The news aggregator recommends items with the goal of maximizing the number of user's clicks (as a measure of her engagement): in order to fulfil its goal, the recommender has to compromise between exploring the user's preferences and exploiting what it has learned so far. After defining suitable metrics for the effectiveness of the recommender systems (such as the click-through rate) and for its impact on the opinion, we perform both extensive numerical simulations and a mathematical analysis of the model. We find that personalised recommendations markedly affect the evolution of opinions and favor the emergence of more extreme ones: the intensity of these effects is inherently related to the effectiveness of the recommender. We also show that by tuning the amount of randomness in the recommendation algorithm, one can seek a balance between the effectiveness of the recommendation system and its impact on the opinions.
Are object detection assessment criteria ready for maritime computer vision?
Venue: arXiv cs.CV 2019
Year: 2019

Maritime vessels equipped with visible and infrared cameras can complement other conventional sensors for object detection. However, application of computer vision techniques in maritime domain received attention only recently. The maritime environment offers its own unique requirements and challenges. Assessment of the quality of detections is a fundamental need in computer vision. However, the conventional assessment metrics suitable for usual object detection are deficient in the maritime setting. Thus, a large body of related work in computer vision appears inapplicable to the maritime setting at the first sight. We discuss the problem of defining assessment metrics suitable for maritime computer vision. We consider new bottom edge proximity metrics as assessment metrics for maritime computer vision. These metrics indicate that existing computer vision approaches are indeed promising for maritime computer vision and can play a foundational role in the emerging field of maritime computer vision.
Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies
Venue: arXiv cs.CR 2019
Year: 2019

Diffie-Hellman key exchange is at the foundations of public-key cryptography, but conventional group-based Diffie-Hellman is vulnerable to Shor's quantum algorithm. A range of "post-quantum Diffie-Hellman" protocols have been proposed to mitigate this threat, including the Couveignes, Rostovtsev-Stolbunov, SIDH, and CSIDH schemes, all based on the combinatorial and number-theoretic structures formed by isogenies of elliptic curves. Pre-and post-quantum Diffie-Hellman schemes resemble each other at the highest level, but the further down we dive, the more differences emerge-differences that are critical when we use Diffie-Hellman as a basic component in more complicated constructions. In this survey we compare and contrast pre-and post-quantum Diffie-Hellman algorithms, highlighting some important subtleties.
Gaussian Process Classification for Variable Fidelity Data
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we address a classification problem where two sources of labels with different levels of fidelity are available. Our approach is to combine data from both sources by applying a co-kriging schema on latent functions, which allows the model to account item-dependent labeling discrepancy. We provide an extension of Laplace inference for Gaussian process classification, that takes into account multi-fidelity data. We evaluate the proposed method on real and synthetic datasets and show that it is more resistant to different levels of discrepancy between sources than other approaches for data fusion. Our method can provide accuracy/cost trade-off for a number of practical tasks such as crowd-sourced data annotation and feasibility regions construction in engineering design.
Answering Science Exam Questions Using Query Rewriting with Background Knowledge
Venue: arXiv cs.AI 2019
Year: 2019

Open-domain question answering (QA) is an important problem in AI and NLP that is emerging as a bellwether for progress on the generalizability of AI methods and techniques. Much of the progress in open-domain QA systems has been realized through advances in information retrieval methods and corpus construction. In this paper, we focus on the recently introduced ARC Challenge dataset, which contains 2,590 multiple choice questions authored for grade-school science exams. These questions are selected to be the most challenging for current QA systems, and current state of the art performance is only slightly better than random chance. We present a system that rewrites a given question into queries that are used to retrieve supporting text from a large corpus of science-related text. Our rewriter is able to incorporate background knowledge from ConceptNet and -- in tandem with a generic textual entailment system trained on SciTail that identifies support in the retrieved results -- outperforms several strong baselines on the end-to-end QA task despite only being trained to identify essential terms in the original source question. We use a generalizable decision methodology over the retrieved evidence and answer candidates to select the best answer. By combining query rewriting, background knowledge, and textual entailment our system is able to outperform several strong baselines on the ARC dataset.
I/O Workload Management for All-Flash Datacenter Storage Systems Based on Total Cost of Ownership
Venue: arXiv cs.PF 2019
Year: 2019

Recently, the capital expenditure of flash-based Solid State Driver (SSDs) keeps declining and the storage capacity of SSDs keeps increasing. As a result, all-flash storage systems have started to become more economically viable for large shared storage installations in datacenters, where metrics like Total Cost of Ownership (TCO) are of paramount importance. On the other hand, flash devices suffer from write amplification, which, if unaccounted, can substantially increase the TCO of a storage system. In this paper, we first develop a TCO model for datacenter all-flash storage systems, and then plug a Write Amplification model (WAF) of NVMe SSDs we build based on empirical data into this TCO model. Our new WAF model accounts for workload characteristics like write rate and percentage of sequential writes. Furthermore, using both the TCO and WAF models as the optimization criterion, we design new flash resource management schemes (MINTCO) to guide datacenter managers to make workload allocation decisions under the consideration of TCO for SSDs. Based on that, we also develop MINTCO-RAID to support RAID SSDs and MINTCO-OFFLINE to optimize the offline workload-disk deployment problem during the initialization phase. Experimental results show that MINTCO can reduce the TCO and keep relatively high throughput and space utilization of the entire datacenter storage resources.