OpenRaiser/Intern-Atlas huggingface dataset:
Points2Surf: Learning Implicit Surfaces from Point Cloud Patches
Venue: arXiv cs.CV 2024
Year: 2024

A key step in any scanning-based asset creation workflow is to convert unordered point clouds to a surface. Classical methods (e.g., Poisson reconstruction) start to degrade in the presence of noisy and partial scans. Hence, deep learning based methods have recently been proposed to produce complete surfaces, even from partial scans. However, such data-driven methods struggle to generalize to new shapes with large geometric and topological variations. We present Points2Surf, a novel patch-based learning framework that produces accurate surfaces directly from raw scans without normals. Learning a prior over a combination of detailed local patches and coarse global information improves generalization performance and reconstruction accuracy. Our extensive comparison on both synthetic and real data demonstrates a clear advantage of our method over state-of-the-art alternatives on previously unseen classes (on average, Points2Surf brings down reconstruction error by 30% over SPR and by 270%+ over deep learning based SotA methods) at the cost of longer computation times and a slight increase in small-scale topological noise in some cases. Our source code, pre-trained model, and dataset are available on: https://github.com/ErlerPhilipp/points2surf
SUBPLEX: Towards a Better Understanding of Black Box Model Explanations at the Subpopulation Level
Venue: arXiv cs.HC 2024
Year: 2024

Understanding the interpretation of machine learning (ML) models has been of paramount importance when making decisions with societal impacts such as transport control, financial activities, and medical diagnosis. While current model interpretation methodologies focus on using locally linear functions to approximate the models or creating self-explanatory models that give explanations to each input instance, they do not focus on model interpretation at the subpopulation level, which is the understanding of model interpretations across different subset aggregations in a dataset. To address the challenges of providing explanations of an ML model across the whole dataset, we propose SUBPLEX, a visual analytics system to help users understand black-box model explanations with subpopulation visual analysis. SUBPLEX is designed through an iterative design process with machine learning researchers to address three usage scenarios of real-life machine learning tasks: model debugging, feature selection, and bias detection. The system applies novel subpopulation analysis on ML model explanations and interactive visualization to explore the explanations on a dataset with different levels of granularity. Based on the system, we conduct user evaluation to assess how understanding the interpretation at a subpopulation level influences the sense-making process of interpreting ML models from a user's perspective. Our results suggest that by providing model explanations for different groups of data, SUBPLEX encourages users to generate more ingenious ideas to enrich the interpretations. It also helps users to acquire a tight integration between programming workflow and visual analytics workflow. Last but not least, we summarize the considerations observed in applying visualization to machine learning interpretations.
Space-Efficient Graph Kernelizations
Venue: arXiv cs.DS 2024
Year: 2024

Let $n$ be the size of a parameterized problem and $k$ the parameter. We present kernels for Feedback Vertex Set, Path Contraction and Cluster Editing/Deletion whose sizes are all polynomial in $k$ and that are computable in polynomial time and with $O(\rm{poly}(k) \log n)$ bits (of working memory). By using kernel cascades, we obtain the best known kernels in polynomial time with $O(\rm{poly}(k) \log n)$ bits.
Almost exact recovery in noisy semi-supervised learning
Venue: arXiv cs.LG 2024
Year: 2024

Graph-based semi-supervised learning methods combine the graph structure and labeled data to classify unlabeled data. In this work, we study the effect of a noisy oracle on classification. In particular, we derive the Maximum A Posteriori (MAP) estimator for clustering a Degree Corrected Stochastic Block Model (DC-SBM) when a noisy oracle reveals a fraction of the labels. We then propose an algorithm derived from a continuous relaxation of the MAP, and we establish its consistency. Numerical experiments show that our approach achieves promising performance on synthetic and real data sets, even in the case of very noisy labeled data.
Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
Venue: arXiv cs.DS 2024
Year: 2024

We show that the volume of a convex body in $\mathbb{R}^{n}$ in the general membership oracle model can be computed to within relative error $\varepsilon$ using $\widetilde{O}(n^{3.5}ψ^{2} + n^3/\varepsilon^{2})$ oracle queries, where $ψ$ is the KLS constant. With the current bound of $ψ=\widetilde{O}(1)$, this gives an $\widetilde{O}(n^{3.5} + n^3/\varepsilon^{2})$ algorithm, improving on the Lovász-Vempala $\widetilde{O}(n^{4}/\varepsilon^{2})$ algorithm from 2003. The main new ingredient is an $\widetilde{O}(n^{3}ψ^{2})$ algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropicize a general convex body. Following this, we can apply the $\widetilde{O}(n^{3}/\varepsilon^{2})$ volume algorithm of Cousins and Vempala for well-rounded convex bodies. We also give an efficient implementation of the new algorithm for convex polytopes defined by $m$ inequalities in $\mathbb{R}^{n}$: polytope volume can be estimated in time $\widetilde{O}(mn^{c}/\varepsilon^{2})$ where $c<3.7$ depends on the current matrix multiplication exponent and improves on the previous best bound.
Interpretable Representations in Explainable AI: From Theory to Practice
Venue: arXiv cs.LG 2024
Year: 2024

