OpenRaiser/Intern-Atlas huggingface dataset:
Tracking Passengers and Baggage Items Using Multiple Overhead Cameras at Security Checkpoints
Venue: arXiv cs.CV 2024
Year: 2024

We introduce a novel framework to track multiple objects in overhead camera videos for airport checkpoint security scenarios where targets correspond to passengers and their baggage items. We propose a self-supervised learning (SSL) technique to provide the model information about instance segmentation uncertainty from overhead images. Our SSL approach improves object detection by employing a test-time data augmentation and a regression-based, rotation-invariant pseudo-label refinement technique. Our pseudo-label generation method provides multiple geometrically transformed images as inputs to a convolutional neural network (CNN), regresses the augmented detections generated by the network to reduce localization errors, and then clusters them using the mean-shift algorithm. The self-supervised detector model is used in a single-camera tracking algorithm to generate temporal identifiers for the targets. Our method also incorporates a multiview trajectory association mechanism to maintain consistent temporal identifiers as passengers travel across camera views. An evaluation of detection, tracking, and association performances on videos obtained from multiple overhead cameras in a realistic airport checkpoint environment demonstrates the effectiveness of the proposed approach. Our results show that self-supervision improves object detection accuracy by up to 42% without increasing the inference time of the model. Our multicamera association method achieves up to 89% multiobject tracking accuracy with an average computation time of less than 15 ms.
Empowering the Edge Intelligence by Air-Ground Integrated Federated Learning
Venue: arXiv cs.NI 2024
Year: 2024

Ubiquitous intelligence has been widely recognized as a critical vision of the future sixth generation (6G) networks, which implies the intelligence over the whole network from the core to the edge including end devices. Nevertheless, fulfilling such vision, particularly the intelligence at the edge, is extremely challenging, due to the limited resources of edge devices as well as the ubiquitous coverage envisioned by 6G. To empower the edge intelligence, in this article, we propose a novel framework called AGIFL (Air-Ground Integrated Federated Learning), which organically integrates air-ground integrated networks and federated learning (FL). In the AGIFL, leveraging the flexible on-demand 3D deployment of aerial nodes such as unmanned aerial vehicles (UAVs), all the nodes can collaboratively train an effective learning model by FL. We also conduct a case study to evaluate the effect of two different deployment schemes of the UAV over the learning and network performance. Last but not the least, we highlight several technical challenges and future research directions in the AGIFL.
Bayesian Inference of Minimally Complex Models with Interactions of Arbitrary Order
Venue: arXiv cs.AI 2024
Year: 2024

Finding the model that best describes a high-dimensional dataset is a daunting task, even more so if one aims to consider all possible high-order patterns of the data, going beyond pairwise models. For binary data, we show that this task becomes feasible when restricting the search to a family of simple models, that we call Minimally Complex Models (MCMs). MCMs are maximum entropy models that have interactions of arbitrarily high order grouped into independent components of minimal complexity. They are simple in information-theoretic terms, which means they can only fit well certain types of data patterns and are therefore easy to falsify. We show that Bayesian model selection restricted to these models is computationally feasible and has many advantages. First, the model evidence, which balances goodness-of-fit against complexity, can be computed efficiently without any parameter fitting, enabling very fast explorations of the space of MCMs. Second, the family of MCMs is invariant under gauge transformations, which can be used to develop a representation-independent approach to statistical modeling. For small systems (up to 15 variables), combining these two results allows us to select the best MCM among all, even though the number of models is already extremely large. For larger systems, we propose simple heuristics to find optimal MCMs in reasonable times. Besides, inference and sampling can be performed without any computational effort. Finally, because MCMs have interactions of any order, they can reveal the presence of important high-order dependencies in the data, providing a new approach to explore high-order dependencies in complex systems. We apply our method to synthetic data and real-world examples, illustrating how MCMs portray the structure of dependencies among variables in a simple manner, extracting falsifiable predictions on symmetries and invariance from the data.
Unifying supervised learning and VAEs -- coverage, systematics and goodness-of-fit in normalizing-flow based neural network models for astro-particle reconstructions
Venue: arXiv cs.LG 2024
Year: 2024

