OpenRaiser/Intern-Atlas huggingface dataset:
Breathing K-Means: Superior K-Means Solutions through Dynamic K-Values
Venue: arXiv cs.LG 2024
Year: 2024

We introduce the breathing k-means algorithm, which on average significantly improves solutions obtained by the widely-known greedy k-means++ algorithm, the default method for k-means clustering in the scikit-learn package. The improvements are achieved through a novel ``breathing'' technique, that cyclically increases and decreases the number of centroids based on local error and utility measures. We conducted experiments using greedy k-means++ as a baseline, comparing it with breathing k-means and five other k-means algorithms. Among the methods investigated, only breathing k-means and better k-means++ consistently outperformed the baseline, with breathing k-means demonstrating a substantial lead. This superior performance was maintained even when comparing the best result of ten runs for all other algorithms to a single run of breathing k-means, highlighting its effectiveness and speed. Our findings indicate that the breathing k-means algorithm outperforms the other k-means techniques, especially greedy k-means++ with ten repetitions, which it dominates in both solution quality and speed. This positions breathing k-means (with the built-in initialization by a single run of greedy k-means++) as a superior alternative to running greedy k-means++ on its own.
A Framework for Modelling, Verification and Transformation of Concurrent Imperative Programs
Venue: arXiv cs.LO 2024
Year: 2024

The paper gives a detailed presentation of a framework, embedded into the simply typed higher-order logic and aimed at the support of sound and structured reasoning about various properties of models of imperative programs with interleaved computations. As a case study, a model of the Peterson's mutual exclusion algorithm will be scrutinised in the course of the paper illustrating applicability of the framework.
Analytics of Longitudinal System Monitoring Data for Performance Prediction
Venue: arXiv cs.DC 2024
Year: 2024

In recent years, several HPC facilities have started continuous monitoring of their systems and jobs to collect performance-related data for understanding performance and operational efficiency. Such data can be used to optimize the performance of individual jobs and the overall system by creating data-driven models that can predict the performance of jobs waiting in the scheduler queue. In this paper, we model the performance of representative control jobs using longitudinal system-wide monitoring data and machine learning to explore the causes of performance variability. We analyze these prediction models in great detail to identify the features that are dominant predictors of performance. We demonstrate that such models can be application-agnostic and can be used for predicting performance of applications that are not included in training.
Skeptic: Automatic, Justified and Privacy-Preserving Password Composition Policy Selection
Venue: arXiv cs.CR 2024
Year: 2024

The choice of password composition policy to enforce on a password-protected system represents a critical security decision, and has been shown to significantly affect the vulnerability of user-chosen passwords to guessing attacks. In practice, however, this choice is not usually rigorous or justifiable, with a tendency for system administrators to choose password composition policies based on intuition alone. In this work, we propose a novel methodology that draws on password probability distributions constructed from large sets of real-world password data which have been filtered according to various password composition policies. Password probabilities are then redistributed to simulate different user password reselection behaviours in order to automatically determine the password composition policy that will induce the distribution of user-chosen passwords with the greatest uniformity, a metric which we show to be a useful proxy to measure overall resistance to password guessing attacks. Further, we show that by fitting power-law equations to the password probability distributions we generate, we can justify our choice of password composition policy without any direct access to user password data. Finally, we present Skeptic -- a software toolkit that implements this methodology, including a DSL to enable system administrators with no background in password security to compare and rank password composition policies without resorting to expensive and time-consuming user studies. Drawing on 205,176,321 pass words across 3 datasets, we lend validity to our approach by demonstrating that the results we obtain align closely with findings from a previous empirical study into password composition policy effectiveness.
String Indexing for Top-$k$ Close Consecutive Occurrences
Venue: arXiv cs.DS 2024
Year: 2024

