OpenRaiser/Intern-Atlas huggingface dataset:
A Discriminative Latent-Variable Model for Bilingual Lexicon Induction
Venue: arXiv cs.CL 2024
Year: 2024

We introduce a novel discriminative latent variable model for bilingual lexicon induction. Our model combines the bipartite matching dictionary prior of Haghighi et al. (2008) with a representation-based approach (Artetxe et al., 2017). To train the model, we derive an efficient Viterbi EM algorithm. We provide empirical results on six language pairs under two metrics and show that the prior improves the induced bilingual lexicons. We also demonstrate how previous work may be viewed as a similarly fashioned latent-variable model, albeit with a different prior.
Contextual Hourglass Network for Semantic Segmentation of High Resolution Aerial Imagery
Venue: arXiv cs.CV 2024
Year: 2024

Semantic segmentation for aerial imagery is a challenging and important problem in remotely sensed imagery analysis. In recent years, with the success of deep learning, various convolutional neural network (CNN) based models have been developed. However, due to the varying sizes of the objects and imbalanced class labels, it can be challenging to obtain accurate pixel-wise semantic segmentation results. To address those challenges, we develop a novel semantic segmentation method and call it Contextual Hourglass Network. In our method, in order to improve the robustness of the prediction, we design a new contextual hourglass module which incorporates attention mechanism on processed low-resolution featuremaps to exploit the contextual semantics. We further exploit the stacked encoder-decoder structure by connecting multiple contextual hourglass modules from end to end. This architecture can effectively extract rich multi-scale features and add more feedback loops for better learning contextual semantics through intermediate supervision. To demonstrate the efficacy of our semantic segmentation method, we test it on Potsdam and Vaihingen datasets. Through the comparisons to other baseline methods, our method yields the best results on overall performance.
A Spectral View of Adversarially Robust Features
Venue: arXiv cs.LG 2024
Year: 2024

Given the apparent difficulty of learning models that are robust to adversarial perturbations, we propose tackling the simpler problem of developing adversarially robust features. Specifically, given a dataset and metric of interest, the goal is to return a function (or multiple functions) that 1) is robust to adversarial perturbations, and 2) has significant variation across the datapoints. We establish strong connections between adversarially robust features and a natural spectral property of the geometry of the dataset and metric of interest. This connection can be leveraged to provide both robust features, and a lower bound on the robustness of any function that has significant variance across the dataset. Finally, we provide empirical evidence that the adversarially robust features given by this spectral approach can be fruitfully leveraged to learn a robust (and accurate) model.
On sequential structures in incompressible multidimensional networks
Venue: arXiv cs.IT 2024
Year: 2024

In order to deal with multidimensional structure representations of real-world networks, as well as with their worst-case irreducible information content analysis, the demand for new graph abstractions increases. This article investigates incompressible multidimensional networks defined by generalized graph representations. In particular, we mathematically study the lossless incompressibility of snapshot-dynamic networks and multiplex networks in comparison to the lossless incompressibility of more general forms of dynamic networks and multilayer networks, from which snapshot-dynamic networks or multiplex networks are particular cases. Our theoretical investigation first explores fundamental and basic conditions for connecting the sequential growth of information with sequential interdimensional structures such as time in dynamic networks, and secondly it presents open problems demanding future investigation. Although there may be a dissonance between sequential information dynamics and sequential topology in the general case, we demonstrate that incompressibility dissolves it, preventing both the algorithmic dynamics and the interdimensional structure of multidimensional networks from displaying a snapshot-like behavior (as characterized by any arbitrary mathematical theory). Thus, beyond methods based on statistics or probability as traditionally seen in random graphs and complex networks models, representational incompressibility implies a necessary underlying constraint in the multidimensional network topology. We argue that the study of how isomorphic transformations and their respective algorithmic information distortions can characterize sequential interdimensional structures in (multidimensional) networks helps the analysis of network topological properties while being agnostic to the chosen theory, algorithm, computation model, and programming language.
Effectiveness of Tree-based Ensembles for Anomaly Discovery: Insights, Batch and Streaming Active Learning
Venue: arXiv cs.LG 2024
Year: 2024

