OpenRaiser/Intern-Atlas huggingface dataset:
Deployment of Real-Time Network Traffic Analysis using GraphBLAS Hypersparse Matrices and D4M Associative Arrays
Venue: arXiv cs.NI 2023
Year: 2023

Matrix/array analysis of networks can provide significant insight into their behavior and aid in their operation and protection. Prior work has demonstrated the analytic, performance, and compression capabilities of GraphBLAS (graphblas.org) hypersparse matrices and D4M (d4m.mit.edu) associative arrays (a mathematical superset of matrices). Obtaining the benefits of these capabilities requires integrating them into operational systems, which comes with its own unique challenges. This paper describes two examples of real-time operational implementations. First, is an operational GraphBLAS implementation that constructs anonymized hypersparse matrices on a high-bandwidth network tap. Second, is an operational D4M implementation that analyzes daily cloud gateway logs. The architectures of these implementations are presented. Detailed measurements of the resources and the performance are collected and analyzed. The implementations are capable of meeting their operational requirements using modest computational resources (a couple of processing cores). GraphBLAS is well-suited for low-level analysis of high-bandwidth connections with relatively structured network data. D4M is well-suited for higher-level analysis of more unstructured data. This work demonstrates that these technologies can be implemented in operational settings.
Adaptive Adversarial Training Does Not Increase Recourse Costs
Venue: arXiv cs.LG 2023
Year: 2023

Recent work has connected adversarial attack methods and algorithmic recourse methods: both seek minimal changes to an input instance which alter a model's classification decision. It has been shown that traditional adversarial training, which seeks to minimize a classifier's susceptibility to malicious perturbations, increases the cost of generated recourse; with larger adversarial training radii correlating with higher recourse costs. From the perspective of algorithmic recourse, however, the appropriate adversarial training radius has always been unknown. Another recent line of work has motivated adversarial training with adaptive training radii to address the issue of instance-wise variable adversarial vulnerability, showing success in domains with unknown attack radii. This work studies the effects of adaptive adversarial training on algorithmic recourse costs. We establish that the improvements in model robustness induced by adaptive adversarial training show little effect on algorithmic recourse costs, providing a potential avenue for affordable robustness in domains where recoursability is critical.
A d-summable approach to Deng information dimension of complex networks
Venue: arXiv cs.IT 2023
Year: 2023

Several new network information dimension definitions have been proposed in recent decades, expanding the scope of applicability of this seminal tool. This paper proposes a new definition based on Deng entropy and d-summability (a concept from geometric measure theory). We will prove to what extent the new formulation will be useful in the theoretical and applied points of view.
Continual Improvement of Threshold-Based Novelty Detection
Venue: arXiv cs.LG 2023
Year: 2023

When evaluated in dynamic, open-world situations, neural networks struggle to detect unseen classes. This issue complicates the deployment of continual learners in realistic environments where agents are not explicitly informed when novel categories are encountered. A common family of techniques for detecting novelty relies on thresholds of similarity between observed data points and the data used for training. However, these methods often require manually specifying (ahead of time) the value of these thresholds, and are therefore incapable of adapting to the nature of the data. We propose a new method for automatically selecting these thresholds utilizing a linear search and leave-one-out cross-validation on the ID classes. We demonstrate that this novel method for selecting thresholds results in improved total accuracy on MNIST, Fashion MNIST, and CIFAR-10.
Sparse Partitioning Around Medoids
Venue: arXiv cs.LG 2023
Year: 2023

