OpenRaiser/Intern-Atlas huggingface dataset:
Using Variable Dwell Time to Accelerate Gaze-Based Web Browsing with Two-Step Selection
Venue: arXiv cs.HC 2022
Year: 2022

In order to avoid the "Midas Touch" problem, gaze-based interfaces for selection often introduce a dwell time: a fixed amount of time the user must fixate upon an object before it is selected. Past interfaces have used a uniform dwell time across all objects. Here, we propose a gaze-based browser using a two-step selection policy with variable dwell time. In the first step, a command, e.g. "back" or "select", is chosen from a menu using a dwell time that is constant across the different commands. In the second step, if the "select" command is chosen, the user selects a hyperlink using a dwell time that varies between different hyperlinks. We assign shorter dwell times to more likely hyperlinks and longer dwell times to less likely hyperlinks. In order to infer the likelihood each hyperlink will be selected, we have developed a probabilistic model of natural gaze behavior while surfing the web. We have evaluated a number of heuristic and probabilistic methods for varying the dwell times using both simulation and experiment. Our results demonstrate that varying dwell time improves the user experience in comparison with fixed dwell time, resulting in fewer errors and increased speed. While all of the methods for varying dwell time resulted in improved performance, the probabilistic models yielded much greater gains than the simple heuristics. The best performing model reduces error rate by 50% compared to 100ms uniform dwell time while maintaining a similar response time. It reduces response time by 60% compared to 300ms uniform dwell time while maintaining a similar error rate.
Two Algorithms for Deciding Coincidence In Double Temporal Recurrence of Eventuality Sequences
Venue: arXiv cs.AI 2022
Year: 2022

Let two sequences of eventualities x (signifying the sequence, x0,x1, x2,...,xn-1) and y (signifying the sequence, y0, y1, y2,..,yn-1) both recur over the same time interval and it is required to determine whether or not a subinterval exists within the said interval which is a common subinterval of the intervals of occurrence of xp and yq. This paper presents two algorithms for solving the problem. the first explores an arbitrary cycle of the double recurrence for the existence of such an interval. its worst case running time is quadratic. The other algorithm is based on the novel notion of gcd-partitions and has a linear worst case running time. If the eventuality sequence pair (W,z) is a gcd-partition for the double recurrence (x, y),then, from a certain property of gcd-partitions, within any cycle of the double recurrence, there exists r and s such that intervals of occurrence of xp and yq are non-disjoint with the interval of co-occurrence of wr and zs. As such, a coincidence between xp and yq occurs within a cycle of the double recurrence if and only if such r and s exist so that the interval of co-occurrence of wr and zs shares a common interval with the common interval of occurrences of xp and yq. The algorithm systematically reduces the number of wr and zs pairs to be explored in the process of finding the existence of the coincidence.
Optimal Auctions through Deep Learning: Advances in Differentiable Economics
Venue: arXiv cs.GT 2022
Year: 2022

Designing an incentive compatible auction that maximizes expected revenue is an intricate task. The single-item case was resolved in a seminal piece of work by Myerson in 1981, but more than 40 years later a full analytical understanding of the optimal design still remains elusive for settings with two or more items. In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal auctions. We model an auction as a multi-layer neural network, frame optimal auction design as a constrained learning problem, and show how it can be solved using standard machine learning pipelines. In addition to providing generalization bounds, we present extensive experimental results, recovering essentially all known solutions that come from the theoretical analysis of optimal auction design problems and obtaining novel mechanisms for settings in which the optimal mechanism is unknown.
Solving multivariate polynomial systems and an invariant from commutative algebra
Venue: arXiv cs.CR 2022
Year: 2022

