OpenRaiser/Intern-Atlas huggingface dataset:
Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation
Venue: arXiv cs.LG 2022
Year: 2022

Myopic exploration policies such as epsilon-greedy, softmax, or Gaussian noise fail to explore efficiently in some reinforcement learning tasks and yet, they perform well in many others. In fact, in practice, they are often selected as the top choices, due to their simplicity. But, for what tasks do such policies succeed? Can we give theoretical guarantees for their favorable performance? These crucial questions have been scarcely investigated, despite the prominent practical importance of these policies. This paper presents a theoretical analysis of such policies and provides the first regret and sample-complexity bounds for reinforcement learning with myopic exploration. Our results apply to value-function-based algorithms in episodic MDPs with bounded Bellman Eluder dimension. We propose a new complexity measure called myopic exploration gap, denoted by alpha, that captures a structural property of the MDP, the exploration policy and the given value function class. We show that the sample-complexity of myopic exploration scales quadratically with the inverse of this quantity, 1 / alpha^2. We further demonstrate through concrete examples that myopic exploration gap is indeed favorable in several tasks where myopic exploration succeeds, due to the corresponding dynamics and reward structure.
Construction and Optimization of TRNG Based Substitution Boxes for Block Encryption Algorithms
Venue: arXiv cs.CR 2022
Year: 2022

Internet of Things is an ecosystem of interconnected devices that are accessible through the internet. The recent research focuses on adding more smartness and intelligence to these edge devices. This makes them susceptible to various kinds of security threats. These edge devices rely on cryptographic techniques to encrypt the pre-processed data collected from the sensors deployed in the field. In this regard, block cipher has been one of the most reliable options through which data security is accomplished. The strength of block encryption algorithms against different attacks is dependent on its nonlinear primitive which is called Substitution Boxes. For the design of S-boxes mainly algebraic and chaos-based techniques are used but researchers also found various weaknesses in these techniques. On the other side, literature endorse the true random numbers for information security due to the reason that, true random numbers are purely non-deterministic. In this paper firstly a natural dynamical phenomenon is utilized for the generation of true random numbers based S-boxes. Secondly, a systematic literature review was conducted to know which metaheuristic optimization technique is highly adopted in the current decade for the optimization of S-boxes. Based on the outcome of Systematic Literature Review (SLR), genetic algorithm is chosen for the optimization of s-boxes. The results of our method validate that the proposed dynamic S-boxes are effective for the block ciphers. Moreover, our results showed that the proposed substitution boxes achieve better
Cybersecurity Law: Legal Jurisdiction and Authority
Venue: arXiv cs.SI 2022
Year: 2022

Cybersecurity threats affect all aspects of society; critical infrastructures (such as networks, corporate systems, water supply systems, and intelligent transportation systems) are especially prone to attacks and can have tangible negative consequences on society. However, these critical cyber systems are generally governed by multiple jurisdictions, for instance the Metro in the Washington, D.C. area is managed by the states of Virginia and Maryland, as well as the District of Columbia (DC) through Washington Metropolitan Area Transit Authority (WMATA). Additionally, the water treatment infrastructure managed by DC Water consists of waste water input from Fairfax and Arlington counties, and the district (i.e. DC). Additionally, cyber attacks usually launch from unknown sources, through unknown switches and servers, and end up at the destination without much knowledge on their source or path. Certain infrastructures are shared amongst multiple countries, another idiosyncrasy that exacerbates the issue of governance. This law paper however, is not concerned with the general governance of these infrastructures, rather with the ambiguity in the relevant laws or doctrines about which authority would prevail in the context of a cyber threat or a cyber-attack, with a focus on federal vs. state issues, international law involvement, federal preemption, technical aspects that could affect lawmaking, and conflicting responsibilities in cases of cyber crime. A legal analysis of previous cases is presented, as well as an extended discussion addressing different sides of the argument.
Predicting Human Performance in Vertical Hierarchical Menu Selection in Immersive AR Using Hand-gesture and Head-gaze
Venue: arXiv cs.HC 2022
Year: 2022

