OpenRaiser/Intern-Atlas huggingface dataset:
Learning the Quality of Machine Permutations in Job Shop Scheduling
Venue: arXiv cs.LG 2022
Year: 2022

In recent years, the power demonstrated by Machine Learning (ML) has increasingly attracted the interest of the optimization community that is starting to leverage ML for enhancing and automating the design of algorithms. One combinatorial optimization problem recently tackled with ML is the Job Shop scheduling Problem (JSP). Most of the works on the JSP using ML focus on Deep Reinforcement Learning (DRL), and only a few of them leverage supervised learning techniques. The recurrent reasons for avoiding supervised learning seem to be the difficulty in casting the right learning task, i.e., what is meaningful to predict, and how to obtain labels. Therefore, we first propose a novel supervised learning task that aims at predicting the quality of machine permutations. Then, we design an original methodology to estimate this quality, and we use these estimations to create an accurate sequential deep learning model (binary accuracy above 95%). Finally, we empirically demonstrate the value of predicting the quality of machine permutations by enhancing the performance of a simple Tabu Search algorithm inspired by the works in the literature.
Local Inversion of maps: Black box Cryptanalysis
Venue: arXiv cs.CR 2022
Year: 2022

This paper is a short summery of results announced in a previous paper on a new universal method for Cryptanalysis which uses a Black Box linear algebra approach to computation of local inversion of nonlinear maps in finite fields. It is shown that one local inverse $x$ of the map equation $y=F(x)$ can be computed by using the minimal polynomial of the sequence $y(k)$ defined by iterates (or recursion) $y(k+1)=F(y(k))$ with $y(0)=y$ when the sequence is periodic. This is the only solution in the periodic orbit of the map $F$. Further, when the degree of the minimal polynomial is of polynomial order in number of bits of the input of $F$ (called low complexity case), the solution can be computed in polynomial time. The method of computation only uses the forward computations $F(y)$ for given $y$ which is why this is called a Black Box approach. Application of this approach is then shown for cryptanalysis of several maps arising in cryptographic primitives. It is shown how in the low complexity cases maps defined by block and stream ciphers can be inverted to find the symmetric key under known plaintext attack. Then it is shown how RSA map can be inverted to find the plaintext as well as an equivalent private key to break the RSA algorithm without factoring the modulus. Finally it is shown that the discrete log computation in finite field and elliptic curves can be formulated as a local inversion problem and the low complexity cases can be solved in polynomial time.
Vessel-following model for inland waterways based on deep reinforcement learning
Venue: arXiv cs.CE 2022
Year: 2022

While deep reinforcement learning (RL) has been increasingly applied in designing car-following models in the last years, this study aims at investigating the feasibility of RL-based vehicle-following for complex vehicle dynamics and strong environmental disturbances. As a use case, we developed an inland waterways vessel-following model based on realistic vessel dynamics, which considers environmental influences, such as varying stream velocity and river profile. We extracted natural vessel behavior from anonymized AIS data to formulate a reward function that reflects a realistic driving style next to comfortable and safe navigation. Aiming at high generalization capabilities, we propose an RL training environment that uses stochastic processes to model leading trajectory and river dynamics. To validate the trained model, we defined different scenarios that have not been seen in training, including realistic vessel-following on the Middle Rhine. Our model demonstrated safe and comfortable driving in all scenarios, proving excellent generalization abilities. Furthermore, traffic oscillations could effectively be dampened by deploying the trained model on a sequence of following vessels.
Fast Discrepancy Minimization with Hereditary Guarantees
Venue: arXiv cs.DS 2022
Year: 2022

Efficiently computing low discrepancy colorings of various set systems, has been studied extensively since the breakthrough work by Bansal (FOCS 2010), who gave the first polynomial time algorithms for several important settings, including for general set systems, sparse set systems and for set systems with bounded hereditary discrepancy. The hereditary discrepancy of a set system, is the maximum discrepancy over all set systems obtainable by deleting a subset of the ground elements. While being polynomial time, Bansal's algorithms were not practical, with e.g. his algorithm for the hereditary setup running in time $Ω(m n^{4.5})$ for set systems with $m$ sets over a ground set of $n$ elements. More efficient algorithms have since then been developed for general and sparse set systems, however, for the hereditary case, Bansal's algorithm remains state-of-the-art. In this work, we give a significantly faster algorithm with hereditary guarantees, running in $O(mn^2\lg(2 + m/n) + n^3)$ time. Our algorithm is based on new structural insights into set systems with bounded hereditary discrepancy. We also implement our algorithm and show experimentally that it computes colorings that are significantly better than random and finishes in a reasonable amount of time, even on set systems with thousands of sets over a ground set of thousands of elements.
Comparing the Utility and Disclosure Risk of Synthetic Data with Samples of Microdata
Venue: arXiv cs.CR 2022
Year: 2022

