OpenRaiser/Intern-Atlas huggingface dataset:
Tit-for-Tat Dynamics and Market Volatility
Venue: arXiv cs.GT 2024
Year: 2024

We consider tit-for-tat dynamics in production markets, where there is a set of $n$ players connected via a weighted graph. Each player $i$ can produce an eponymous good using its linear production function, given as input various amounts of goods in the system. In the tit-for-tat dynamic, each player $i$ shares its good with its neighbors in fractions proportional to how much they helped player $i$'s production in the last round. Our contribution is to characterize the asymptotic behavior of the dynamic as a function of the graph structure, finding that the fortune of a player grows in the long term if and only if the player has a good self loop (i.e. the player works well alone) or works well with at least one other player. We also consider a generalized damped update, where the players may update their strategies with different speeds, and obtain a lower bound on their rate of growth by identifying a function that gives insight into the behavior of the dynamical system. The model can capture circular economies, where players use each other's products, and organizational partnerships, where fostering long-term growth of an organization hinges on creating relationships in which reciprocal exchanges between the agents in the organization are paramount.
Hexagonal Image Processing in the Context of Machine Learning: Conception of a Biologically Inspired Hexagonal Deep Learning Framework
Venue: arXiv cs.LG 2024
Year: 2024

Inspired by the human visual perception system, hexagonal image processing in the context of machine learning deals with the development of image processing systems that combine the advantages of evolutionary motivated structures based on biological models. While conventional state-of-the-art image processing systems of recording and output devices almost exclusively utilize square arranged methods, their hexagonal counterparts offer a number of key advantages that can benefit both researchers and users. This contribution serves as a general application-oriented approach the synthesis of the therefore designed hexagonal image processing framework, called Hexnet, the processing steps of hexagonal image transformation, and dependent methods. The results of our created test environment show that the realized framework surpasses current approaches of hexagonal image processing systems, while hexagonal artificial neural networks can benefit from the implemented hexagonal architecture. As hexagonal lattice format based deep neural networks, also called H-DNN, can be compared to their square counterparts by transforming classical square lattice based data sets into their hexagonal representation, they can also result in a reduction of trainable parameters as well as result in increased training and test rates.
Towards better social crisis data with HERMES: Hybrid sensing for EmeRgency ManagEment System
Venue: arXiv cs.HC 2024
Year: 2024

People involved in mass emergencies increasingly publish information-rich contents in online social networks (OSNs), thus acting as a distributed and resilient network of human sensors. In this work we present HERMES, a system designed to enrich the information spontaneously disclosed by OSN users in the aftermath of disasters. HERMES leverages a mixed data collection strategy, called hybrid sensing, and state-of-the-art AI techniques. Evaluated in real-world emergencies, HERMES proved to increase: (i) the amount of the available damage information; (ii) the density (up to 7x) and the variety (up to 18x) of the retrieved geographic information; (iii) the geographic coverage (up to 30%) and granularity.
EPIC: An Energy-Efficient, High-Performance GPGPU Computing Research Infrastructure
Venue: arXiv cs.DC 2024
Year: 2024

The pursuit of many research questions requires massive computational resources. State-of-the-art research in physical processes using simulations, the training of neural networks for deep learning, or the analysis of big data are all dependent on the availability of sufficient and performant computational resources. For such research, access to a high-performance computing infrastructure is indispensable. Many scientific workloads from such research domains are inherently parallel and can benefit from the data-parallel architecture of general purpose graphics processing units (GPGPUs). However, GPGPU resources are scarce at Norway's national infrastructure. EPIC is a GPGPU enabled computing research infrastructure at NTNU. It enables NTNU's researchers to perform experiments that otherwise would be impossible, as time-to-solution would simply take too long.
SeMA: Extending and Analyzing Storyboards to Develop Secure Android Apps
Venue: arXiv cs.SE 2024
Year: 2024

Mobile apps provide various critical services, such as banking, communication, and healthcare. To this end, they have access to our personal information and have the ability to perform actions on our behalf. Hence, securing mobile apps is crucial to ensuring the privacy and safety of its users. Recent research efforts have focused on developing solutions to secure mobile ecosystems (i.e., app platforms, apps, and app stores), specifically in the context of detecting vulnerabilities in Android apps. Despite this attention, known vulnerabilities are often found in mobile apps, which can be exploited by malicious apps to harm the user. Further, fixing vulnerabilities after developing an app has downsides in terms of time, resources, user inconvenience, and information loss. In an attempt to address this concern, we have developed SeMA, a mobile app development methodology that builds on existing mobile app design artifacts such as storyboards. With SeMA, security is a first-class citizen in an app's design -- app designers and developers can collaborate to specify and reason about the security properties of an app at an abstract level without being distracted by implementation level details. Our realization of SeMA using Android Studio tooling demonstrates the methodology is complementary to existing design and development practices. An evaluation of the effectiveness of SeMA shows the methodology can detect and help prevent 49 vulnerabilities known to occur in Android apps. Further, a usability study of the methodology involving ten real-world developers shows the methodology is likely to reduce the development time and help developers uncover and prevent known vulnerabilities while designing apps.
Zeta Functions and the (Linear) Logic of Markov Processes
Venue: arXiv cs.LO 2024
Year: 2024