There are currently limited guidelines on designing user interfaces (UI) for immersive augmented reality (AR) applications. Designers must reflect on their experience designing UI for desktop and mobile applications and conjecture how a UI will influence AR users' performance. In this work, we introduce a predictive model for determining users' performance for a target UI without the subsequent involvement of participants in user studies. The model is trained on participants' responses to objective performance measures such as consumed endurance (CE) and pointing time (PT) using hierarchical drop-down menus. Large variability in the depth and context of the menus is ensured by randomly and dynamically creating the hierarchical drop-down menus and associated user tasks from words contained in the lexical database WordNet. Subjective performance bias is reduced by incorporating the users' non-verbal standard performance WAIS-IV during the model training. The semantic information of the menu is encoded using the Universal Sentence Encoder. We present the results of a user study that demonstrates that the proposed predictive model achieves high accuracy in predicting the CE on hierarchical menus of users with various cognitive abilities. To the best of our knowledge, this is the first work on predicting CE in designing UI for immersive AR applications.
ILX: Intelligent "Location+X" Data Systems (Vision Paper)
Venue: arXiv cs.DB 2022
Year: 2022

Due to the ubiquity of mobile phones and location-detection devices, location data is being generated in very large volumes. Queries and operations that are performed on location data warrant the use of database systems. Despite that, location data is being supported in data systems as an afterthought. Typically, relational or NoSQL data systems that are mostly designed with non-location data in mind get extended with spatial or spatiotemporal indexes, some query operators, and higher level syntactic sugar in order to support location data. The ubiquity of location data and location data services call for systems that are solely designed and optimized for the efficient support of location data. This paper envisions designing intelligent location+X data systems, ILX for short, where location is treated as a first-class citizen type. ILX is tailored with location data as the main data type (location-first). Because location data is typically augmented with other data types X, e.g., graphs, text data, click streams, annotations, etc., ILX needs to be extensible to support other data types X along with location. This paper envisions the main features that ILX should support, and highlights research challenges in realizing and supporting ILX.
Variational Distillation for Multi-View Learning
Venue: arXiv cs.CV 2022
Year: 2022

Information Bottleneck (IB) based multi-view learning provides an information theoretic principle for seeking shared information contained in heterogeneous data descriptions. However, its great success is generally attributed to estimate the multivariate mutual information which is intractable when the network becomes complicated. Moreover, the representation learning tradeoff, {\it i.e.}, prediction-compression and sufficiency-consistency tradeoff, makes the IB hard to satisfy both requirements simultaneously. In this paper, we design several variational information bottlenecks to exploit two key characteristics ({\it i.e.}, sufficiency and consistency) for multi-view representation learning. Specifically, we propose a Multi-View Variational Distillation (MV$^2$D) strategy to provide a scalable, flexible and analytical solution to fitting MI by giving arbitrary input of viewpoints but without explicitly estimating it. Under rigorously theoretical guarantee, our approach enables IB to grasp the intrinsic correlation between observations and semantic labels, producing predictive and compact representations naturally. Also, our information-theoretic constraint can effectively neutralize the sensitivity to heterogeneous data by eliminating both task-irrelevant and view-specific information, preventing both tradeoffs in multiple view cases. To verify our theoretically grounded strategies, we apply our approaches to various benchmarks under three different applications. Extensive experiments to quantitatively and qualitatively demonstrate the effectiveness of our approach against state-of-the-art methods.
C-SENN: Contrastive Self-Explaining Neural Network
Venue: arXiv cs.CV 2022
Year: 2022