Most statistical agencies release randomly selected samples of Census microdata, usually with sample fractions under 10% and with other forms of statistical disclosure control (SDC) applied. An alternative to SDC is data synthesis, which has been attracting growing interest, yet there is no clear consensus on how to measure the associated utility and disclosure risk of the data. The ability to produce synthetic Census microdata, where the utility and associated risks are clearly understood, could mean that more timely and wider-ranging access to microdata would be possible. This paper follows on from previous work by the authors which mapped synthetic Census data on a risk-utility (R-U) map. The paper presents a framework to measure the utility and disclosure risk of synthetic data by comparing it to samples of the original data of varying sample fractions, thereby identifying the sample fraction which has equivalent utility and risk to the synthetic data. Three commonly used data synthesis packages are compared with some interesting results. Further work is needed in several directions but the methodology looks very promising.
Automated Classification of General Movements in Infants Using a Two-stream Spatiotemporal Fusion Network
Venue: arXiv cs.CV 2022
Year: 2022

The assessment of general movements (GMs) in infants is a useful tool in the early diagnosis of neurodevelopmental disorders. However, its evaluation in clinical practice relies on visual inspection by experts, and an automated solution is eagerly awaited. Recently, video-based GMs classification has attracted attention, but this approach would be strongly affected by irrelevant information, such as background clutter in the video. Furthermore, for reliability, it is necessary to properly extract the spatiotemporal features of infants during GMs. In this study, we propose an automated GMs classification method, which consists of preprocessing networks that remove unnecessary background information from GMs videos and adjust the infant's body position, and a subsequent motion classification network based on a two-stream structure. The proposed method can efficiently extract the essential spatiotemporal features for GMs classification while preventing overfitting to irrelevant information for different recording environments. We validated the proposed method using videos obtained from 100 infants. The experimental results demonstrate that the proposed method outperforms several baseline models and the existing methods.
On Session Typing, Probabilistic Polynomial Time, and Cryptographic Experiments (Long Version)
Venue: arXiv cs.LO 2022
Year: 2022

A system of session types is introduced as induced by a Curry Howard correspondence applied to Bounded Linear Logic, and then extending the thus obtained type system with probabilistic choices and ground types. The obtained system satisfies the expected properties, like subject reduction and progress, but also unexpected ones, like a polynomial bound on the time needed to reduce processes. This makes the system suitable for modelling experiments and proofs from the so-called computational model of cryptography.
Stochastic optimal well control in subsurface reservoirs using reinforcement learning
Venue: arXiv cs.LG 2022
Year: 2022

We present a case study of model-free reinforcement learning (RL) framework to solve stochastic optimal control for a predefined parameter uncertainty distribution and partially observable system. We focus on robust optimal well control problem which is a subject of intensive research activities in the field of subsurface reservoir management. For this problem, the system is partially observed since the data is only available at well locations. Furthermore, the model parameters are highly uncertain due to sparsity of available field data. In principle, RL algorithms are capable of learning optimal action policies -- a map from states to actions -- to maximize a numerical reward signal. In deep RL, this mapping from state to action is parameterized using a deep neural network. In the RL formulation of the robust optimal well control problem, the states are represented by saturation and pressure values at well locations while the actions represent the valve openings controlling the flow through wells. The numerical reward refers to the total sweep efficiency and the uncertain model parameter is the subsurface permeability field. The model parameter uncertainties are handled by introducing a domain randomisation scheme that exploits cluster analysis on its uncertainty distribution. We present numerical results using two state-of-the-art RL algorithms, proximal policy optimization (PPO) and advantage actor-critic (A2C), on two subsurface flow test cases representing two distinct uncertainty distributions of permeability field. The results were benchmarked against optimisation results obtained using differential evolution algorithm. Furthermore, we demonstrate the robustness of the proposed use of RL by evaluating the learned control policy on unseen samples drawn from the parameter uncertainty distribution that were not used during the training process.
Meta-Learning the Difference: Preparing Large Language Models for Efficient Adaptation
Venue: arXiv cs.CL 2022
Year: 2022

Large pretrained language models (PLMs) are often domain- or task-adapted via fine-tuning or prompting. Finetuning requires modifying all of the parameters and having enough data to avoid overfitting while prompting requires no training and few examples but limits performance. Instead, we prepare PLMs for data- and parameter-efficient adaptation by learning to learn the difference between general and adapted PLMs. This difference is expressed in terms of model weights and sublayer structure through our proposed dynamic low-rank reparameterization and learned architecture controller. Experiments on few-shot dialogue completion, low-resource abstractive summarization, and multi-domain language modeling show improvements in adaptation time and performance over direct finetuning or preparation via domain-adaptive pretraining. Ablations show our task-adaptive reparameterization (TARP) and model search (TAMS) components individually improve on other parameter-efficient transfer like adapters and structure-learning methods like learned sparsification.
Ride-Hailing for Autonomous Vehicles: Hyperledger Fabric-Based Secure and Decentralize Blockchain Platform
Venue: arXiv cs.DC 2022
Year: 2022

