OpenRaiser/Intern-Atlas huggingface dataset:
How social influence affects the wisdom of crowds in influence networks
Venue: arXiv cs.SI 2023
Year: 2023

A long-standing debate is whether social influence improves the collective wisdom of a crowd or undermines it. This paper addresses this question based on a naive learning setting in influence systems theory: in our models individuals evolve their estimates of an unknown truth according to the weighted-average opinion dynamics. A formal mathematization is provided with rigorous theoretical analysis. We obtain various conditions for improving, optimizing and undermining the crowd accuracy, respectively. We prove that if the wisdom of finite-size group is improved, then the collective estimate converges to the truth as group size increases, provided individuals' variances are finite. We show that whether social influence improves or undermines the wisdom is determined by the social power allocation of the influence system: if the influence system allocates relatively larger social power to relatively more accurate individuals, it improves the wisdom; on the contrary, if the influence system assigns less social power to more accurate individuals, it undermines the wisdom. At a population level, individuals' susceptibilities to interpersonal influence and network centralities are both crucial. To improve the wisdom, more accurate individuals should be less susceptible and have larger network centralities. Particularly, in democratic influence networks, if relatively more accurate individuals are relatively less susceptible, the wisdom is improved; if more accurate individuals are more susceptible, the wisdom is undermined, which is consistent with the reported empirical evidence. Our investigation provides a theoretical framework for understanding the role social influence plays in the emergence of collective wisdom.
Preferential attachment hypergraph with vertex deactivation
Venue: arXiv cs.DM 2023
Year: 2023

In the field of complex networks, hypergraph models have so far received significantly less attention than graphs. However, many real-life networks feature multiary relations (co-authorship, protein reactions) may therefore be modeled way better by hypergraphs. Also, a recent study by Broido and Clauset suggests that a power-law degree distribution is not as ubiquitous in the natural systems as it was thought so far. They experimentally confirm that a majority of networks (56% of around 1000 networks that undergone the test) favor a power-law with an exponential cutoff over other distributions. We address the two above observations by introducing a preferential attachment hypergraph model which allows for vertex deactivations. The phenomenon of vertex deactivations is rare in existing theoretical models and omnipresent in real-life scenarios (social network accounts which are not maintained forever, collaboration networks in which people retire, technological networks in which devices break down). We prove that the degree distribution of the proposed model follows a power-law with an exponential cutoff. We also check experimentally that a Scopus collaboration network has the same characteristic. We believe that our model will predict well the behavior of systems from a variety of domains.
What Petri Net Obliges Us to Say: Comparing Approaches for Behavior Composition
Venue: arXiv cs.SE 2023
Year: 2023

We identify and demonstrate a weakness of Petri Nets (PN) in specifying composite behavior of reactive systems. Specifically, we show how, when specifying multiple requirements in one PN model, modelers are obliged to specify mechanisms for combining these requirements. This yields, in many cases, over-specification and incorrect models. We demonstrate how some execution paths are missed, and some are generated unintentionally. To support this claim, we analyze PN models from the literature, identify the combination mechanisms, and demonstrate their effect on the correctness of the model. To address this problem, we propose to model the system behavior using behavioral programming (BP), a software development and modeling paradigm designed for seamless integration of independent requirements. Specifically, we demonstrate how the semantics of BP, which define how to interweave scenarios into a single model, allow avoiding the over-specification. Additionally, while BP maintains the same mathematical properties as PN, it provides means for changing the model dynamically, thus increasing the agility of the specification. We compare BP and PN in quantitative and qualitative measures by analyzing the models, their generated execution paths, and the specification process. Finally, while BP is supported by tools that allow for applying formal methods and reasoning techniques to the model, it lacks the legacy of PN tools and algorithms. To address this issue, we propose semantics and a tool for translating BP models to PN and vice versa.
AdapterBias: Parameter-efficient Token-dependent Representation Shift for Adapters in NLP Tasks
Venue: arXiv cs.CL 2023
Year: 2023