Partitioning Around Medoids (PAM, k-Medoids) is a popular clustering technique to use with arbitrary distance functions or similarities, where each cluster is represented by its most central object, called the medoid or the discrete median. In operations research, this family of problems is also known as facility location problem (FLP). FastPAM recently introduced a speedup for large k to make it applicable for larger problems, but the method still has a runtime quadratic in N. In this chapter, we discuss a sparse and asymmetric variant of this problem, to be used for example on graph data such as road networks. By exploiting sparsity, we can avoid the quadratic runtime and memory requirements, and make this method scalable to even larger problems, as long as we are able to build a small enough graph of sufficient connectivity to perform local optimization. Furthermore, we consider asymmetric cases, where the set of medoids is not identical to the set of points to be covered (or in the interpretation of facility location, where the possible facility locations are not identical to the consumer locations). Because of sparsity, it may be impossible to cover all points with just k medoids for too small k, which would render the problem unsolvable, and this breaks common heuristics for finding a good starting condition. We, hence, consider determining k as a part of the optimization problem and propose to first construct a greedy initial solution with a larger k, then to optimize the problem by alternating between PAM-style "swap" operations where the result is improved by replacing medoids with better alternatives and "remove" operations to reduce the number of k until neither allows further improving the result quality. We demonstrate the usefulness of this method on a problem from electrical engineering, with the input graph derived from cartographic data.
Experience Capture in Shipbuilding through Computer Applications and Neural Networks
Venue: arXiv cs.SI 2023
Year: 2023

It has always been a severe loss for any establishment when an experienced hand retires or moves to another firm. The specific details of what his job/position entails will always make the work more efficient. To curtail such losses, it is possible to implement a system that takes input from a new employee regarding the challenges he/she is facing and match it to a previous occurrence where someone else held his/her chair. This system could be made possible with input through the ages from the array of individuals who managed that particular job and processing this data through a neural network that recognizes the pattern. The paper is based on data collected from traditional wooden dhow builders and some of the modern day unconventional shipyards. Since the requirements for successful implementation in such scenarios seems too steep at the moment, an alternate approach has been suggested by implementation through the design processes across multiple shipyards. The process entails the traditional value passed down through generations regarding a particular profession and analysis has been done regarding how this knowledge/experience can be captured and preserved for future generations to work upon. A series of tools including SharePoint, MATLAB, and some similar software working in tandem can be used for the design of the same. This research will provide valuable insight as to how information sharing can be applied through generations for effective application of production capabilities.
In Situ Soil Property Estimation for Autonomous Earthmoving Using Physics-Infused Neural Networks
Venue: arXiv cs.RO 2023
Year: 2023

A novel, learning-based method for in situ estimation of soil properties using a physics-infused neural network (PINN) is presented. The network is trained to produce estimates of soil cohesion, angle of internal friction, soil-tool friction, soil failure angle, and residual depth of cut which are then passed through an earthmoving model based on the fundamental equation of earthmoving (FEE) to produce an estimated force. The network ingests a short history of kinematic observations along with past control commands and predicts interaction forces accurately with average error of less than 2kN, 13% of the measured force. To validate the approach, an earthmoving simulation of a bladed vehicle is developed using Vortex Studio, enabling comparison of the estimated parameters to pseudo-ground-truth values which is challenging in real-world experiments. The proposed approach is shown to enable accurate estimation of interaction forces and produces meaningful parameter estimates even when the model and the environmental physics deviate substantially.
Comparative Evaluation of Metaheuristic Algorithms for Hyperparameter Selection in Short-Term Weather Forecasting
Venue: arXiv cs.NE 2023
Year: 2023

Weather forecasting plays a vital role in numerous sectors, but accurately capturing the complex dynamics of weather systems remains a challenge for traditional statistical models. Apart from Auto Regressive time forecasting models like ARIMA, deep learning techniques (Vanilla ANNs, LSTM and GRU networks), have shown promise in improving forecasting accuracy by capturing temporal dependencies. This paper explores the application of metaheuristic algorithms, namely Genetic Algorithm (GA), Differential Evolution (DE), and Particle Swarm Optimization (PSO), to automate the search for optimal hyperparameters in these model architectures. Metaheuristic algorithms excel in global optimization, offering robustness, versatility, and scalability in handling non-linear problems. We present a comparative analysis of different model architectures integrated with metaheuristic optimization, evaluating their performance in weather forecasting based on metrics such as Mean Squared Error (MSE) and Mean Absolute Percentage Error (MAPE). The results demonstrate the potential of metaheuristic algorithms in enhancing weather forecasting accuracy \& helps in determining the optimal set of hyper-parameters for each model. The paper underscores the importance of harnessing advanced optimization techniques to select the most suitable metaheuristic algorithm for the given weather forecasting task.
Music Source Separation with Band-Split RoPE Transformer
Venue: arXiv cs.SD 2023
Year: 2023

