OpenRaiser/Intern-Atlas huggingface dataset:
Unbiased Top-k Learning to Rank with Causal Likelihood Decomposition
Venue: arXiv cs.IR 2024
Year: 2024

Unbiased learning to rank has been proposed to alleviate the biases in the search ranking, making it possible to train ranking models with user interaction data. In real applications, search engines are designed to display only the most relevant k documents from the retrieved candidate set. The rest candidates are discarded. As a consequence, position bias and sample selection bias usually occur simultaneously. Existing unbiased learning to rank approaches either focus on one type of bias (e.g., position bias) or mitigate the position bias and sample selection bias with separate components, overlooking their associations. In this study, we first analyze the mechanisms and associations of position bias and sample selection bias from the viewpoint of a causal graph. Based on the analysis, we propose Causal Likelihood Decomposition (CLD), a unified approach to simultaneously mitigating these two biases in top-k learning to rank. By decomposing the log-likelihood of the biased data as an unbiased term that only related to relevance, plus other terms related to biases, CLD successfully detaches the relevance from position bias and sample selection bias. An unbiased ranking model can be obtained from the unbiased term, via maximizing the whole likelihood. An extension to the pairwise neural ranking is also developed. Advantages of CLD include theoretical soundness and a unified framework for pointwise and pairwise unbiased top-k learning to rank. Extensive experimental results verified that CLD, including its pairwise neural extension, outperformed the baselines by mitigating both the position bias and the sample selection bias. Empirical studies also showed that CLD is robust to the variation of bias severity and the click noise.
Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks
Venue: arXiv cs.LG 2024
Year: 2024

Lipschitz constants of neural networks allow for guarantees of robustness in image classification, safety in controller design, and generalizability beyond the training data. As calculating Lipschitz constants is NP-hard, techniques for estimating Lipschitz constants must navigate the trade-off between scalability and accuracy. In this work, we significantly push the scalability frontier of a semidefinite programming technique known as LipSDP while achieving zero accuracy loss. We first show that LipSDP has chordal sparsity, which allows us to derive a chordally sparse formulation that we call Chordal-LipSDP. The key benefit is that the main computational bottleneck of LipSDP, a large semidefinite constraint, is now decomposed into an equivalent collection of smaller ones: allowing Chordal-LipSDP to outperform LipSDP particularly as the network depth grows. Moreover, our formulation uses a tunable sparsity parameter that enables one to gain tighter estimates without incurring a significant computational cost. We illustrate the scalability of our approach through extensive numerical experiments.
Quadratic Neuron-empowered Heterogeneous Autoencoder for Unsupervised Anomaly Detection
Venue: arXiv cs.NE 2024
Year: 2024

Inspired by the complexity and diversity of biological neurons, a quadratic neuron is proposed to replace the inner product in the current neuron with a simplified quadratic function. Employing such a novel type of neurons offers a new perspective on developing deep learning. When analyzing quadratic neurons, we find that there exists a function such that a heterogeneous network can approximate it well with a polynomial number of neurons but a purely conventional or quadratic network needs an exponential number of neurons to achieve the same level of error. Encouraged by this inspiring theoretical result on heterogeneous networks, we directly integrate conventional and quadratic neurons in an autoencoder to make a new type of heterogeneous autoencoders. To our best knowledge, it is the first heterogeneous autoencoder that is made of different types of neurons. Next, we apply the proposed heterogeneous autoencoder to unsupervised anomaly detection for tabular data and bearing fault signals. The anomaly detection faces difficulties such as data unknownness, anomaly feature heterogeneity, and feature unnoticeability, which is suitable for the proposed heterogeneous autoencoder. Its high feature representation ability can characterize a variety of anomaly data (heterogeneity), discriminate the anomaly from the normal (unnoticeability), and accurately learn the distribution of normal samples (unknownness). Experiments show that heterogeneous autoencoders perform competitively compared to other state-of-the-art models.
How do media talk about the Covid-19 pandemic? Metaphorical thematic clustering in Italian online newspapers
Venue: arXiv cs.CL 2024
Year: 2024

