OpenRaiser/Intern-Atlas huggingface dataset:
The dynamics of belief: continuously monitoring and visualising complex systems
Venue: arXiv cs.AI 2024
Year: 2024

The rise of AI in human contexts places new demands on automated systems to be transparent and explainable. We examine some anthropomorphic ideas and principles relevant to such accountablity in order to develop a theoretical framework for thinking about digital systems in complex human contexts and the problem of explaining their behaviour. Structurally, systems are made of modular and hierachical components, which we abstract in a new system model using notions of modes and mode transitions. A mode is an independent component of the system with its own objectives, monitoring data, and algorithms. The behaviour of a mode, including its transitions to other modes, is determined by functions that interpret each mode's monitoring data in the light of its objectives and algorithms. We show how these belief functions can help explain system behaviour by visualising their evaluation as trajectories in higher-dimensional geometric spaces. These ideas are formalised mathematically by abstract and concrete simplicial complexes. We offer three techniques: a framework for design heuristics, a general system theory based on modes, and a geometric visualisation, and apply them in three types of human-centred systems.
Status Update Control and Analysis under Two-Way Delay
Venue: arXiv cs.IT 2024
Year: 2024

We study status updating under two-way delay in a system consisting of a sampler, a sink, and a controller residing at the sink. The controller controls the sampling process by sending request packets to the sampler. Upon receiving a request, the sampler generates a sample and transmits the status update packet to the sink. Transmissions of both request and status update packets encounter random delays. We develop optimal control policies to minimize the average age of information (AoI) using the tools of Markov decision processes in two scenarios. We begin with the system having at most one active request, i.e., a generated request for which the sink has not yet received a status update packet. Then, as the main distinctive feature of this paper, we initiate pipelining-type status updating by studying a system having at most two active requests. Furthermore, we conduct AoI analysis by deriving the average AoI expressions for the Zero-Wait-1, Zero-Wait-2, and Wait-1 policies. According to the Zero-Wait-1 policy, whenever a status update packet is delivered to the sink, a new request packet is inserted into the system. The Zero-Wait-2 policy operates similarly, except that the system holds two active requests. According to the Wait-1 policy, whenever a status update packet is delivered to the sink, a new request is sent after a waiting time which is a function of the current AoI. Numerical results illustrate the performance of each status updating policy under different system parameter values.
On the Complexity of Distance-$d$ Independent Set Reconfiguration
Venue: arXiv cs.DS 2024
Year: 2024

For a fixed positive integer $d \geq 2$, a distance-$d$ independent set (D$d$IS) of a graph is a vertex subset whose distance between any two members is at least $d$. Imagine that there is a token placed on each member of a D$d$IS. Two D$d$ISs are adjacent under Token Sliding ($\mathsf{TS}$) if one can be obtained from the other by moving a token from one vertex to one of its unoccupied adjacent vertices. Under Token Jumping ($\mathsf{TJ}$), the target vertex needs not to be adjacent to the original one. The Distance-$d$ Independent Set Reconfiguration (D$d$ISR) problem under $\mathsf{TS}/\mathsf{TJ}$ asks if there is a corresponding sequence of adjacent D$d$ISs that transforms one given D$d$IS into another. The problem for $d = 2$, also known as the Independent Set Reconfiguration problem, has been well-studied in the literature and its computational complexity on several graph classes has been known. In this paper, we study the computational complexity of D$d$ISR on different graphs under $\mathsf{TS}$ and $\mathsf{TJ}$ for any fixed $d \geq 3$. On chordal graphs, we show that D$d$ISR under $\mathsf{TJ}$ is in $\mathtt{P}$ when $d$ is even and $\mathtt{PSPACE}$-complete when $d$ is odd. On split graphs, there is an interesting complexity dichotomy: D$d$ISR is $\mathtt{PSPACE}$-complete for $d = 2$ but in $\mathtt{P}$ for $d=3$ under $\mathsf{TS}$, while under $\mathsf{TJ}$ it is in $\mathtt{P}$ for $d = 2$ but $\mathtt{PSPACE}$-complete for $d = 3$. Additionally, certain well-known hardness results for $d = 2$ on perfect graphs and planar graphs of maximum degree three and bounded bandwidth can be extended for $d \geq 3$.
Joint Communication and Channel Discrimination
Venue: arXiv cs.IT 2024
Year: 2024