Music source separation (MSS) aims to separate a music recording into multiple musically distinct stems, such as vocals, bass, drums, and more. Recently, deep learning approaches such as convolutional neural networks (CNNs) and recurrent neural networks (RNNs) have been used, but the improvement is still limited. In this paper, we propose a novel frequency-domain approach based on a Band-Split RoPE Transformer (called BS-RoFormer). BS-RoFormer relies on a band-split module to project the input complex spectrogram into subband-level representations, and then arranges a stack of hierarchical Transformers to model the inner-band as well as inter-band sequences for multi-band mask estimation. To facilitate training the model for MSS, we propose to use the Rotary Position Embedding (RoPE). The BS-RoFormer system trained on MUSDB18HQ and 500 extra songs ranked the first place in the MSS track of Sound Demixing Challenge (SDX23). Benchmarking a smaller version of BS-RoFormer on MUSDB18HQ, we achieve state-of-the-art result without extra training data, with 9.80 dB of average SDR.
Epi-Curriculum: Episodic Curriculum Learning for Low-Resource Domain Adaptation in Neural Machine Translation
Venue: arXiv cs.LG 2023
Year: 2023

Neural Machine Translation (NMT) models have become successful, but their performance remains poor when translating on new domains with a limited number of data. In this paper, we present a novel approach Epi-Curriculum to address low-resource domain adaptation (DA), which contains a new episodic training framework along with denoised curriculum learning. Our episodic training framework enhances the model's robustness to domain shift by episodically exposing the encoder/decoder to an inexperienced decoder/encoder. The denoised curriculum learning filters the noised data and further improves the model's adaptability by gradually guiding the learning process from easy to more difficult tasks. Experiments on English-German and English-Romanian translation show that: (i) Epi-Curriculum improves both model's robustness and adaptability in seen and unseen domains; (ii) Our episodic training framework enhances the encoder and decoder's robustness to domain shift.
Fast and Resource-Efficient Object Tracking on Edge Devices: A Measurement Study
Venue: arXiv cs.CV 2023
Year: 2023

Object tracking is an important functionality of edge video analytic systems and services. Multi-object tracking (MOT) detects the moving objects and tracks their locations frame by frame as real scenes are being captured into a video. However, it is well known that real time object tracking on the edge poses critical technical challenges, especially with edge devices of heterogeneous computing resources. This paper examines the performance issues and edge-specific optimization opportunities for object tracking. We will show that even the well trained and optimized MOT model may still suffer from random frame dropping problems when edge devices have insufficient computation resources. We present several edge specific performance optimization strategies, collectively coined as EMO, to speed up the real time object tracking, ranging from window-based optimization to similarity based optimization. Extensive experiments on popular MOT benchmarks demonstrate that our EMO approach is competitive with respect to the representative methods for on-device object tracking techniques in terms of run-time performance and tracking accuracy. EMO is released on Github at https://github.com/git-disl/EMO.
Geometry of Sensitivity: Twice Sampling and Hybrid Clipping in Differential Privacy with Optimal Gaussian Noise and Application to Deep Learning
Venue: arXiv cs.CR 2023
Year: 2023