Neural-network based predictions of event properties in astro-particle physics are getting more and more common. However, in many cases the result is just utilized as a point prediction. Statistical uncertainties, coverage, systematic uncertainties or a goodness-of-fit measure are often not calculated. Here we describe a certain choice of training and network architecture that allows to incorporate all these properties into a single network model. We show that a KL-divergence objective of the joint distribution of data and labels allows to unify supervised learning and variational autoencoders (VAEs) under one umbrella of stochastic variational inference. The unification motivates an extended supervised learning scheme which allows to calculate a goodness-of-fit p-value for the neural network model. Conditional normalizing flows amortized with a neural network are crucial in this construction. We discuss how to calculate coverage probabilities without numerical integration for specific "base-ordered" contours that are unique to normalizing flows. Furthermore we show how systematic uncertainties can be included via effective marginalization during training. The proposed extended supervised training incorporates (1) coverage calculation, (2) systematics and (3) a goodness-of-fit measure in a single machine-learning model. There are in principle no constraints on the shape of the involved distributions, in fact the machinery works with complex multi-modal distributions defined on product spaces like $\mathbb{R}^n \times \mathbb{S}^m$. The coverage calculation, however, requires care in its interpretation when the distributions are too degenerate. We see great potential for exploiting this per-event information in event selections or for fast astronomical alerts which require uncertainty guarantees.
Resolving Intent Ambiguities by Retrieving Discriminative Clarifying Questions
Venue: arXiv cs.AI 2024
Year: 2024

Task oriented Dialogue Systems generally employ intent detection systems in order to map user queries to a set of pre-defined intents. However, user queries appearing in natural language can be easily ambiguous and hence such a direct mapping might not be straightforward harming intent detection and eventually the overall performance of a dialogue system. Moreover, acquiring domain-specific clarification questions is costly. In order to disambiguate queries which are ambiguous between two intents, we propose a novel method of generating discriminative questions using a simple rule based system which can take advantage of any question generation system without requiring annotated data of clarification questions. Our approach aims at discrimination between two intents but can be easily extended to clarification over multiple intents. Seeking clarification from the user to classify user intents not only helps understand the user intent effectively, but also reduces the roboticity of the conversation and makes the interaction considerably natural.
Determinantal Point Process as an alternative to NMS
Venue: arXiv cs.CV 2024
Year: 2024

We present a determinantal point process (DPP) inspired alternative to non-maximum suppression (NMS) which has become an integral step in all state-of-the-art object detection frameworks. DPPs have been shown to encourage diversity in subset selection problems. We pose NMS as a subset selection problem and posit that directly incorporating DPP like framework can improve the overall performance of the object detection system. We propose an optimization problem which takes the same inputs as NMS, but introduces a novel sub-modularity based diverse subset selection functional. Our results strongly indicate that the modifications proposed in this paper can provide consistent improvements to state-of-the-art object detection pipelines.
XCSP3-core: A Format for Representing Constraint Satisfaction/Optimization Problems
Venue: arXiv cs.AI 2024
Year: 2024

In this document, we introduce XCSP3-core, a subset of XCSP3 that allows us to represent constraint satisfaction/optimization problems. The interest of XCSP3-core is multiple: (i) focusing on the most popular frameworks (CSP and COP) and constraints, (ii) facilitating the parsing process by means of dedicated XCSP3-core parsers written in Java and C++ (using callback functions), (iii) and defining a core format for comparisons (competitions) of constraint solvers.
Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
Venue: arXiv cs.DS 2024
Year: 2024

We present combinatorial and parallelizable algorithms for maximization of a submodular function, not necessarily monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal query complexity to $0.193 - \varepsilon$. The conference version of this work mistakenly employed a subroutine that does not work for non-monotone, submodular functions. In this version, we propose a fixed and improved subroutine to add a set with high average marginal gain, ThreshSeq, which returns a solution in $O( \log(n) )$ adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio $1/6 - \varepsilon$, adaptivity $O( \log (n) )$, and query complexity $O( n \log (k) )$, while the second has approximation ratio $0.193 - \varepsilon$, adaptivity $O( \log^2 (n) )$, and query complexity $O(n \log (k))$. Our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension.
End-to-end Kernel Learning via Generative Random Fourier Features
Venue: arXiv cs.LG 2024
Year: 2024

Random Fourier features (RFFs) provide a promising way for kernel learning in a spectral case. Current RFFs-based kernel learning methods usually work in a two-stage way. In the first-stage process, learning the optimal feature map is often formulated as a target alignment problem, which aims to align the learned kernel with the pre-defined target kernel (usually the ideal kernel). In the second-stage process, a linear learner is conducted with respect to the mapped random features. Nevertheless, the pre-defined kernel in target alignment is not necessarily optimal for the generalization of the linear learner. Instead, in this paper, we consider a one-stage process that incorporates the kernel learning and linear learner into a unifying framework. To be specific, a generative network via RFFs is devised to implicitly learn the kernel, followed by a linear classifier parameterized as a full-connected layer. Then the generative network and the classifier are jointly trained by solving the empirical risk minimization (ERM) problem to reach a one-stage solution. This end-to-end scheme naturally allows deeper features, in correspondence to a multi-layer structure, and shows superior generalization performance over the classical two-stage, RFFs-based methods in real-world classification tasks. Moreover, inspired by the randomized resampling mechanism of the proposed method, its enhanced adversarial robustness is investigated and experimentally verified.
Generating Emotive Gaits for Virtual Agents Using Affect-Based Autoregression
Venue: arXiv cs.GR 2024
Year: 2024