Transformer-based pre-trained models with millions of parameters require large storage. Recent approaches tackle this shortcoming by training adapters, but these approaches still require a relatively large number of parameters. In this study, AdapterBias, a surprisingly simple yet effective adapter architecture, is proposed. AdapterBias adds a token-dependent shift to the hidden output of transformer layers to adapt to downstream tasks with only a vector and a linear layer. Extensive experiments are conducted to demonstrate the effectiveness of AdapterBias. The experiments show that our proposed method can dramatically reduce the trainable parameters compared to the previous works with a minimal decrease in task performances compared with fine-tuned pre-trained models. We further find that AdapterBias automatically learns to assign more significant representation shifts to the tokens related to the task in consideration.
Improved Reconstruction for Fourier-Sparse Signals
Venue: arXiv cs.DS 2023
Year: 2023

We revisit the classical problem of Fourier-sparse signal reconstruction -- a variant of the \emph{Set Query} problem -- which asks to efficiently reconstruct (a subset of) a $d$-dimensional Fourier-sparse signal ($\|\hat{x}(t)\|_0 \leq k$), from minimum \emph{noisy} samples of $x(t)$ in the time domain. We present a unified framework for this problem by developing a theory of sparse Fourier transforms (SFT) for frequencies lying on a \emph{lattice}, which can be viewed as a ``semi-continuous'' version of SFT in between discrete and continuous domains. Using this framework, we obtain the following results: $\bullet$ **Dimension-free Fourier sparse recovery** We present a sample-optimal discrete Fourier Set-Query algorithm with $O(k^{ω+1})$ reconstruction time in one dimension, \emph{independent} of the signal's length ($n$) and $\ell_\infty$-norm. This complements the state-of-art algorithm of [Kapralov, STOC 2017], whose reconstruction time is $\tilde{O}(k \log^2 n \log R^*)$, where $R^* \approx \|\hat{x}\|_\infty$ is a signal-dependent parameter, and the algorithm is limited to low dimensions. By contrast, our algorithm works for arbitrary $d$ dimensions, mitigating the $\exp(d)$ blowup in decoding time to merely linear in $d$. A key component in our algorithm is fast spectral sparsification of the Fourier basis. $\bullet$ **High-accuracy Fourier interpolation** In one dimension, we design a poly-time $(3+ \sqrt{2} +ε)$-approximation algorithm for continuous Fourier interpolation. This bypasses a barrier of all previous algorithms [Price and Song, FOCS 2015, Chen, Kane, Price and Song, FOCS 2016], which only achieve $c>100$ approximation for this basic problem. Our main contribution is a new analytic tool for hierarchical frequency decomposition based on \emph{noise cancellation}.
Evocube: a Genetic Labeling Framework for Polycube-Maps
Venue: arXiv cs.GR 2023
Year: 2023

Polycube-maps are used as base-complexes in various fields of computational geometry, including the generation of regular all-hexahedral meshes free of internal singularities. However, the strict alignment constraints behind polycube-based methods make their computation challenging for CAD models used in numerical simulation via Finite Element Method (FEM). We propose a novel approach based on an evolutionary algorithm to robustly compute polycube-maps in this context. We address the labeling problem, which aims to precompute polycube alignment by assigning one of the base axes to each boundary face on the input. Previous research has described ways to initialize and improve a labeling via greedy local fixes. However, such algorithms lack robustness and often converge to inaccurate solutions for complex geometries. Our proposed framework alleviates this issue by embedding labeling operations in an evolutionary heuristic, defining fitness, crossover, and mutations in the context of labeling optimization. We evaluate our method on a thousand smooth and CAD meshes, showing Evocube converges to valid labelings on a wide range of shapes. The limitations of our method are also discussed thoroughly.
Imagining, Studying and Realising A Less Harmful App Ecosystem
Venue: arXiv cs.HC 2023
Year: 2023