Interpretable representations are the backbone of many explainers that target black-box predictive systems based on artificial intelligence and machine learning algorithms. They translate the low-level data representation necessary for good predictive performance into high-level human-intelligible concepts used to convey the explanatory insights. Notably, the explanation type and its cognitive complexity are directly controlled by the interpretable representation, tweaking which allows to target a particular audience and use case. However, many explainers built upon interpretable representations overlook their merit and fall back on default solutions that often carry implicit assumptions, thereby degrading the explanatory power and reliability of such techniques. To address this problem, we study properties of interpretable representations that encode presence and absence of human-comprehensible concepts. We demonstrate how they are operationalised for tabular, image and text data; discuss their assumptions, strengths and weaknesses; identify their core building blocks; and scrutinise their configuration and parameterisation. In particular, this in-depth analysis allows us to pinpoint their explanatory properties, desiderata and scope for (malicious) manipulation in the context of tabular data where a linear model is used to quantify the influence of interpretable concepts on a black-box prediction. Our findings lead to a range of recommendations for designing trustworthy interpretable representations; specifically, the benefits of class-aware (supervised) discretisation of tabular data, e.g., with decision trees, and sensitivity of image interpretable representations to segmentation granularity and occlusion colour.
Moderately Supervised Learning: Definition, Framework and Generality
Venue: arXiv cs.CV 2024
Year: 2024

Learning with supervision has achieved remarkable success in numerous artificial intelligence (AI) applications. In the current literature, by referring to the properties of the labels prepared for the training dataset, learning with supervision is categorized as supervised learning (SL) and weakly supervised learning (WSL). SL concerns the situation where the training data set is assigned with ideal (complete, exact and accurate) labels, while WSL concerns the situation where the training data set is assigned with non-ideal (incomplete, inexact or inaccurate) labels. However, various solutions for SL tasks have shown that the given labels are not always easy to learn, and the transformation from the given labels to easy-to-learn targets can significantly affect the performance of the final SL solutions. Without considering the properties of the transformation from the given labels to easy-to-learn targets, the definition of SL conceals some details that can be critical to building the appropriate solutions for specific SL tasks. Thus, for engineers in the AI application field, it is desirable to reveal these details systematically. This article attempts to achieve this goal by expanding the categorization of SL and investigating the sub-type moderately supervised learning (MSL) that concerns the situation where the given labels are ideal, but due to the simplicity in annotation, careful designs are required to transform the given labels into easy-to-learn targets. From the perspectives of the definition, framework and generality, we conceptualize MSL to present a complete fundamental basis to systematically analyse MSL tasks. At meantime, revealing the relation between the conceptualization of MSL and the mathematicians' vision, this paper as well establishes a tutorial for AI application engineers to refer to viewing a problem to be solved from the mathematicians' vision.
Deep sr-DDL: Deep Structurally Regularized Dynamic Dictionary Learning to Integrate Multimodal and Dynamic Functional Connectomics data for Multidimensional Clinical Characterizations
Venue: arXiv cs.LG 2024
Year: 2024

We propose a novel integrated framework that jointly models complementary information from resting-state functional MRI (rs-fMRI) connectivity and diffusion tensor imaging (DTI) tractography to extract biomarkers of brain connectivity predictive of behavior. Our framework couples a generative model of the connectomics data with a deep network that predicts behavioral scores. The generative component is a structurally-regularized Dynamic Dictionary Learning (sr-DDL) model that decomposes the dynamic rs-fMRI correlation matrices into a collection of shared basis networks and time varying subject-specific loadings. We use the DTI tractography to regularize this matrix factorization and learn anatomically informed functional connectivity profiles. The deep component of our framework is an LSTM-ANN block, which uses the temporal evolution of the subject-specific sr-DDL loadings to predict multidimensional clinical characterizations. Our joint optimization strategy collectively estimates the basis networks, the subject-specific time-varying loadings, and the neural network weights. We validate our framework on a dataset of neurotypical individuals from the Human Connectome Project (HCP) database to map to cognition and on a separate multi-score prediction task on individuals diagnosed with Autism Spectrum Disorder (ASD) in a five-fold cross validation setting. Our hybrid model outperforms several state-of-the-art approaches at clinical outcome prediction and learns interpretable multimodal neural signatures of brain organization.
KNN-DBSCAN: a DBSCAN in high dimensions
Venue: arXiv cs.DC 2024
Year: 2024