We consider a basic joint communication and sensing setup comprising a transmitter, a receiver and a sensor. The transmitter sends a codeword to the receiver through a discrete memoryless channel, and the receiver is interested in decoding the transmitted codeword. At the same time, the sensor picks up a noisy version of the transmitted codeword through one of two possible discrete memoryless channels. The sensor knows the codeword and wishes to discriminate between the two possible channels, i.e. to identify the channel that has generated the output given the input. We study the trade-off between communication and sensing in the asymptotic regime, captured in terms of the channel coding rate against the two types of discrimination error exponents. We characterize the optimal trade-off between the rate and the exponents for general discrete memoryless channels with an input cost constraint.
Random Assignment of Indivisible Goods under Constraints
Venue: arXiv cs.GT 2024
Year: 2024

We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions under which there always exists a random assignment that simultaneously satisfies efficiency and envy-freeness. The probabilistic serial mechanism ensures the existence of such an assignment for the unconstrained setting. In this paper, we consider a more general setting in which each agent can consume a set of items only if the set satisfies her feasibility constraint. Such constraints must be taken into account in student course placements, employee shift assignments, and so on. We demonstrate that an efficient and envy-free assignment may not exist even for the simple case of partition matroid constraints, where the items are categorized, and each agent demands one item from each category. We then identify special cases in which an efficient and envy-free assignment always exists. For these cases, the probabilistic serial cannot be naturally extended; therefore, we provide mechanisms to find the desired assignment using various approaches.
Minimum Cost Adaptive Submodular Cover
Venue: arXiv cs.DS 2024
Year: 2024

Adaptive submodularity is a fundamental concept in stochastic optimization, with numerous applications such as sensor placement, hypothesis identification and viral marketing. We consider the problem of minimum cost cover of adaptive-submodular functions, and provide a $4(1+\ln Q)$-approximation algorithm, where $Q$ is the goal value. In fact, we consider a significantly more general objective of minimizing the $p^{th}$ moment of the coverage cost, and show that our algorithm simultaneously achieves a $(p+1)^{p+1}\cdot (\ln Q+1)^p$ approximation guarantee for all $p\ge 1$. All our approximation ratios are best possible up to constant factors (assuming $P\ne NP$). Moreover, our results also extend to the setting where one wants to cover {\em multiple} adaptive-submodular functions. Finally, we evaluate the empirical performance of our algorithm on instances of hypothesis identification.
GraVoS: Voxel Selection for 3D Point-Cloud Detection
Venue: arXiv cs.CV 2024
Year: 2024

3D object detection within large 3D scenes is challenging not only due to the sparsity and irregularity of 3D point clouds, but also due to both the extreme foreground-background scene imbalance and class imbalance. A common approach is to add ground-truth objects from other scenes. Differently, we propose to modify the scenes by removing elements (voxels), rather than adding ones. Our approach selects the "meaningful" voxels, in a manner that addresses both types of dataset imbalance. The approach is general and can be applied to any voxel-based detector, yet the meaningfulness of a voxel is network-dependent. Our voxel selection is shown to improve the performance of several prominent 3D detection methods.
A Survey on Open Radio Access Networks: Challenges, Research Directions, and Open Source Approaches
Venue: arXiv cs.NI 2024
Year: 2024