Desktop browser extensions have long allowed users to improve their experience online and tackle widespread harms on websites. So far, no equivalent solution exists for mobile apps, despite the fact that individuals now spend significantly more time on mobile than on desktop, and arguably face similarly widespread harms. In this work, we investigate mobile app extensions, a previously underexplored concept to study and address digital harms within mobile apps in a decentralised, community-driven way. We analyse challenges to adoption of this approach so far, and present a ready-to-use implementation for Android as a result of significant and careful system development. Through a range of case studies, we demonstrate that our implementation can already reduce (though not completely eliminate) a wide range of harms - similarly as browser extensions do on desktops. Our method provides a versatile foundation for a range of follow-up research into digital harms in mobile apps that has not previously been possible, given that browser extensions have long been a fruitful foundation for research studies on desktops. In other words, our system tries to address the gap of a focus on desktop interventions in previous research.
Traction of Interlocking Spikes on a Granular Material
Venue: arXiv cs.RO 2023
Year: 2023

The interlock drive system generates traction by inserting narrow articulated spikes into the ground and by leveraging the soil's strength to resist horizontal draft forces. The system promises high tractive performance in low gravity environments where tires have little traction for lack of weight. At Earth and Space 2021 we reported the performance of such spikes on a silty clay loam, a cohesive soil. We found that in such soil, traction below a critical depth is provided by a zone of lateral soil failure. We also found that the articulation translates a horizontal draft force into a vertical penetration force strong enough to penetrate a narrow spike to a depth where the soil can sustain the draft force, in a self-regulating way. It is conceivable that a granular material like regolith or sand with little to no cohesive strength provides less vertical penetration resistance and less resistance to a horizontal draft force than a cohesive soil, which leads to the question of whether and how much tractive force an interlocking spike can generate on a granular material. Here we report on field trials that study different spike designs in dry and unsaturated moist sand. The results demonstrate that a loose granular material requires larger spikes than a cohesive soil, that these larger spikes penetrate dry and moist sand reliably, and that they promise good tractive efficiency. The trials indicate that on sand, a larger spike diameter can improve the pull/weight ratio without a loss of tractive performance.
Star-specific Key-homomorphic PRFs from Learning with Linear Regression
Venue: arXiv cs.CR 2023
Year: 2023

We introduce a novel method to derandomize the learning with errors (LWE) problem by generating deterministic yet sufficiently independent LWE instances that are constructed by using linear regression models, which are generated via (wireless) communication errors. We also introduce star-specific key-homomorphic (SSKH) pseudorandom functions (PRFs), which are defined by the respective sets of parties that construct them. We use our derandomized variant of LWE to construct a SSKH PRF family. The sets of parties constructing SSKH PRFs are arranged as star graphs with possibly shared vertices, i.e., the pairs of sets may have non-empty intersections. We reduce the security of our SSKH PRF family to the hardness of LWE. To establish the maximum number of SSKH PRFs that can be constructed -- by a set of parties -- in the presence of passive/active and external/internal adversaries, we prove several bounds on the size of maximally cover-free at most $t$-intersecting $k$-uniform family of sets $\mathcal{H}$, where the three properties are defined as: (i) $k$-uniform: $\forall A \in \mathcal{H}: |A| = k$, (ii) at most $t$-intersecting: $\forall A, B \in \mathcal{H}, B \neq A: |A \cap B| \leq t$, (iii) maximally cover-free: $\forall A \in \mathcal{H}: A \not\subseteq \bigcup\limits_{\substack{B \in \mathcal{H} \\ B \neq A}} B$. For the same purpose, we define and compute the mutual information between different linear regression hypotheses that are generated from overlapping training datasets.
Transformers in Time-series Analysis: A Tutorial
Venue: arXiv cs.LG 2023
Year: 2023