The author introduced models of linear logic known as ''Interaction Graphs'' which generalise Girard's various geometry of interaction constructions. In this work, we establish how these models essentially rely on a deep connection between zeta functions and the execution of programs, expressed as a cocycle. This is first shown in the simple case of graphs, before begin lifted to dynamical systems. Focussing on probabilistic models, we then explain how the notion of graphings used in Interaction Graphs captures a natural class of sub-Markov processes. We then extend the realisability constructions and the notion of zeta function to provide a realisability model of second-order linear logic over the set of all (discrete-time) sub-Markov processes.
An Equivalence between Bayesian Priors and Penalties in Variational Inference
Venue: arXiv cs.LG 2024
Year: 2024

In machine learning, it is common to optimize the parameters of a probabilistic model, modulated by an ad hoc regularization term that penalizes some values of the parameters. Regularization terms appear naturally in Variational Inference, a tractable way to approximate Bayesian posteriors: the loss to optimize contains a Kullback--Leibler divergence term between the approximate posterior and a Bayesian prior. We fully characterize the regularizers that can arise according to this procedure, and provide a systematic way to compute the prior corresponding to a given penalty. Such a characterization can be used to discover constraints over the penalty function, so that the overall procedure remains Bayesian.
Exploratory Machine Learning with Unknown Unknowns
Venue: arXiv cs.LG 2024
Year: 2024

In conventional supervised learning, a training dataset is given with ground-truth labels from a known label set, and the learned model will classify unseen instances to known labels. This paper studies a new problem setting in which there are unknown classes in the training data misperceived as other labels, and thus their existence appears unknown from the given supervision. We attribute the unknown unknowns to the fact that the training dataset is badly advised by the incompletely perceived label space due to the insufficient feature information. To this end, we propose the exploratory machine learning, which examines and investigates training data by actively augmenting the feature space to discover potentially hidden classes. Our method consists of three ingredients including rejection model, feature exploration, and model cascade. We provide theoretical analysis to justify its superiority, and validate the effectiveness on both synthetic and real datasets.
Input Validation for Neural Networks via Runtime Local Robustness Verification
Venue: arXiv cs.LG 2024
Year: 2024

Local robustness verification can verify that a neural network is robust wrt. any perturbation to a specific input within a certain distance. We call this distance Robustness Radius. We observe that the robustness radii of correctly classified inputs are much larger than that of misclassified inputs which include adversarial examples, especially those from strong adversarial attacks. Another observation is that the robustness radii of correctly classified inputs often follow a normal distribution. Based on these two observations, we propose to validate inputs for neural networks via runtime local robustness verification. Experiments show that our approach can protect neural networks from adversarial examples and improve their accuracies.
A Survey on 3D Skeleton-Based Action Recognition Using Learning Method
Venue: arXiv cs.CV 2024
Year: 2024

3D skeleton-based action recognition (3D SAR) has gained significant attention within the computer vision community, owing to the inherent advantages offered by skeleton data. As a result, a plethora of impressive works, including those based on conventional handcrafted features and learned feature extraction methods, have been conducted over the years. However, prior surveys on action recognition have primarily focused on video or RGB data-dominated approaches, with limited coverage of reviews related to skeleton data. Furthermore, despite the extensive application of deep learning methods in this field, there has been a notable absence of research that provides an introductory or comprehensive review from the perspective of deep learning architectures. To address these limitations, this survey first underscores the importance of action recognition and emphasizes the significance of 3D skeleton data as a valuable modality. Subsequently, we provide a comprehensive introduction to mainstream action recognition techniques based on four fundamental deep architectures, i.e., Recurrent Neural Networks (RNNs), Convolutional Neural Networks (CNNs), Graph Convolutional Network (GCN), and Transformers. All methods with the corresponding architectures are then presented in a data-driven manner with detailed discussion. Finally, we offer insights into the current largest 3D skeleton dataset, NTU-RGB+D, and its new edition, NTU-RGB+D 120, along with an overview of several top-performing algorithms on these datasets. To the best of our knowledge, this research represents the first comprehensive discussion of deep learning-based action recognition using 3D skeleton data.
The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms
Venue: arXiv cs.LG 2024
Year: 2024

