OpenRaiser/Intern-Atlas huggingface dataset:
Tracking Truth with Liquid Democracy
Venue: arXiv cs.DM 2024
Year: 2024

The dynamics of random transitive delegations on a graph are of particular interest when viewed through the lens of an emerging voting paradigm, liquid democracy. This paradigm allows voters to choose between directly voting and transitively delegating their votes to other voters, so that those selected cast a vote weighted by the number of delegations they received. In the epistemic setting, where voters decide on a binary issue for which there is a ground truth, previous work showed that a few voters may amass such a large amount of influence that liquid democracy is less likely to identify the ground truth than direct voting. We quantify the amount of permissible concentration of power and examine more realistic delegation models, showing they behave well by ensuring that (with high probability) there is a permissible limit on the maximum number of delegations received. Our theoretical results demonstrate that the delegation process is similar to well-known processes on random graphs that are sufficiently bounded for our purposes. Along the way, we prove new bounds on the size of the largest component in an infinite Pólya urn process, which may be of independent interest. In addition, we empirically validate the theoretical results, running six experiments (for a total of $N=168$ participants, $62$ delegation graphs and over $11k$ votes collected). We find that empirical delegation behaviors meet the conditions for our positive theoretical guarantees. Overall, our work alleviates concerns raised about liquid democracy and bolsters the case for the applicability of this emerging paradigm.
Learning from Successful and Failed Demonstrations via Optimization
Venue: arXiv cs.RO 2024
Year: 2024

Learning from Demonstration (LfD) is a popular approach that allows humans to teach robots new skills by showing the correct way(s) of performing the desired skill. Human-provided demonstrations, however, are not always optimal and the teacher usually addresses this issue by discarding or replacing sub-optimal (noisy or faulty) demonstrations. We propose a novel LfD representation that learns from both successful and failed demonstrations of a skill. Our approach encodes the two subsets of captured demonstrations (labeled by the teacher) into a statistical skill model, constructs a set of quadratic costs, and finds an optimal reproduction of the skill under novel problem conditions (i.e. constraints). The optimal reproduction balances convergence towards successful examples and divergence from failed examples. We evaluate our approach through several 2D and 3D experiments in real-world using a UR5e manipulator arm and also show that it can reproduce a skill from only failed demonstrations. The benefits of exploiting both failed and successful demonstrations are shown through comparison with two existing LfD approaches. We also compare our approach against an existing skill refinement method and show its capabilities in a multi-coordinate setting.
Generalized Nash Equilibrium Problems with Mixed-Integer Variables
Venue: arXiv cs.GT 2024
Year: 2024

We consider generalized Nash equilibrium problems (GNEPs) with non-convex strategy spaces and non-convex cost functions. This general class of games includes the important case of games with mixed-integer variables for which only a few results are known in the literature. We present a new approach to characterize equilibria via a convexification technique using the Nikaido-Isoda function. To any given instance of the GNEP, we construct a set of convexified instances and show that a feasible strategy profile is an equilibrium for the original instance if and only if it is an equilibrium for any convexified instance and the convexified cost functions coincide with the initial ones. We develop this convexification approach along three dimensions: We first show that for quasi-linear models, where a convexified instance exists in which for fixed strategies of the opponent players, the cost function of every player is linear and the respective strategy space is polyhedral, the convexification reduces the GNEP to a standard (non-linear) optimization problem. Secondly, we derive two complete characterizations of those GNEPs for which the convexification leads to a jointly constrained or a jointly convex GNEP, respectively. These characterizations require new concepts related to the interplay of the convex hull operator applied to restricted subsets of feasible strategies and may be interesting on their own. Note that this characterization is also computationally relevant as jointly convex GNEPs have been extensively studied in the literature. Finally, we demonstrate the applicability of our results by presenting a numerical study regarding the computation of equilibria for three classes of GNEPs related to integral network flows and discrete market equilibria.
High-Efficiency Resonant Beam Charging and Communication
Venue: arXiv cs.ET 2024
Year: 2024

With the development of Internet of Things (IoT), demands of power and data for IoT devices increase drastically. In order to resolve the supply-demand contradiction, simultaneous wireless information and power transfer (SWIPT) has been envisioned as an enabling technology by providing high-power energy transfer and high-rate data delivering concurrently. In this paper, we introduce a high-efficiency resonant beam (RB) charging and communication scheme. The scheme utilizes the semiconductor materials as gain medium, which has a better energy absorption capacity compared with the traditional solid-state one. Moreover, the telescope internal modulator (TIM) are adopted in the scheme which can concentrate beams to match the gain size, reducing the transmission loss. To evaluate the scheme SWIPT performance, we establish an analytical model and study the influence factors of its beam transmission, energy conversion, output power, and spectral efficiency. Numerical results shows that the proposed RB system can realize 16 W electric power output with 11 % end-to-end conversion efficiency, and support 18 bit/s/Hz spectral efficiency for communication.
Capturing Tie Strength with Algebraic Topology
Venue: arXiv cs.SI 2024
Year: 2024

