OpenRaiser/Intern-Atlas huggingface dataset:
Euclidean TSP in Narrow Strips
Venue: arXiv cs.CG 2024
Year: 2024

We investigate how the complexity of Euclidean TSP for point sets $P$ inside the strip $(-\infty,+\infty)\times [0,δ]$ depends on the strip width $δ$. We obtain two main results. First, for the case where the points have distinct integer $x$-coordinates, we prove that a shortest bitonic tour (which can be computed in $O(n\log^2 n)$ time using an existing algorithm) is guaranteed to be a shortest tour overall when $δ\leq 2\sqrt{2}$, a bound which is best possible. Second, we present an algorithm that is fixed-parameter tractable with respect to $δ$. Our algorithm has running time $2^{O(\sqrtδ)} n + O(δ^2 n^2)$ for sparse point sets, where each $1\timesδ$ rectangle inside the strip contains $O(1)$ points. For random point sets, where the points are chosen uniformly at random from the rectangle $[0,n]\times [0,δ]$, it has an expected running time of $2^{O(\sqrtδ)} n$. These results generalise to point sets $P$ inside a hypercylinder of width $δ$. In this case, the factors $2^{O(\sqrtδ)}$ become $2^{O(δ^{1-1/d})}$.
Gaussian Process Boosting
Venue: arXiv cs.LG 2024
Year: 2024

We introduce a novel way to combine boosting with Gaussian process and mixed effects models. This allows for relaxing, first, the zero or linearity assumption for the prior mean function in Gaussian process and grouped random effects models in a flexible non-parametric way and, second, the independence assumption made in most boosting algorithms. The former is advantageous for prediction accuracy and for avoiding model misspecifications. The latter is important for efficient learning of the fixed effects predictor function and for obtaining probabilistic predictions. Our proposed algorithm is also a novel solution for handling high-cardinality categorical variables in tree-boosting. In addition, we present an extension that scales to large data using a Vecchia approximation for the Gaussian process model relying on novel results for covariance parameter inference. We obtain increased prediction accuracy compared to existing approaches on multiple simulated and real-world data sets.
Word frequency and sentiment analysis of twitter messages during Coronavirus pandemic
Venue: arXiv cs.IR 2024
Year: 2024

The COVID-19 epidemic has had a great impact on social media conversation, especially on sites like Twitter, which has emerged as a hub for public reaction and information sharing. This paper deals by analyzing a vast dataset of Twitter messages related to this disease, starting from January 2020. Two approaches were used: a statistical analysis of word frequencies and a sentiment analysis to gauge user attitudes. Word frequencies are modeled using unigrams, bigrams, and trigrams, with power law distribution as the fitting model. The validity of the model is confirmed through metrics like Sum of Squared Errors (SSE), R-squared ($R^2$), and Root Mean Squared Error (RMSE). High $R^2$ and low SSE/RMSE values indicate a good fit for the model. Sentiment analysis is conducted to understand the general emotional tone of Twitter users messages. The results reveal that a majority of tweets exhibit neutral sentiment polarity, with only 2.57\% expressing negative polarity.
Blockchain in Healthcare and Medicine: A Contemporary Research of Applications, Challenges, and Future Perspectives
Venue: arXiv cs.CR 2024
Year: 2024

Blockchain technology is one of the most contemporary and disruptive technologies in the world. It has gained considerable attention in numerous applications such as financial services, cybersecurity applications, Internet of Things (IoT), network data management. Now its range of applications is beyond the financial services as the healthcare industry has also adopted blockchain technology in its various subdomains such as Electronic Health Records (EHR), medical supply chain management system, genomic market, neuroscience technology, clinical research, and pharmaceutical medicine. Blockchain is considered a secure and viable solution for storing and accessing patients medical records and the patients can diagnosed and treated with safe and secure data sharing. Blockchain technology will revolutionize the healthcare systems with personalized, authentic, and secure access to the clinical data of patients and that data can be used for further health improvements and clinical researches. In this paper, we conduct a contemporary research on existing applications and developments in healthcare industry with the use of blockchain technology. We also discuss some robust applications and various existing companies that are using blockchain solutions for securing their data along with some current challenges and future perspectives.
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
Venue: arXiv cs.CG 2024
Year: 2024