Ride-hailing and ride-sharing applications have recently gained popularity as a convenient alternative to traditional modes of travel. Current research into autonomous vehicles is accelerating rapidly and will soon become a critical component of a ride-hailing platforms architecture. Implementing an autonomous vehicle ride-hailing platform proves a difficult challenge due to the centralized nature of traditional ride-hailing architectures. In a traditional ride-hailing environment the drivers operate their own personal vehicles so it follows that a fleet of autonomous vehicles would be required for a centralized ride-hailing platform to succeed. Decentralization of the ride-hailing platform would remove a roadblock along the way to an autonomous vehicle ride-hailing platform by allowing owners of autonomous vehicles to add their vehicles to a community-driven fleet when not in use. Blockchain technology is an attractive choice for this decentralized architecture due to its immutability and fault tolerance. This thesis proposes a framework for developing a decentralized ride-hailing architecture that is verifiably secure. This framework is implemented on the Hyperledger Fabric blockchain platform. The evaluation of the implementation is done by applying known security models, utilizing a static analysis tool, and performing a performance analysis under heavy network load.
Reinforcement Learning-based Joint User Scheduling and Link Configuration in Millimeter-wave Networks
Venue: arXiv cs.NI 2022
Year: 2022

In this paper, we develop algorithms for joint user scheduling and three types of mmWave link configuration: relay selection, codebook optimization, and beam tracking in millimeter wave (mmWave) networks. Our goal is to design an online controller that dynamically schedules users and configures their links to minimize the system delay. To solve this complex scheduling problem, we model it as a dynamic decision-making process and develop two reinforcement learning-based solutions. The first solution is based on deep reinforcement learning (DRL), which leverages the proximal policy optimization to train a neural network-based solution. Due to the potential high sample complexity of DRL, we also propose an empirical multi-armed bandit (MAB)-based solution, which decomposes the decision-making process into a sequential of sub-actions and exploits classic maxweight scheduling and Thompson sampling to decide those sub-actions. Our evaluation of the proposed solutions confirms their effectiveness in providing acceptable system delay. It also shows that the DRL-based solution has better delay performance while the MAB-based solution has a faster training process.
RWT-SLAM: Robust Visual SLAM for Highly Weak-textured Environments
Venue: arXiv cs.CV 2022
Year: 2022

As a fundamental task for intelligent robots, visual SLAM has made great progress over the past decades. However, robust SLAM under highly weak-textured environments still remains very challenging. In this paper, we propose a novel visual SLAM system named RWT-SLAM to tackle this problem. We modify LoFTR network which is able to produce dense point matching under low-textured scenes to generate feature descriptors. To integrate the new features into the popular ORB-SLAM framework, we develop feature masks to filter out the unreliable features and employ KNN strategy to strengthen the matching robustness. We also retrained visual vocabulary upon new descriptors for efficient loop closing. The resulting RWT-SLAM is tested in various public datasets such as TUM and OpenLORIS, as well as our own data. The results shows very promising performance under highly weak-textured environments.
Blockchain-based Medical Image Sharing and Automated Critical-results Notification: A Novel Framework
Venue: arXiv cs.HC 2022
Year: 2022

In teleradiology, medical images are transmitted to offsite radiologists for interpretation and the dictation report is sent back to the original site to aid timely diagnosis and proper patient care. Although teleradiology offers great benefits including time and cost efficiency, after-hour coverages, and staffing shortage management, there are some technical and operational limitations to overcome in reaching its full potential. We analyzed the current teleradiology workflow to identify inefficiencies. Image unavailability and delayed critical result communication stemmed from lack of system integration between teleradiology practice and healthcare institutions are among the most substantial factors causing prolonged turnaround time. In this paper, we propose a blockchain-based medical image sharing and automated critical-results notification platform to address the current limitation. We believe the proposed platform will enhance efficiency in workflow by eliminating the need for intermediaries and will benefit patients by eliminating the need for storing medical images in hard copies. While considerable progress was achieved, further research on governance and HIPAA compliance is required to optimize the adoption of the new application. Towards an idea to a working paradigm, we will implement the prototype during the next phase of our study.
A Study on the Predictability of Sample Learning Consistency
Venue: arXiv cs.LG 2022
Year: 2022

