OpenRaiser/Intern-Atlas huggingface dataset:
The Potential of Using Google Expeditions and Google Lens Tools under STEM-education in Ukraine
Venue: arXiv cs.CY 2021
Year: 2021

The expediency of using the augmented reality in the case of using of STEM-education in Ukraine is shown. The features of the augmented reality and its classification are described. The possibilities of using the Google Expeditions and Google Lens as platforms of the augmented reality is analyzed. A comparison, analysis, synthesis, induction and deduction was carried out to study the potential of using augmented reality platforms in the educational process. Main haracteristics of Google Expeditions and Google Lens are described. There determined that augmented reality tools can improve students motivation to learn and correspond to trends of STEM-education. However, there problems of using of augmented reality platforms, such as the lack of awareness of this system by teachers, the lack of guidance, the absence of the Ukrainian-language interface and responding of educational programs of the Ministry of Education and Science of Ukraine. There proposed to involve methodical and pedagogical specialists to development of methodical provision of the tools of augmented reality.
Graph connectivity in log steps using label propagation
Venue: arXiv cs.DS 2021
Year: 2021

The fastest deterministic algorithms for connected components take logarithmic time and perform superlinear work on a Parallel Random Access Machine (PRAM). These algorithms maintain a spanning forest by merging and compressing trees, which requires pointer-chasing operations that increase memory access latency and are limited to shared-memory systems. Many of these PRAM algorithms are also very complicated to implement. Another popular method is "leader-contraction" where the challenge is to select a constant fraction of leaders that are adjacent to a constant fraction of non-leaders with high probability. Instead we investigate label propagation because it is deterministic and does not rely on pointer-chasing. Label propagation exchanges representative labels within a component using simple graph traversal, but it is inherently difficult to complete in a sublinear number of steps. We are able to solve the problems with label propagation for graph connectivity. We introduce a surprisingly simple framework for deterministic graph connectivity using label propagation that is easily adaptable to many computational models. It propagates directed edges and alternates edge direction to achieve linear edge count each step and sublinear convergence. We present new algorithms in PRAM, Stream, and MapReduce for a simple, undirected graph $G=(V,E)$ with $n=|V|$ vertices, $m=|E|$ edges. Our approach takes $O(m)$ work each step, but we can only prove logarithmic convergence on a path graph. It was conjectured by Liu and Tarjan (2019) to take $O(\log n)$ steps or possibly $O(\log^2 n)$ steps. We leave the proof of convergence as an open problem.
Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching
Venue: arXiv cs.LG 2021
Year: 2021

Graph similarity computation is one of the core operations in many graph-based applications, such as graph similarity search, graph database analysis, graph clustering, etc. Since computing the exact distance/similarity between two graphs is typically NP-hard, a series of approximate methods have been proposed with a trade-off between accuracy and speed. Recently, several data-driven approaches based on neural networks have been proposed, most of which model the graph-graph similarity as the inner product of their graph-level representations, with different techniques proposed for generating one embedding per graph. However, using one fixed-dimensional embedding per graph may fail to fully capture graphs in varying sizes and link structures, a limitation that is especially problematic for the task of graph similarity computation, where the goal is to find the fine-grained difference between two graphs. In this paper, we address the problem of graph similarity computation from another perspective, by directly matching two sets of node embeddings without the need to use fixed-dimensional vectors to represent whole graphs for their similarity computation. The model, GraphSim, achieves the state-of-the-art performance on four real-world graph datasets under six out of eight settings (here we count a specific dataset and metric combination as one setting), compared to existing popular methods for approximate Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) computation.
Driving Skill Modeling Using Neural Networks for Performance-based Haptic Assistance
Venue: arXiv cs.HC 2021
Year: 2021

This paper addresses a data-driven framework, modeling expert driving skills for performance-based haptic assistance using neural networks (NNs). We have built a haptic driving training simulator to collect expert driving data and to provide proper haptic feedback. We establish an expert driving skill model by training NNs with the collected data. Then, the skill model is applied to performance-based haptic assistance to provide optimized references of the steering/pedaling movements. We evaluate the skill model and its application to performance-based haptic assistance in two user experiments. The results of the first experiment demonstrate that our skill model has appropriately captured experts' steering/pedaling skills. The results of the second experiment show that our performance-based haptic assistance can help novice drivers perform steering as expert drivers, but cannot assist their pedaling performance.
Encoding two-dimensional range top-k queries
Venue: arXiv cs.DS 2021
Year: 2021