In many real-world AD applications including computer security and fraud prevention, the anomaly detector must be configurable by the human analyst to minimize the effort on false positives. One important way to configure the detector is by providing true labels (nominal or anomaly) for a few instances. Recent work on active anomaly discovery has shown that greedily querying the top-scoring instance and tuning the weights of ensemble detectors based on label feedback allows us to quickly discover true anomalies. This paper makes four main contributions to improve the state-of-the-art in anomaly discovery using tree-based ensembles. First, we provide an important insight that explains the practical successes of unsupervised tree-based ensembles and active learning based on greedy query selection strategy. We also present empirical results on real-world data to support our insights and theoretical analysis to support active learning. Second, we develop a novel batch active learning algorithm to improve the diversity of discovered anomalies based on a formalism called compact description to describe the discovered anomalies. Third, we develop a novel active learning algorithm to handle streaming data setting. We present a data drift detection algorithm that not only detects the drift robustly, but also allows us to take corrective actions to adapt the anomaly detector in a principled manner. Fourth, we present extensive experiments to evaluate our insights and our tree-based active anomaly discovery algorithms in both batch and streaming data settings. Our results show that active learning allows us to discover significantly more anomalies than state-of-the-art unsupervised baselines, our batch active learning algorithm discovers diverse anomalies, and our algorithms under the streaming-data setup are competitive with the batch setup.
On Solving Reachability in Grid Digraphs using a Psuedoseparator
Venue: arXiv cs.CC 2024
Year: 2024

The reachability problem asks to decide if there exists a path from one vertex to another in a digraph. In a grid digraph, the vertices are the points of a two-dimensional square grid, and an edge can occur between a vertex and its immediate horizontal and vertical neighbors only. Asano and Doerr (CCCG'11) presented the first simultaneous time-space bound for reachability in grid digraphs by solving the problem in polynomial time and $O(n^{1/2 + ε})$ space. In 2018, the space complexity was improved to $\tilde{O}(n^{1/3})$ by Ashida and Nakagawa (SoCG'18). In this paper, we show that there exists a polynomial-time algorithm that uses $O(n^{1/4 + ε})$ space to solve the reachability problem in a grid digraph containing $n$ vertices. We define and construct a new separator-like device called pseudoseparator to develop a divide-and-conquer algorithm. This algorithm works in a space-efficient manner to solve reachability.
A Session Type System for Asynchronous Unreliable Broadcast Communication
Venue: arXiv cs.LO 2024
Year: 2024

Session types are formal specifications of communication protocols, allowing protocol implementations to be verified by typechecking. Up to now, session type disciplines have assumed that the communication medium is reliable, with no loss of messages. However, unreliable broadcast communication is common in a wide class of distributed systems such as ad-hoc and wireless sensor networks. Often such systems have structured communication patterns that should be amenable to analysis by means of session types, but the necessary theory has not previously been developed. We introduce the Unreliable Broadcast Session Calculus, a process calculus with unreliable broadcast communication, and equip it with a session type system that we show is sound. We capture two common operations, broadcast and gather, inhabiting dual session types. Message loss may lead to non-synchronised session endpoints. To further account for unreliability we provide with an autonomous recovery mechanism that does not require acknowledgements from session participants. Our type system ensures soundness, safety, and progress between the synchronised endpoints within a session. We demonstrate the expressiveness of our framework by implementing Paxos, the textbook protocol for reaching consensus in an unreliable, asynchronous network.
A Review on the Application of Blockchain for the Next Generation of Cybersecure Industry 4.0 Smart Factories
Venue: arXiv cs.DC 2024
Year: 2024

Industry 4.0 is a concept devised for improving the way modern factories operate through the use of some of the latest technologies, like the ones used for creating Industrial Internet of Things (IIoT), robotics or Big Data applications. One of such technologies is blockchain, which is able to add trust, security and decentralization to different industrial fields. This article focuses on analyzing the benefits and challenges that arise when using blockchain and smart contracts to develop Industry 4.0 applications. In addition, this paper presents a thorough review on the most relevant blockchain-based applications for Industry 4.0 technologies. Thus, its aim is to provide a detailed guide for future Industry 4.0 developers that allows for determining how blockchain can enhance the next generation of cybersecure industrial applications.
Model-Based Reinforcement Learning for Atari
Venue: arXiv cs.LG 2024
Year: 2024