We study the fundamental problem of the construction of optimal randomization in Differential Privacy. Depending on the clipping strategy or additional properties of the processing function, the corresponding sensitivity set theoretically determines the necessary randomization to produce the required security parameters. Towards the optimal utility-privacy tradeoff, finding the minimal perturbation for properly-selected sensitivity sets stands as a central problem in DP research. In practice, l_2/l_1-norm clippings with Gaussian/Laplace noise mechanisms are among the most common setups. However, they also suffer from the curse of dimensionality. For more generic clipping strategies, the understanding of the optimal noise for a high-dimensional sensitivity set remains limited. In this paper, we revisit the geometry of high-dimensional sensitivity sets and present a series of results to characterize the non-asymptotically optimal Gaussian noise for Rényi DP (RDP). Our results are both negative and positive: on one hand, we show the curse of dimensionality is tight for a broad class of sensitivity sets satisfying certain symmetry properties; but if, fortunately, the representation of the sensitivity set is asymmetric on some group of orthogonal bases, we show the optimal noise bounds need not be explicitly dependent on either dimension or rank. We also revisit sampling in the high-dimensional scenario, which is the key for both privacy amplification and computation efficiency in large-scale data processing. We propose a novel method, termed twice sampling, which implements both sample-wise and coordinate-wise sampling, to enable Gaussian noises to fit the sensitivity geometry more closely. With closed-form RDP analysis, we prove twice sampling produces asymptotic improvement of the privacy amplification given an additional infinity-norm restriction, especially for small sampling rate.
Efficient Training for Visual Tracking with Deformable Transformer
Venue: arXiv cs.CV 2023
Year: 2023

Recent Transformer-based visual tracking models have showcased superior performance. Nevertheless, prior works have been resource-intensive, requiring prolonged GPU training hours and incurring high GFLOPs during inference due to inefficient training methods and convolution-based target heads. This intensive resource use renders them unsuitable for real-world applications. In this paper, we present DETRack, a streamlined end-to-end visual object tracking framework. Our framework utilizes an efficient encoder-decoder structure where the deformable transformer decoder acting as a target head, achieves higher sparsity than traditional convolution heads, resulting in decreased GFLOPs. For training, we introduce a novel one-to-many label assignment and an auxiliary denoising technique, significantly accelerating model's convergence. Comprehensive experiments affirm the effectiveness and efficiency of our proposed method. For instance, DETRack achieves 72.9% AO on challenging GOT-10k benchmarks using only 20% of the training epochs required by the baseline, and runs with lower GFLOPs than all the transformer-based trackers.
Vector-Processing for Mobile Devices: Benchmark and Analysis
Venue: arXiv cs.AR 2023
Year: 2023

Vector processing has become commonplace in today's CPU microarchitectures. Vector instructions improve performance and energy which is crucial for resource-constraint mobile devices. The research community currently lacks a comprehensive benchmark suite to study the benefits of vector processing for mobile devices. This paper presents Swan-an extensive vector processing benchmark suite for mobile applications. Swan consists of a diverse set of data-parallel workloads from four commonly used mobile applications: operating system, web browser, audio/video messaging application, and PDF rendering engine. Using Swan benchmark suite, we conduct a detailed analysis of the performance, power, and energy consumption of vectorized workloads, and show that: (a) Vectorized kernels increase the pressure on cache hierarchy due to the higher rate of memory requests. (b) Vector processing is more beneficial for workloads with lower precision operations and higher cache hit rates. (c) Limited Instruction-Level Parallelism and strided memory accesses to multi-dimensional data structures prevent vector processing benefits from scaling with more SIMD functional units and wider registers. (d) Despite lower computation throughput than domain-specific accelerators, such as GPU, vector processing outperforms these accelerators for kernels with lower operation counts. Finally, we show five common computation patterns in mobile data-parallel workloads that dominate the execution time.
When Stars Control a Grammar's Work
Venue: arXiv cs.FL 2023
Year: 2023