We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering \topk{} queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For an $m \times n$ array, with $m \le n$, we first propose an encoding for answering 1-sided \topk{} queries, whose query range is restricted to $[1 \dots m][1 \dots a]$, for $1 \le a \le n$. Next, we propose an encoding for answering for the general (4-sided) \topk{} queries that takes $(m\lg{(k+1)n \choose n}+2nm(m-1)+o(n))$ bits, which generalizes the \textit{joint Cartesian tree} of Golin et al. [TCS 2016]. Compared with trivial $O(nm\lg{n})$-bit encoding, our encoding takes less space when $m = o(\lg{n})$. In addition to the upper bound results for the encodings, we also give lower bounds on encodings for answering $1$ and $4$-sided \topk{} queries, which show that our upper bound results are almost optimal.
Stair Climbing Stabilization of the HRP-4 Humanoid Robot using Whole-body Admittance Control
Venue: arXiv cs.RO 2021
Year: 2021

We consider dynamic stair climbing with the HRP-4 humanoid robot as part of an Airbus manufacturing use-case demonstrator. We share experimental knowledge gathered so as to achieve this task, which HRP-4 had never been challenged to before. In particular, we extend walkingstabilization based on linear inverted pendulum tracking by quadratic programming-based wrench distribution and a whole-body admittance controller that applies both end-effector and CoM strategies. While existing stabilizers tend to use either one or the other, our experience suggests that the combination of these two approaches improves tracking performance. We demonstrate this solution in an on-site experiment where HRP-4 climbs an industrial staircase with 18.5 cm high steps, and release our walking controller as open source software.
Simulator Predictive Control: Using Learned Task Representations and MPC for Zero-Shot Generalization and Sequencing
Venue: arXiv cs.RO 2021
Year: 2021

Simulation-to-real transfer is an important strategy for making reinforcement learning practical with real robots. Successful sim-to-real transfer systems have difficulty producing policies which generalize across tasks, despite training for thousands of hours equivalent real robot time. To address this shortcoming, we present a novel approach to efficiently learning new robotic skills directly on a real robot, based on model-predictive control (MPC) and an algorithm for learning task representations. In short, we show how to reuse the simulation from the pre-training step of sim-to-real methods as a tool for foresight, allowing the sim-to-real policy adapt to unseen tasks. Rather than end-to-end learning policies for single tasks and attempting to transfer them, we first use simulation to simultaneously learn (1) a continuous parameterization (i.e. a skill embedding or latent) of task-appropriate primitive skills, and (2) a single policy for these skills which is conditioned on this representation. We then directly transfer our multi-skill policy to a real robot, and actuate the robot by choosing sequences of skill latents which actuate the policy, with each latent corresponding to a pre-learned primitive skill controller. We complete unseen tasks by choosing new sequences of skill latents to control the robot using MPC, where our MPC model is composed of the pre-trained skill policy executed in the simulation environment, run in parallel with the real robot. We discuss the background and principles of our method, detail its practical implementation, and evaluate its performance by using our method to train a real Sawyer Robot to achieve motion tasks such as drawing and block pushing.
Rethinking Breiman's Dilemma in Neural Networks: Phase Transitions of Margin Dynamics
Venue: arXiv cs.LG 2021
Year: 2021

Margin enlargement over training data has been an important strategy since perceptrons in machine learning for the purpose of boosting the robustness of classifiers toward a good generalization ability. Yet Breiman (1999) showed a dilemma that a uniform improvement on margin distribution does NOT necessarily reduces generalization errors. In this paper, we revisit Breiman's dilemma in deep neural networks with recently proposed spectrally normalized margins, from a novel perspective based on phase transitions of normalized margin distributions in training dynamics. Normalized margin distribution of a classifier over the data, can be divided into two parts: low/small margins such as some negative margins for misclassified samples vs. high/large margins for high confident correctly classified samples, that often behave differently during the training process. Low margins for training and test datasets are often effectively reduced in training, along with reductions of training and test errors; while high margins may exhibit different dynamics, reflecting the trade-off between expressive power of models and complexity of data. When data complexity is comparable to the model expressiveness, high margin distributions for both training and test data undergo similar decrease-increase phase transitions during training. In such cases, one can predict the trend of generalization or test error by margin-based generalization bounds with restricted Rademacher complexities, shown in two ways in this paper with early stopping time exploiting such phase transitions. On the other hand, over-expressive models may have both low and high training margins undergoing uniform improvements, with a distinct phase transition in test margin dynamics. This reconfirms the Breiman's dilemma associated with overparameterized neural networks where margins fail to predict overfitting.
Mobility Offer Allocations in Corporate Settings
Venue: arXiv cs.AI 2021
Year: 2021