In this study, we use a self-explaining neural network (SENN), which learns unsupervised concepts, to acquire concepts that are easy for people to understand automatically. In concept learning, the hidden layer retains verbalizable features relevant to the output, which is crucial when adapting to real-world environments where explanations are required. However, it is known that the interpretability of concepts output by SENN is reduced in general settings, such as autonomous driving scenarios. Thus, this study combines contrastive learning with concept learning to improve the readability of concepts and the accuracy of tasks. We call this model Contrastive Self-Explaining Neural Network (C-SENN).
5th Place Solution for YouTube-VOS Challenge 2022: Video Object Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Video object segmentation (VOS) has made significant progress with the rise of deep learning. However, there still exist some thorny problems, for example, similar objects are easily confused and tiny objects are difficult to be found. To solve these problems and further improve the performance of VOS, we propose a simple yet effective solution for this task. In the solution, we first analyze the distribution of the Youtube-VOS dataset and supplement the dataset by introducing public static and video segmentation datasets. Then, we improve three network architectures with different characteristics and train several networks to learn the different characteristics of objects in videos. After that, we use a simple way to integrate all results to ensure that different models complement each other. Finally, subtle post-processing is carried out to ensure accurate video object segmentation with precise boundaries. Extensive experiments on Youtube-VOS dataset show that the proposed solution achieves the state-of-the-art performance with an 86.1% overall score on the YouTube-VOS 2022 test set, which is 5th place on the video object segmentation track of the Youtube-VOS Challenge 2022.
NLOS Ranging Mitigation with Neural Network Model for UWB Localization
Venue: arXiv cs.RO 2022
Year: 2022

Localization of robots is vital for navigation and path planning, such as in cases where a map of the environment is needed. Ultra-Wideband (UWB) for indoor location systems has been gaining popularity over the years with the introduction of low-cost UWB modules providing centimetre-level accuracy. However, in the presence of obstacles in the environment, Non-Line-Of-Sight (NLOS) measurements from the UWB will produce inaccurate results. As low-cost UWB devices do not provide channel information, we propose an approach to decide if a measurement is within Line-Of-Sight (LOS) or not by using some signal strength information provided by low-cost UWB modules through a Neural Network (NN) model. The result of this model is the probability of a ranging measurement being LOS which was used for localization through the Weighted-Least-Square (WLS) method. Our approach improves localization accuracy by 16.93% on the lobby testing data and 27.97% on the corridor testing data using the NN model trained with all extracted inputs from the office training data.
Analyzing Büchi Automata with Graph Neural Networks
Venue: arXiv cs.FL 2022
Year: 2022

Büchi Automata on infinite words present many interesting problems and are used frequently in program verification and model checking. A lot of these problems on Büchi automata are computationally hard, raising the question if a learning-based data-driven analysis might be more efficient than using traditional algorithms. Since Büchi automata can be represented by graphs, graph neural networks are a natural choice for such a learning-based analysis. In this paper, we demonstrate how graph neural networks can be used to reliably predict basic properties of Büchi automata when trained on automatically generated random automata datasets.
FoR$^2$M: Recognition and Repair of Foldings in Mesh Surfaces. Application to 3D Object Degradation
Venue: arXiv cs.CG 2022
Year: 2022

Triangular meshes are the most popular representations of 3D objects, but many mesh surfaces contain topological singularities that represent a challenge for displaying or further processing them properly. One such singularity is the self-intersections that may be present in mesh surfaces that have been created by a scanning procedure or by a deformation transformation, such as off-setting. Mesh foldings comprise a special case of mesh surface self-intersections, where the faces of the 3D model intersect and become reversed, with respect to the unfolded part of the mesh surface. A novel method for the recognition and repair of mesh surface foldings is presented, which exploits the structural characteristics of the foldings in order to efficiently detect the folded regions. Following detection, the foldings are removed and any gaps so created are filled based on the geometry of the 3D model. The proposed method is directly applicable to simple mesh surface representations while it does not perform any embedding of the 3D mesh (i.e. voxelization, projection). Target of the proposed method is to facilitate mesh degradation procedures in a fashion that retains the original structure, given the operator, in the most efficient manner.
A Systematic Mapping Study Addressing the Reliability of Mobile Applications: The Need to Move Beyond Testing Reliability
Venue: arXiv cs.SE 2022
Year: 2022