We present a novel autoregression network to generate virtual agents that convey various emotions through their walking styles or gaits. Given the 3D pose sequences of a gait, our network extracts pertinent movement features and affective features from the gait. We use these features to synthesize subsequent gaits such that the virtual agents can express and transition between emotions represented as combinations of happy, sad, angry, and neutral. We incorporate multiple regularizations in the training of our network to simultaneously enforce plausible movements and noticeable emotions on the virtual agents. We also integrate our approach with an AR environment using a Microsoft HoloLens and can generate emotive gaits at interactive rates to increase the social presence. We evaluate how human observers perceive both the naturalness and the emotions from the generated gaits of the virtual agents in a web-based study. Our results indicate around 89% of the users found the naturalness of the gaits satisfactory on a five-point Likert scale, and the emotions they perceived from the virtual agents are statistically similar to the intended emotions of the virtual agents. We also use our network to augment existing gait datasets with emotive gaits and will release this augmented dataset for future research in emotion prediction and emotive gait synthesis. Our project website is available at https://gamma.umd.edu/gen_emotive_gaits/.
Transcending Transcend: Revisiting Malware Classification in the Presence of Concept Drift
Venue: arXiv cs.CR 2024
Year: 2024

Machine learning for malware classification shows encouraging results, but real deployments suffer from performance degradation as malware authors adapt their techniques to evade detection. This phenomenon, known as concept drift, occurs as new malware examples evolve and become less and less like the original training examples. One promising method to cope with concept drift is classification with rejection in which examples that are likely to be misclassified are instead quarantined until they can be expertly analyzed. We propose TRANSCENDENT, a rejection framework built on Transcend, a recently proposed strategy based on conformal prediction theory. In particular, we provide a formal treatment of Transcend, enabling us to refine conformal evaluation theory -- its underlying statistical engine -- and gain a better understanding of the theoretical reasons for its effectiveness. In the process, we develop two additional conformal evaluators that match or surpass the performance of the original while significantly decreasing the computational overhead. We evaluate TRANSCENDENT on a malware dataset spanning 5 years that removes sources of experimental bias present in the original evaluation. TRANSCENDENT outperforms state-of-the-art approaches while generalizing across different malware domains and classifiers. To further assist practitioners, we determine the optimal operational settings for a TRANSCENDENT deployment and show how it can be applied to many popular learning algorithms. These insights support both old and new empirical findings, making Transcend a sound and practical solution for the first time. To this end, we release TRANSCENDENT as open source, to aid the adoption of rejection strategies by the security community.
C for a tiny system
Venue: arXiv cs.PL 2024
Year: 2024

We have implemented support for Padauk microcontrollers, tiny 8-Bit devices with 60 B to 256 B of RAM, in the Small Device C Compiler (SDCC), showing that the use of (mostly) standard C to program such minimal devices is feasible. We report on our experience and on the difficulties in supporting the hardware multithreading present on some of these devices. To make the devices a better target for C, we propose various enhancements of the architecture, and empirically evaluated their impact on code size.
Learning Calibrated Uncertainties for Domain Shift: A Distributionally Robust Learning Approach
Venue: arXiv cs.LG 2024
Year: 2024

We propose a framework for learning calibrated uncertainties under domain shifts, where the source (training) distribution differs from the target (test) distribution. We detect such domain shifts via a differentiable density ratio estimator and train it together with the task network, composing an adjusted softmax predictive form concerning domain shift. In particular, the density ratio estimation reflects the closeness of a target (test) sample to the source (training) distribution. We employ it to adjust the uncertainty of prediction in the task network. This idea of using the density ratio is based on the distributionally robust learning (DRL) framework, which accounts for the domain shift by adversarial risk minimization. We show that our proposed method generates calibrated uncertainties that benefit downstream tasks, such as unsupervised domain adaptation (UDA) and semi-supervised learning (SSL). On these tasks, methods like self-training and FixMatch use uncertainties to select confident pseudo-labels for re-training. Our experiments show that the introduction of DRL leads to significant improvements in cross-domain performance. We also show that the estimated density ratios align with human selection frequencies, suggesting a positive correlation with a proxy of human perceived uncertainties.
A Refined Laser Method and Faster Matrix Multiplication
Venue: arXiv cs.DS 2024
Year: 2024

