OpenRaiser/Intern-Atlas huggingface dataset:
Learning to Control Linear Systems can be Hard
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we study the statistical difficulty of learning to control linear systems. We focus on two standard benchmarks, the sample complexity of stabilization, and the regret of the online learning of the Linear Quadratic Regulator (LQR). Prior results state that the statistical difficulty for both benchmarks scales polynomially with the system state dimension up to system-theoretic quantities. However, this does not reveal the whole picture. By utilizing minimax lower bounds for both benchmarks, we prove that there exist non-trivial classes of systems for which learning complexity scales dramatically, i.e. exponentially, with the system dimension. This situation arises in the case of underactuated systems, i.e. systems with fewer inputs than states. Such systems are structurally difficult to control and their system theoretic quantities can scale exponentially with the system dimension dominating learning complexity. Under some additional structural assumptions (bounding systems away from uncontrollability), we provide qualitatively matching upper bounds. We prove that learning complexity can be at most exponential with the controllability index of the system, that is the degree of underactuation.
Interleaved Prange: A New Generic Decoder for Interleaved Codes
Venue: arXiv cs.IT 2022
Year: 2022

Due to the recent challenges in post-quantum cryptography, several new approaches for code-based cryptography have been proposed. For example, a variant of the McEliece cryptosystem based on interleaved codes was proposed. In order to deem such new settings secure, we first need to understand and analyze the complexity of the underlying problem, in this case the problem of decoding a random interleaved code. A simple approach to decode such codes, would be to randomly choose a vector in the row span of the received matrix and run a classical information set decoding algorithm on this erroneous codeword. In this paper, we propose a new generic decoder for interleaved codes, which is an adaption of the classical idea of information set decoding by Prange and perfectly fits the interleaved setting. We then analyze the cost of the new algorithm and a comparison to the simple approach described above shows the superiority of Interleaved Prange.
Patching Leaks in the Charformer for Efficient Character-Level Generation
Venue: arXiv cs.CL 2022
Year: 2022

Character-based representations have important advantages over subword-based ones for morphologically rich languages. They come with increased robustness to noisy input and do not need a separate tokenization step. However, they also have a crucial disadvantage: they notably increase the length of text sequences. The GBST method from Charformer groups (aka downsamples) characters to solve this, but allows information to leak when applied to a Transformer decoder. We solve this information leak issue, thereby enabling character grouping in the decoder. We show that Charformer downsampling has no apparent benefits in NMT over previous downsampling methods in terms of translation quality, however it can be trained roughly 30% faster. Promising performance on English--Turkish translation indicate the potential of character-level models for morphologically-rich languages.
Failure Detection in Medical Image Classification: A Reality Check and Benchmarking Testbed
Venue: arXiv cs.AI 2022
Year: 2022

Failure detection in automated image classification is a critical safeguard for clinical deployment. Detected failure cases can be referred to human assessment, ensuring patient safety in computer-aided clinical decision making. Despite its paramount importance, there is insufficient evidence about the ability of state-of-the-art confidence scoring methods to detect test-time failures of classification models in the context of medical imaging. This paper provides a reality check, establishing the performance of in-domain misclassification detection methods, benchmarking 9 widely used confidence scores on 6 medical imaging datasets with different imaging modalities, in multiclass and binary classification settings. Our experiments show that the problem of failure detection is far from being solved. We found that none of the benchmarked advanced methods proposed in the computer vision and machine learning literature can consistently outperform a simple softmax baseline, demonstrating that improved out-of-distribution detection or model calibration do not necessarily translate to improved in-domain misclassification detection. Our developed testbed facilitates future work in this important area
Solving infinite-horizon POMDPs with memoryless stochastic policies in state-action space
Venue: arXiv cs.LG 2022
Year: 2022

Reward optimization in fully observable Markov decision processes is equivalent to a linear program over the polytope of state-action frequencies. Taking a similar perspective in the case of partially observable Markov decision processes with memoryless stochastic policies, the problem was recently formulated as the optimization of a linear objective subject to polynomial constraints. Based on this we present an approach for Reward Optimization in State-Action space (ROSA). We test this approach experimentally in maze navigation tasks. We find that ROSA is computationally efficient and can yield stability improvements over other existing methods.
Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration
Venue: arXiv cs.LG 2022
Year: 2022