The complexity of computing the solutions of a system of multivariate polynomial equations by means of Groebner bases computations is upper bounded by a function of the solving degree. In this paper, we discuss how to rigorously estimate the solving degree of a system, focusing on systems arising within public-key cryptography. In particular, we show that it is upper bounded by, and often equal to, the Castelnuovo-Mumford regularity of the ideal generated by the homogenization of the equations of the system, or by the equations themselves in case they are homogeneous. We discuss the underlying commutative algebra and clarify under which assumptions the commonly used results hold. In particular, we discuss the assumption of being in generic coordinates (often required for bounds obtained following this type of approach) and prove that systems that contain the field equations or their fake Weil descent are in generic coordinates. We also compare the notion of solving degree with that of degree of regularity, which is commonly used in the literature. We complement the paper with some examples of bounds obtained following the strategy that we describe.
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
Venue: arXiv cs.DS 2022
Year: 2022

Given a directed graph $G$ and a list $(s_1,t_1),\dots,(s_d,t_d)$ of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of $G$ that contains a directed $s_i\to t_i$ path for every $1\le i \le k$. The special case Directed Steiner Tree (when we ask for paths from a root $r$ to terminals $t_1,\dots,t_d$) is known to be fixed-parameter tractable parameterized by the number of terminals, while the special case Strongly Connected Steiner Subgraph (when we ask for a path from every $t_i$ to every other $t_j$) is known to be W[1]-hard. We systematically explore the complexity landscape of directed Steiner problems to fully understand which other special cases are FPT or W[1]-hard. Formally, if $\mathcal{H}$ is a class of directed graphs, then we look at the special case of Directed Steiner Network where the list $(s_1,t_1),\dots,(s_d,t_d)$ of requests form a directed graph that is a member of $\mathcal{H}$. Our main result is a complete characterization of the classes $\mathcal{H}$ resulting in fixed-parameter tractable special cases: we show that if every pattern in $\mathcal{H}$ has the combinatorial property of being "transitively equivalent to a bounded-length caterpillar with a bounded number of extra edges," then the problem is FPT, and it is W[1]-hard for every recursively enumerable $\mathcal{H}$ not having this property. This complete dichotomy unifies and generalizes the known results showing that Directed Steiner Tree is FPT [Dreyfus and Wagner, Networks 1971], $q$-Root Steiner Tree is FPT for constant $q$ [Suchý, WG 2016], Strongly Connected Steiner Subgraph is W[1]-hard [Guo et al., SIAM J. Discrete Math. 2011], and Directed Steiner Network is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl, SIAM J. Comput. 2006], and moreover reveals a large continent of tractable cases that were not known before.
Behavior Trees in Robotics and AI: An Introduction
Venue: arXiv cs.RO 2022
Year: 2022

A Behavior Tree (BT) is a way to structure the switching between different tasks in an autonomous agent, such as a robot or a virtual entity in a computer game. BTs are a very efficient way of creating complex systems that are both modular and reactive. These properties are crucial in many applications, which has led to the spread of BT from computer game programming to many branches of AI and Robotics. In this book, we will first give an introduction to BTs, then we describe how BTs relate to, and in many cases generalize, earlier switching structures. These ideas are then used as a foundation for a set of efficient and easy to use design principles. Properties such as safety, robustness, and efficiency are important for an autonomous system, and we describe a set of tools for formally analyzing these using a state space description of BTs. With the new analysis tools, we can formalize the descriptions of how BTs generalize earlier approaches. We also show the use of BTs in automated planning and machine learning. Finally, we describe an extended set of tools to capture the behavior of Stochastic BTs, where the outcomes of actions are described by probabilities. These tools enable the computation of both success probabilities and time to completion.
How to Train a CAT: Learning Canonical Appearance Transformations for Direct Visual Localization Under Illumination Change
Venue: arXiv cs.RO 2022
Year: 2022