Corporate mobility is often based on a fixed assignment of vehicles to employees. Relaxing this fixation and including alternatives such as public transportation or taxis for business and private trips could increase fleet utilization and foster the use of battery electric vehicles. We introduce the mobility offer allocation problem as the core concept of a flexible booking system for corporate mobility. The problem is equivalent to interval scheduling on dedicated unrelated parallel machines. We show that the problem is NP-hard to approximate within any factor. We describe problem specific conflict graphs for representing and exploring the structure of feasible solutions. A characterization of all maximum cliques in these conflict graphs reveals symmetries which allow to formulate stronger integer linear programming models. We also present an adaptive large neighborhood search based approach which makes use of conflict graphs as well. In a computational study, the approaches are evaluated. It was found that greedy heuristics perform best if very tight run-time requirements are given, a solver for the integer linear programming model performs best on small and medium instances, and the adaptive large neighborhood search performs best on large instances.
PILAE: A Non-gradient Descent Learning Scheme for Deep Feedforward Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

In this work, a non-gradient descent learning (NGDL) scheme was proposed for deep feedforward neural networks (DNN). It is known that an autoencoder can be used as the building blocks of the multi-layer perceptron (MLP) DNN, the MLP is taken as an example to illustrate the proposed scheme of pseudoinverse learning algorithm for autoencoder (PILAE) in this paper. The PILAE with low rank approximation is a NGDL algorithm, and the encoder weight matrix is set to be the low rank approximation of the pseudoinverse of the input matrix, while the decoder weight matrix is calculated by the pseudoinverse learning algorithm. It is worth to note that only very few network structure hyper-parameters need to be tuned compared with classical gradient descent learning algorithm. Hence, the proposed algorithm could be regarded as a quasi-automated training algorithm which could be utilized in automated machine learning field. The experimental results show that the proposed learning scheme for DNN could achieve better performance on considering the tradeoff between training efficiency and classification accuracy.
Structured Neural Summarization
Venue: arXiv cs.LG 2021
Year: 2021

Summarization of long sequences into a concise statement is a core problem in natural language processing, requiring non-trivial understanding of the input. Based on the promising results of graph neural networks on highly structured data, we develop a framework to extend existing sequence encoders with a graph component that can reason about long-distance relationships in weakly structured data such as text. In an extensive evaluation, we show that the resulting hybrid sequence-graph models outperform both pure sequence models as well as pure graph models on a range of summarization tasks.
Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution
Venue: arXiv cs.DS 2021
Year: 2021

A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: Given a sequence of random variables $X_1,\dots,X_n$ drawn independently from a distribution $F$, the goal is to choose a stopping time $τ$ so as to maximize $α$ such that for all distributions $F$ we have $\mathbb{E}[X_τ] \geq α\cdot \mathbb{E}[\max_tX_t]$. What makes this problem challenging is that the decision whether $τ=t$ may only depend on the values of the random variables $X_1,\dots,X_t$ and on the distribution $F$. For quite some time the best known bound for the problem was $α\geq1-1/e\approx0.632$ [Hill and Kertz, 1982]. Only recently this bound was improved by Abolhassani et al. [2017], and a tight bound of $α\approx0.745$ was obtained by Correa et al. [2017]. The case where $F$ is unknown, such that the decision whether $τ=t$ may depend only on the values of the first $t$ random variables but not on $F$, is equally well motivated (e.g., [Azar et al., 2014]) but has received much less attention. A straightforward guarantee for this case of $α\geq1/e\approx0.368$ can be derived from the solution to the secretary problem. Our main result is that this bound is tight. Motivated by this impossibility result we investigate the case where the stopping time may additionally depend on a limited number of samples from~$F$. An extension of our main result shows that even with $o(n)$ samples $α\leq 1/e$, so that the interesting case is the one with $Ω(n)$ samples. Here we show that $n$ samples allow for a significant improvement over the secretary problem, while $O(n^2)$ samples are equivalent to knowledge of the distribution: specifically, with $n$ samples $α\geq1-1/e\approx0.632$ and $α\leq\ln(2)\approx0.693$, and with $O(n^2)$ samples $α\geq0.745-ε$ for any $ε>0$.
Context-Dependent Upper-Confidence Bounds for Directed Exploration
Venue: arXiv cs.LG 2021
Year: 2021

Directed exploration strategies for reinforcement learning are critical for learning an optimal policy in a minimal number of interactions with the environment. Many algorithms use optimism to direct exploration, either through visitation estimates or upper confidence bounds, as opposed to data-inefficient strategies like ε-greedy that use random, undirected exploration. Most data-efficient exploration methods require significant computation, typically relying on a learned model to guide exploration. Least-squares methods have the potential to provide some of the data-efficiency benefits of model-based approaches -- because they summarize past interactions -- with the computation closer to that of model-free approaches. In this work, we provide a novel, computationally efficient, incremental exploration strategy, leveraging this property of least-squares temporal difference learning (LSTD). We derive upper confidence bounds on the action-values learned by LSTD, with context-dependent (or state-dependent) noise variance. Such context-dependent noise focuses exploration on a subset of variable states, and allows for reduced exploration in other states. We empirically demonstrate that our algorithm can converge more quickly than other incremental exploration strategies using confidence estimates on action-values.
The Graph-Based Behavior-Aware Recommendation for Interactive News
Venue: arXiv cs.IR 2021
Year: 2021