The classic string indexing problem is to preprocess a string $S$ into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string $P$, report all occurrences of $P$ within $S$. In this paper, we study a basic and natural extension of string indexing called the string indexing for top-$k$ close consecutive occurrences problem (SITCCO). Here, a consecutive occurrence is a pair $(i,j)$, $i < j$, such that $P$ occurs at positions $i$ and $j$ in $S$ and there is no occurrence of $P$ between $i$ and $j$, and their distance is defined as $j-i$. Given a pattern $P$ and a parameter $k$, the goal is to report the top-$k$ consecutive occurrences of $P$ in $S$ of minimal distance. The challenge is to compactly represent $S$ while supporting queries in time close to the length of $P$ and $k$. We give three time-space trade-offs for the problem. Let $n$ be the length of $S$, $m$ the length of $P$, and $ε\in(0,1]$. Our first result achieves $O(n\log n)$ space and optimal query time of $O(m+k)$. Our second and third results achieve linear space and query times either $O(m+k^{1+ε})$ or $O(m + k \log^{1+ε} n)$. Along the way, we develop several techniques of independent interest, including a new translation of the problem into a line segment intersection problem and a new recursive clustering technique for trees.
Rectangle Tiling Binary Arrays
Venue: arXiv cs.CG 2024
Year: 2024

The problem of rectangle tiling binary arrays is defined as follows. Given an $n \times n$ array $A$ of zeros and ones and a natural number $p$, our task is to partition $A$ into at most $p$ rectangular tiles, so that the maximal weight of a tile is minimized. A tile is any rectangular subarray of $A$. The weight of a tile is the sum of elements that fall within it. We present a linear $(O(n^2))$ time $(\frac{3}{2}+\frac{p^2}{w(A)})$-approximation algorithm (where $\frac{p^2}{w(A)} < \frac{1}{2}$) for this problem, where $w(A)$ denotes the weight of the whole array $A$. This improves on the previously known approximation with the ratio $2$. The result is best possible in the following sense. The algorithm employs the lower bound of $L=\lceil \frac{w(A)}{p} \rceil$, which is the only known and used bound on the optimum in all algorithms for rectangle tiling. We prove that a better approximation factor for the binary \RTILE cannot be achieved using $L$, because there exist arrays, whose every partition contains a tile with weight at least $(\frac{3}{2}+\frac{p^2}{w(A)})L$. We also consider the dual problem of rectangle tiling for binary arrays, where we are given an upper bound on the weight of the tiles, and we have to cover the array $A$ with the minimum number of non-overlapping tiles. Both problems have natural extensions to $d$-dimensional versions, for which we provide analogous results.
The Transpension Type: Technical Report
Venue: arXiv cs.LO 2024
Year: 2024

The purpose of these notes is to give a categorical semantics for the transpension type (Nuyts and Devriese, Transpension: The Right Adjoint to the Pi-type, Accepted at LMCS, 2024), which is right adjoint to a potentially substructural dependent function type. In section 2 we discuss some prerequisites. In section 3, we define multipliers and discuss their properties. In section 4, we study how multipliers lift from base categories to presheaf categories. In section 5, we explain how typical presheaf modalities can be used in the presence of the transpension type. In section 6, we study commutation properties of prior modalities, substitution modalities and multiplier modalities.
Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses
Venue: arXiv cs.LG 2024
Year: 2024

I study adversarial attacks against stochastic bandit algorithms. At each round, the learner chooses an arm, and a stochastic reward is generated. The adversary strategically adds corruption to the reward, and the learner is only able to observe the corrupted reward at each round. Two sets of results are presented in this paper. The first set studies the optimal attack strategies for the adversary. The adversary has a target arm he wishes to promote, and his goal is to manipulate the learner into choosing this target arm $T - o(T)$ times. I design attack strategies against UCB and Thompson Sampling that only spend $\widehat{O}(\sqrt{\log T})$ cost. Matching lower bounds are presented, and the vulnerability of UCB, Thompson sampling, and $\varepsilon$-greedy are exactly characterized. The second set studies how the learner can defend against the adversary. Inspired by literature on smoothed analysis and behavioral economics, I present two simple algorithms that achieve a competitive ratio arbitrarily close to 1.
Image Colorization: A Survey and Dataset
Venue: arXiv cs.CV 2024
Year: 2024