The contribution presents a study on figurative language of the first months of the COVID-19 crisis in Italian online newspapers. Particularly, we contrast topics and metaphorical language used by journalists in the first and second phase of the government response to the pandemic in Spring 2020. The analysis is conducted on a journalistic corpus collected between February 24th and June 3rd, 2020. The analysis is performed using both quantitative and qualitative approaches, combining Structural Topic Modelling (Roberts et al. 2016), Conceptual Metaphor Theory (Lakoff & Johnson, 1980), and qualitative-corpus based metaphor analysis (Charteris-Black, 2004). We find a significant shift in topics discussed across Phase 1 and Phase 2, and interesting overlaps in topic-specific metaphors. Using qualitative corpus analysis, we present a more in-depth case study discussing metaphorical collocations of the topics of Economy and Society
Breaking through the $Ω(n)$-space barrier: Population Protocols Decide Double-exponential Thresholds
Venue: arXiv cs.DC 2024
Year: 2024

Population protocols are a model of distributed computation in which finite-state agents interact randomly in pairs. A protocol decides for any initial configuration whether it satisfies a fixed property, specified as a predicate on the set of configurations. A family of protocols deciding predicates $φ_n$ is succinct if it uses $\mathcal{O}(|φ_n|)$ states, where $φ_n$ is encoded as quantifier-free Presburger formula with coefficients in binary. (All predicates decidable by population protocols can be encoded in this manner.) While it is known that succinct protocols exist for all predicates, it is open whether protocols with $o(|φ_n|)$ states exist for \emph{any} family of predicates $φ_n$. We answer this affirmatively, by constructing protocols with $\mathcal{O}(\log|φ_n|)$ states for some family of threshold predicates $φ_n(x)\Leftrightarrow x\ge k_n$, with $k_1,k_2,...\in\mathbb{N}$. (In other words, protocols with $\mathcal{O}(n)$ states that decide $x\ge k$ for a $k\ge 2^{2^n}$.) This matches a known lower bound. Moreover, our construction for threshold predicates is the first that is not $1$-aware, and it is almost self-stabilising.
Computing in Anonymous Dynamic Networks Is Linear
Venue: arXiv cs.DC 2024
Year: 2024

We give the first linear-time counting algorithm for processes in anonymous 1-interval-connected dynamic networks with a leader. As a byproduct, we are able to compute in $3n$ rounds every function that is deterministically computable in such networks. If explicit termination is not required, the running time improves to $2n$ rounds, which we show to be optimal up to a small additive constant (this is also the first non-trivial lower bound for counting). As our main tool of investigation, we introduce a combinatorial structure called "history tree", which is of independent interest. This makes our paper completely self-contained, our proofs elegant and transparent, and our algorithms straightforward to implement. In recent years, considerable effort has been devoted to the design and analysis of counting algorithms for anonymous 1-interval-connected networks with a leader. A series of increasingly sophisticated works, mostly based on classical mass-distribution techniques, have recently led to a celebrated counting algorithm in $O({n^{4+ ε}} \log^{3} (n))$ rounds (for $ε>0$), which was the state of the art prior to this paper. Our contribution not only opens a promising line of research on applications of history trees, but also demonstrates that computation in anonymous dynamic networks is practically feasible, and far less demanding than previously conjectured.
Encodability Criteria for Quantum Based Systems
Venue: arXiv cs.LO 2024
Year: 2024