Clustering is a fundamental task in machine learning. One of the most successful and broadly used algorithms is DBSCAN, a density-based clustering algorithm. DBSCAN requires $ε$-nearest neighbor graphs of the input dataset, which are computed with range-search algorithms and spatial data structures like KD-trees. Despite many efforts to design scalable implementations for DBSCAN, existing work is limited to low-dimensional datasets, as constructing $ε$-nearest neighbor graphs is expensive in high-dimensions. In this paper, we modify DBSCAN to enable use of $κ$-nearest neighbor graphs of the input dataset. The $κ$-nearest neighbor graphs are constructed using approximate algorithms based on randomized projections. Although these algorithms can become inaccurate or expensive in high-dimensions, they possess a much lower memory overhead than constructing $ε$-nearest neighbor graphs. We delineate the conditions under which $k$NN-DBSCAN produces the same clustering as DBSCAN. We also present an efficient parallel implementation of the overall algorithm using OpenMP for shared memory and MPI for distributed memory parallelism. We present results on up to 16 billion points in 20 dimensions, and perform weak and strong scaling studies using synthetic data. Our code is efficient in both low and high dimensions. We can cluster one billion points in 3D in less than one second on 28K cores on the Frontera system at the Texas Advanced Computing Center (TACC). In our largest run, we cluster 65 billion points in 20 dimensions in less than 40 seconds using 114,688 x86 cores on TACC's Frontera system. Also, we compare with a state of the art parallel DBSCAN code; on 20d/4M point dataset, our code is up to 37$\times$ faster.
One head is better than two: a polynomial restriction for propositional definite Horn forgetting
Venue: arXiv cs.AI 2024
Year: 2024

Logical forgetting is \np-complete even in the simple case of propositional Horn formulae, and may exponentially increase their size. A way to forget is to replace each variable to forget with the body of each clause whose head is the variable. It takes polynomial time in the single-head case: each variable is at most the head of a clause. Some formulae are not single-head but can be made so to simplify forgetting. They are single-head equivalent. The first contribution of this article is the study of a semantical characterization of single-head equivalence. Two necessary conditions are given. They are sufficient when the formula is inequivalent: it makes two sets of variables equivalent only if they are also equivalent to their intersection. All acyclic formulae are inequivalent. The second contribution of this article is an incomplete algorithm for turning a formula single-head. In case of success, forgetting becomes possible in polynomial time and produces a polynomial-size formula, none of which is otherwise guaranteed. The algorithm is complete on inequivalent formulae.
Detectability of hierarchical communities in networks
Venue: arXiv cs.SI 2024
Year: 2024

We study the problem of recovering a planted hierarchy of partitions in a network. The detectability of a single planted partition has previously been analysed in detail and a phase transition has been identified below which the partition cannot be detected. Here we show that, in the hierarchical setting, there exist additional phases in which the presence of multiple consistent partitions can either help or hinder detection. Accordingly, the detectability limit for non-hierarchical partitions typically provides insufficient information about the detectability of the complete hierarchical structure, as we highlight with several constructive examples.
Regret Bounds and Reinforcement Learning Exploration of EXP-based Algorithms
Venue: arXiv cs.LG 2024
Year: 2024

We study the challenging exploration incentive problem in both bandit and reinforcement learning, where the rewards are scale-free and potentially unbounded, driven by real-world scenarios and differing from existing work. Past works in reinforcement learning either assume costly interactions with an environment or propose algorithms finding potentially low quality local maxima. Motivated by EXP-type methods that integrate multiple agents (experts) for exploration in bandits with the assumption that rewards are bounded, we propose new algorithms, namely EXP4.P and EXP4-RL for exploration in the unbounded reward case, and demonstrate their effectiveness in these new settings. Unbounded rewards introduce challenges as the regret cannot be limited by the number of trials, and selecting suboptimal arms may lead to infinite regret. Specifically, we establish EXP4.P's regret upper bounds in both bounded and unbounded linear and stochastic contextual bandits. Surprisingly, we also find that by including one sufficiently competent expert, EXP4.P can achieve global optimality in the linear case. This unbounded reward result is also applicable to a revised version of EXP3.P in the Multi-armed Bandit scenario. In EXP4-RL, we extend EXP4.P from bandit scenarios to reinforcement learning to incentivize exploration by multiple agents, including one high-performing agent, for both efficiency and excellence. This algorithm has been tested on difficult-to-explore games and shows significant improvements in exploration compared to state-of-the-art.
MAC Address Anonymization for Crowd Counting
Venue: arXiv cs.CR 2024
Year: 2024