From logistics to the natural sciences, combinatorial optimisation on graphs underpins numerous real-world applications. Reinforcement learning (RL) has shown particular promise in this setting as it can adapt to specific problem structures and does not require pre-solved instances for these, often NP-hard, problems. However, state-of-the-art (SOTA) approaches typically suffer from severe scalability issues, primarily due to their reliance on expensive graph neural networks (GNNs) at each decision step. We introduce ECORD; a novel RL algorithm that alleviates this expense by restricting the GNN to a single pre-processing step, before entering a fast-acting exploratory phase directed by a recurrent unit. Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem, whilst also providing orders of magnitude improvement in speed and scalability. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73% on 500 vertex graphs with a decreased wall-clock time. Moreover, ECORD retains strong performance when generalising to larger graphs with up to 10000 vertices.
Enhanced physics-informed neural networks for hyperelasticity
Venue: arXiv cs.CE 2022
Year: 2022

Physics-informed neural networks have gained growing interest. Specifically, they are used to solve partial differential equations governing several physical phenomena. However, physics-informed neural network models suffer from several issues and can fail to provide accurate solutions in many scenarios. We discuss a few of these challenges and the techniques, such as the use of Fourier transform, that can be used to resolve these issues. This paper proposes and develops a physics-informed neural network model that combines the residuals of the strong form and the potential energy, yielding many loss terms contributing to the definition of the loss function to be minimized. Hence, we propose using the coefficient of variation weighting scheme to dynamically and adaptively assign the weight for each loss term in the loss function. The developed PINN model is standalone and meshfree. In other words, it can accurately capture the mechanical response without requiring any labeled data. Although the framework can be used for many solid mechanics problems, we focus on three-dimensional (3D) hyperelasticity, where we consider two hyperelastic models. Once the model is trained, the response can be obtained almost instantly at any point in the physical domain, given its spatial coordinates. We demonstrate the framework's performance by solving different problems with various boundary conditions.
The Internet of People (IoP): A New Wave in Pervasive Mobile Computing
Venue: arXiv cs.NI 2022
Year: 2022

Cyber-Physical convergence, the fast expansion of the Internet at its edge, and tighter interactions between human users and their personal mobile devices push towards an Internet where the human user becomes more central than ever, and where their personal devices become their proxies in the cyber world, in addition to acting as a fundamental tool to sense the physical world. The current Internet paradigm, which is infrastructure-centric, is not the right one to cope with such emerging scenario with a wider range of applications. This calls for a radically new Internet paradigm, that we name the Internet of People (IoP), where the humans and their personal devices are not seen merely as end users of applications, but become active elements of the Internet. Note that IoP is not a replacement of the current Internet infrastructure, but it exploits legacy Internet services as (reliable) primitives to achieve end-to-end connectivity on a global-scale. In this visionary paper, we first discuss the key features of the IoP paradigm along with the underlying research issues and challenges. Then we present emerging networking and computing paradigms that are anticipating IoP
Ainur: A Framework for Repeatable End-to-End Wireless Edge Computing Testbed Research
Venue: arXiv cs.NI 2022
Year: 2022

Experimental research on wireless networking in combination with edge and cloud computing has been the subject of explosive interest in the last decade. This development has been driven by the increasing complexity of modern wireless technologies and the extensive softwarization of these through projects such as a Open Radio Access Network (O-RAN). In this context, a number of small- to mid-scale testbeds have emerged, employing a variety of technologies to target a wide array of use-cases and scenarios in the context of novel mobile communication technologies such as 5G and beyond-5G. Little work, however, has yet been devoted to developing a standard framework for wireless testbed automation which is hardware-agnostic and compatible with edge- and cloud-native technologies. Such a solution would simplify the development of new testbeds by completely or partially removing the requirement for custom management and orchestration software. In this paper, we present the first such mostly hardware-agnostic wireless testbed automation framework, Ainur. It is designed to configure, manage, orchestrate, and deploy workloads from an end-to-end perspective. Ainur is built on top of cloud-native technologies such as Docker, and is provided as FOSS to the community through the KTH-EXPECA/Ainur repository on GitHub. We demonstrate the utility of the platform with a series of scenarios, showcasing in particular its flexibility with respect to physical link definition, computation placement, and automation of arbitrarily complex experimental scenarios.
Fake It Till You Make It: Towards Accurate Near-Distribution Novelty Detection
Venue: arXiv cs.CV 2022
Year: 2022