Transformer architecture has widespread applications, particularly in Natural Language Processing and computer vision. Recently Transformers have been employed in various aspects of time-series analysis. This tutorial provides an overview of the Transformer architecture, its applications, and a collection of examples from recent research papers in time-series analysis. We delve into an explanation of the core components of the Transformer, including the self-attention mechanism, positional encoding, multi-head, and encoder/decoder. Several enhancements to the initial, Transformer architecture are highlighted to tackle time-series tasks. The tutorial also provides best practices and techniques to overcome the challenge of effectively training Transformers for time-series analysis.
Automatic Segmentation of Aircraft Dents in Point Clouds
Venue: arXiv cs.CV 2023
Year: 2023

Dents on the aircraft skin are frequent and may easily go undetected during airworthiness checks, as their inspection process is tedious and extremely subject to human factors and environmental conditions. Nowadays, 3D scanning technologies are being proposed for more reliable, human-independent measurements, yet the process of inspection and reporting remains laborious and time consuming because data acquisition and validation are still carried out by the engineer. For full automation of dent inspection, the acquired point cloud data must be analysed via a reliable segmentation algorithm, releasing humans from the search and evaluation of damage. This paper reports on two developments towards automated dent inspection. The first is a method to generate a synthetic dataset of dented surfaces to train a fully convolutional neural network. The training of machine learning algorithms needs a substantial volume of dent data, which is not readily available. Dents are thus simulated in random positions and shapes, within criteria and definitions of a Boeing 737 structural repair manual. The noise distribution from the scanning apparatus is then added to reflect the complete process of 3D point acquisition on the training. The second proposition is a surface fitting strategy to convert 3D point clouds to 2.5D. This allows higher resolution point clouds to be processed with a small amount of memory compared with state-of-the-art methods involving 3D sampling approaches. Simulations with available ground truth data show that the proposed technique reaches an intersection-over-union of over 80%. Experiments over dent samples prove an effective detection of dents with a speed of over 500 000 points per second.
Rooted America: Immobility and Segregation of the Intercounty Migration Network
Venue: arXiv cs.SI 2023
Year: 2023

Despite the popular narrative that the United States is a "land of mobility," the country may have become a "rooted America" after a decades-long decline in migration rates. This article interrogates the lingering question about the social forces that limit migration, with an empirical focus on internal migration in the United States. We propose a systemic, network model of migration flows, combining demographic, economic, political, and geographic factors and network dependence structures that reflect the internal dynamics of migration systems. Using valued temporal exponential-family random graph models, we model the network of intercounty migration flows from 2011 to 2015. Our analysis reveals a pattern of segmented immobility, where fewer people migrate between counties with dissimilar political contexts, levels of urbanization, and racial compositions. Probing our model using "knockout experiments" suggests one would have observed approximately 4.6 million (27 percent) more intercounty migrants each year were the segmented immobility mechanisms inoperative. This article offers a systemic view of internal migration and reveals the social and political cleavages that underlie geographic immobility in the United States.
Communication-Efficient Adaptive Federated Learning
Venue: arXiv cs.LG 2023
Year: 2023

Federated learning is a machine learning training paradigm that enables clients to jointly train models without sharing their own localized data. However, the implementation of federated learning in practice still faces numerous challenges, such as the large communication overhead due to the repetitive server-client synchronization and the lack of adaptivity by SGD-based model updates. Despite that various methods have been proposed for reducing the communication cost by gradient compression or quantization, and the federated versions of adaptive optimizers such as FedAdam are proposed to add more adaptivity, the current federated learning framework still cannot solve the aforementioned challenges all at once. In this paper, we propose a novel communication-efficient adaptive federated learning method (FedCAMS) with theoretical convergence guarantees. We show that in the nonconvex stochastic optimization setting, our proposed FedCAMS achieves the same convergence rate of $O(\frac{1}{\sqrt{TKm}})$ as its non-compressed counterparts. Extensive experiments on various benchmarks verify our theoretical analysis.
Probabilistic Control and Majorization of Optimal Control
Venue: arXiv cs.LG 2023
Year: 2023

