OpenRaiser/Intern-Atlas huggingface dataset:
Parameterizing Path Partitions
Venue: arXiv cs.DS 2024
Year: 2024

We study the algorithmic complexity of partitioning the vertex set of a given (di)graph into a small number of paths. The Path Partition problem (PP) has been studied extensively, as it includes Hamiltonian Path as a special case. The natural variants where the paths are required to be either \emph{induced} (Induced Path Partition, IPP) or \emph{shortest} (Shortest Path Partition, SPP), have received much less attention. Both problems are known to be NP-complete on undirected graphs; we strengthen this by showing that they remain so even on planar bipartite directed acyclic graphs (DAGs), and that SPP remains NP-hard on undirected bipartite graphs. When parameterized by the natural parameter ``number of paths'', both SPP and IPP are shown to be W[1]-hard on DAGs. We also show that SPP is in XP both for DAGs and undirected graphs for the same parameter, as well as for other special subclasses of directed graphs (IPP is known to be NP-hard on undirected graphs, even for two paths). On the positive side, we show that for undirected graphs, both problems are in FPT, parameterized by neighborhood diversity. We also give an explicit algorithm for the vertex cover parameterization of PP. When considering the dual parameterization (graph order minus number of paths), all three variants, IPP, SPP and PP, are shown to be in FPT for undirected graphs. We also lift the mentioned neighborhood diversity and dual parameterization results to directed graphs; here, we need to define a proper novel notion of directed neighborhood diversity. As we also show, most of our results transfer to the case of covering by edge-disjoint paths, and purely covering.
CinPatent: Datasets for Patent Classification
Venue: arXiv cs.CL 2024
Year: 2024

Patent classification is the task that assigns each input patent into several codes (classes). Due to its high demand, several datasets and methods have been introduced. However, the lack of both systematic performance comparison of baselines and access to some datasets creates a gap for the task. To fill the gap, we introduce two new datasets in English and Japanese collected by using CPC codes. The English dataset includes 45,131 patent documents with 425 labels and the Japanese dataset contains 54,657 documents with 523 labels. To facilitate the next studies, we compare the performance of strong multi-label text classification methods on the two datasets. Experimental results show that AttentionXML is consistently better than other strong baselines. The ablation study is also conducted in two aspects: the contribution of different parts (title, abstract, description, and claims) of a patent and the behavior of baselines in terms of performance with different training data segmentation. We release the two new datasets with the code of the baselines.
LMFLOSS: A Hybrid Loss For Imbalanced Medical Image Classification
Venue: arXiv cs.CV 2024
Year: 2024

With advances in digital technology, the classification of medical images has become a crucial step for image-based clinical decision support systems. Automatic medical image classification represents a pivotal domain where the use of AI holds the potential to create a significant social impact. However, several challenges act as obstacles to the development of practical and effective solutions. One of these challenges is the prevalent class imbalance problem in most medical imaging datasets. As a result, existing AI techniques, particularly deep-learning-based methodologies, often underperform in such scenarios. In this study, we propose a novel framework called Large Margin aware Focal (LMF) loss to mitigate the class imbalance problem in medical imaging. The LMF loss represents a linear combination of two loss functions optimized by two hyperparameters. This framework harnesses the distinct characteristics of both loss functions by enforcing wider margins for minority classes while simultaneously emphasizing challenging samples found in the datasets. We perform rigorous experiments on three neural network architectures and with four medical imaging datasets. We provide empirical evidence that our proposed framework consistently outperforms other baseline methods, showing an improvement of 2%-9% in macro-f1 scores. Through class-wise analysis of f1 scores, we also demonstrate how the proposed framework can significantly improve performance for minority classes. The results of our experiments show that our proposed framework can perform consistently well across different architectures and datasets. Overall, our study demonstrates a simple and effective approach to addressing the class imbalance problem in medical imaging datasets. We hope our work will inspire new research toward a more generalized approach to medical image classification.
Learning k-Level Structured Sparse Neural Networks Using Group Envelope Regularization
Venue: arXiv cs.LG 2024
Year: 2024