Interactive news recommendation has been launched and attracted much attention recently. In this scenario, user's behavior evolves from single click behavior to multiple behaviors including like, comment, share etc. However, most of the existing methods still use single click behavior as the unique criterion of judging user's preferences. Further, although heterogeneous graphs have been applied in different areas, a proper way to construct a heterogeneous graph for interactive news data with an appropriate learning mechanism on it is still desired. To address the above concerns, we propose a graph-based behavior-aware network, which simultaneously considers six different types of behaviors as well as user's demand on the news diversity. We have three main steps. First, we build an interaction behavior graph for multi-level and multi-category data. Second, we apply DeepWalk on the behavior graph to obtain entity semantics, then build a graph-based convolutional neural network called G-CNN to learn news representations, and an attention-based LSTM to learn behavior sequence representations. Third, we introduce core and coritivity features for the behavior graph, which measure the concentration degree of user's interests. These features affect the trade-off between accuracy and diversity of our personalized recommendation system. Taking these features into account, our system finally achieves recommending news to different users at their different levels of concentration degrees.
GPSfM: Global Projective SFM Using Algebraic Constraints on Multi-View Fundamental Matrices
Venue: arXiv cs.CV 2021
Year: 2021

This paper addresses the problem of recovering projective camera matrices from collections of fundamental matrices in multiview settings. We make two main contributions. First, given ${n \choose 2}$ fundamental matrices computed for $n$ images, we provide a complete algebraic characterization in the form of conditions that are both necessary and sufficient to enabling the recovery of camera matrices. These conditions are based on arranging the fundamental matrices as blocks in a single matrix, called the $n$-view fundamental matrix, and characterizing this matrix in terms of the signs of its eigenvalues and rank structures. Secondly, we propose a concrete algorithm for projective structure-from-motion that utilizes this characterization. Given a complete or partial collection of measured fundamental matrices, our method seeks camera matrices that minimize a global algebraic error for the measured fundamental matrices. In contrast to existing methods, our optimization, without any initialization, produces a consistent set of fundamental matrices that corresponds to a unique set of cameras (up to a choice of projective frame). Our experiments indicate that our method achieves state of the art performance in both accuracy and running time.
Deep Learning Model for Finding New Superconductors
Venue: arXiv cs.LG 2021
Year: 2021

Exploration of new superconductors still relies on the experience and intuition of experts and is largely a process of experimental trial and error. In one study, only 3% of the candidate materials showed superconductivity. Here, we report the first deep learning model for finding new superconductors. We introduced the method named "reading periodic table" which represented the periodic table in a way that allows deep learning to learn to read the periodic table and to learn the law of elements for the purpose of discovering novel superconductors that are outside the training data. It is recognized that it is difficult for deep learning to predict something outside the training data. Although we used only the chemical composition of materials as information, we obtained an $R^{2}$ value of 0.92 for predicting $T_\text{c}$ for materials in a database of superconductors. We also introduced the method named "garbage-in" to create synthetic data of non-superconductors that do not exist. Non-superconductors are not reported, but the data must be required for deep learning to distinguish between superconductors and non-superconductors. We obtained three remarkable results. The deep learning can predict superconductivity for a material with a precision of 62%, which shows the usefulness of the model; it found the recently discovered superconductor CaBi2 and another one Hf0.5Nb0.2V2Zr0.3, neither of which is in the superconductor database; and it found Fe-based high-temperature superconductors (discovered in 2008) from the training data before 2008. These results open the way for the discovery of new high-temperature superconductor families. The candidate materials list, data, and method are openly available from the link https://github.com/tomo835g/Deep-Learning-to-find-Superconductors.
Top-K Off-Policy Correction for a REINFORCE Recommender System
Venue: arXiv cs.LG 2021
Year: 2021

Industrial recommender systems deal with extremely large action spaces -- many millions of items to recommend. Moreover, they need to serve billions of users, who are unique at any point in time, making a complex user state space. Luckily, huge quantities of logged implicit feedback (e.g., user clicks, dwell time) are available for learning. Learning from the logged feedback is however subject to biases caused by only observing feedback on recommendations selected by the previous versions of the recommender. In this work, we present a general recipe of addressing such biases in a production top-K recommender system at Youtube, built with a policy-gradient-based algorithm, i.e. REINFORCE. The contributions of the paper are: (1) scaling REINFORCE to a production recommender system with an action space on the orders of millions; (2) applying off-policy correction to address data biases in learning from logged feedback collected from multiple behavior policies; (3) proposing a novel top-K off-policy correction to account for our policy recommending multiple items at a time; (4) showcasing the value of exploration. We demonstrate the efficacy of our approaches through a series of simulations and multiple live experiments on Youtube.