The association between tie strength and social structure is a fundamental topic in the social sciences. We study this association by analyzing tie strength in higher-order networks, an increasingly relevant model which can encode group interactions between three or more individuals. First, we introduce three measures based on algebraic topology which characterize the network context and influence of an edge. Our experimental results across 15 datasets indicate that these measures outperform standard network proxies in estimating tie strength. We further find that these measures can replicate and explain a puzzle wherein certain bridging ties are surprisingly strong. We then consider a single centrality measure which combines the three initial measures, is highly inversely related to tie strength, and can be interpreted through an information exchange process which highlights ties that have access to useful information. In this sense, we are able to illuminate the information advantages of weak ties due to their network position.
Unifying Global-Local Representations in Salient Object Detection with Transformer
Venue: arXiv cs.CV 2024
Year: 2024

The fully convolutional network (FCN) has dominated salient object detection for a long period. However, the locality of CNN requires the model deep enough to have a global receptive field and such a deep model always leads to the loss of local details. In this paper, we introduce a new attention-based encoder, vision transformer, into salient object detection to ensure the globalization of the representations from shallow to deep layers. With the global view in very shallow layers, the transformer encoder preserves more local representations to recover the spatial details in final saliency maps. Besides, as each layer can capture a global view of its previous layer, adjacent layers can implicitly maximize the representation differences and minimize the redundant features, making that every output feature of transformer layers contributes uniquely for final prediction. To decode features from the transformer, we propose a simple yet effective deeply-transformed decoder. The decoder densely decodes and upsamples the transformer features, generating the final saliency map with less noise injection. Experimental results demonstrate that our method significantly outperforms other FCN-based and transformer-based methods in five benchmarks by a large margin, with an average of 12.17% improvement in terms of Mean Absolute Error (MAE). Code will be available at https://github.com/OliverRensu/GLSTR.
Interference Mitigation using Optimized Angle Diversity Receiver in LiFi Cellular Network
Venue: arXiv cs.IT 2024
Year: 2024

Light-fidelity (LiFi) is an emerging technology for high-speed short-range mobile communications. Inter-cell interference (ICI) is an important issue that limits the system performance in an optical attocell network. Angle diversity receivers (ADRs) have been proposed to mitigate ICI. In this paper, the structure of pyramid receivers (PRs) and truncated pyramid receivers (TPRs) are studied. The coverage problems of PRs and TPRs are defined and investigated, and the lower bound of field of view (FOV) for each PD is given analytically. The impact of random device orientation and diffuse link signal propagation are taken into consideration. The performances of PRs and TPRs are compared and then optimized ADR structures are proposed. The performance comparison between the select best combining (SBC) and maximum ratio combining (MRC) is given under different noise levels. It is shown that SBC will outperform MRC in an interference limited system, otherwise, MRC is a preferred scheme. In addition, the double source system, where each LiFi AP consists of two sources transmitting the same information signals but with opposite polarity, is proved to outperform the single source (SS) system under certain conditions.
PICCOLO: Point Cloud-Centric Omnidirectional Localization
Venue: arXiv cs.CV 2024
Year: 2024