The open radio access network (RAN) aims to bring openness and intelligence to the traditional closed and proprietary RAN technology and offer flexibility, performance improvement, and cost-efficiency in the RAN deployment and operation. This paper provides a comprehensive survey of the open RAN development. We briefly summarized the RAN evolution history and the state-of-the-art technologies applied in open RAN. The open RAN-related projects, activities, and standardization is then discussed. We then summarize the challenges and future research directions required to support the open RAN. Finally, we discuss some solutions to tackle these issues from the open source's perspective.
A note on incorrect inferences in non-binary qualitative probabilistic networks
Venue: arXiv cs.AI 2024
Year: 2024

Qualitative probabilistic networks (QPNs) combine the conditional independence assumptions of Bayesian networks with the qualitative properties of positive and negative dependence. They formalise various intuitive properties of positive dependence to allow inferences over a large network of variables. However, we will demonstrate in this paper that, due to an incorrect symmetry property, many inferences obtained in non-binary QPNs are not mathematically true. We will provide examples of such incorrect inferences and briefly discuss possible resolutions.
Kernel Memory Networks: A Unifying Framework for Memory Modeling
Venue: arXiv cs.NE 2024
Year: 2024

We consider the problem of training a neural network to store a set of patterns with maximal noise robustness. A solution, in terms of optimal weights and state update rules, is derived by training each individual neuron to perform either kernel classification or interpolation with a minimum weight norm. By applying this method to feed-forward and recurrent networks, we derive optimal models, termed kernel memory networks, that include, as special cases, many of the hetero- and auto-associative memory models that have been proposed over the past years, such as modern Hopfield networks and Kanerva's sparse distributed memory. We modify Kanerva's model and demonstrate a simple way to design a kernel memory network that can store an exponential number of continuous-valued patterns with a finite basin of attraction. The framework of kernel memory networks offers a simple and intuitive way to understand the storage capacity of previous memory models, and allows for new biological interpretations in terms of dendritic non-linearities and synaptic cross-talk.
Hierarchical Compositional Representations for Few-shot Action Recognition
Venue: arXiv cs.CV 2024
Year: 2024

Recently action recognition has received more and more attention for its comprehensive and practical applications in intelligent surveillance and human-computer interaction. However, few-shot action recognition has not been well explored and remains challenging because of data scarcity. In this paper, we propose a novel hierarchical compositional representations (HCR) learning approach for few-shot action recognition. Specifically, we divide a complicated action into several sub-actions by carefully designed hierarchical clustering and further decompose the sub-actions into more fine-grained spatially attentional sub-actions (SAS-actions). Although there exist large differences between base classes and novel classes, they can share similar patterns in sub-actions or SAS-actions. Furthermore, we adopt the Earth Mover's Distance in the transportation problem to measure the similarity between video samples in terms of sub-action representations. It computes the optimal matching flows between sub-actions as distance metric, which is favorable for comparing fine-grained patterns. Extensive experiments show our method achieves the state-of-the-art results on HMDB51, UCF101 and Kinetics datasets.
A Novel Plug-and-Play Approach for Adversarially Robust Generalization
Venue: arXiv cs.LG 2024
Year: 2024

In this work, we propose a robust framework that employs adversarially robust training to safeguard the ML models against perturbed testing data. Our contributions can be seen from both computational and statistical perspectives. Firstly, from a computational/optimization point of view, we derive the ready-to-use exact solution for several widely used loss functions with a variety of norm constraints on adversarial perturbation for various supervised and unsupervised ML problems, including regression, classification, two-layer neural networks, graphical models, and matrix completion. The solutions are either in closed-form, or an easily tractable optimization problem such as 1-D convex optimization, semidefinite programming, difference of convex programming or a sorting-based algorithm. Secondly, from statistical/generalization viewpoint, using some of these results, we derive novel bounds of the adversarial Rademacher complexity for various problems, which entails new generalization bounds. Thirdly, we perform some sanity-check experiments on real-world datasets for supervised problems such as regression and classification, as well as for unsupervised problems such as matrix completion and learning graphical models, with very little computational overhead.
Individual Tree Detection in Large-Scale Urban Environments using High-Resolution Multispectral Imagery
Venue: arXiv cs.CV 2024
Year: 2024

