OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of Boolean Functions
Venue: arXiv cs.DM 2021
Year: 2021

The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : \{0,1\}^n \to \{0,1\}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a "highlight" showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1-5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the book's chapters.
Multi-Horizon Forecasting for Limit Order Books: Novel Deep Learning Approaches and Hardware Acceleration using Intelligent Processing Units
Venue: arXiv cs.LG 2021
Year: 2021

We design multi-horizon forecasting models for limit order book (LOB) data by using deep learning techniques. Unlike standard structures where a single prediction is made, we adopt encoder-decoder models with sequence-to-sequence and Attention mechanisms to generate a forecasting path. Our methods achieve comparable performance to state-of-art algorithms at short prediction horizons. Importantly, they outperform when generating predictions over long horizons by leveraging the multi-horizon setup. Given that encoder-decoder models rely on recurrent neural layers, they generally suffer from slow training processes. To remedy this, we experiment with utilising novel hardware, so-called Intelligent Processing Units (IPUs) produced by Graphcore. IPUs are specifically designed for machine intelligence workload with the aim to speed up the computation process. We show that in our setup this leads to significantly faster training times when compared to training models with GPUs.
Nori: Concealing the Concealed Identifier in 5G
Venue: arXiv cs.CR 2021
Year: 2021

IMSI catchers have been a long standing and serious privacy problem in pre-5G mobile networks. To tackle this, 3GPP introduced the Subscription Concealed Identifier (SUCI) and other countermeasures in 5G. In this paper, we analyze the new SUCI mechanism and discover that it provides very poor anonymity when used with the variable length Network Specific Identifiers (NSI), which are part of the 5G standard. When applied to real-world name length data, we see that SUCI only provides 1-anonymity, meaning that individual subscribers can easily be identified and tracked. We strongly recommend 3GPP and GSMA to standardize and recommend the use of a padding mechanism for SUCI before variable length identifiers get more commonly used. We further show that the padding schemes, commonly used for network traffic, are not optimal for padding of identifiers based on real names. We propose a new improved padding scheme that achieves much less message expansion for a given $k$-anonymity.
Graph Convolutional Networks in Feature Space for Image Deblurring and Super-resolution
Venue: arXiv cs.CV 2021
Year: 2021

Graph convolutional networks (GCNs) have achieved great success in dealing with data of non-Euclidean structures. Their success directly attributes to fitting graph structures effectively to data such as in social media and knowledge databases. For image processing applications, the use of graph structures and GCNs have not been fully explored. In this paper, we propose a novel encoder-decoder network with added graph convolutions by converting feature maps to vertexes of a pre-generated graph to synthetically construct graph-structured data. By doing this, we inexplicitly apply graph Laplacian regularization to the feature maps, making them more structured. The experiments show that it significantly boosts performance for image restoration tasks, including deblurring and super-resolution. We believe it opens up opportunities for GCN-based approaches in more applications.
Assessment and Decision-Making in Universities: Analytics of the Administration-Staff Compromises
Venue: arXiv cs.CY 2021
Year: 2021

Various processes in academic organizations include the decision points where selecting people through their assessment and ranking is performed, and the impact of wrong or right choices can be very high. How do we simultaneously ensure that these selection decisions are well balanced, fair, and unbiased by satisfying the key stakeholders' wishes? How much and what kinds of evidence must be used to make them? How can both the evidence and the procedures be made transparent and unambitious for everyone? In this paper, we suggest a set of so-called deep evidence-based analytics, which is applied on top of the collective awareness platform (portal for managing higher education processes). The deep evidence, in addition to the facts about the individual academic achievements of personnel, includes the evidence about individual rewards. However, what is more important is that such evidence also includes explicit individual value systems (formalized personal preferences in the self-assessment of both achievements and the rewards). We provide formalized procedures that can be used to drive the academic assessment and selection processes within universities based on advanced (deep) evidence and with different balances of decision power between administrations and personnel. We also show how this analytics enables computational evidence for some abstract properties of an academic organization related to its organizational culture, such as organizational democracy, justice, and work passion. We present the analytics together with examples of its actual use within Ukrainian higher education at the Trust portal.
Principled Design of Translation, Scale, and Rotation Invariant Variation Operators for Metaheuristics
Venue: arXiv cs.NE 2021
Year: 2021