The aim in packing problems is to decide if a given set of pieces can be placed inside a given container. A packing problem is defined by the types of pieces and containers to be handled, and the motions that are allowed to move the pieces. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint. We establish a framework which enables us to show that for many combinations of allowed pieces, containers and motions, the resulting problem is $\exists \mathbb{R}$-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that it is an $\exists \mathbb{R}$-complete problem to decide if a set of convex polygons, each of which has at most $7$ corners, can be packed into a square. Restricted to translations, we show that the following problems are $\exists \mathbb{R}$-complete: (i) pieces bounded by segments and hyperbolic curves to be packed in a square, and (ii) convex polygons to be packed in a container bounded by segments and hyperbolic curves.
A Prescription of Methodological Guidelines for Comparing Bio-inspired Optimization Algorithms
Venue: arXiv cs.NE 2024
Year: 2024

Bio-inspired optimization (including Evolutionary Computation and Swarm Intelligence) is a growing research topic with many competitive bio-inspired algorithms being proposed every year. In such an active area, preparing a successful proposal of a new bio-inspired algorithm is not an easy task. Given the maturity of this research field, proposing a new optimization technique with innovative elements is no longer enough. Apart from the novelty, results reported by the authors should be proven to achieve a significant advance over previous outcomes from the state of the art. Unfortunately, not all new proposals deal with this requirement properly. Some of them fail to select appropriate benchmarks or reference algorithms to compare with. In other cases, the validation process carried out is not defined in a principled way (or is even not done at all). Consequently, the significance of the results presented in such studies cannot be guaranteed. In this work we review several recommendations in the literature and propose methodological guidelines to prepare a successful proposal, taking all these issues into account. We expect these guidelines to be useful not only for authors, but also for reviewers and editors along their assessment of new contributions to the field.
Privacy at Scale: Introducing the PrivaSeer Corpus of Web Privacy Policies
Venue: arXiv cs.IR 2024
Year: 2024

Organisations disclose their privacy practices by posting privacy policies on their website. Even though users often care about their digital privacy, they often don't read privacy policies since they require a significant investment in time and effort. Although natural language processing can help in privacy policy understanding, there has been a lack of large scale privacy policy corpora that could be used to analyse, understand, and simplify privacy policies. Thus, we create PrivaSeer, a corpus of over one million English language website privacy policies, which is significantly larger than any previously available corpus. We design a corpus creation pipeline which consists of crawling the web followed by filtering documents using language detection, document classification, duplicate and near-duplication removal, and content extraction. We investigate the composition of the corpus and show results from readability tests, document similarity, keyphrase extraction, and explored the corpus through topic modeling.
Statistical Discrimination in Ratings-Guided Markets
Venue: arXiv cs.GT 2024
Year: 2024

We study statistical discrimination of individuals based on payoff-irrelevant social identities in markets that utilize ratings and recommendations for social learning. Even though rating/recommendation algorithms can be designed to be fair and unbiased, ratings-based social learning can still lead to discriminatory outcomes. Our model demonstrates how users' attention choices can result in asymmetric data sampling across social groups, leading to discriminatory inferences and potential discrimination based on group identities.
Learning Feature Descriptors using Camera Pose Supervision
Venue: arXiv cs.CV 2024
Year: 2024

Recent research on learned visual descriptors has shown promising improvements in correspondence estimation, a key component of many 3D vision tasks. However, existing descriptor learning frameworks typically require ground-truth correspondences between feature points for training, which are challenging to acquire at scale. In this paper we propose a novel weakly-supervised framework that can learn feature descriptors solely from relative camera poses between images. To do so, we devise both a new loss function that exploits the epipolar constraint given by camera poses, and a new model architecture that makes the whole pipeline differentiable and efficient. Because we no longer need pixel-level ground-truth correspondences, our framework opens up the possibility of training on much larger and more diverse datasets for better and unbiased descriptors. We call the resulting descriptors CAmera Pose Supervised, or CAPS, descriptors. Though trained with weak supervision, CAPS descriptors outperform even prior fully-supervised descriptors and achieve state-of-the-art performance on a variety of geometric tasks. Project Page: https://qianqianwang68.github.io/CAPS/
Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
Venue: arXiv cs.LG 2024
Year: 2024