Quantum based systems are a relatively new research area for that different modelling languages including process calculi are currently under development. Encodings are often used to compare process calculi. Quality criteria are used then to rule out trivial or meaningless encodings. In this new context of quantum based systems, it is necessary to analyse the applicability of these quality criteria and to potentially extend or adapt them. As a first step, we test the suitability of classical criteria for encodings between quantum based languages and discuss new criteria. Concretely, we present an encoding, from a language inspired by CQP into a language inspired by qCCS. We show that this encoding satisfies compositionality, name invariance (for channel and qubit names), operational correspondence, divergence reflection, success sensitiveness, and that it preserves the size of quantum registers. Then we show that there is no encoding from qCCS into CQP that is compositional, operationally corresponding, and success sensitive.
OneMax is not the Easiest Function for Fitness Improvements
Venue: arXiv cs.NE 2024
Year: 2024

We study the $(1:s+1)$ success rule for controlling the population size of the $(1,λ)$-EA. It was shown by Hevia Fajardo and Sudholt that this parameter control mechanism can run into problems for large $s$ if the fitness landscape is too easy. They conjectured that this problem is worst for the OneMax benchmark, since in some well-established sense OneMax is known to be the easiest fitness landscape. In this paper we disprove this conjecture and show that OneMax is not the easiest fitness landscape with respect to finding improving steps. As a consequence, we show that there exists $s$ and $\varepsilon$ such that the self-adjusting $(1,λ)$-EA with $(1:s+1)$-rule optimizes OneMax efficiently when started with $\varepsilon n$ zero-bits, but does not find the optimum in polynomial time on Dynamic BinVal. Hence, we show that there are landscapes where the problem of the $(1:s+1)$-rule for controlling the population size of the $(1, λ)$-EA is more severe than for OneMax.
Towards cost-effective and resource-aware aggregation at Edge for Federated Learning
Venue: arXiv cs.LG 2024
Year: 2024

Federated Learning (FL) is a machine learning approach that addresses privacy and data transfer costs by computing data at the source. It's particularly popular for Edge and IoT applications where the aggregator server of FL is in resource-capped edge data centers for reducing communication costs. Existing cloud-based aggregator solutions are resource-inefficient and expensive at the Edge, leading to low scalability and high latency. To address these challenges, this study compares prior and new aggregation methodologies under the changing demands of IoT and Edge applications. This work is the first to propose an adaptive FL aggregator at the Edge, enabling users to manage the cost and efficiency trade-off. An extensive comparative analysis demonstrates that the design improves scalability by up to 4X, time efficiency by 8X, and reduces costs by more than 2X compared to extant cloud-based static methodologies.
Multiple-environment Self-adaptive Network for Aerial-view Geo-localization
Venue: arXiv cs.CV 2024
Year: 2024

Aerial-view geo-localization tends to determine an unknown position through matching the drone-view image with the geo-tagged satellite-view image. This task is mostly regarded as an image retrieval problem. The key underpinning this task is to design a series of deep neural networks to learn discriminative image descriptors. However, existing methods meet large performance drops under realistic weather, such as rain and fog, since they do not take the domain shift between the training data and multiple test environments into consideration. To minor this domain gap, we propose a Multiple-environment Self-adaptive Network (MuSe-Net) to dynamically adjust the domain shift caused by environmental changing. In particular, MuSe-Net employs a two-branch neural network containing one multiple-environment style extraction network and one self-adaptive feature extraction network. As the name implies, the multiple-environment style extraction network is to extract the environment-related style information, while the self-adaptive feature extraction network utilizes an adaptive modulation module to dynamically minimize the environment-related style gap. Extensive experiments on two widely-used benchmarks, i.e., University-1652 and CVUSA, demonstrate that the proposed MuSe-Net achieves a competitive result for geo-localization in multiple environments. Furthermore, we observe that the proposed method also shows great potential to the unseen extreme weather, such as mixing the fog, rain and snow.
CoFHEE: A Co-processor for Fully Homomorphic Encryption Execution (Extended Version)
Venue: arXiv cs.CR 2024
Year: 2024