In the past three decades, a large number of metaheuristics have been proposed and shown high performance in solving complex optimization problems. While most variation operators in existing metaheuristics are empirically designed, this paper aims to design new operators automatically, which are expected to be search space independent and thus exhibit robust performance on different problems. For this purpose, this work first investigates the influence of translation invariance, scale invariance, and rotation invariance on the search behavior and performance of some representative operators. Then, we deduce the generic form of translation, scale, and rotation invariant operators. Afterwards, a principled approach is proposed for the automated design of operators, which searches for high-performance operators based on the deduced generic form. The experimental results demonstrate that the operators generated by the proposed approach outperform state-of-the-art ones on a variety of problems with complex landscapes and up to 1000 decision variables.
Feasible Actor-Critic: Constrained Reinforcement Learning for Ensuring Statewise Safety
Venue: arXiv cs.LG 2021
Year: 2021

The safety constraints commonly used by existing safe reinforcement learning (RL) methods are defined only on expectation of initial states, but allow each certain state to be unsafe, which is unsatisfying for real-world safety-critical tasks. In this paper, we introduce the feasible actor-critic (FAC) algorithm, which is the first model-free constrained RL method that considers statewise safety, e.g, safety for each initial state. We claim that some states are inherently unsafe no matter what policy we choose, while for other states there exist policies ensuring safety, where we say such states and policies are feasible. By constructing a statewise Lagrange function available on RL sampling and adopting an additional neural network to approximate the statewise Lagrange multiplier, we manage to obtain the optimal feasible policy which ensures safety for each feasible state and the safest possible policy for infeasible states. Furthermore, the trained multiplier net can indicate whether a given state is feasible or not through the statewise complementary slackness condition. We provide theoretical guarantees that FAC outperforms previous expectation-based constrained RL methods in terms of both constraint satisfaction and reward optimization. Experimental results on both robot locomotive tasks and safe exploration tasks verify the safety enhancement and feasibility interpretation of the proposed method.
An Algorithm for Reordering Buffer Management Problem and Experimental Evaluations on Discrete Distributions
Venue: arXiv cs.DS 2021
Year: 2021

In the reordering buffer management problem, a sequence of requests must be executed by a service station, where a cost occurs for each pair of consecutive requests with different attributes. A reordering buffer management algorithm aims to permute the input sequence using the buffer to minimize the total cost. Reordering buffers has many potential applications in computer sciences and economics. In this article, we proved the minimum buffer length for the optimal solution to the reordering buffer management problem in the offline setting. With the assumption that color selection is always made when the buffer is full, selecting the most frequent color from the buffer given the smallest buffer size $k$ that satisfies either $o_1 < 2 \cdot \lceil \frac{k}σ \rceil$ OR $o_2 < \lceil \frac{k}σ \rceil$ guarantees the optimal solution, where $o_1$ and $o_2$ represent respectively the frequency of the most and the second most frequent colors in the input sequence $\mathcal{X}$, and $σ$ is the number of distinct colors appearing in $\mathcal{X}$. We proposed a new algorithm for the online setting of the problem that uses the results of the proof made on the minimum buffer length required for the optimal solution. Moreover, we presented the results of the first experimental setup that uses input sequences following discrete distributions to evaluate the performance of algorithms. Out of 432 cases, the new algorithm showed the best performance in 409 cases that is approximately $95\%$ of all cases.
Resource and Response Aware Path Planning for Long-term Autonomy of Ground Robots in Agriculture
Venue: arXiv cs.RO 2021
Year: 2021

Achieving long-term autonomy for mobile robots operating in real-world unstructured environments such as farms remains a significant challenge. This is made increasingly complex in the presence of moving humans or livestock. These environments require a robot to be adaptive in its immediate plans, accounting for the state of nearby individuals and the response that they might have to the robot's actions. Additionally, in order to achieve longer-term goals, consideration of the limited on-board resources available to the robot is required, especially for extended missions such as weeding an agricultural field. To achieve efficient long-term autonomy, it is thus crucial to understand the impact that online dynamic updates to an energy efficient offline plan might have on resource usage whilst navigating through crowds or herds. To address these challenges, a hierarchical planning framework is proposed, integrating an online local dynamic path planner with an offline longer-term objective-based planner. This framework acts to achieve long-term autonomy through awareness of both dynamic responses of individuals to a robot's motion and the limited resources available. This paper details the hierarchical approach and its integration on a robotic platform, including a comprehensive description of the planning framework and associated perception modules. The approach is evaluated in real-world trials on farms, requiring both consideration of limited battery capacity and the presence of nearby moving individuals. These trials additionally demonstrate the ability of the framework to adapt resource use through variation of the local dynamic planner, allowing adaptive behaviour in changing environments. A summary video is available at https://youtu.be/DGVTrYwJ304.
ADNet: Attention-guided Deformable Convolutional Network for High Dynamic Range Imaging
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we present an attention-guided deformable convolutional network for hand-held multi-frame high dynamic range (HDR) imaging, namely ADNet. This problem comprises two intractable challenges of how to handle saturation and noise properly and how to tackle misalignments caused by object motion or camera jittering. To address the former, we adopt a spatial attention module to adaptively select the most appropriate regions of various exposure low dynamic range (LDR) images for fusion. For the latter one, we propose to align the gamma-corrected images in the feature-level with a Pyramid, Cascading and Deformable (PCD) alignment module. The proposed ADNet shows state-of-the-art performance compared with previous methods, achieving a PSNR-$l$ of 39.4471 and a PSNR-$μ$ of 37.6359 in NTIRE 2021 Multi-Frame HDR Challenge.
Attention-based Reinforcement Learning for Real-Time UAV Semantic Communication
Venue: arXiv cs.MA 2021
Year: 2021