We introduce a novel deep learning method for detection of individual trees in urban environments using high-resolution multispectral aerial imagery. We use a convolutional neural network to regress a confidence map indicating the locations of individual trees, which are localized using a peak finding algorithm. Our method provides complete spatial coverage by detecting trees in both public and private spaces, and can scale to very large areas. We performed a thorough evaluation of our method, supported by a new dataset of over 1,500 images and almost 100,000 tree annotations, covering eight cities, six climate zones, and three image capture years. We trained our model on data from Southern California, and achieved a precision of 73.6% and recall of 73.3% using test data from this region. We generally observed similar precision and slightly lower recall when extrapolating to other California climate zones and image capture dates. We used our method to produce a map of trees in the entire urban forest of California, and estimated the total number of urban trees in California to be about 43.5 million. Our study indicates the potential for deep learning methods to support future urban forestry studies at unprecedented scales.
Robust and Large-Payload DNN Watermarking via Fixed, Distribution-Optimized, Weights
Venue: arXiv cs.CV 2024
Year: 2024

The design of an effective multi-bit watermarking algorithm hinges upon finding a good trade-off between the three fundamental requirements forming the watermarking trade-off triangle, namely, robustness against network modifications, payload, and unobtrusiveness, ensuring minimal impact on the performance of the watermarked network. In this paper, we first revisit the nature of the watermarking trade-off triangle for the DNN case, then we exploit our findings to propose a white-box, multi-bit watermarking method achieving very large payload and strong robustness against network modification. In the proposed system, the weights hosting the watermark are set prior to training, making sure that their amplitude is large enough to bear the target payload and survive network modifications, notably retraining, and are left unchanged throughout the training process. The distribution of the weights carrying the watermark is theoretically optimised to ensure the secrecy of the watermark and make sure that the watermarked weights are indistinguishable from the non-watermarked ones. The proposed method can achieve outstanding performance, with no significant impact on network accuracy, including robustness against network modifications, retraining and transfer learning, while ensuring a payload which is out of reach of state of the art methods achieving a lower - or at most comparable - robustness.
Quo Vadis: Hybrid Machine Learning Meta-Model based on Contextual and Behavioral Malware Representations
Venue: arXiv cs.CR 2024
Year: 2024

We propose a hybrid machine learning architecture that simultaneously employs multiple deep learning models analyzing contextual and behavioral characteristics of Windows portable executable, producing a final prediction based on a decision from the meta-model. The detection heuristic in contemporary machine learning Windows malware classifiers is typically based on the static properties of the sample since dynamic analysis through virtualization is challenging for vast quantities of samples. To surpass this limitation, we employ a Windows kernel emulation that allows the acquisition of behavioral patterns across large corpora with minimal temporal and computational costs. We partner with a security vendor for a collection of more than 100k int-the-wild samples that resemble the contemporary threat landscape, containing raw PE files and filepaths of applications at the moment of execution. The acquired dataset is at least ten folds larger than reported in related works on behavioral malware analysis. Files in the training dataset are labeled by a professional threat intelligence team, utilizing manual and automated reverse engineering tools. We estimate the hybrid classifier's operational utility by collecting an out-of-sample test set three months later from the acquisition of the training set. We report an improved detection rate, above the capabilities of the current state-of-the-art model, especially under low false-positive requirements. Additionally, we uncover a meta-model's ability to identify malicious activity in validation and test sets even if none of the individual models express enough confidence to mark the sample as malevolent. We conclude that the meta-model can learn patterns typical to malicious samples from representation combinations produced by different analysis techniques. We publicly release pre-trained models and anonymized dataset of emulation reports.
Macro Ethics Principles for Responsible AI Systems: Taxonomy and Future Directions
Venue: arXiv cs.CY 2024
Year: 2024