Model-free reinforcement learning (RL) can be used to learn effective policies for complex tasks, such as Atari games, even from image observations. However, this typically requires very large amounts of interaction -- substantially more, in fact, than a human would need to learn the same games. How can people learn so quickly? Part of the answer may be that people can learn how the game works and predict which actions will lead to desirable outcomes. In this paper, we explore how video prediction models can similarly enable agents to solve Atari games with fewer interactions than model-free methods. We describe Simulated Policy Learning (SimPLe), a complete model-based deep RL algorithm based on video prediction models and present a comparison of several model architectures, including a novel architecture that yields the best results in our setting. Our experiments evaluate SimPLe on a range of Atari games in low data regime of 100k interactions between the agent and the environment, which corresponds to two hours of real-time play. In most games SimPLe outperforms state-of-the-art model-free algorithms, in some games by over an order of magnitude.
A Concept-Value Network as a Brain Model
Venue: arXiv cs.NE 2024
Year: 2024

This paper suggests a statistical framework for describing the relations between the physical and conceptual entities of a brain-like model. Features and concept instances are put into context, where the paper suggests that features may be the electrical wiring, although chemical connections are also possible. With this idea, the actual length of the connection is important, because it is related to firing rates and neuron synchronization, but the signal type is less important. The paper then suggests that concepts are neuron groups that link feature sets and concept instances are determined by chemical signals from those groups. Therefore, features become the static horizontal framework of the neural system and concepts are vertically interconnected combinations of these. With regards to functionality, the neuron is then considered to be functional and the more horizontal memory structures can even be glial. This would also suggest that features can be distributed entities and not concentrated to a single area. Another aspect could be signal 'breaks' that compartmentalise a pattern and may help with neural binding.
Online Computation with Untrusted Advice
Venue: arXiv cs.DS 2024
Year: 2024

We study a generalization of the advice complexity model of online computation in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust if the advice is adversarial, and efficient is the advice is foolproof. We focus on four well-studied online problems, namely ski rental, online bidding, bin packing and list update. For ski rental and online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the competitive ratios achieved, whereas for bin packing and list update, we give online algorithms with worst-case tradeoffs in their competitiveness, depending on whether the advice is trusted or adversarial. More importantly, we demonstrate how to prove lower bounds, within this model, on the tradeoff between the number of advice bits and the competitiveness of any online algorithm.
Revisiting Shor's quantum algorithm for computing general discrete logarithms
Venue: arXiv cs.CR 2024
Year: 2024

We heuristically show that Shor's algorithm for computing general discrete logarithms achieves an expected success probability of approximately 60% to 82% in a single run when modified to enable efficient implementation with the semi-classical Fourier transform. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the classical post-processing, or by performing two limited searches in the post-processing, we show how the algorithm can be further modified to achieve a success probability that heuristically exceeds 99% in a single run. We provide concrete heuristic estimates of the success probability of the modified algorithm, as a function of the group order $r$, the size of the search space in the classical post-processing, and the additional number of group operations evaluated quantumly. In the limit as $r \rightarrow \infty$, we heuristically show that the success probability tends to one. In analogy with our earlier works, we show how the modified quantum algorithm may be heuristically simulated classically when the logarithm $d$ and $r$ are both known. Furthermore, we heuristically show how slightly better tradeoffs may be achieved, compared to our earlier works, if $r$ is known when computing $d$. We generalize our heuristic to cover some of our earlier works, and compare it to the non-heuristic analyses in those works.
On the Evaluation Metric for Hashing
Venue: arXiv cs.IR 2024
Year: 2024

Due to its low storage cost and fast query speed, hashing has been widely used for large-scale approximate nearest neighbor (ANN) search. Bucket search, also called hash lookup, can achieve fast query speed with a sub-linear time cost based on the inverted index table constructed from hash codes. Many metrics have been adopted to evaluate hashing algorithms. However, all existing metrics are improper to evaluate the hash codes for bucket search. On one hand, all existing metrics ignore the retrieval time cost which is an important factor reflecting the performance of search. On the other hand, some of them, such as mean average precision (MAP), suffer from the uncertainty problem as the ranked list is based on integer-valued Hamming distance, and are insensitive to Hamming radius as these metrics only depend on relative Hamming distance. Other metrics, such as precision at Hamming radius R, fail to evaluate global performance as these metrics only depend on one specific Hamming radius. In this paper, we first point out the problems of existing metrics which have been ignored by the hashing community, and then propose a novel evaluation metric called radius aware mean average precision (RAMAP) to evaluate hash codes for bucket search. Furthermore, two coding strategies are also proposed to qualitatively show the problems of existing metrics. Experiments demonstrate that our proposed RAMAP can provide more proper evaluation than existing metrics.
To Infinity and Beyond: Continuing De Bruijn Sequences by Extending the Alphabet
Venue: arXiv cs.DM 2024
Year: 2024