We investigate a Bayesian $k$-armed bandit problem in the \emph{many-armed} regime, where $k \geq \sqrt{T}$ and $T$ represents the time horizon. Initially, and aligned with recent literature on many-armed bandit problems, we observe that subsampling plays a key role in designing optimal algorithms; the conventional UCB algorithm is sub-optimal, whereas a subsampled UCB (SS-UCB), which selects $Θ(\sqrt{T})$ arms for execution under the UCB framework, achieves rate-optimality. However, despite SS-UCB's theoretical promise of optimal regret, it empirically underperforms compared to a greedy algorithm that consistently chooses the empirically best arm. This observation extends to contextual settings through simulations with real-world data. Our findings suggest a new form of \emph{free exploration} beneficial to greedy algorithms in the many-armed context, fundamentally linked to a tail event concerning the prior distribution of arm rewards. This finding diverges from the notion of free exploration, which relates to covariate variation, as recently discussed in contextual bandit literature. Expanding upon these insights, we establish that the subsampled greedy approach not only achieves rate-optimality for Bernoulli bandits within the many-armed regime but also attains sublinear regret across broader distributions. Collectively, our research indicates that in the many-armed regime, practitioners might find greater value in adopting greedy algorithms.
Wavelet-based temporal models of human activity for anomaly detection in smart robot-assisted environments
Venue: arXiv cs.AI 2024
Year: 2024

Abstract. Detecting anomalies in patterns of sensor data is important in many practical applications, including domestic activity monitoring for Active Assisted Living (AAL). How to represent and analyse these patterns, however, remains a challenging task, especially when data is relatively scarce and an explicit model is required to be fine-tuned for specific scenarios. This paper, therefore, presents a new approach for temporal modelling of long-term human activities with smart-home sensors, which is used to detect anomalous situations in a robot-assisted environment. The model is based on wavelet transforms and used to forecast smart sensor data, providing a temporal prior to detect unexpected events in human environments. To this end, a new extension of Hybrid Markov Logic Networks has been developed that merges different anomaly indicators, including activities detected by binary sensors, expert logic rules, and wavelet-based temporal models. The latter in particular allows the inference system to discover deviations from long-term activity patterns, which cannot be detected by simpler frequency-based models. Two new publicly available datasets were collected using several smart-sensors to evaluate the approach in office and domestic scenarios. The experimental results demonstrate the effectiveness of the proposed solutions and their successful deployment in complex human environments, showing their potential for future smart-home and robot integrated services.
Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation
Venue: arXiv cs.LO 2024
Year: 2024

In this paper, we explore the issue of inconsistency handling over prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts. In the database setting, a closely related scenario has been studied and led to the definition of three different notions of optimal repairs (global, Pareto, and completion) of a prioritized inconsistent database. After transferring the notions of globally-, Pareto- and completion-optimal repairs to our setting, we study the data complexity of the core reasoning tasks: query entailment under inconsistency-tolerant semantics based upon optimal repairs, existence of a unique optimal repair, and enumeration of all optimal repairs. Our results provide a nearly complete picture of the data complexity of these tasks for ontologies formulated in common DL-Lite dialects. The second contribution of our work is to clarify the relationship between optimal repairs and different notions of extensions for (set-based) argumentation frameworks. Among our results, we show that Pareto-optimal repairs correspond precisely to stable extensions (and often also to preferred extensions), and we propose a novel semantics for prioritized KBs which is inspired by grounded extensions and enjoys favourable computational properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks.
3D Crowd Counting via Geometric Attention-guided Multi-View Fusion
Venue: arXiv cs.CV 2024
Year: 2024

Recently multi-view crowd counting using deep neural networks has been proposed to enable counting in large and wide scenes using multiple cameras. The current methods project the camera-view features to the average-height plane of the 3D world, and then fuse the projected multi-view features to predict a 2D scene-level density map on the ground (i.e., birds-eye view). Unlike the previous research, we consider the variable height of the people in the 3D world and propose to solve the multi-view crowd counting task through 3D feature fusion with 3D scene-level density maps, instead of the 2D density map on the ground plane. Compared to 2D fusion, the 3D fusion extracts more information of the people along the z-dimension (height), which helps to address the scale variations across multiple views. The 3D density maps still preserve the 2D density maps property that the sum is the count, while also providing 3D information about the crowd density. Furthermore, instead of using the standard method of copying the features along the view ray in the 2D-to-3D projection, we propose an attention module based on a height estimation network, which forces each 2D pixel to be projected to one 3D voxel along the view ray. We also explore the projection consistency among the 3D prediction and the ground truth in the 2D views to further enhance the counting performance. The proposed method is tested on the synthetic and real-world multiview counting datasets and achieves better or comparable counting performance to the state-of-the-art.
Optimal No-regret Learning in Repeated First-price Auctions
Venue: arXiv cs.LG 2024
Year: 2024