The extensive need for computational resources poses a significant obstacle to deploying large-scale Deep Neural Networks (DNN) on devices with constrained resources. At the same time, studies have demonstrated that a significant number of these DNN parameters are redundant and extraneous. In this paper, we introduce a novel approach for learning structured sparse neural networks, aimed at bridging the DNN hardware deployment challenges. We develop a novel regularization technique, termed Weighted Group Sparse Envelope Function (WGSEF), generalizing the Sparse Envelop Function (SEF), to select (or nullify) neuron groups, thereby reducing redundancy and enhancing computational efficiency. The method speeds up inference time and aims to reduce memory demand and power consumption, thanks to its adaptability which lets any hardware specify group definitions, such as filters, channels, filter shapes, layer depths, a single parameter (unstructured), etc. The properties of the WGSEF enable the pre-definition of a desired sparsity level to be achieved at the training convergence. In the case of redundant parameters, this approach maintains negligible network accuracy degradation or can even lead to improvements in accuracy. Our method efficiently computes the WGSEF regularizer and its proximal operator, in a worst-case linear complexity relative to the number of group variables. Employing a proximal-gradient-based optimization technique, to train the model, it tackles the non-convex minimization problem incorporating the neural network loss and the WGSEF. Finally, we experiment and illustrate the efficiency of our proposed method in terms of the compression ratio, accuracy, and inference latency.
Interactive and Iterative Peer Assessment
Venue: arXiv cs.GT 2024
Year: 2024

Iterative peer grading activities may keep students engaged during in-class project presentations. Effective methods for collecting and aggregating peer assessment data are essential. Students tend to grade projects favorably. So, while asking students for numeric grades is a common approach, it often leads to inflated grades across all projects, resulting in numerous ties for the top grades. Additionally, students may strategically assign lower grades to others' projects so that their projects will shine. Alternatively, requesting students to rank all projects from best to worst presents challenges due to limitations in human cognitive capacity. To address these issues, we propose a novel peer grading model consisting of (a) an algorithm designed to elicit student evaluations and (b) a median-based voting protocol for aggregating grades to a single ranked order that reduces ties. An application based on our model was deployed and tested in a university course, demonstrating fewer ties between alternatives and a significant decrease in students' cognitive and communication burdens.
Classical and quantum Merlin-Arthur automata
Venue: arXiv cs.FL 2024
Year: 2024

We introduce Merlin-Arthur (MA) automata where Merlin provides a certificate at the beginning of computation and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, and MA-QFAs) and postselecting MA-PFAs and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We present several results using different certificate lengths. We show that MA-DFAs use constant length certificates, and they are equivalent to multi-entry DFAs. Thus, they recognize all and only regular languages, but they can be exponential and polynomial state efficient over binary and unary languages, respectively. With sublinear length certificates, MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2. With linear length certificates, MA-PostPFAs can recognize these nonstochastic unary languages with bounded error. With arbitrarily long certificates, bounded-error MA-PostPFAs can verify every unary decidable language. With sublinear length certificates, bounded-error MA-PostQFAs can verify several nonstochastic unary languages. With linear length certificates, they can verify every unary language and some NP-complete binary languages. With exponential length certificates, they can verify every binary language.
Skeletal Video Anomaly Detection using Deep Learning: Survey, Challenges and Future Directions
Venue: arXiv cs.CV 2024
Year: 2024

The existing methods for video anomaly detection mostly utilize videos containing identifiable facial and appearance-based features. The use of videos with identifiable faces raises privacy concerns, especially when used in a hospital or community-based setting. Appearance-based features can also be sensitive to pixel-based noise, straining the anomaly detection methods to model the changes in the background and making it difficult to focus on the actions of humans in the foreground. Structural information in the form of skeletons describing the human motion in the videos is privacy-protecting and can overcome some of the problems posed by appearance-based features. In this paper, we present a survey of privacy-protecting deep learning anomaly detection methods using skeletons extracted from videos. We present a novel taxonomy of algorithms based on the various learning approaches. We conclude that skeleton-based approaches for anomaly detection can be a plausible privacy-protecting alternative for video anomaly detection. Lastly, we identify major open research questions and provide guidelines to address them.
Benchmarking the Robustness of LiDAR Semantic Segmentation Models
Venue: arXiv cs.CV 2024
Year: 2024