Responsible AI must be able to make or support decisions that consider human values and can be justified by human morals. Accommodating values and morals in responsible decision making is supported by adopting a perspective of macro ethics, which views ethics through a holistic lens incorporating social context. Normative ethical principles inferred from philosophy can be used to methodically reason about ethics and make ethical judgements in specific contexts. Operationalising normative ethical principles thus promotes responsible reasoning under the perspective of macro ethics. We survey AI and computer science literature and develop a taxonomy of 21 normative ethical principles which can be operationalised in AI. We describe how each principle has previously been operationalised, highlighting key themes that AI practitioners seeking to implement ethical principles should be aware of. We envision that this taxonomy will facilitate the development of methodologies to incorporate normative ethical principles in reasoning capacities of responsible AI systems.
BOBA: Byzantine-Robust Federated Learning with Label Skewness
Venue: arXiv cs.LG 2024
Year: 2024

In federated learning, most existing robust aggregation rules (AGRs) combat Byzantine attacks in the IID setting, where client data is assumed to be independent and identically distributed. In this paper, we address label skewness, a more realistic and challenging non-IID setting, where each client only has access to a few classes of data. In this setting, state-of-the-art AGRs suffer from selection bias, leading to significant performance drop for particular classes; they are also more vulnerable to Byzantine attacks due to the increased variation among gradients of honest clients. To address these limitations, we propose an efficient two-stage method named BOBA. Theoretically, we prove the convergence of BOBA with an error of the optimal order. Our empirical evaluations demonstrate BOBA's superior unbiasedness and robustness across diverse models and datasets when compared to various baselines. Our code is available at https://github.com/baowenxuan/BOBA .
Information FOMO: The unhealthy fear of missing out on information. A method for removing misleading data for healthier models
Venue: arXiv cs.LG 2024
Year: 2024

Misleading or unnecessary data can have out-sized impacts on the health or accuracy of Machine Learning (ML) models. We present a Bayesian sequential selection method, akin to Bayesian experimental design, that identifies critically important information within a dataset, while ignoring data that is either misleading or brings unnecessary complexity to the surrogate model of choice. Our method improves sample-wise error convergence and eliminates instances where more data leads to worse performance and instabilities of the surrogate model, often termed sample-wise ``double descent''. We find these instabilities are a result of the complexity of the underlying map and linked to extreme events and heavy tails. Our approach has two key features. First, the selection algorithm dynamically couples the chosen model and data. Data is chosen based on its merits towards improving the selected model, rather than being compared strictly against other data. Second, a natural convergence of the method removes the need for dividing the data into training, testing, and validation sets. Instead, the selection metric inherently assesses testing and validation error through global statistics of the model. This ensures that key information is never wasted in testing or validation. The method is applied using both Gaussian process regression and deep neural network surrogate models.
naab: A ready-to-use plug-and-play corpus for Farsi
Venue: arXiv cs.CL 2024
Year: 2024

The rise of large language models (LLMs) has transformed numerous natural language processing (NLP) tasks, yet their performance in low and mid-resource languages, such as Farsi, still lags behind resource-rich languages like English. To address this gap, we introduce naab, the largest publicly available, cleaned, and ready-to-use Farsi textual corpus. naab consists of 130GB of data, comprising over 250 million paragraphs and 15 billion words. Named after the Farsi word NAAB (meaning "pure" or "high-grade"), this corpus is openly accessible via Hugging Face, offering researchers a valuable resource for Farsi NLP tasks. In addition to naab, we provide naab-raw, an unprocessed version of the dataset, along with a pre-processing toolkit that allows users to clean their custom corpora. These resources empower NLP researchers and practitioners, particularly those focusing on low-resource languages, to improve the performance of LLMs in their respective domains and bridge the gap between resource-rich and resource-poor languages.