Probabilistic control design is founded on the principle that a rational agent attempts to match modelled with an arbitrary desired closed-loop system trajectory density. The framework was originally proposed as a tractable alternative to traditional optimal control design, parametrizing desired behaviour through fictitious transition and policy densities and using the information projection as a proximity measure. In this work we introduce an alternative parametrization of desired closed-loop behaviour and explore alternative proximity measures between densities. It is then illustrated how the associated probabilistic control problems solve into uncertain or probabilistic policies. Our main result is to show that the probabilistic control objectives majorize conventional, stochastic and risk sensitive, optimal control objectives. This observation allows us to identify two probabilistic fixed point iterations that converge to the deterministic optimal control policies establishing an explicit connection between either formulations. Further we demonstrate that the risk sensitive optimal control formulation is also technically equivalent to a Maximum Likelihood estimation problem on a probabilistic graph model where the notion of costs is directly encoded into the model. The associated treatment of the estimation problem is then shown to coincide with the moment projected probabilistic control formulation. That way optimal decision making can be reformulated as an iterative inference problem. Based on these insights we discuss directions for algorithmic development.
Forget Less, Count Better: A Domain-Incremental Self-Distillation Learning Benchmark for Lifelong Crowd Counting
Venue: arXiv cs.CV 2023
Year: 2023

Crowd counting has important applications in public safety and pandemic control. A robust and practical crowd counting system has to be capable of continuously learning with the new incoming domain data in real-world scenarios instead of fitting one domain only. Off-the-shelf methods have some drawbacks when handling multiple domains: (1) the models will achieve limited performance (even drop dramatically) among old domains after training images from new domains due to the discrepancies of intrinsic data distributions from various domains, which is called catastrophic forgetting; (2) the well-trained model in a specific domain achieves imperfect performance among other unseen domains because of the domain shift; and (3) it leads to linearly increasing storage overhead, either mixing all the data for training or simply training dozens of separate models for different domains when new ones are available. To overcome these issues, we investigated a new crowd counting task in the incremental domains training setting called Lifelong Crowd Counting. Its goal is to alleviate the catastrophic forgetting and improve the generalization ability using a single model updated by the incremental domains. Specifically, we propose a self-distillation learning framework as a benchmark (Forget Less, Count Better, or FLCB) for lifelong crowd counting, which helps the model sustainably leverage previous meaningful knowledge for better crowd counting to mitigate the forgetting when the new data arrive. In addition, a new quantitative metric, normalized backward transfer (nBwT), is developed to evaluate the forgetting degree of the model in the lifelong learning process. Extensive experimental results demonstrate the superiority of our proposed benchmark in achieving a low catastrophic forgetting degree and strong generalization ability.
Machine Learning-Friendly Biomedical Datasets for Equivalence and Subsumption Ontology Matching
Venue: arXiv cs.AI 2023
Year: 2023

Ontology Matching (OM) plays an important role in many domains such as bioinformatics and the Semantic Web, and its research is becoming increasingly popular, especially with the application of machine learning (ML) techniques. Although the Ontology Alignment Evaluation Initiative (OAEI) represents an impressive effort for the systematic evaluation of OM systems, it still suffers from several limitations including limited evaluation of subsumption mappings, suboptimal reference mappings, and limited support for the evaluation of ML-based systems. To tackle these limitations, we introduce five new biomedical OM tasks involving ontologies extracted from Mondo and UMLS. Each task includes both equivalence and subsumption matching; the quality of reference mappings is ensured by human curation, ontology pruning, etc.; and a comprehensive evaluation framework is proposed to measure OM performance from various perspectives for both ML-based and non-ML-based OM systems. We report evaluation results for OM systems of different types to demonstrate the usage of these resources, all of which are publicly available as part of the new BioML track at OAEI 2022.