When using LiDAR semantic segmentation models for safety-critical applications such as autonomous driving, it is essential to understand and improve their robustness with respect to a large range of LiDAR corruptions. In this paper, we aim to comprehensively analyze the robustness of LiDAR semantic segmentation models under various corruptions. To rigorously evaluate the robustness and generalizability of current approaches, we propose a new benchmark called SemanticKITTI-C, which features 16 out-of-domain LiDAR corruptions in three groups, namely adverse weather, measurement noise and cross-device discrepancy. Then, we systematically investigate 11 LiDAR semantic segmentation models, especially spanning different input representations (e.g., point clouds, voxels, projected images, and etc.), network architectures and training schemes. Through this study, we obtain two insights: 1) We find out that the input representation plays a crucial role in robustness. Specifically, under specific corruptions, different representations perform variously. 2) Although state-of-the-art methods on LiDAR semantic segmentation achieve promising results on clean data, they are less robust when dealing with noisy data. Finally, based on the above observations, we design a robust LiDAR segmentation model (RLSeg) which greatly boosts the robustness with simple but effective modifications. It is promising that our benchmark, comprehensive analysis, and observations can boost future research in robust LiDAR semantic segmentation for safety-critical applications.
Non-Adaptive Prophet Inequalities for Minor-Closed Classes of Matroids
Venue: arXiv cs.GT 2024
Year: 2024

We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight $2$-competitive mechanism for all matroids. However, it is not known what classes of matroids admit non-adaptive mechanisms with constant guarantee. Recently, it was shown that there are constant-competitive non-adaptive mechanisms for graphic matroids. In this work, we show that various known classes of matroids admit constant-competitive non-adaptive mechanisms.
TempSAL -- Uncovering Temporal Information for Deep Saliency Prediction
Venue: arXiv cs.CV 2024
Year: 2024

Deep saliency prediction algorithms complement the object recognition features, they typically rely on additional information, such as scene context, semantic relationships, gaze direction, and object dissimilarity. However, none of these models consider the temporal nature of gaze shifts during image observation. We introduce a novel saliency prediction model that learns to output saliency maps in sequential time intervals by exploiting human temporal attention patterns. Our approach locally modulates the saliency predictions by combining the learned temporal maps. Our experiments show that our method outperforms the state-of-the-art models, including a multi-duration saliency model, on the SALICON benchmark. Our code will be publicly available on GitHub.
Perturbation results for distance-edge-monitoring numbers
Venue: arXiv cs.DM 2024
Year: 2024

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph $G=(V(G), E(G))$, a set $M \subseteq V(G)$ is a distance-edge-monitoring set if for every edge $e \in E(G)$, there is a vertex $x \in M$ and a vertex $y \in V(G)$ such that the edge $e$ belongs to all shortest paths between $x$ and $y$. The smallest size of such a set in $G$ is denoted by $\operatorname{dem}(G)$. Denoted by $G-e$ (resp. $G \backslash u$) the subgraph of $G$ obtained by removing the edge $e$ from $G$ (resp. a vertex $u$ together with all its incident edges from $G$). In this paper, we first show that $\operatorname{dem}(G-e)- \operatorname{dem}(G)\leq 2$ for any graph $G$ and edge $e \in E(G)$. Moreover, the bound is sharp. Next, we construct two graphs $G$ and $H$ to show that $\operatorname{dem}(G)-\operatorname{dem}(G\setminus u)$ and $\operatorname{dem}(H\setminus v)-\operatorname{dem}(H)$ can be arbitrarily large, where $u \in V(G)$ and $v \in V(H)$. We also study the relation between $\operatorname{dem}(H)$ and $\operatorname{dem}(G)$, where $H$ is a subgraph of $G$. In the end, we give an algorithm to judge whether the distance-edge monitoring set still remain in the resulting graph when any edge of the graph $G$ is deleted.
Do You Need a Hand? -- a Bimanual Robotic Dressing Assistance Scheme
Venue: arXiv cs.RO 2024
Year: 2024

Developing physically assistive robots capable of dressing assistance has the potential to significantly improve the lives of the elderly and disabled population. However, most robotics dressing strategies considered a single robot only, which greatly limited the performance of the dressing assistance. In fact, healthcare professionals perform the task bimanually. Inspired by them, we propose a bimanual cooperative scheme for robotic dressing assistance. In the scheme, an interactive robot joins hands with the human thus supporting/guiding the human in the dressing process, while the dressing robot performs the dressing task. We identify a key feature that affects the dressing action and propose an optimal strategy for the interactive robot using the feature. A dressing coordinate based on the posture of the arm is defined to better encode the dressing policy. We validate the interactive dressing scheme with extensive experiments and also an ablation study. The experiment video is available on https://sites.google.com/view/bimanualassitdressing/home
A Divide-Align-Conquer Strategy for Program Synthesis
Venue: arXiv cs.AI 2024
Year: 2024