Direct visual localization has recently enjoyed a resurgence in popularity with the increasing availability of cheap mobile computing power. The competitive accuracy and robustness of these algorithms compared to state-of-the-art feature-based methods, as well as their natural ability to yield dense maps, makes them an appealing choice for a variety of mobile robotics applications. However, direct methods remain brittle in the face of appearance change due to their underlying assumption of photometric consistency, which is commonly violated in practice. In this paper, we propose to mitigate this problem by training deep convolutional encoder-decoder models to transform images of a scene such that they correspond to a previously-seen canonical appearance. We validate our method in multiple environments and illumination conditions using high-fidelity synthetic RGB-D datasets, and integrate the trained models into a direct visual localization pipeline, yielding improvements in visual odometry (VO) accuracy through time-varying illumination conditions, as well as improved metric relocalization performance under illumination change, where conventional methods normally fail. We further provide a preliminary investigation of transfer learning from synthetic to real environments in a localization context. An open-source implementation of our method using PyTorch is available at https://github.com/utiasSTARS/cat-net.
DPC-Net: Deep Pose Correction for Visual Localization
Venue: arXiv cs.CV 2022
Year: 2022

We present a novel method to fuse the power of deep networks with the computational efficiency of geometric and probabilistic localization algorithms. In contrast to other methods that completely replace a classical visual estimator with a deep network, we propose an approach that uses a convolutional neural network to learn difficult-to-model corrections to the estimator from ground-truth training data. To this end, we derive a novel loss function for learning SE(3) corrections based on a matrix Lie groups approach, with a natural formulation for balancing translation and rotation errors. We use this loss to train a Deep Pose Correction network (DPC-Net) that predicts corrections for a particular estimator, sensor and environment. Using the KITTI odometry dataset, we demonstrate significant improvements to the accuracy of a computationally-efficient sparse stereo visual odometry pipeline, that render it as accurate as a modern computationally-intensive dense estimator. Further, we show how DPC-Net can be used to mitigate the effect of poorly calibrated lens distortion parameters.
Redesigning Bitcoin's fee market
Venue: arXiv cs.CR 2022
Year: 2022