The migration of computation to the cloud has raised concerns regarding the security and privacy of sensitive data, as their need to be decrypted before processing, renders them susceptible to potential breaches. Fully Homomorphic Encryption (FHE) serves as a countermeasure to this issue by enabling computation to be executed directly on encrypted data. Nevertheless, the execution of FHE is orders of magnitude slower compared to unencrypted computation, thereby impeding its practicality and adoption. Therefore, enhancing the performance of FHE is crucial for its implementation in real-world scenarios. In this study, we elaborate on our endeavors to design, implement, fabricate, and post-silicon validate CoFHEE, a co-processor for low-level polynomial operations targeting Fully Homomorphic Encryption execution. With a compact design area of $12mm^2$, CoFHEE features ASIC implementations of fundamental polynomial operations, including polynomial addition and subtraction, Hadamard product, and Number Theoretic Transform, which underlie most higher-level FHE primitives. CoFHEE is capable of natively supporting polynomial degrees of up to $n = 2^{14}$ with a coefficient size of 128 bits, and has been fabricated and silicon-verified using 55nm CMOS technology. To evaluate it, we conduct performance and power experiments on our chip, and compare it to state-of-the-art software implementations and other ASIC designs.
Conceptual structure and the growth of scientific knowledge
Venue: arXiv cs.SI 2024
Year: 2024

How does scientific knowledge grow? This question has occupied a central place in the philosophy of science, stimulating heated debates, but yielding no clear consensus. Many explanations can be understood in terms of whether and how they view the expansion of knowledge as proceeding through the accretion of scientific concepts into larger conceptual structures. Here, we examine these views empirically, performing a large-scale analysis of the physical and social sciences, spanning five decades. Using natural language processing techniques, we create semantic networks of concepts, wherein noun phrases become linked when used in the same paper abstract. For both the physical and social sciences, we observe increasingly rigid conceptual cores (i.e., densely connected sets of highly central nodes) accompanied by the proliferation of periphery concepts (i.e., sparsely connected nodes that are highly connected to the core). Subsequently, we examine the relationship between conceptual structure and the growth of scientific knowledge, finding that scientific works are more innovative in fields with cores that have higher conceptual churn and with larger cores. Furthermore, scientific consensus is associated with reduced conceptual churn and fewer conceptual cores. Overall, our findings suggest that while the organization of scientific concepts is important for the growth of knowledge, the mechanisms vary across time.
A benchmark dataset for deep learning-based airplane detection: HRPlanes
Venue: arXiv cs.CV 2024
Year: 2024

Airplane detection from satellite imagery is a challenging task due to the complex backgrounds in the images and differences in data acquisition conditions caused by the sensor geometry and atmospheric effects. Deep learning methods provide reliable and accurate solutions for automatic detection of airplanes; however, huge amount of training data is required to obtain promising results. In this study, we create a novel airplane detection dataset called High Resolution Planes (HRPlanes) by using images from Google Earth (GE) and labeling the bounding box of each plane on the images. HRPlanes include GE images of several different airports across the world to represent a variety of landscape, seasonal and satellite geometry conditions obtained from different satellites. We evaluated our dataset with two widely used object detection methods namely YOLOv4 and Faster R-CNN. Our preliminary results show that the proposed dataset can be a valuable data source and benchmark data set for future applications. Moreover, proposed architectures and results of this study could be used for transfer learning of different datasets and models for airplane detection.
Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation
Venue: arXiv cs.IT 2024
Year: 2024