Image colorization estimates RGB colors for grayscale images or video frames to improve their aesthetic and perceptual quality. Over the last decade, deep learning techniques for image colorization have significantly progressed, necessitating a systematic survey and benchmarking of these techniques. This article presents a comprehensive survey of recent state-of-the-art deep learning-based image colorization techniques, describing their fundamental block architectures, inputs, optimizers, loss functions, training protocols, training data, etc. It categorizes the existing colorization techniques into seven classes and discusses important factors governing their performance, such as benchmark datasets and evaluation metrics. We highlight the limitations of existing datasets and introduce a new dataset specific to colorization. We perform an extensive experimental evaluation of existing image colorization methods using both existing datasets and our proposed one. Finally, we discuss the limitations of existing methods and recommend possible solutions and future research directions for this rapidly evolving topic of deep image colorization. The dataset and codes for evaluation are publicly available at https://github.com/saeed-anwar/ColorSurvey.
Generic Analysis of Model Product Lines via Constraint Lifting
Venue: arXiv cs.SE 2024
Year: 2024

Engineering a product-line is more than just describing a product-line: to be correct, every variant that can be generated must satisfy some constraints. To ensure that all such variants will be correct (e.g. well-typed) there are only two ways: either to check the variants of interest individually or to come up with a complex product-line analysis algorithm, specific to every constraint. In this paper, we address a generalization of this problem: we propose a mechanism that allows to check whether a constraint holds simultaneously for all variants which might be generated. The main contribution of this paper is a function that assumes constraints that shall be fulfilled by all variants and generates ("lifts") out of them constraints for the product-line. These lifted constraints can then be checked directly on a model product-line, thus simultaneously be verified for all variants. The lifting is formulated in a very general manner, which allows to make use of generic algorithms like SMT solving or theorem proving in a modular way. We show how to verify lifted constraints using SMT solving by automatically translating model product-lines and constraints. The applicability of the approach is demonstrated with an industrial case study, in which we apply our lifting to a domain specific modelling language for manufacturing planning. Finally, a runtime analysis shows scalability by analyzing different model product-lines with production planning data from the BMW Group and Miele.
"Hey Model!" - Natural User Interactions and Agency in Accessible Interactive 3D Models
Venue: arXiv cs.HC 2024
Year: 2024

While developments in 3D printing have opened up opportunities for improved access to graphical information for people who are blind or have low vision (BLV), they can provide only limited detailed and contextual information. Interactive 3D printed models (I3Ms) that provide audio labels and/or a conversational agent interface potentially overcome this limitation. We conducted a Wizard-of-Oz exploratory study to uncover the multi-modal interaction techniques that BLV people would like to use when exploring I3Ms, and investigated their attitudes towards different levels of model agency. These findings informed the creation of an I3M prototype of the solar system. A second user study with this model revealed a hierarchy of interaction, with BLV users preferring tactile exploration, followed by touch gestures to trigger audio labels, and then natural language to fill in knowledge gaps and confirm understanding.
PyCSP3: Modeling Combinatorial Constrained Problems in Python
Venue: arXiv cs.AI 2024
Year: 2024

In this document, we introduce PyCSP$3$, a Python library that allows us to write models of combinatorial constrained problems in a declarative manner. Currently, with PyCSP$3$, you can write models of constraint satisfaction and optimization problems. More specifically, you can build CSP (Constraint Satisfaction Problem) and COP (Constraint Optimization Problem) models. Importantly, there is a complete separation between the modeling and solving phases: you write a model, you compile it (while providing some data) in order to generate an XCSP$3$ instance (file), and you solve that problem instance by means of a constraint solver. You can also directly pilot the solving procedure in PyCSP$3$, possibly conducting an incremental solving strategy. In this document, you will find all that you need to know about PyCSP$3$, with more than 50 illustrative models.
Towards Fine-grained Large Object Segmentation 1st Place Solution to 3D AI Challenge 2020 -- Instance Segmentation Track
Venue: arXiv cs.CV 2024
Year: 2024