The complexity of matrix multiplication is measured in terms of $ω$, the smallest real number such that two $n\times n$ matrices can be multiplied using $O(n^{ω+ε})$ field operations for all $ε>0$; the best bound until now is $ω<2.37287$ [Le Gall'14]. All bounds on $ω$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $ω$, and we indeed obtain the best bound on $ω$ to date: $$ω< 2.37286.$$ The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.
Local Perceptions and Practices of News Sharing and Fake News
Venue: arXiv cs.HC 2024
Year: 2024

Fake news is a prevalent problem, particularly in digital media, that undermines trust and cooperation among people. As a variety of global mitigation efforts arise, the understanding of how people consider fake news becomes important, especially in local contexts. To that end, we carried out a survey with 75 participants in Singapore to understand people's perceptions of and practices with news (real and fake). Locally, fake news was found to be more pervasive in instant messaging apps than in social media, with the problem attributed more strongly to sharing than to creation. Good news sharing practices were generally observed. Highest trust was reported in government communication platforms across 11 media items. These results show that Singapore possesses a peculiar sociocultural scene, suggesting that efforts directed towards locally relevant measures may be more effective in addressing fake news in Singapore. We detail the survey results and recommended directions in this paper.
On the Semantic Expressiveness of Iso- and Equi-Recursive Types
Venue: arXiv cs.PL 2024
Year: 2024

Recursive types extend the simply-typed lambda calculus (STLC) with the additional expressive power to enable diverging computation and to encode recursive data-types (e.g., lists). Two formulations of recursive types exist: iso-recursive and equi-recursive. The relative advantages of iso- and equi-recursion are well-studied when it comes to their impact on type-inference. However, the relative semantic expressiveness of the two formulations remains unclear so far. This paper studies the semantic expressiveness of STLC with iso- and equi-recursive types, proving that these formulations are equally expressive. In fact, we prove that they are both as expressive as STLC with only term-level recursion. We phrase these equi-expressiveness results in terms of full abstraction of three canonical compilers between these three languages (STLC with iso-, with equi-recursive types and with term-level recursion). Our choice of languages allows us to study expressiveness when interacting over both a simply-typed and a recursively-typed interface. The three proofs all rely on a typed version of a proof technique called approximate backtranslation. Together, our results show that there is no difference in semantic expressiveness between STLCs with iso- and equi-recursive types. In this paper, we focus on a simply-typed setting but we believe our results scale to more powerful type systems like System F.
Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners
Venue: arXiv cs.DB 2024
Year: 2024

The regular spanners (characterised by vset-automata) are closed under the algebraic operations of union, join and projection, and have desirable algorithmic properties. The core spanners (introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015) as a formalisation of the core functionality of the query language AQL used in IBM's SystemT) additionally need string-equality selections and it has been shown by Freydenberger and Holldack (ICDT 2016, Theory of Computing Systems 2018) that this leads to high complexity and even undecidability of the typical problems in static analysis and query evaluation. We propose an alternative approach to core spanners: by incorporating the string-equality selections directly into the regular language that represents the underlying regular spanner (instead of treating it as an algebraic operation on the table extracted by the regular spanner), we obtain a fragment of core spanners that, while having slightly weaker expressive power than the full class of core spanners, arguably still covers the intuitive applications of string-equality selections for information extraction and has much better upper complexity bounds of the typical problems in static analysis and query evaluation.
The Agile Coach Role: Coaching for Agile Performance Impact
Venue: arXiv cs.SE 2024
Year: 2024

It is increasingly common to introduce agile coaches to help gain speed and advantage in agile companies. Following the success of Spotify, the role of the agile coach has branched out in terms of tasks and responsibilities, but little research has been conducted to examine how this role is practiced. This paper examines the role of the agile coach through 19 semistructured interviews with agile coaches from ten different companies. We describe the role in terms of the tasks the coach has in agile projects, valuable traits, skills, tools, and the enablers of agile coaching. Our findings indicate that agile coaches perform at the team and organizational levels. They affect effort, strategies, knowledge, and skills of the agile teams. The most essential traits of an agile coach are being emphatic, people-oriented, able to listen, diplomatic, and persistent. We suggest empirically based advice for agile coaching, for example companies giving their agile coaches the authority to implement the required organizational changes within and outside the teams.