We aim for image-based novelty detection. Despite considerable progress, existing models either fail or face a dramatic drop under the so-called "near-distribution" setting, where the differences between normal and anomalous samples are subtle. We first demonstrate existing methods experience up to 20% decrease in performance in the near-distribution setting. Next, we propose to exploit a score-based generative model to produce synthetic near-distribution anomalous data. Our model is then fine-tuned to distinguish such data from the normal samples. We provide a quantitative as well as qualitative evaluation of this strategy, and compare the results with a variety of GAN-based models. Effectiveness of our method for both the near-distribution and standard novelty detection is assessed through extensive experiments on datasets in diverse applications such as medical images, object classification, and quality control. This reveals that our method considerably improves over existing models, and consistently decreases the gap between the near-distribution and standard novelty detection performance. The code repository is available at https://github.com/rohban-lab/FITYMI.
Efficient Federated Learning with Spike Neural Networks for Traffic Sign Recognition
Venue: arXiv cs.LG 2022
Year: 2022

With the gradual popularization of self-driving, it is becoming increasingly important for vehicles to smartly make the right driving decisions and autonomously obey traffic rules by correctly recognizing traffic signs. However, for machine learning-based traffic sign recognition on the Internet of Vehicles (IoV), a large amount of traffic sign data from distributed vehicles is needed to be gathered in a centralized server for model training, which brings serious privacy leakage risk because of traffic sign data containing lots of location privacy information. To address this issue, we first exploit privacy-preserving federated learning to perform collaborative training for accurate recognition models without sharing raw traffic sign data. Nevertheless, due to the limited computing and energy resources of most devices, it is hard for vehicles to continuously undertake complex artificial intelligence tasks. Therefore, we introduce powerful Spike Neural Networks (SNNs) into traffic sign recognition for energy-efficient and fast model training, which is the next generation of neural networks and is practical and well-fitted to IoV scenarios. Furthermore, we design a novel encoding scheme for SNNs based on neuron receptive fields to extract information from the pixel and spatial dimensions of traffic signs to achieve high-accuracy training. Numerical results indicate that the proposed federated SNN outperforms traditional federated convolutional neural networks in terms of accuracy, noise immunity, and energy efficiency as well.
Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories
Venue: arXiv cs.LG 2022
Year: 2022

Combinatorial optimisation problems framed as mixed integer linear programmes (MILPs) are ubiquitous across a range of real-world applications. The canonical branch-and-bound algorithm seeks to exactly solve MILPs by constructing a search tree of increasingly constrained sub-problems. In practice, its solving time performance is dependent on heuristics, such as the choice of the next variable to constrain ('branching'). Recently, machine learning (ML) has emerged as a promising paradigm for branching. However, prior works have struggled to apply reinforcement learning (RL), citing sparse rewards, difficult exploration, and partial observability as significant challenges. Instead, leading ML methodologies resort to approximating high quality handcrafted heuristics with imitation learning (IL), which precludes the discovery of novel policies and requires expensive data labelling. In this work, we propose retro branching; a simple yet effective approach to RL for branching. By retrospectively deconstructing the search tree into multiple paths each contained within a sub-tree, we enable the agent to learn from shorter trajectories with more predictable next states. In experiments on four combinatorial tasks, our approach enables learning-to-branch without any expert guidance or pre-training. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables, with ablations verifying that our retrospectively constructed trajectories are essential to achieving these results.
Granular Generalized Variable Precision Rough Sets and Rational Approximations
Venue: arXiv cs.AI 2022
Year: 2022

Rational approximations are introduced and studied in granular graded rough sets and generalizations thereof by the first author in recent research papers. The concept of rationality is determined by related ontologies and coherence between granularity, mereology and approximations in the context. In addition, a framework for rational approximations is introduced by her in the mentioned paper(s). Granular approximations constructed as per the procedures of variable precision rough sets (VPRS) are likely to be more rational than those constructed from a classical perspective under certain conditions. This may continue to hold for some generalizations of the former. However, a formal characterization of such conditions is not available in the previously published literature. In this research, theoretical aspects of the problem are critically examined, uniform generalizations of granular VPRS are introduced, new connections with granular graded rough sets are proved, appropriate concepts of substantial parthood are introduced, their extent of compatibility with the framework is accessed, and the framework is extended. Basic assumptions are explained in detail, and additional examples are constructed for readability. Furthermore, meta applications to cluster validation, image segmentation and dynamic sorting are invented. Extensions to direct generalizations of VPRS such as probabilistic rough sets are a natural consequence of the work.
Characterizing Tourist Daily Trip Chains Using Mobile Phone Big Data
Venue: arXiv cs.SI 2022
Year: 2022