The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neural networks through the example of the classical NP-hard Knapsack Problem. Our main contribution is a class of recurrent neural networks (RNNs) with rectified linear units that are iteratively applied to each item of a Knapsack instance and thereby compute optimal or provably good solution values. We show that an RNN of depth four and width depending quadratically on the profit of an optimum Knapsack solution is sufficient to find optimum Knapsack solutions. We also prove the following tradeoff between the size of an RNN and the quality of the computed Knapsack solution: for Knapsack instances consisting of $n$ items, an RNN of depth five and width $w$ computes a solution of value at least $1-\mathcal{O}(n^2/\sqrt{w})$ times the optimum solution value. Our results build upon a classical dynamic programming formulation of the Knapsack Problem as well as a careful rounding of profit values that are also at the core of the well-known fully polynomial-time approximation scheme for the Knapsack Problem. A carefully conducted computational study qualitatively supports our theoretical size bounds. Finally, we point out that our results can be generalized to many other combinatorial optimization problems that admit dynamic programming solution methods, such as various Shortest Path Problems, the Longest Common Subsequence Problem, and the Traveling Salesperson Problem.
A Distributed Multi-Vehicle Coordination Algorithm for Navigation in Tight Environments
Venue: arXiv cs.RO 2024
Year: 2024

This work presents a distributed method for multi-vehicle coordination based on nonlinear model predictive control (NMPC) and dual decomposition. Our approach allows the vehicles to coordinate in tight spaces (e.g., busy highway lanes or parking lots) by using a polytopic description of each vehicle's shape and formulating collision avoidance as a dual optimization problem. Our method accommodates heterogeneous teams of vehicles (i.e., vehicles with different polytopic shapes and dynamic models can be part of the same team). Our method allows the vehicles to share their intentions in a distributed fashion without relying on a central coordinator and efficiently provides collision-free trajectories for the vehicles. In addition, our method decouples the individual-vehicles' trajectory optimization from their collision-avoidance objectives enhancing the scalability of the method and allowing one to exploit parallel hardware architectures. All these features are particularly important for vehicular applications, where the systems operate at high-frequency rates in dynamic environments. To validate our method, we apply it in a vehicular application, that is, the autonomous lane-merging of a team of connected vehicles to form a platoon. We compare our design with the centralized NMPC design to show the computational benefits of the proposed distributed algorithm.
Epoch-evolving Gaussian Process Guided Learning
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we propose a novel learning scheme called epoch-evolving Gaussian Process Guided Learning (GPGL), which aims at characterizing the correlation information between the batch-level distribution and the global data distribution. Such correlation information is encoded as context labels and needs renewal every epoch. With the guidance of the context label and ground truth label, GPGL scheme provides a more efficient optimization through updating the model parameters with a triangle consistency loss. Furthermore, our GPGL scheme can be further generalized and naturally applied to the current deep models, outperforming the existing batch-based state-of-the-art models on mainstream datasets (CIFAR-10, CIFAR-100, and Tiny-ImageNet) remarkably.
Homotopy Theoretic and Categorical Models of Neural Information Networks
Venue: arXiv cs.LO 2024
Year: 2024

In this paper we develop a novel mathematical formalism for the modeling of neural information networks endowed with additional structure in the form of assignments of resources, either computational or metabolic or informational. The starting point for this construction is the notion of summing functors and of Segal's Gamma-spaces in homotopy theory. The main results in this paper include functorial assignments of concurrent/distributed computing architectures and associated binary codes to networks and their subsystems, a categorical form of the Hopfield network dynamics, which recovers the usual Hopfield equations when applied to a suitable category of weighted codes, a functorial assignment to networks of corresponding information structures and information cohomology, and a cohomological version of integrated information.
Partitioned Least Squares
Venue: arXiv cs.LG 2024
Year: 2024

In this paper we propose a variant of the linear least squares model allowing practitioners to partition the input features into groups of variables that they require to contribute similarly to the final result. The output allows practitioners to assess the importance of each group and of each variable in the group. We formally show that the new formulation is not convex and provide two alternative methods to deal with the problem: one non-exact method based on an alternating least squares approach; and one exact method based on a reformulation of the problem using an exponential number of sub-problems whose minimum is guaranteed to be the optimal solution. We formally show the correctness of the exact method and also compare the two solutions showing that the exact solution provides better results in a fraction of the time required by the alternating least squares solution (assuming that the number of partitions is small). For the sake of completeness, we also provide an alternative branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large, and a proof of NP-completeness of the optimization problem introduced in this paper.
Quantifying intrinsic causal contributions via structure preserving interventions
Venue: arXiv cs.AI 2024
Year: 2024