Graph-controlled insertion-deletion (GCID) systems are regulated extensions of insertion-deletion systems. Such a system has several components and each component contains some insertion-deletion rules. The components are the vertices of a directed control graph. A rule is applied to a string in a component and the resultant string is moved to the target component specified in the rule. The language of the system is the set of all terminal strings collected in the final component. We impose the restriction in the structure of the underlying graph to be a star structure where there is a central, control component which acts like a master and transmits a string (after applying one of its rules) to one of the components specified in the (applied) rule. A component which receives the string can process the obtained string with any applicable rule available in it and sends back the resultant string only to the center component. With this restriction, we obtain computational completeness for some descriptional complexity measures
Pumping Lemmata for Recognizable Weighted Languages over Artinian Semirings
Venue: arXiv cs.FL 2023
Year: 2023

Pumping lemmata are the main tool to prove that a certain language does not belong to a class of languages like the recognizable languages or the context-free languages. Essentially two pumping lemmata exist for the recognizable weighted languages: the classical one for the Boolean semiring (i.e., the unweighted case), which can be generalized to zero-sum free semirings, and the one for fields. A joint generalization of these two pumping lemmata is provided that applies to all Artinian semirings, over which all finitely generated semimodules have a finite bound on the length of chains of strictly increasing subsemimodules. Since Artinian rings are exactly those that satisfy the Descending Chain Condition, the Artinian semirings include all fields and naturally also all finite semirings (like the Boolean semiring). The new pumping lemma thus covers most previously known pumping lemmata for recognizable weighted languages.
Solving the Weighted HOM-Problem With the Help of Unambiguity
Venue: arXiv cs.FL 2023
Year: 2023

The HOM-problem, which asks whether the image of a regular tree language under a tree homomorphism is again regular, is known to be decidable by [Godoy, Giménez, Ramos, Àlvarez: The HOM problem is decidable. STOC (2010)]. Research on the weighted version of this problem, however, is still in its infancy since it requires customized investigations. In this paper we address the weighted HOM-problem and strive to keep the underlying semiring as general as possible. In return, we restrict the input: We require the tree homomorphism h to be tetris-free, a condition weaker than injectivity, and for the given weighted tree automaton, we propose an ambiguity notion with respect to h. These assumptions suffice to ensure decidability of the thus restricted HOM-problem for all zero-sum free semirings by allowing us to reduce it to the (decidable) unweighted case.
Once-Marking and Always-Marking 1-Limited Automata
Venue: arXiv cs.FL 2023
Year: 2023

Single-tape nondeterministic Turing machines that are allowed to replace the symbol in each tape cell only when it is scanned for the first time are also known as 1-limited automata. These devices characterize, exactly as finite automata, the class of regular languages. However, they can be extremely more succinct. Indeed, in the worst case the size gap from 1-limited automata to one-way deterministic finite automata is double exponential. Here we introduce two restricted versions of 1-limited automata, once-marking 1-limited automata and always-marking 1-limited automata, and study their descriptional complexity. We prove that once-marking 1-limited automata still exhibit a double exponential size gap to one-way deterministic finite automata. However, their deterministic restriction is polynomially related in size to two-way deterministic finite automata, in contrast to deterministic 1-limited automata, whose equivalent two-way deterministic finite automata in the worst case are exponentially larger. For always-marking 1-limited automata, we prove that the size gap to one-way deterministic finite automata is only a single exponential. The gap remains exponential even in the case the given machine is deterministic. We obtain other size relationships between different variants of these machines and finite automata and we present some problems that deserve investigation.
Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars
Venue: arXiv cs.CC 2023
Year: 2023

Tree-controlled grammars are context-free grammars where the derivation process is controlled in such a way that every word on a level of the derivation tree must belong to a certain control language. We investigate the generative capacity of such tree-controlled grammars where the control languages are special regular sets, especially strictly locally testable languages or languages restricted by resources of the generation (number of non-terminal symbols or production rules) or acceptance (number of states). Furthermore, the set theoretic inclusion relations of these subregular language families themselves are studied.