Research has shown that counting WiFi packets called probe requests (PRs) implicitly provides a proxy for the number of people in an area. In this paper, we discuss a crowd counting system involving WiFi sensors detecting PRs over the air, then extracting and anonymizing their media access control (MAC) addresses using a hash-based approach. This paper discusses an anonymization procedure and shows time-synchronization inaccuracies among sensors and hashing collision rates to be low enough to prevent anonymization from interfering with counting algorithms. In particular, we derive an approximation of the collision rate of uniformly distributed identifiers, with analytical error bounds.
Claraprint: a chord and melody based fingerprint for western classical music cover detection
Venue: arXiv cs.IR 2024
Year: 2024

Cover song detection has been an active field in the Music Information Retrieval (MIR) community during the past decades. Most of the research community focused in solving it for a wide range of music genres with diverse characteristics. Western classical music, a genre heavily based on the recording of "cover songs", or musical works, represents a large heritage, offering immediate application for an efficient fingerprint algorithm. We propose an engineering approach for retrieving a cover song from a reference database thanks to a fingerprint designed for classical musical works. We open a new data set to encourage the scientific community to use it for further researches regarding this genre.
Pairbot: A Novel Model for Autonomous Mobile Robot Systems Consisting of Paired Robots
Venue: arXiv cs.DC 2024
Year: 2024

Programmable matter (PM) is a form of matter capable of dynamically altering its physical properties, such as shape or density, through programmable means. From a robotics perspective, PM can be realized as a distributed system consisting of numerous small computational entities working collaboratively to achieve specific objectives. Although autonomous mobile robot systems serve as an important example and have been researched for more than two decades, these robots often fail to perform even basic tasks, revealing a considerable gap in PM implementation. In this paper, we introduce a novel computational paradigm, termed the Pairing Robot model (Pairbot model), which is built on an autonomous mobile robot system. In this model, each robot forms a pair with another, enabling them to recognize each other and adapt their positions to achieve designated goals. This fundamental principle of pairing substantially enhances inter-robot connectivity compared to conventional LCM-type model, even under asynchronous scheduler conditions. This shift has considerable implications for computational capabilities, specifically in problem solvability. We explore two specific challenges -- the perpetual marching problem and the 7-pairbots-gathering problem -- to demonstrate the computational power of Pairbot model. This model provides new avenues and insights to address inherent issues in autonomous mobile robots.
Massive Uncoordinated Multiple Access for Beyond 5G
Venue: arXiv cs.IT 2024
Year: 2024

Existing wireless communication systems have been mainly designed to provide substantial gain in terms of data rates. However, 5G and Beyond will depart from this scheme, with the objective not only to provide services with higher data rates. One of the main goals is to support massive machine-type communications (mMTC) in the IoT applications. Supporting massive uplink (UP) communications for devices with sporadic traffic pattern and short-packet size, as it is in many mMTC use cases, is a challenging task, particularly when the control signaling is not negligible in size compared to the payload. Also, channel estimation is challenging for sporadic and short-packet transmission due to the limited number of employed pilots. In this paper, a new UP multiple access (MA) scheme is proposed for mMTC, which can support a large number of uncoordinated IoT devices with short-packet and sporadic traffic. The proposed UP MA scheme removes the overheads associated with the device identifier as well as pilots related to channel estimation. An alternative mechanism for device identification is proposed, where a unique spreading code is dedicated to each IoT device. This unique code is simultaneously used for the spreading purpose and device identification. Two IoT device identification algorithms which employ sparse signal reconstruction methods are proposed to determine the active IoT devices prior to data detection. Specifically, the BIC model order selection method is employed to develop an IoT device identification algorithm for unknown and time-varying probability of device activity. Our proposed MA scheme benefits from a non-coherent multiuser detection algorithm based on machine learning to enable data detection without a priori knowledge on channel state information. The effectiveness of the proposed MA scheme for known and unknown probability of activity is supported by simulation results.
Facebook Political Ads And Accountability: Outside Groups Are Most Negative, Especially When Hiding Donors
Venue: arXiv cs.CY 2024
Year: 2024

The emergence of online political advertising has come with little regulation, allowing political advertisers on social media to avoid accountability. We analyze how transparency and accountability deficits caused by dark money and disappearing groups relate to the sentiment of political ads on Facebook. We obtained 430,044 ads with FEC-registered advertisers from Facebook's ad library that ran between August-November 2018. We compare ads run by candidates, parties, and outside groups, which we classify by (1) their donor transparency (dark money or disclosed) and (2) the group's permanence (only FEC-registered in 2018 or persistent across cycles). The most negative advertising came from dark money and disappearing outside groups, which were mostly corporations or 501(c) organizations. However, only dark money was associated with a significant decrease in ad sentiment. These results suggest that accountability for political speech matters for advertising tone, especially in the context of affective polarization on social media.