We present PICCOLO, a simple and efficient algorithm for omnidirectional localization. Given a colored point cloud and a 360 panorama image of a scene, our objective is to recover the camera pose at which the panorama image is taken. Our pipeline works in an off-the-shelf manner with a single image given as a query and does not require any training of neural networks or collecting ground-truth poses of images. Instead, we match each point cloud color to the holistic view of the panorama image with gradient-descent optimization to find the camera pose. Our loss function, called sampling loss, is point cloud-centric, evaluated at the projected location of every point in the point cloud. In contrast, conventional photometric loss is image-centric, comparing colors at each pixel location. With a simple change in the compared entities, sampling loss effectively overcomes the severe visual distortion of omnidirectional images, and enjoys the global context of the 360 view to handle challenging scenarios for visual localization. PICCOLO outperforms existing omnidirectional localization algorithms in both accuracy and stability when evaluated in various environments. Code is available at \url{https://github.com/82magnolia/panoramic-localization/}.
Pre-training Language Model Incorporating Domain-specific Heterogeneous Knowledge into A Unified Representation
Venue: arXiv cs.CL 2024
Year: 2024

Existing technologies expand BERT from different perspectives, e.g. designing different pre-training tasks, different semantic granularities, and different model architectures. Few models consider expanding BERT from different text formats. In this paper, we propose a heterogeneous knowledge language model (\textbf{HKLM}), a unified pre-trained language model (PLM) for all forms of text, including unstructured text, semi-structured text, and well-structured text. To capture the corresponding relations among these multi-format knowledge, our approach uses masked language model objective to learn word knowledge, uses triple classification objective and title matching objective to learn entity knowledge and topic knowledge respectively. To obtain the aforementioned multi-format text, we construct a corpus in the tourism domain and conduct experiments on 5 tourism NLP datasets. The results show that our approach outperforms the pre-training of plain text using only 1/4 of the data. We further pre-train the domain-agnostic HKLM and achieve performance gains on the XNLI dataset.
Empirical Study of Named Entity Recognition Performance Using Distribution-aware Word Embedding
Venue: arXiv cs.CL 2024
Year: 2024

With the fast development of Deep Learning techniques, Named Entity Recognition (NER) is becoming more and more important in the information extraction task. The greatest difficulty that the NER task faces is to keep the detectability even when types of NE and documents are unfamiliar. Realizing that the specificity information may contain potential meanings of a word and generate semantic-related features for word embedding, we develop a distribution-aware word embedding and implement three different methods to make use of the distribution information in a NER framework. And the result shows that the performance of NER will be improved if the word specificity is incorporated into existing NER methods.
Quantum secure non-malleable-extractors
Venue: arXiv cs.CR 2024
Year: 2024

We construct several explicit quantum secure non-malleable-extractors. All the quantum secure non-malleable-extractors we construct are based on the constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015]. 1) We construct the first explicit quantum secure non-malleable-extractor for (source) min-entropy $k \geq \textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$ ($n$ is the length of the source and $ε$ is the error parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that the inner-product based non-malleable-extractor proposed by Li [2012] is quantum secure, however it required linear (in $n$) min-entropy and seed length. Using the connection between non-malleable-extractors and privacy amplification (established first in the quantum setting by Cohen and Vidick [2017]), we get a $2$-round privacy amplification protocol that is secure against active quantum adversaries with communication $\textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$, exponentially improving upon the linear communication required by the protocol due to [2019]. 2) We construct an explicit quantum secure $2$-source non-malleable-extractor for min-entropy $k \geq n- n^{Ω(1)}$, with an output of size $n^{Ω(1)}$ and error $2^{- n^{Ω(1)}}$. 3) We also study their natural extensions when the tampering of the inputs is performed $t$-times. We construct explicit quantum secure $t$-non-malleable-extractors for both seeded ($t=d^{Ω(1)}$) as well as $2$-source case ($t=n^{Ω(1)}$).
New Versions of Gradient Temporal Difference Learning
Venue: arXiv cs.LG 2024
Year: 2024

Sutton, Szepesvári and Maei introduced the first gradient temporal-difference (GTD) learning algorithms compatible with both linear function approximation and off-policy training. The goal of this paper is (a) to propose some variants of GTDs with extensive comparative analysis and (b) to establish new theoretical analysis frameworks for the GTDs. These variants are based on convex-concave saddle-point interpretations of GTDs, which effectively unify all the GTDs into a single framework, and provide simple stability analysis based on recent results on primal-dual gradient dynamics. Finally, numerical comparative analysis is given to evaluate these approaches.
An objective function for order preserving hierarchical clustering
Venue: arXiv cs.LG 2024
Year: 2024

We present a theory and an objective function for similarity-based hierarchical clustering of probabilistic partial orders and directed acyclic graphs (DAGs). Specifically, given elements $x \le y$ in the partial order, and their respective clusters $[x]$ and $[y]$, the theory yields an order relation $\le'$ on the clusters such that $[x]\le'[y]$. The theory provides a concise definition of order-preserving hierarchical clustering, and offers a classification theorem identifying the order-preserving trees (dendrograms). To determine the optimal order-preserving trees, we develop an objective function that frames the problem as a bi-objective optimisation, aiming to satisfy both the order relation and the similarity measure. We prove that the optimal trees under the objective are both order-preserving and exhibit high-quality hierarchical clustering. Since finding an optimal solution is NP-hard, we introduce a polynomial-time approximation algorithm and demonstrate that the method outperforms existing methods for order-preserving hierarchical clustering by a significant margin.
Extracting Event Temporal Relations via Hyperbolic Geometry
Venue: arXiv cs.CL 2024
Year: 2024