Intense competition in the mobile apps market means it is important to maintain high levels of app reliability to avoid losing users. Yet despite its importance, app reliability is underexplored in the research literature. To address this need, we identify, analyse, and classify the state-of-the-art in the field of mobile apps' reliability through a systematic mapping study. From the results of such a study, researchers in the field can identify pressing research gaps, and developers can gain knowledge about existing solutions, to potentially leverage them in practice. We found 87 relevant papers which were then analysed and classified based on their research focus, research type, contribution, research method, study settings, data, quality attributes and metrics used. Results indicate that there is a lack of research on understanding reliability with regard to context-awareness, self-healing, ageing and rejuvenation, and runtime event handling. These aspects have rarely been studied, or if studied, there is limited evaluation. We also identified several other research gaps including the need to conduct more research in real-world industrial projects. Furthermore, little attention has been paid towards quality standards while conducting research. Outcomes here show numerous opportunities for greater research depth and breadth on mobile app reliability.
Entanglement-Assisted and Subsystem Quantum Codes: New Propagation Rules and Constructions
Venue: arXiv cs.IT 2022
Year: 2022

This paper proposes new propagation rules on quantum codes in the entanglement-assisted and in quantum subsystem scenarios. The rules lead to new families of such quantum codes whose parameters are demonstrably optimal. To obtain the results, we devise tools to puncture and shorten codes in ways that ensure their Hermitian hulls have certain desirable properties. More specifically, we give a general framework to construct $k$-dimensional generalized Reed-Solomon codes whose Hermitian hulls are $(k-1)$-dimensional maximum distance separable codes.
Fewer Errors, but More Stereotypes? The Effect of Model Size on Gender Bias
Venue: arXiv cs.CL 2022
Year: 2022

The size of pretrained models is increasing, and so is their performance on a variety of NLP tasks. However, as their memorization capacity grows, they might pick up more social biases. In this work, we examine the connection between model size and its gender bias (specifically, occupational gender bias). We measure bias in three masked language model families (RoBERTa, DeBERTa, and T5) in two setups: directly using prompt based method, and using a downstream task (Winogender). We find on the one hand that larger models receive higher bias scores on the former task, but when evaluated on the latter, they make fewer gender errors. To examine these potentially conflicting results, we carefully investigate the behavior of the different models on Winogender. We find that while larger models outperform smaller ones, the probability that their mistakes are caused by gender bias is higher. Moreover, we find that the proportion of stereotypical errors compared to anti-stereotypical ones grows with the model size. Our findings highlight the potential risks that can arise from increasing model size.
Finding $k$-Secluded Trees Faster
Venue: arXiv cs.DS 2022
Year: 2022

We revisit the \textsc{$k$-Secluded Tree} problem. Given a vertex-weighted undirected graph $G$, its objective is to find a maximum-weight induced subtree $T$ whose open neighborhood has size at most $k$. We present a fixed-parameter tractable algorithm that solves the problem in time $2^{\mathcal{O}(k \log k)}\cdot n^{\mathcal{O}(1)}$, improving on a double-exponential running time from earlier work by Golovach, Heggernes, Lima, and Montealegre. Starting from a single vertex, our algorithm grows a $k$-secluded tree by branching on vertices in the open neighborhood of the current tree $T$. To bound the branching depth, we prove a structural result that can be used to identify a vertex that belongs to the neighborhood of any $k$-secluded supertree $T' \supseteq T$ once the open neighborhood of $T$ becomes sufficiently large. We extend the algorithm to enumerate compact descriptions of all maximum-weight $k$-secluded trees, which allows us to count the number of maximum-weight $k$-secluded trees containing a specified vertex in the same running time.
flow-based clustering and spectral clustering: a comparison
Venue: arXiv cs.LG 2022
Year: 2022