We study online learning in repeated first-price auctions where a bidder, only observing the winning bid at the end of each auction, learns to adaptively bid in order to maximize her cumulative payoff. To achieve this goal, the bidder faces censored feedback: if she wins the bid, then she is not able to observe the highest bid of the other bidders, which we assume is \textit{iid} drawn from an unknown distribution. In this paper, we develop the first learning algorithm that achieves a near-optimal $\widetilde{O}(\sqrt{T})$ regret bound, by exploiting two structural properties of first-price auctions, i.e. the specific feedback structure and payoff function. We first formulate the feedback structure in first-price auctions as partially ordered contextual bandits, a combination of the graph feedback across actions (bids), the cross learning across contexts (private values), and a partial order over the contexts. We establish both strengths and weaknesses of this framework, by showing a curious separation that a regret nearly independent of the action/context sizes is possible under stochastic contexts, but is impossible under adversarial contexts. In particular, this framework leads to an $O(\sqrt{T}\log^{2.5}T)$ regret for first-price auctions when the bidder's private values are \emph{iid}. Despite the limitation of the above framework, we further exploit the special payoff function of first-price auctions to develop a sample-efficient algorithm even in the presence of adversarially generated private values. We establish an $O(\sqrt{T}\log^3 T)$ regret bound for this algorithm, hence providing a complete characterization of optimal learning guarantees for first-price auctions.
The Discrete Gaussian for Differential Privacy
Venue: arXiv cs.DS 2024
Year: 2024

A key tool for building differentially private systems is adding Gaussian noise to the output of a function evaluated on a sensitive dataset. Unfortunately, using a continuous distribution presents several practical challenges. First and foremost, finite computers cannot exactly represent samples from continuous distributions, and previous work has demonstrated that seemingly innocuous numerical errors can entirely destroy privacy. Moreover, when the underlying data is itself discrete (e.g., population counts), adding continuous noise makes the result less interpretable. With these shortcomings in mind, we introduce and analyze the discrete Gaussian in the context of differential privacy. Specifically, we theoretically and experimentally show that adding discrete Gaussian noise provides essentially the same privacy and accuracy guarantees as the addition of continuous Gaussian noise. We also present an simple and efficient algorithm for exact sampling from this distribution. This demonstrates its applicability for privately answering counting queries, or more generally, low-sensitivity integer-valued queries.
The Mathematical Syntax of Architectures
Venue: arXiv cs.LO 2024
Year: 2024

Despite several (accepted) standards, core notions typically employed in information technology or system engineering architectures lack the precise and exact foundations encountered in logic, algebra, and other branches of mathematics. In this contribution we define the syntactical aspects of the term architecture in a mathematically rigorous way. We motivate our particular choice by demonstrating (i) how commonly understood and expected properties of an architecture -- as defined by various standards -- can be suitably identified or derived within our formalization, (ii) how our concept is fully compatible with real life (business) architectures, and (iii) how our definition complements recent foundational work in this area (Wilkinson 2018, Dickersen 2020, Efatmaneshnik 2020). We furthermore develop a rigorous notion of architectural similarity based on the notion of homomorphisms allowing the class of architectures to be regarded as a category, Arch. We demonstrate the applicability of our concepts to theory by deriving theorems on the classification of certain types of architectures. Inter alia, we derive a no go theorem proving that, in contrast to n-tier architectures, one cannot sensibly define generic architectural modularity on the syntactical level alone.
Families of sequences with good family complexity and cross-correlation measure
Venue: arXiv cs.IT 2024
Year: 2024

In this paper we study pseudorandomness of a family of sequences in terms of two measures, the family complexity ($f$-complexity) and the cross-correlation measure of order $\ell$. We consider sequences not only on binary alphabet but also on $k$-symbols ($k$-ary) alphabet. We first generalize some known methods on construction of the family of binary pseudorandom sequences. We prove a bound on the $f$-complexity of a large family of binary sequences of Legendre-symbols of certain irreducible polynomials. We show that this family as well as its dual family have both a large family complexity and a small cross-correlation measure up to a rather large order. Next, we present another family of binary sequences having high $f$-complexity and low cross-correlation measure. Then we extend the results to the family of sequences on $k$-symbols alphabet.