The Bitcoin payment system involves two agent types: Users that transact with the currency and pay fees and miners in charge of authorizing transactions and securing the system in return for these fees. Two of Bitcoin's challenges are (i) securing sufficient miner revenues as block rewards decrease, and (ii) alleviating the throughput limitation due to a small maximal block size cap. These issues are strongly related as increasing the maximal block size may decrease revenue due to Bitcoin's pay-your-bid approach. To decouple them, we analyze the "monopolistic auction", showing: (i) its revenue does not decrease as the maximal block size increases, (ii) it is resilient to an untrusted auctioneer (the miner), and (iii) simplicity for transaction issuers (bidders), as the average gain from strategic bid shading (relative to bidding one's value) diminishes as the number of bids increases.
A Benchmark Environment Motivated by Industrial Control Problems
Venue: arXiv cs.AI 2022
Year: 2022

In the research area of reinforcement learning (RL), frequently novel and promising methods are developed and introduced to the RL community. However, although many researchers are keen to apply their methods on real-world problems, implementing such methods in real industry environments often is a frustrating and tedious process. Generally, academic research groups have only limited access to real industrial data and applications. For this reason, new methods are usually developed, evaluated and compared by using artificial software benchmarks. On one hand, these benchmarks are designed to provide interpretable RL training scenarios and detailed insight into the learning process of the method on hand. On the other hand, they usually do not share much similarity with industrial real-world applications. For this reason we used our industry experience to design a benchmark which bridges the gap between freely available, documented, and motivated artificial benchmarks and properties of real industrial problems. The resulting industrial benchmark (IB) has been made publicly available to the RL community by publishing its Java and Python code, including an OpenAI Gym wrapper, on Github. In this paper we motivate and describe in detail the IB's dynamics and identify prototypic experimental settings that capture common situations in real-world industry control problems.
Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes under Bit-wise Noise
Venue: arXiv cs.NE 2022
Year: 2022

In many real-world optimization problems, the objective function evaluation is subject to noise, and we cannot obtain the exact objective value. Evolutionary algorithms (EAs), a type of general-purpose randomized optimization algorithm, have been shown to be able to solve noisy optimization problems well. However, previous theoretical analyses of EAs mainly focused on noise-free optimization, which makes the theoretical understanding largely insufficient for the noisy case. Meanwhile, the few existing theoretical studies under noise often considered the one-bit noise model, which flips a randomly chosen bit of a solution before evaluation; while in many realistic applications, several bits of a solution can be changed simultaneously. In this paper, we study a natural extension of one-bit noise, the bit-wise noise model, which independently flips each bit of a solution with some probability. We analyze the running time of the (1+1)-EA solving OneMax and LeadingOnes under bit-wise noise for the first time, and derive the ranges of the noise level for polynomial and super-polynomial running time bounds. The analysis on LeadingOnes under bit-wise noise can be easily transferred to one-bit noise, and improves the previously known results. Since our analysis discloses that the (1+1)-EA can be efficient only under low noise levels, we also study whether the sampling strategy can bring robustness to noise. We prove that using sampling can significantly increase the largest noise level allowing a polynomial running time, that is, sampling is robust to noise.
Sequence Pairs with Lowest Combined Autocorrelation and Crosscorrelation
Venue: arXiv cs.IT 2022
Year: 2022

Pursley and Sarwate established a lower bound on a combined measure of autocorrelation and crosscorrelation for a pair $(f,g)$ of binary sequences (i.e., sequences with terms in $\{-1,1\}$). If $f$ is a nonzero sequence, then its autocorrelation demerit factor, $\text{ADF}(f)$, is the sum of the squared magnitudes of the aperiodic autocorrelation values over all nonzero shifts for the sequence obtained by normalizing $f$ to have unit Euclidean norm. If $(f,g)$ is a pair of nonzero sequences, then their crosscorrelation demerit factor, $\text{CDF}(f,g)$, is the sum of the squared magnitudes of the aperiodic crosscorrelation values over all shifts for the sequences obtained by normalizing both $f$ and $g$ to have unit Euclidean norm. Pursley and Sarwate showed that for binary sequences, the sum of $\text{CDF}(f,g)$ and the geometric mean of $\text{ADF}(f)$ and $\text{ADF}{(g)}$ must be at least $1$. For randomly selected pairs of long binary sequences, this quantity is typically around $2$. In this paper, we show that Pursley and Sarwate's bound is met for binary sequences precisely when $(f,g)$ is a Golay complementary pair. We also prove a generalization of this result for sequences whose terms are arbitrary complex numbers. We investigate constructions that produce infinite families of Golay complementary pairs, and compute the asymptotic values of autocorrelation and crosscorrelation demerit factors for such families.
CGAlgebra: a Mathematica package for conformal geometric algebra. v.2.0
Venue: arXiv cs.MS 2022
Year: 2022

A tutorial of the Mathematica package CGAlgebra, for conformal geometric algebra calculations is presented. Using rule-based programming, the 5-dimensional conformal geometric algebra is implemented and defined functions simplify the calculations of geometric, outer and inner products, as well as many other calculations related with geometric transformations. CGAlgebra is available from https://github.com/jlaragonvera/Geometric-Algebra
AI2-THOR: An Interactive 3D Environment for Visual AI
Venue: arXiv cs.CV 2022
Year: 2022

We introduce The House Of inteRactions (THOR), a framework for visual AI research, available at http://ai2thor.allenai.org. AI2-THOR consists of near photo-realistic 3D indoor scenes, where AI agents can navigate in the scenes and interact with objects to perform tasks. AI2-THOR enables research in many different domains including but not limited to deep reinforcement learning, imitation learning, learning by interaction, planning, visual question answering, unsupervised representation learning, object detection and segmentation, and learning models of cognition. The goal of AI2-THOR is to facilitate building visually intelligent models and push the research forward in this domain.
ZOOpt: Toolbox for Derivative-Free Optimization
Venue: arXiv cs.LG 2022
Year: 2022

Recent advances in derivative-free optimization allow efficient approximation of the global-optimal solutions of sophisticated functions, such as functions with many local optima, non-differentiable and non-continuous functions. This article describes the ZOOpt (Zeroth Order Optimization) toolbox that provides efficient derivative-free solvers and is designed easy to use. ZOOpt provides single-machine parallel optimization on the basis of python core and multi-machine distributed optimization for time-consuming tasks by incorporating with the Ray framework -- a famous platform for building distributed applications. ZOOpt particularly focuses on optimization problems in machine learning, addressing high-dimensional and noisy problems such as hyper-parameter tuning and direct policy search. The toolbox is maintained toward a ready-to-use tool in real-world machine learning tasks.
Trends in Processor Architecture
Venue: arXiv cs.AR 2022
Year: 2022

This paper presents an overview of the main trends in processor architecture. It starts with an analysis of the past evolution of processors and the main driving forces behind it, and then it focuses on a description of the main architectural features of current processors. Finally, it presents a discussion on some promising directions for future evolution of processor architectures.
ASMCNN: An Efficient Brain Extraction Using Active Shape Model and Convolutional Neural Networks
Venue: arXiv cs.CV 2022
Year: 2022

Brain extraction (skull stripping) is a challenging problem in neuroimaging. It is due to the variability in conditions from data acquisition or abnormalities in images, making brain morphology and intensity characteristics changeable and complicated. In this paper, we propose an algorithm for skull stripping in Magnetic Resonance Imaging (MRI) scans, namely ASMCNN, by combining the Active Shape Model (ASM) and Convolutional Neural Network (CNN) for taking full of their advantages to achieve remarkable results. Instead of working with 3D structures, we process 2D image sequences in the sagittal plane. First, we divide images into different groups such that, in each group, shapes and structures of brain boundaries have similar appearances. Second, a modified version of ASM is used to detect brain boundaries by utilizing prior knowledge of each group. Finally, CNN and post-processing methods, including Conditional Random Field (CRF), Gaussian processes, and several special rules are applied to refine the segmentation contours. Experimental results show that our proposed method outperforms current state-of-the-art algorithms by a significant margin in all experiments.
Effects of Jamming Attacks on Wireless Networked Control Systems Under Disturbance
Venue: arXiv cs.SY 2022
Year: 2022

Jamming attacks on wireless networked control systems are investigated for the scenarios where the system dynamics face exogenous disturbance. In particular, the control input packets are assumed to be transmitted from a controller to a remotely located linear plant over an insecure wireless communication channel that is subject to jamming attacks. The time-varying likelihood of transmission failures on this channel depends on the power of the jamming interference signal emitted by an attacker. We show that jamming attacks can prevent stability when the system faces disturbance, even if the attacked system without disturbance is stable. We also show that stability under jamming and disturbance can be achieved if the average jamming interference power is restricted in a certain way that we characterize in the paper. We illustrate our results on an example networked control system with a fading wireless channel, where the outage probability is affected by jamming attacks.
On Integer Programming, Discrepancy, and Convolution
Venue: arXiv cs.DS 2022
Year: 2022

Integer programs with m constraints are solvable in pseudo-polynomial time in $Δ$, the largest coefficient in a constraint, when m is a fixed constant. We give a new algorithm with a running time of $O(\sqrt{m}Δ)^{2m} + O(nm)$, which improves on the state-of-the-art. Moreover, we show that improving on our algorithm for any $m$ is equivalent to improving over the quadratic time algorithm for $(\min,~+)$-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a specialized algorithm with running time $O(\sqrt{m} Δ)^{(1 + o(1))m} + O(nm)$ for testing feasibility of an integer program and also give a tight lower bound, which is based on the SETH in this case.
Development of formal models, algorithms, procedures, engineering and functioning of the software system "Instrumental complex for ontological engineering purpose"
Venue: arXiv cs.SE 2022
Year: 2022

The given paper considered a generalized model representation of the software system "Instrumental complex for ontological engineering purpose". Represented complete software system development process. Developed relevant formal models of the software system "Instrumental complex for ontological engineering purpose", represented as mathematical expressions, UML diagrams, and also described the three-tier architecture of the software system "Instrumental complex for ontological engineering purpose" in a client-server environment.