We propose and study a novel graph clustering method for data with an intrinsic network structure. Similar to spectral clustering, we exploit an intrinsic network structure of data to construct Euclidean feature vectors. These feature vectors can then be fed into basic clustering methods such as k-means or Gaussian mixture model (GMM) based soft clustering. What sets our approach apart from spectral clustering is that we do not use the eigenvectors of a graph Laplacian to construct the feature vectors. Instead, we use the solutions of total variation minimization problems to construct feature vectors that reflect connectivity between data points. Our motivation is that the solutions of total variation minimization are piece-wise constant around a given set of seed nodes. These seed nodes can be obtained from domain knowledge or by simple heuristics that are based on the network structure of data. Our results indicate that our clustering methods can cope with certain graph structures that are challenging for spectral clustering methods.
SynWMD: Syntax-aware Word Mover's Distance for Sentence Similarity Evaluation
Venue: arXiv cs.CL 2022
Year: 2022

Word Mover's Distance (WMD) computes the distance between words and models text similarity with the moving cost between words in two text sequences. Yet, it does not offer good performance in sentence similarity evaluation since it does not incorporate word importance and fails to take inherent contextual and structural information in a sentence into account. An improved WMD method using the syntactic parse tree, called Syntax-aware Word Mover's Distance (SynWMD), is proposed to address these two shortcomings in this work. First, a weighted graph is built upon the word co-occurrence statistics extracted from the syntactic parse trees of sentences. The importance of each word is inferred from graph connectivities. Second, the local syntactic parsing structure of words is considered in computing the distance between words. To demonstrate the effectiveness of the proposed SynWMD, we conduct experiments on 6 textual semantic similarity (STS) datasets and 4 sentence classification datasets. Experimental results show that SynWMD achieves state-of-the-art performance on STS tasks. It also outperforms other WMD-based methods on sentence classification tasks.
Fast and Safe Aerial Payload Transport in Urban Areas
Venue: arXiv cs.RO 2022
Year: 2022

This paper studies the problem of fast and safe aerial payload transport by a single quadcopter in urban areas. The quadcopter payload system (QPS) is considered as a rigid body and modeled with a nonlinear dynamics. The urban area is modeled as an obstacle-laden environment with obstacle geometries obtained by incorporating realistic LIDAR data. Our approach for payload transport is decomposed into high-level motion planning and low-level trajectory control. For the low-level trajectory tracking, a feedback linearization control is applied to stably track the desired trajectory of the quadcopter. For high-level motion planning, we integrate A* search and polynomial planning to define a safe trajectory for the quadcopter assuring collision avoidance, boundedness of the quadcopter rotor speeds and tracking error, and fast arrival to a target destination from an arbitrary initial location.
Bio-inspired Neural Network-based Optimal Path Planning for UUVs under the Effect of Ocean Currents
Venue: arXiv cs.RO 2022
Year: 2022

To eliminate the effect of ocean currents when addressing the optimal path in the underwater environment, an intelligent algorithm designed for the unmanned underwater vehicle (UUV) is proposed in this paper. The algorithm consists of two parts: a neural network-based algorithm that deducts the shortest path and avoids all possible collisions; and an adjusting component that balances off the deviation brought by the effect of ocean currents. The optimization results of the proposed algorithm are presented in detail, and compared with the path planning algorithm that does not consider the effect of currents. Results of the comparison prove the effectiveness of the path planning method when encountering currents of different directions and velocities.
Renormalized Sparse Neural Network Pruning
Venue: arXiv cs.LG 2022
Year: 2022

Large neural networks are heavily over-parameterized. This is done because it improves training to optimality. However once the network is trained, this means many parameters can be zeroed, or pruned, leaving an equivalent sparse neural network. We propose renormalizing sparse neural networks in order to improve accuracy. We prove that our method's error converges to zero as network parameters cluster or concentrate. We prove that without renormalizing, the error does not converge to zero in general. We experiment with our method on real world datasets MNIST, Fashion MNIST, and CIFAR-10 and confirm a large improvement in accuracy with renormalization versus standard pruning.