We propose a notion of causal influence that describes the `intrinsic' part of the contribution of a node on a target node in a DAG. By recursively writing each node as a function of the upstream noise terms, we separate the intrinsic information added by each node from the one obtained from its ancestors. To interpret the intrinsic information as a {\it causal} contribution, we consider `structure-preserving interventions' that randomize each node in a way that mimics the usual dependence on the parents and does not perturb the observed joint distribution. To get a measure that is invariant with respect to relabelling nodes we use Shapley based symmetrization and show that it reduces in the linear case to simple ANOVA after resolving the target node into noise variables. We describe our contribution analysis for variance and entropy, but contributions for other target metrics can be defined analogously. The code is available in the package gcm of the open source library DoWhy.
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Venue: arXiv cs.CG 2024
Year: 2024

Given a closed simple polygon $P$, we say two points $p,q$ see each other if the segment $pq$ is fully contained in $P$. The art gallery problem seeks a minimum size set $G\subset P$ of guards that sees $P$ completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods and is attributed to Sharir. As the art gallery problem is ER-complete, it seems unlikely to avoid algebraic methods, without additional assumptions. In this paper, we introduce the notion of vision stability. In order to describe vision stability consider an enhanced guard that can see "around the corner" by an angle of $δ$ or a diminished guard whose vision is by an angle of $δ$ "blocked" by reflex vertices. A polygon $P$ has vision stability $δ$ if the optimal number of enhanced guards to guard $P$ is the same as the optimal number of diminished guards to guard $P$. We will argue that most relevant polygons are vision stable. We describe a one-shot vision stable algorithm that computes an optimal guard set for visionstable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision stable polygon. We implemented an iterative visionstable algorithm and show its practical performance is slower, but comparable with other state of the art algorithms. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord $c$ of a polygon, we denote by $n(c)$ the number of vertices visible from $c$. The chord-width of a polygon is the maximum $n(c)$ over all possible chords $c$. The set of vision stable polygons admits an FPT algorithm when parametrized by the chord-width. Furthermore, the one-shot algorithm runs in FPT time, when parameterized by the number of reflex vertices.
On a Novel Application of Wasserstein-Procrustes for Unsupervised Cross-Lingual Learning
Venue: arXiv cs.CL 2024
Year: 2024

The emergence of unsupervised word embeddings, pre-trained on very large monolingual text corpora, is at the core of the ongoing neural revolution in Natural Language Processing (NLP). Initially introduced for English, such pre-trained word embeddings quickly emerged for a number of other languages. Subsequently, there have been a number of attempts to align the embedding spaces across languages, which could enable a number of cross-language NLP applications. Performing the alignment using unsupervised cross-lingual learning (UCL) is especially attractive as it requires little data and often rivals supervised and semi-supervised approaches. Here, we analyze popular methods for UCL and we find that often their objectives are, intrinsically, versions of the Wasserstein-Procrustes problem. Hence, we devise an approach to solve Wasserstein-Procrustes in a direct way, which can be used to refine and to improve popular UCL methods such as iterative closest point (ICP), multilingual unsupervised and supervised embeddings (MUSE) and supervised Procrustes methods. Our evaluation experiments on standard datasets show sizable improvements over these approaches. We believe that our rethinking of the Wasserstein-Procrustes problem could enable further research, thus helping to develop better algorithms for aligning word embeddings across languages. Our code and instructions to reproduce the experiments are available at https://github.com/guillemram97/wp-hungarian.
Competing Bandits: The Perils of Exploration Under Competition
Venue: arXiv cs.GT 2024
Year: 2024

Most online platforms strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We study the interplay between exploration and competition: how such platforms balance the exploration for learning and the competition for users. Here users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing platforms. We consider a stylized duopoly model in which two firms face the same multi-armed bandit problem. Users arrive one by one and choose between the two firms, so that each firm makes progress on its bandit problem only if it is chosen. Through a mix of theoretical results and numerical simulations, we study whether and to what extent competition incentivizes the adoption of better bandit algorithms, and whether it leads to welfare increases for users. We find that stark competition induces firms to commit to a "greedy" bandit algorithm that leads to low welfare. However, weakening competition by providing firms with some "free" users incentivizes better exploration strategies and increases welfare. We investigate two channels for weakening the competition: relaxing the rationality of users and giving one firm a first-mover advantage. Our findings are closely related to the "competition vs. innovation" relationship, and elucidate the first-mover advantage in the digital economy.