This technical report introduces our solutions of Team 'FineGrainedSeg' for Instance Segmentation track in 3D AI Challenge 2020. In order to handle extremely large objects in 3D-FUTURE, we adopt PointRend as our basic framework, which outputs more fine-grained masks compared to HTC and SOLOv2. Our final submission is an ensemble of 5 PointRend models, which achieves the 1st place on both validation and test leaderboards. The code is available at https://github.com/zehuichen123/3DFuture_ins_seg.
6-DoF Grasp Planning using Fast 3D Reconstruction and Grasp Quality CNN
Venue: arXiv cs.CV 2024
Year: 2024

Recent consumer demand for home robots has accelerated performance of robotic grasping. However, a key component of the perception pipeline, the depth camera, is still expensive and inaccessible to most consumers. In addition, grasp planning has significantly improved recently, by leveraging large datasets and cloud robotics, and by limiting the state and action space to top-down grasps with 4 degrees of freedom (DoF). By leveraging multi-view geometry of the object using inexpensive equipment such as off-the-shelf RGB cameras and state-of-the-art algorithms such as Learn Stereo Machine (LSM\cite{kar2017learning}), the robot is able to generate more robust grasps from different angles with 6-DoF. In this paper, we present a modification of LSM to graspable objects, evaluate the grasps, and develop a 6-DoF grasp planner based on Grasp-Quality CNN (GQ-CNN\cite{mahler2017dex}) that exploits multiple camera views to plan a robust grasp, even in the absence of a possible top-down grasp.
Dodging DeepFake Detection via Implicit Spatial-Domain Notch Filtering
Venue: arXiv cs.CV 2024
Year: 2024

The current high-fidelity generation and high-precision detection of DeepFake images are at an arms race. We believe that producing DeepFakes that are highly realistic and 'detection evasive' can serve the ultimate goal of improving future generation DeepFake detection capabilities. In this paper, we propose a simple yet powerful pipeline to reduce the artifact patterns of fake images without hurting image quality by performing implicit spatial-domain notch filtering. We first demonstrate that frequency-domain notch filtering, although famously shown to be effective in removing periodic noise in the spatial domain, is infeasible for our task at hand due to the manual designs required for the notch filters. We, therefore, resort to a learning-based approach to reproduce the notch filtering effects, but solely in the spatial domain. We adopt a combination of adding overwhelming spatial noise for breaking the periodic noise pattern and deep image filtering to reconstruct the noise-free fake images, and we name our method DeepNotch. Deep image filtering provides a specialized filter for each pixel in the noisy image, producing filtered images with high fidelity compared to their DeepFake counterparts. Moreover, we also use the semantic information of the image to generate an adversarial guidance map to add noise intelligently. Our large-scale evaluation on 3 representative state-of-the-art DeepFake detection methods (tested on 16 types of DeepFakes) has demonstrated that our technique significantly reduces the accuracy of these 3 fake image detection methods, 36.79% on average and up to 97.02% in the best case.
On the Mysteries of MAX NAE-SAT
Venue: arXiv cs.CC 2024
Year: 2024

MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size $k$, for some $k\ge 2$. We refer to this problem as MAX NAE-$\{k\}$-SAT. For $k=2$, it is essentially the celebrated MAX CUT problem. For $k=3$, it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For $k\ge 4$, it is known that an approximation ratio of $1-\frac{1}{2^{k-1}}$, obtained by choosing a random assignment, is optimal, assuming $P\ne NP$. For every $k\ge 2$, an approximation ratio of at least $\frac{7}{8}$ can be obtained for MAX NAE-$\{k\}$-SAT. There was some hope, therefore, that there is also a $\frac{7}{8}$-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no $\frac{7}{8}$-approximation algorithm for MAX NAE-SAT, assuming the unique games conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-$\{3,5\}$-SAT (i.e., MAX NAE-SAT where all clauses have size $3$ or $5$), the best approximation ratio that can be achieved, assuming UGC, is at most $\frac{3(\sqrt{21}-4)}{2}\approx 0.8739$. Using calculus of variations, we extend the analysis of O'Donnell and Wu for MAX CUT to MAX NAE-$\{3\}$-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-$\{3\}$-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is $\approx 0.9089$. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-$\{3,5\}$-SAT with a conjectured approximation ratio of 0.8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0.8698.
Mean-Variance Efficient Reinforcement Learning with Applications to Dynamic Financial Investment
Venue: arXiv cs.LG 2024
Year: 2024

This study investigates the mean-variance (MV) trade-off in reinforcement learning (RL), an instance of the sequential decision-making under uncertainty. Our objective is to obtain MV-efficient policies whose means and variances are located on the Pareto efficient frontier with respect to the MV trade-off; under the condition, any increase in the expected reward would necessitate a corresponding increase in variance, and vice versa. To this end, we propose a method that trains our policy to maximize the expected quadratic utility, defined as a weighted sum of the first and second moments of the rewards obtained through our policy. We subsequently demonstrate that the maximizer indeed qualifies as an MV-efficient policy. Previous studies that employed constrained optimization to address the MV trade-off have encountered computational challenges. However, our approach is more computationally efficient as it eliminates the need for gradient estimation of variance, a contributing factor to the double sampling issue observed in existing methodologies. Through experimentation, we validate the efficacy of our approach.
Speakers Fill Lexical Semantic Gaps with Context
Venue: arXiv cs.CL 2024
Year: 2024

Lexical ambiguity is widespread in language, allowing for the reuse of economical word forms and therefore making language more efficient. If ambiguous words cannot be disambiguated from context, however, this gain in efficiency might make language less clear -- resulting in frequent miscommunication. For a language to be clear and efficiently encoded, we posit that the lexical ambiguity of a word type should correlate with how much information context provides about it, on average. To investigate whether this is the case, we operationalise the lexical ambiguity of a word as the entropy of meanings it can take, and provide two ways to estimate this -- one which requires human annotation (using WordNet), and one which does not (using BERT), making it readily applicable to a large number of languages. We validate these measures by showing that, on six high-resource languages, there are significant Pearson correlations between our BERT-based estimate of ambiguity and the number of synonyms a word has in WordNet (e.g. $ρ= 0.40$ in English). We then test our main hypothesis -- that a word's lexical ambiguity should negatively correlate with its contextual uncertainty -- and find significant correlations on all 18 typologically diverse languages we analyse. This suggests that, in the presence of ambiguity, speakers compensate by making contexts more informative.
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
Venue: arXiv cs.CG 2024
Year: 2024

We revisit the classic task of finding the shortest tour of $n$ points in $d$-dimensional Euclidean space, for any fixed constant $d \geq 2$. We determine the optimal dependence on $\varepsilon$ in the running time of an algorithm that computes a $(1+\varepsilon)$-approximate tour, under a plausible assumption. Specifically, we give an algorithm that runs in $2^{\mathcal{O}(1/\varepsilon^{d-1})} n\log n$ time. This improves the previously smallest dependence on $\varepsilon$ in the running time $(1/\varepsilon)^{\mathcal{O}(1/\varepsilon^{d-1})}n \log n$ of the algorithm by Rao and Smith~(STOC 1998). We also show that a $2^{o(1/\varepsilon^{d-1})}\text{poly}(n)$ algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH). Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a new idea that we call \emph{sparsity-sensitive patching}. On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. We demonstrate that our technique extends to other problems, by showing that for Steiner Tree and Rectilinear Steiner Tree it yields the same running time. We complement our results with a matching Gap-ETH lower bound for Rectilinear Steiner Tree.