This article presents proof that the reverse of the Prefer Max De Bruijn sequence can be expanded into an infinite De Bruijn sequence by increasing the size of the alphabet. Furthermore, we show that every De Bruijn sequence possessing this characteristic exhibits behavior similar to that of the reverse of the Prefer Max De Bruijn sequence.
Asymmetric Distributed Trust
Venue: arXiv cs.DC 2024
Year: 2024

Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory, broadcast primitives, and a consensus protocol among processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust.
Interpretable Feature Learning in Multivariate Big Data Analysis for Network Monitoring
Venue: arXiv cs.NI 2024
Year: 2024

There is an increasing interest in the development of new data-driven models useful to assess the performance of communication networks. For many applications, like network monitoring and troubleshooting, a data model is of little use if it cannot be interpreted by a human operator. In this paper, we present an extension of the Multivariate Big Data Analysis (MBDA) methodology, a recently proposed interpretable data analysis tool. In this extension, we propose a solution to the automatic derivation of features, a cornerstone step for the application of MBDA when the amount of data is massive. The resulting network monitoring approach allows us to detect and diagnose disparate network anomalies, with a data-analysis workflow that combines the advantages of interpretable and interactive models with the power of parallel processing. We apply the extended MBDA to two case studies: UGR'16, a benchmark flow-based real-traffic dataset for anomaly detection, and Dartmouth'18, the longest and largest Wi-Fi trace known to date.
Anteater: Interactive Visualization of Program Execution Values in Context
Venue: arXiv cs.HC 2024
Year: 2024

Debugging is famously one the hardest parts in programming. In this paper, we tackle the question: what does a debugging environment look like when we take interactive visualization as a central design principle? We introduce Anteater, an interactive visualization system for tracing and exploring the execution of Python programs. Existing systems often have visualization components built on top of an existing infrastructure. In contrast, Anteater's organization of trace data enables an intermediate representation which can be leveraged to automatically synthesize a variety of visualizations and interactions. These interactive visualizations help with tasks such as discovering important structures in the execution and understanding and debugging unexpected behaviors. To assess the utility of Anteater, we conducted a participant study where programmers completed tasks on their own python programs using Anteater. Finally, we discuss limitations and where further research is needed.
Deep Learning Service for Efficient Data Distribution Aware Sorting
Venue: arXiv cs.DS 2024
Year: 2024

In this paper, we present a neural network-enabled data distribution aware sorting method, coined as NN-sort. Our approach explores the potential of developing deep learning techniques to speed up large-scale sort operations, enabling data distribution aware sorting as a deep learning service. Compared to traditional pairwise comparison-based sorting algorithms, which sort data elements by performing pairwise operations, NN-sort leverages the neural network model to learn the data distribution and uses it to map large-scale data elements into ordered ones. Our experiments demonstrate the significant advantage of using NN-sort. Measurements on both synthetic and real-world datasets show that NN-sort yields 2.18x to 10x performance improvement over traditional sorting algorithms.
Blocking Bandits
Venue: arXiv cs.LG 2024
Year: 2024

We consider a novel stochastic multi-armed bandit setting, where playing an arm makes it unavailable for a fixed number of time slots thereafter. This models situations where reusing an arm too often is undesirable (e.g. making the same product recommendation repeatedly) or infeasible (e.g. compute job scheduling on machines). We show that with prior knowledge of the rewards and delays of all the arms, the problem of optimizing cumulative reward does not admit any pseudo-polynomial time algorithm (in the number of arms) unless randomized exponential time hypothesis is false, by mapping to the PINWHEEL scheduling problem. Subsequently, we show that a simple greedy algorithm that plays the available arm with the highest reward is asymptotically $(1-1/e)$ optimal. When the rewards are unknown, we design a UCB based algorithm which is shown to have $c \log T + o(\log T)$ cumulative regret against the greedy algorithm, leveraging the free exploration of arms due to the unavailability. Finally, when all the delays are equal the problem reduces to Combinatorial Semi-bandits providing us with a lower bound of $c' \log T+ ω(\log T)$.