A major bottleneck in search-based program synthesis is the exponentially growing search space which makes learning large programs intractable. Humans mitigate this problem by leveraging the compositional nature of the real world: In structured domains, a logical specification can often be decomposed into smaller, complementary solution programs. We show that compositional segmentation can be applied in the programming by examples setting to divide the search for large programs across multiple smaller program synthesis problems. For each example, we search for a decomposition into smaller units which maximizes the reconstruction accuracy in the output under a latent task program. A structural alignment of the constituent parts in the input and output leads to pairwise correspondences used to guide the program synthesis search. In order to align the input/output structures, we make use of the Structure-Mapping Theory (SMT), a formal model of human analogical reasoning which originated in the cognitive sciences. We show that decomposition-driven program synthesis with structural alignment outperforms Inductive Logic Programming (ILP) baselines on string transformation tasks even with minimal knowledge priors. Unlike existing methods, the predictive accuracy of our agent monotonically increases for additional examples and achieves an average time complexity of $\mathcal{O}(m)$ in the number $m$ of partial programs for highly structured domains such as strings. We extend this method to the complex setting of visual reasoning in the Abstraction and Reasoning Corpus (ARC) for which ILP methods were previously infeasible.
Descriptional Complexity of Finite Automata -- Selected Highlights
Venue: arXiv cs.FL 2024
Year: 2024

The state complexity, respectively, nondeterministic state complexity of a regular language $L$ is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for $L$. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.
Inside the Black Box: Detecting and Mitigating Algorithmic Bias across Racialized Groups in College Student-Success Prediction
Venue: arXiv cs.CY 2024
Year: 2024

Colleges and universities are increasingly turning to algorithms that predict college-student success to inform various decisions, including those related to admissions, budgeting, and student-success interventions. Because predictive algorithms rely on historical data, they capture societal injustices, including racism. In this study, we examine how the accuracy of college student success predictions differs between racialized groups, signaling algorithmic bias. We also evaluate the utility of leading bias-mitigating techniques in addressing this bias. Using nationally representative data from the Education Longitudinal Study of 2002 and various machine learning modeling approaches, we demonstrate how models incorporating commonly used features to predict college-student success are less accurate when predicting success for racially minoritized students. Common approaches to mitigating algorithmic bias are generally ineffective at eliminating disparities in prediction outcomes and accuracy between racialized groups.
Earn While You Reveal: Private Set Intersection that Rewards Participants
Venue: arXiv cs.CR 2024
Year: 2024

In Private Set Intersection protocols (PSIs), a non-empty result always reveals something about the private input sets of the parties. Moreover, in various variants of PSI, not all parties necessarily receive or are interested in the result. Nevertheless, to date, the literature has assumed that those parties who do not receive or are not interested in the result still contribute their private input sets to the PSI for free, although doing so would cost them their privacy. In this work, for the first time, we propose a multi-party PSI, called "Anesidora", that rewards parties who contribute their private input sets to the protocol. Anesidora is efficient; it mainly relies on symmetric key primitives and its computation and communication complexities are linear with the number of parties and set cardinality. It remains secure even if the majority of parties are corrupted by active colluding adversaries.
Proportional Fairness in Obnoxious Facility Location
Venue: arXiv cs.GT 2024
Year: 2024

We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, we show that our proportional fairness axioms are incompatible with strategyproofness, and prove asymptotically tight $ε$-price of anarchy and stability bounds for proportionally fair welfare-optimal mechanisms. In the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare. Finally, we prove existence results for two extensions to our model.
Efficient Preference-Based Reinforcement Learning Using Learned Dynamics Models
Venue: arXiv cs.LG 2024
Year: 2024

Preference-based reinforcement learning (PbRL) can enable robots to learn to perform tasks based on an individual's preferences without requiring a hand-crafted reward function. However, existing approaches either assume access to a high-fidelity simulator or analytic model or take a model-free approach that requires extensive, possibly unsafe online environment interactions. In this paper, we study the benefits and challenges of using a learned dynamics model when performing PbRL. In particular, we provide evidence that a learned dynamics model offers the following benefits when performing PbRL: (1) preference elicitation and policy optimization require significantly fewer environment interactions than model-free PbRL, (2) diverse preference queries can be synthesized safely and efficiently as a byproduct of standard model-based RL, and (3) reward pre-training based on suboptimal demonstrations can be performed without any environmental interaction. Our paper provides empirical evidence that learned dynamics models enable robots to learn customized policies based on user preferences in ways that are safer and more sample efficient than prior preference learning approaches. Supplementary materials and code are available at https://sites.google.com/berkeley.edu/mop-rl.