Detecting events and their evolution through time is a crucial task in natural language understanding. Recent neural approaches to event temporal relation extraction typically map events to embeddings in the Euclidean space and train a classifier to detect temporal relations between event pairs. However, embeddings in the Euclidean space cannot capture richer asymmetric relations such as event temporal relations. We thus propose to embed events into hyperbolic spaces, which are intrinsically oriented at modeling hierarchical structures. We introduce two approaches to encode events and their temporal relations in hyperbolic spaces. One approach leverages hyperbolic embeddings to directly infer event relations through simple geometrical operations. In the second one, we devise an end-to-end architecture composed of hyperbolic neural units tailored for the temporal relation extraction task. Thorough experimental assessments on widely used datasets have shown the benefits of revisiting the tasks on a different geometrical space, resulting in state-of-the-art performance on several standard metrics. Finally, the ablation study and several qualitative analyses highlighted the rich event semantics implicitly encoded into hyperbolic spaces.
The concept of class invariant in object-oriented programming
Venue: arXiv cs.PL 2024
Year: 2024

Class invariants -- consistency constraints preserved by every operation on objects of a given type -- are fundamental to building, understanding and verifying object-oriented programs. For verification, however, they raise difficulties, which have not yet received a generally accepted solution. The present work introduces a proof rule meant to address these issues and allow verification tools to benefit from invariants. It clarifies the notion of invariant and identifies the three associated problems: callbacks, furtive access and reference leak. As an example, the 2016 Ethereum DAO bug, in which $50 million were stolen, resulted from a callback invalidating an invariant. The discussion starts with a simplified model of computation and an associated proof rule, demonstrating its soundness. It then removes one by one the three simplifying assumptions, each removal raising one of the three issues, and leading to a corresponding adaptation to the proof rule. The final version of the rule can tackle tricky examples, including "challenge problems" listed in the literature.
Diagnosability of labeled $\mathfrak{D_p}$ automata
Venue: arXiv cs.FL 2024
Year: 2024

In this paper, we formulate a notion of diagnosability for labeled weighted automata over a class of dioids which admit both positive and negative numbers as well as vectors. The weights can represent diverse physical meanings such as time elapsing and position deviations. We also develop an original tool called concurrent composition to verify diagnosability for such automata. These results are fundamentally new compared with the existing ones in the literature.
Towards Incremental Transformers: An Empirical Analysis of Transformer Models for Incremental NLU
Venue: arXiv cs.CL 2024
Year: 2024

Incremental processing allows interactive systems to respond based on partial inputs, which is a desirable property e.g. in dialogue agents. The currently popular Transformer architecture inherently processes sequences as a whole, abstracting away the notion of time. Recent work attempts to apply Transformers incrementally via restart-incrementality by repeatedly feeding, to an unchanged model, increasingly longer input prefixes to produce partial outputs. However, this approach is computationally costly and does not scale efficiently for long sequences. In parallel, we witness efforts to make Transformers more efficient, e.g. the Linear Transformer (LT) with a recurrence mechanism. In this work, we examine the feasibility of LT for incremental NLU in English. Our results show that the recurrent LT model has better incremental performance and faster inference speed compared to the standard Transformer and LT with restart-incrementality, at the cost of part of the non-incremental (full sequence) quality. We show that the performance drop can be mitigated by training the model to wait for right context before committing to an output and that training with input prefixes is beneficial for delivering correct partial outputs.
Network Interventions: Applying Network Science for Pragmatic Action in Public Administration and Policy
Venue: arXiv cs.SI 2024
Year: 2024

Public management and policy scholars have engaged in extensive development of theory and empirical study of networks and collaborative systems of governance. This scholarship has focused on understanding the mechanisms of network formation and the implications of network properties on individual and collective outcomes. Despite rich descriptive work and inferential analyses, little work has attempted to intervene in these systems. In this article, we develop the foundation for a new body of research in our field focused on network interventions. Network interventions are defined as the purposeful use of network data to identify strategies for accelerating behavior change, improving performance, and producing desirable outcomes (Valente, 2012). We extend network intervention strategies from the field of public health to public sector inter-organizational and governance networks. Public sector actors have an interest in network interventions based on the fundamental pursuit of efficiency, effectiveness, and equity. Network interventions can increase the uptake of an organizational change among employees, improve the performance of a governance system, or promote the spread of a successful policy across jurisdictions. We provide scholars and practitioners with a useful way to conceptualize where, why, and how network interventions might be deployed in the pursuit of public value.
Learning from Crowds with Crowd-Kit
Venue: arXiv cs.HC 2024
Year: 2024

This paper presents Crowd-Kit, a general-purpose computational quality control toolkit for crowdsourcing. Crowd-Kit provides efficient and convenient implementations of popular quality control algorithms in Python, including methods for truth inference, deep learning from crowds, and data quality estimation. Our toolkit supports multiple modalities of answers and provides dataset loaders and example notebooks for faster prototyping. We extensively evaluated our toolkit on several datasets of different natures, enabling benchmarking computational quality control methods in a uniform, systematic, and reproducible way using the same codebase. We release our code and data under the Apache License 2.0 at https://github.com/Toloka/crowd-kit.