We consider the problem of evaluating arbitrary multivariate polynomials over a massive dataset containing multiple inputs, on a distributed computing system with a master node and multiple worker nodes. Generalized Lagrange Coded Computing (GLCC) codes are proposed to simultaneously provide resiliency against stragglers who do not return computation results in time, security against adversarial workers who deliberately modify results for their benefit, and information-theoretic privacy of the dataset amidst possible collusion of workers. GLCC codes are constructed by first partitioning the dataset into multiple groups, then encoding the dataset using carefully designed interpolating polynomials, and sharing multiple encoded data points to each worker, such that interference computation results across groups can be eliminated at the master. Particularly, GLCC codes include the state-of-the-art Lagrange Coded Computing (LCC) codes as a special case, and exhibit a more flexible tradeoff between communication and computation overheads in optimizing system efficiency. Furthermore, we apply GLCC to distributed training of machine learning models, and demonstrate that GLCC codes achieve a speedup of up to $2.5\text{--}3.9\times$ over LCC codes in training time, across experiments for training image classifiers on different datasets, model architectures, and straggler patterns.
Parallel Synthesis for Autoregressive Speech Generation
Venue: arXiv cs.SD 2024
Year: 2024

Autoregressive neural vocoders have achieved outstanding performance in speech synthesis tasks such as text-to-speech and voice conversion. An autoregressive vocoder predicts a sample at some time step conditioned on those at previous time steps. Though it synthesizes natural human speech, the iterative generation inevitably makes the synthesis time proportional to the utterance length, leading to low efficiency. Many works were dedicated to generating the whole speech sequence in parallel and proposed GAN-based, flow-based, and score-based vocoders. This paper proposed a new thought for the autoregressive generation. Instead of iteratively predicting samples in a time sequence, the proposed model performs frequency-wise autoregressive generation (FAR) and bit-wise autoregressive generation (BAR) to synthesize speech. In FAR, a speech utterance is split into frequency subbands, and a subband is generated conditioned on the previously generated one. Similarly, in BAR, an 8-bit quantized signal is generated iteratively from the first bit. By redesigning the autoregressive method to compute in domains other than the time domain, the number of iterations in the proposed model is no longer proportional to the utterance length but to the number of subbands/bits, significantly increasing inference efficiency. Besides, a post-filter is employed to sample signals from output posteriors; its training objective is designed based on the characteristics of the proposed methods. Experimental results show that the proposed model can synthesize speech faster than real-time without GPU acceleration. Compared with baseline vocoders, the proposed model achieves better MUSHRA results and shows good generalization ability for unseen speakers and 44 kHz speech.
Incentives in Social Decision Schemes with Pairwise Comparison Preferences
Venue: arXiv cs.GT 2024
Year: 2024

Social decision schemes (SDSs) map the ordinal preferences of individual voters over multiple alternatives to a probability distribution over the alternatives. In order to study the axiomatic properties of SDSs, we lift preferences over alternatives to preferences over lotteries using the natural -- but little understood -- pairwise comparison (PC) preference extension. This extension postulates that one lottery is preferred to another if the former is more likely to return a preferred outcome. We settle three open questions raised by Brandt (2017): (i) there is no Condorcet-consistent SDS that satisfies PC-strategyproofness; (ii) there is no anonymous and neutral SDS that satisfies PC-efficiency and PC-strategyproofness; and (iii) there is no anonymous and neutral SDS that satisfies PC-efficiency and strict PC-participation. All three impossibilities require $m\geq 4$ alternatives and turn into possibilities when $m\leq 3$. We furthermore settle an open problem raised by Aziz et al. (2015) by showing that no path of PC-improvements originating from an inefficient lottery may lead to a PC-efficient lottery.
On the limitations of data-based price discrimination
Venue: arXiv cs.GT 2024
Year: 2024

The classic third degree price discrimination (3PD) model requires the knowledge of the distribution of buyer valuations and the covariate to set the price conditioned on the covariate. In terms of generating revenue, the classic result shows that 3PD is at least as good as uniform pricing. What if the seller has to set a price based only on a sample of observations from the underlying distribution? Is it still obvious that the seller should engage in 3PD? This paper sheds light on these fundamental questions. In particular, the comparison of the revenue performance between 3PD and uniform pricing is ambiguous overall when prices are set based on samples. This finding is in the nature of statistical learning under uncertainty: a curse of dimensionality, but also other small sample complications.