Tourists tend to visit multiple destinations out of their variety-seeking motivations in their trips. Thus, it is critical to discover travel patterns involving multi-destinations in tourism research. Existing relevant research most relied on survey data or focused on citizens due to the lack of large-scale, fine-grained tourism datasets. Several scholars have mentioned the notion of trip chains, but few works have been done towards quantitatively identifying the structures of trip chains. In this paper, we propose a model for quantitatively characterizing tourist daily trip chains. After applying this model to tourist mobile phone big data, underlying tourist travel patterns are discovered. Through the framework, we find that: (1) Most "hybrid" (inter-city and intra-city) and "intra-city" (only intra-city) patterns can be captured by only 13 key trip chains relatively; (2) For two continuous days, almost all kinds of original chains have a rather high probability to transfer to either the first two transferred chains, or other infrequent chains in our study areas; (3) The principle of least efforts (PLE) affects tourists' structures of trip chains. We can use average degree and average travel distance to interpret tourist travel behavior (achieving tasks in PLE). This study not only demonstrate the complex daily travel trip chains from tourism big data, but also fill the gap in tourism literature on multi-destination trips by discovering significant and underlying patterns based on mobile datasets.
Discrimination-Based Double Auction for Maximizing Social Welfare in the Electricity and Heating Market Considering Privacy Preservation
Venue: arXiv cs.GT 2022
Year: 2022

This paper proposes a doubled-sided auction mechanism with price discrimination for social welfare (SW) maximization in the electricity and heating market. In this mechanism, energy service providers (ESPs) submit offers and load aggregators (LAs) submit bids to an energy trading center (ETC) to maximize their utility; in turn, the selfless ETC as an auctioneer leverages dis-criminatory price weights to regulate the behaviors of ESPs and LAs, which combines the individual benefits of each stakeholder with the overall social welfare to achieve the global optimum. Nash games are employed to describe the interactions between players with the same market role. Theoretically, we first prove the existence and uniqueness of the Nash equilibrium; then, considering the requirement of game players to preserve privacy, a distributed algorithm based on the alternating direction method of multipliers is developed to implement distributed bidding and analytical target cascading algorithm is applied to reach the balance of demand and supply. We validated the proposed mechanism using case studies on a city-level distribution system. The results indicated that the achieved SW improved by 4%-15% compared with other mechanisms, and also verified the effectiveness of the distributed algorithm.
Data Generation for Satellite Image Classification Using Self-Supervised Representation Learning
Venue: arXiv cs.CV 2022
Year: 2022

Supervised deep neural networks are the-state-of-the-art for many tasks in the remote sensing domain, against the fact that such techniques require the dataset consisting of pairs of input and label, which are rare and expensive to collect in term of both manpower and resources. On the other hand, there are abundance of raw satellite images available both for commercial and academic purposes. Hence, in this work, we tackle the insufficient labeled data problem in satellite image classification task by introducing the process based on the self-supervised learning technique to create the synthetic labels for satellite image patches. These synthetic labels can be used as the training dataset for the existing supervised learning techniques. In our experiments, we show that the models trained on the synthetic labels give similar performance to the models trained on the real labels. And in the process of creating the synthetic labels, we also obtain the visual representation vectors that are versatile and knowledge transferable.
Looks Like Magic: Transfer Learning in GANs to Generate New Card Illustrations
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we propose MAGICSTYLEGAN and MAGICSTYLEGAN-ADA - both incarnations of the state-of-the-art models StyleGan2 and StyleGan2 ADA - to experiment with their capacity of transfer learning into a rather different domain: creating new illustrations for the vast universe of the game "Magic: The Gathering" cards. This is a challenging task especially due to the variety of elements present in these illustrations, such as humans, creatures, artifacts, and landscapes - not to mention the plethora of art styles of the images made by various artists throughout the years. To solve the task at hand, we introduced a novel dataset, named MTG, with thousands of illustration from diverse card types and rich in metadata. The resulting set is a dataset composed by a myriad of both realistic and fantasy-like illustrations. Although, to investigate effects of diversity we also introduced subsets that contain specific types of concepts, such as forests, islands, faces, and humans. We show that simpler models, such as DCGANs, are not able to learn to generate proper illustrations in any setting. On the other side, we train instances of MAGICSTYLEGAN using all proposed subsets, being able to generate high quality illustrations. We perform experiments to understand how well pre-trained features from StyleGan2 can be transferred towards the target domain. We show that in well trained models we can find particular instances of noise vector that realistically represent real images from the dataset. Moreover, we provide both quantitative and qualitative studies to support our claims, and that demonstrate that MAGICSTYLEGAN is the state-of-the-art approach for generating Magic illustrations. Finally, this paper highlights some emerging properties regarding transfer learning in GANs, which is still a somehow under-explored field in generative learning research.