In this article, we study the problem of air-to-ground ultra-reliable and low-latency communication (URLLC) for a moving ground user. This is done by controlling multiple unmanned aerial vehicles (UAVs) in real time while avoiding inter-UAV collisions. To this end, we propose a novel multi-agent deep reinforcement learning (MADRL) framework, coined a graph attention exchange network (GAXNet). In GAXNet, each UAV constructs an attention graph locally measuring the level of attention to its neighboring UAVs, while exchanging the attention weights with other UAVs so as to reduce the attention mismatch between them. Simulation results corroborates that GAXNet achieves up to 4.5x higher rewards during training. At execution, without incurring inter-UAV collisions, GAXNet achieves 6.5x lower latency with the target 0.0000001 error rate, compared to a state-of-the-art baseline framework.
Designing Limitless Path in Virtual Reality Environment
Venue: arXiv cs.HC 2021
Year: 2021

Walking in a Virtual Environment is a bounded task. It is challenging for a subject to navigate a large virtual environment designed in a limited physical space. External hardware support may be required to achieve such an act in a concise physical area without compromising navigation and virtual scene rendering quality. This paper proposes an algorithmic approach to let a subject navigate a limitless virtual environment within a limited physical space with no additional external hardware support apart from the regular Head-Mounted-Device (HMD) itself. As part of our work, we developed a Virtual Art Gallery as a use-case to validate our algorithm. We conducted a simple user-study to gather feedback from the participants to evaluate the ease of locomotion of the application. The results showed that our algorithm could generate limitless paths of our use-case under predefined conditions and can be extended to other use-cases.
PAL: Intelligence Augmentation using Egocentric Visual Context Detection
Venue: arXiv cs.CV 2021
Year: 2021

Egocentric visual context detection can support intelligence augmentation applications. We created a wearable system, called PAL, for wearable, personalized, and privacy-preserving egocentric visual context detection. PAL has a wearable device with a camera, heart-rate sensor, on-device deep learning, and audio input/output. PAL also has a mobile/web application for personalized context labeling. We used on-device deep learning models for generic object and face detection, low-shot custom face and context recognition (e.g., activities like brushing teeth), and custom context clustering (e.g., indoor locations). The models had over 80\% accuracy in in-the-wild contexts (~1000 images) and we tested PAL for intelligence augmentation applications like behavior change. We have made PAL is open-source to further support intelligence augmentation using personalized and privacy-preserving egocentric visual contexts.
PLM: Partial Label Masking for Imbalanced Multi-label Classification
Venue: arXiv cs.CV 2021
Year: 2021

Neural networks trained on real-world datasets with long-tailed label distributions are biased towards frequent classes and perform poorly on infrequent classes. The imbalance in the ratio of positive and negative samples for each class skews network output probabilities further from ground-truth distributions. We propose a method, Partial Label Masking (PLM), which utilizes this ratio during training. By stochastically masking labels during loss computation, the method balances this ratio for each class, leading to improved recall on minority classes and improved precision on frequent classes. The ratio is estimated adaptively based on the network's performance by minimizing the KL divergence between predicted and ground-truth distributions. Whereas most existing approaches addressing data imbalance are mainly focused on single-label classification and do not generalize well to the multi-label case, this work proposes a general approach to solve the long-tail data imbalance issue for multi-label classification. PLM is versatile: it can be applied to most objective functions and it can be used alongside other strategies for class imbalance. Our method achieves strong performance when compared to existing methods on both multi-label (MultiMNIST and MSCOCO) and single-label (imbalanced CIFAR-10 and CIFAR-100) image classification datasets.
GOO: A Dataset for Gaze Object Prediction in Retail Environments
Venue: arXiv cs.CV 2021
Year: 2021