Curriculum Learning is a powerful training method that allows for faster and better training in some settings. This method, however, requires having a notion of which examples are difficult and which are easy, which is not always trivial to provide. A recent metric called C-Score acts as a proxy for example difficulty by relating it to learning consistency. Unfortunately, this method is quite compute intensive which limits its applicability for alternative datasets. In this work, we train models through different methods to predict C-Score for CIFAR-100 and CIFAR-10. We find, however, that these models generalize poorly both within the same distribution as well as out of distribution. This suggests that C-Score is not defined by the individual characteristics of each sample but rather by other factors. We hypothesize that a sample's relation to its neighbours, in particular, how many of them share the same labels, can help in explaining C-Scores. We plan to explore this in future work.
Automatic Synthesis of Neurons for Recurrent Neural Nets
Venue: arXiv cs.NE 2022
Year: 2022

We present a new class of neurons, ARNs, which give a cross entropy on test data that is up to three times lower than the one achieved by carefully optimized LSTM neurons. The explanations for the huge improvements that often are achieved are elaborate skip connections through time, up to four internal memory states per neuron and a number of novel activation functions including small quadratic forms. The new neurons were generated using automatic programming and are formulated as pure functional programs that easily can be transformed. We present experimental results for eight datasets and found excellent improvements for seven of them, but LSTM remained the best for one dataset. The results are so promising that automatic programming to generate new neurons should become part of the standard operating procedure for any machine learning practitioner who works on time series data such as sensor signals.
Dynamic Community Detection via Adversarial Temporal Graph Representation Learning
Venue: arXiv cs.SI 2022
Year: 2022

Dynamic community detection has been prospered as a powerful tool for quantifying changes in dynamic brain network connectivity patterns by identifying strongly connected sets of nodes. However, as the network science problems and network data to be processed become gradually more sophisticated, it awaits a better method to efficiently learn low dimensional representation from dynamic network data and reveal its latent function that changes over time in the brain network. In this work, an adversarial temporal graph representation learning (ATGRL) framework is proposed to detect dynamic communities from a small sample of brain network data. It adopts a novel temporal graph attention network as an encoder to capture more efficient spatio-temporal features by attention mechanism in both spatial and temporal dimensions. In addition, the framework employs adversarial training to guide the learning of temporal graph representation and optimize the measurable modularity loss to maximize the modularity of community. Experiments on the real-world brain networks datasets are demonstrated to show the effectiveness of this new method.
CausalAgents: A Robustness Benchmark for Motion Forecasting using Causal Relationships
Venue: arXiv cs.LG 2022
Year: 2022

As machine learning models become increasingly prevalent in motion forecasting for autonomous vehicles (AVs), it is critical to ensure that model predictions are safe and reliable. However, exhaustively collecting and labeling the data necessary to fully test the long tail of rare and challenging scenarios is difficult and expensive. In this work, we construct a new benchmark for evaluating and improving model robustness by applying perturbations to existing data. Specifically, we conduct an extensive labeling effort to identify causal agents, or agents whose presence influences human drivers' behavior in any format, in the Waymo Open Motion Dataset (WOMD), and we use these labels to perturb the data by deleting non-causal agents from the scene. We evaluate a diverse set of state-of-the-art deep-learning model architectures on our proposed benchmark and find that all models exhibit large shifts under even non-causal perturbation: we observe a 25-38% relative change in minADE as compared to the original. We also investigate techniques to improve model robustness, including increasing the training dataset size and using targeted data augmentations that randomly drop non-causal agents throughout training. Finally, we release the causal agent labels (at https://github.com/google-research/causal-agents) as an additional attribute to WOMD and the robustness benchmarks to aid the community in building more reliable and safe deep-learning models for motion forecasting.
Information-Gathering in Latent Bandits
Venue: arXiv cs.LG 2022
Year: 2022

In the latent bandit problem, the learner has access to reward distributions and -- for the non-stationary variant -- transition models of the environment. The reward distributions are conditioned on the arm and unknown latent states. The goal is to use the reward history to identify the latent state, allowing for the optimal choice of arms in the future. The latent bandit setting lends itself to many practical applications, such as recommender and decision support systems, where rich data allows the offline estimation of environment models with online learning remaining a critical component. Previous solutions in this setting always choose the highest reward arm according to the agent's beliefs about the state, not explicitly considering the value of information-gathering arms. Such information-gathering arms do not necessarily provide the highest reward, thus may never be chosen by an agent that chooses the highest reward arms at all times. In this paper, we present a method for information-gathering in latent bandits. Given particular reward structures and transition matrices, we show that choosing the best arm given the agent's beliefs about the states incurs higher regret. Furthermore, we show that by choosing arms carefully, we obtain an improved estimation of the state distribution, and thus lower the cumulative regret through better arm choices in the future. We evaluate our method on both synthetic and real-world data sets, showing significant improvement in regret over state-of-the-art methods.