One of the most fundamental and information-laden actions humans do is to look at objects. However, a survey of current works reveals that existing gaze-related datasets annotate only the pixel being looked at, and not the boundaries of a specific object of interest. This lack of object annotation presents an opportunity for further advancing gaze estimation research. To this end, we present a challenging new task called gaze object prediction, where the goal is to predict a bounding box for a person's gazed-at object. To train and evaluate gaze networks on this task, we present the Gaze On Objects (GOO) dataset. GOO is composed of a large set of synthetic images (GOO Synth) supplemented by a smaller subset of real images (GOO-Real) of people looking at objects in a retail environment. Our work establishes extensive baselines on GOO by re-implementing and evaluating selected state-of-the art models on the task of gaze following and domain adaptation. Code is available on github.
Learning First-Order Representations for Planning from Black-Box States: New Results
Venue: arXiv cs.AI 2021
Year: 2021

Recently Bonet and Geffner have shown that first-order representations for planning domains can be learned from the structure of the state space without any prior knowledge about the action schemas or domain predicates. For this, the learning problem is formulated as the search for a simplest first-order domain description D that along with information about instances I_i (number of objects and initial state) determine state space graphs G(P_i) that match the observed state graphs G_i where P_i = (D, I_i). The search is cast and solved approximately by means of a SAT solver that is called over a large family of propositional theories that differ just in the parameters encoding the possible number of action schemas and domain predicates, their arities, and the number of objects. In this work, we push the limits of these learners by moving to an answer set programming (ASP) encoding using the CLINGO system. The new encodings are more transparent and concise, extending the range of possible models while facilitating their exploration. We show that the domains introduced by Bonet and Geffner can be solved more efficiently in the new approach, often optimally, and furthermore, that the approach can be easily extended to handle partial information about the state graphs as well as noise that prevents some states from being distinguished.
Precise Approximation of Convolutional Neural Networks for Homomorphically Encrypted Data
Venue: arXiv cs.CR 2021
Year: 2021

Homomorphic encryption is one of the representative solutions to privacy-preserving machine learning (PPML) classification enabling the server to classify private data of clients while guaranteeing privacy. This work focuses on PPML using word-wise fully homomorphic encryption (FHE). In order to implement deep learning on word-wise homomorphic encryption (HE), the ReLU and max-pooling functions should be approximated by some polynomials for homomorphic operations. Most of the previous studies focus on HE-friendly networks, where the ReLU and max-pooling functions are approximated using low-degree polynomials. However, for the classification of the CIFAR-10 dataset, using a low-degree polynomial requires designing a new deep learning model and training. In addition, this approximation by low-degree polynomials cannot support deeper neural networks due to large approximation errors. Thus, we propose a precise polynomial approximation technique for the ReLU and max-pooling functions. Precise approximation using a single polynomial requires an exponentially high-degree polynomial, which results in a significant number of non-scalar multiplications. Thus, we propose a method to approximate the ReLU and max-pooling functions accurately using a composition of minimax approximate polynomials of small degrees. If we replace the ReLU and max-pooling functions with the proposed approximate polynomials, well-studied deep learning models such as ResNet and VGGNet can still be used without further modification for PPML on FHE. Even pre-trained parameters can be used without retraining. We approximate the ReLU and max-pooling functions in the ResNet-152 using the composition of minimax approximate polynomials of degrees 15, 27, and 29. Then, we succeed in classifying the plaintext ImageNet dataset with 77.52% accuracy, which is very close to the original model accuracy of 78.31%.
RtFPS: An Interactive Map that Visualizes and Predicts Wildfires in the US
Venue: arXiv cs.LG 2021
Year: 2021

Climate change has largely impacted our daily lives. As one of its consequences, we are experiencing more wildfires. In the year 2020, wildfires burned a record number of 8,888,297 acres in the US. To awaken people's attention to climate change, and to visualize the current risk of wildfires, We developed RtFPS, "Real-Time Fire Prediction System". It provides a real-time prediction visualization of wildfire risk at specific locations base on a Machine Learning model. It also provides interactive map features that show the historical wildfire events with environmental info.