OpenRaiser/Intern-Atlas huggingface dataset:
Computationally Relaxed Locally Decodable Codes, Revisited
Venue: arXiv cs.IT 2023
Year: 2023

We revisit computationally relaxed locally decodable codes (crLDCs) (Blocki et al., Trans. Inf. Theory '21) and give two new constructions. Our first construction is a Hamming crLDC that is conceptually simpler than prior constructions, leveraging digital signature schemes and an appropriately chosen Hamming code. Our second construction is an extension of our Hamming crLDC to handle insertion-deletion (InsDel) errors, yielding an InsDel crLDC. This extension crucially relies on the noisy binary search techniques of Block et al. (FSTTCS '20) to handle InsDel errors. Both crLDC constructions have binary codeword alphabets, are resilient to a constant fraction of Hamming and InsDel errors, respectively, and under suitable parameter choices have poly-logarithmic locality and encoding length linear in the message length and polynomial in the security parameter. These parameters compare favorably to prior constructions in the poly-logarithmic locality regime.
Autoencoders for discovering manifold dimension and coordinates in data from complex dynamical systems
Venue: arXiv cs.LG 2023
Year: 2023

While many phenomena in physics and engineering are formally high-dimensional, their long-time dynamics often live on a lower-dimensional manifold. The present work introduces an autoencoder framework that combines implicit regularization with internal linear layers and $L_2$ regularization (weight decay) to automatically estimate the underlying dimensionality of a data set, produce an orthogonal manifold coordinate system, and provide the mapping functions between the ambient space and manifold space, allowing for out-of-sample projections. We validate our framework's ability to estimate the manifold dimension for a series of datasets from dynamical systems of varying complexities and compare to other state-of-the-art estimators. We analyze the training dynamics of the network to glean insight into the mechanism of low-rank learning and find that collectively each of the implicit regularizing layers compound the low-rank representation and even self-correct during training. Analysis of gradient descent dynamics for this architecture in the linear case reveals the role of the internal linear layers in leading to faster decay of a "collective weight variable" incorporating all layers, and the role of weight decay in breaking degeneracies and thus driving convergence along directions in which no decay would occur in its absence. We show that this framework can be naturally extended for applications of state-space modeling and forecasting by generating a data-driven dynamic model of a spatiotemporally chaotic partial differential equation using only the manifold coordinates. Finally, we demonstrate that our framework is robust to hyperparameter choices.
Logion: Machine Learning for Greek Philology
Venue: arXiv cs.CL 2023
Year: 2023

This paper presents machine-learning methods to address various problems in Greek philology. After training a BERT model on the largest premodern Greek dataset used for this purpose to date, we identify and correct previously undetected errors made by scribes in the process of textual transmission, in what is, to our knowledge, the first successful identification of such errors via machine learning. Additionally, we demonstrate the model's capacity to fill gaps caused by material deterioration of premodern manuscripts and compare the model's performance to that of a domain expert. We find that best performance is achieved when the domain expert is provided with model suggestions for inspiration. With such human-computer collaborations in mind, we explore the model's interpretability and find that certain attention heads appear to encode select grammatical features of premodern Greek.
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Venue: arXiv cs.DS 2023
Year: 2023

For any finite set $\mathcal{H} = \{H_1,\ldots,H_p\}$ of graphs, a graph is $\mathcal{H}$-subgraph-free if it does not contain any of $H_1,\ldots,H_p$ as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity is determined on classes of $\mathcal{H}$-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most~$3$ and examine their complexity on $H$-subgraph-free graph classes where $H$ is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree $3$. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.
RadAdapt: Radiology Report Summarization via Lightweight Domain Adaptation of Large Language Models
Venue: arXiv cs.CL 2023
Year: 2023

We systematically investigate lightweight strategies to adapt large language models (LLMs) for the task of radiology report summarization (RRS). Specifically, we focus on domain adaptation via pretraining (on natural language, biomedical text, or clinical text) and via discrete prompting or parameter-efficient fine-tuning. Our results consistently achieve best performance by maximally adapting to the task via pretraining on clinical text and fine-tuning on RRS examples. Importantly, this method fine-tunes a mere 0.32% of parameters throughout the model, in contrast to end-to-end fine-tuning (100% of parameters). Additionally, we study the effect of in-context examples and out-of-distribution (OOD) training before concluding with a radiologist reader study and qualitative analysis. Our findings highlight the importance of domain adaptation in RRS and provide valuable insights toward developing effective natural language processing solutions for clinical tasks.
Solving Inverse Problems with Score-Based Generative Priors learned from Noisy Data
Venue: arXiv cs.LG 2023
Year: 2023

We present SURE-Score: an approach for learning score-based generative models using training samples corrupted by additive Gaussian noise. When a large training set of clean samples is available, solving inverse problems via score-based (diffusion) generative models trained on the underlying fully-sampled data distribution has recently been shown to outperform end-to-end supervised deep learning. In practice, such a large collection of training data may be prohibitively expensive to acquire in the first place. In this work, we present an approach for approximately learning a score-based generative model of the clean distribution, from noisy training data. We formulate and justify a novel loss function that leverages Stein's unbiased risk estimate to jointly denoise the data and learn the score function via denoising score matching, while using only the noisy samples. We demonstrate the generality of SURE-Score by learning priors and applying posterior sampling to ill-posed inverse problems in two practical applications from different domains: compressive wireless multiple-input multiple-output channel estimation and accelerated 2D multi-coil magnetic resonance imaging reconstruction, where we demonstrate competitive reconstruction performance when learning at signal-to-noise ratio values of 0 and 10 dB, respectively.
Hybrid model for Single-Stage Multi-Person Pose Estimation
Venue: arXiv cs.CV 2023
Year: 2023

In general, human pose estimation methods are categorized into two approaches according to their architectures: regression (i.e., heatmap-free) and heatmap-based methods. The former one directly estimates precise coordinates of each keypoint using convolutional and fully-connected layers. Although this approach is able to detect overlapped and dense keypoints, unexpected results can be obtained by non-existent keypoints in a scene. On the other hand, the latter one is able to filter the non-existent ones out by utilizing predicted heatmaps for each keypoint. Nevertheless, it suffers from quantization error when obtaining the keypoint coordinates from its heatmaps. In addition, unlike the regression one, it is difficult to distinguish densely placed keypoints in an image. To this end, we propose a hybrid model for single-stage multi-person pose estimation, named HybridPose, which mutually overcomes each drawback of both approaches by maximizing their strengths. Furthermore, we introduce self-correlation loss to inject spatial dependencies between keypoint coordinates and their visibility. Therefore, HybridPose is capable of not only detecting densely placed keypoints, but also filtering the non-existent keypoints in an image. Experimental results demonstrate that proposed HybridPose exhibits the keypoints visibility without performance degradation in terms of the pose estimation accuracy.
The AI Revolution in Education: Will AI Replace or Assist Teachers in Higher Education?
Venue: arXiv cs.CY 2023
Year: 2023

This paper explores the potential of artificial intelligence (AI) in higher education, specifically its capacity to replace or assist human teachers. By reviewing relevant literature and analysing survey data from students and teachers, the study provides a comprehensive perspective on the future role of educators in the face of advancing AI technologies. Findings suggest that although some believe AI may eventually replace teachers, the majority of participants argue that human teachers possess unique qualities, such as critical thinking, creativity, and emotions, which make them irreplaceable. The study also emphasizes the importance of social-emotional competencies developed through human interactions, which AI technologies cannot currently replicate. The research proposes that teachers can effectively integrate AI to enhance teaching and learning without viewing it as a replacement. To do so, teachers need to understand how AI can work well with teachers and students while avoiding potential pitfalls, develop AI literacy, and address practical issues such as data protection, ethics, and privacy. The study reveals that students value and respect human teachers, even as AI becomes more prevalent in education. The study also introduces a roadmap for students, teachers, and universities. This roadmap serves as a valuable guide for refining teaching skills, fostering personal connections, and designing curriculums that effectively balance the strengths of human educators with AI technologies. The future of education lies in the synergy between human teachers and AI. By understanding and refining their unique qualities, teachers, students, and universities can effectively navigate the integration of AI, ensuring a well-rounded and impactful learning experience.
EasyHeC: Accurate and Automatic Hand-eye Calibration via Differentiable Rendering and Space Exploration
Venue: arXiv cs.RO 2023
Year: 2023

Hand-eye calibration is a critical task in robotics, as it directly affects the efficacy of critical operations such as manipulation and grasping. Traditional methods for achieving this objective necessitate the careful design of joint poses and the use of specialized calibration markers, while most recent learning-based approaches using solely pose regression are limited in their abilities to diagnose inaccuracies. In this work, we introduce a new approach to hand-eye calibration called EasyHeC, which is markerless, white-box, and delivers superior accuracy and robustness. We propose to use two key technologies: differentiable rendering-based camera pose optimization and consistency-based joint space exploration, which enables accurate end-to-end optimization of the calibration process and eliminates the need for the laborious manual design of robot joint poses. Our evaluation demonstrates superior performance in synthetic and real-world datasets, enhancing downstream manipulation tasks by providing precise camera poses for locating and interacting with objects. The code is available at the project page: https://ootts.github.io/easyhec.
Multi-Task Multi-Behavior MAP-Elites
Venue: arXiv cs.NE 2023
Year: 2023

We propose Multi-Task Multi-Behavior MAP-Elites, a variant of MAP-Elites that finds a large number of high-quality solutions for a large set of tasks (optimization problems from a given family). It combines the original MAP-Elites for the search for diversity and Multi-Task MAP-Elites for leveraging similarity between tasks. It performs better than three baselines on a humanoid fault-recovery set of tasks, solving more tasks and finding twice as many solutions per solved task.
Revisiting the Minimum Constraint Removal Problem in Mobile Robotics
Venue: arXiv cs.RO 2023
Year: 2023

The minimum constraint removal problem seeks to find the minimum number of constraints, i.e., obstacles, that need to be removed to connect a start to a goal location with a collision-free path. This problem is NP-hard and has been studied in robotics, wireless sensing, and computational geometry. This work contributes to the existing literature by presenting and discussing two results. The first result shows that the minimum constraint removal is NP-hard for simply connected obstacles where each obstacle intersects a constant number of other obstacles. The second result demonstrates that for $n$ simply connected obstacles in the plane, instances of the minimum constraint removal problem with minimum removable obstacles lower than $(n+1)/3$ can be solved in polynomial time. This result is also empirically validated using several instances of randomly sampled axis-parallel rectangles.
Incremental Maximization via Continuization
Venue: arXiv cs.DS 2023
Year: 2023

We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but also describes how to gradually grow the solution as the cardinality bound increases. The goal is to find an incremental solution that guarantees a good competitive ratio against the optimum solution for all cardinalities simultaneously. The central challenge is to characterize maximization problems where this is possible, and to determine the best-possible competitive ratio that can be attained. A lower bound of $2.18$ and an upper bound of $φ+ 1 \approx 2.618$ are known on the competitive ratio for monotone and accountable objectives [Bernstein et al., Math. Prog., 2022], which capture a wide range of maximization problems. We introduce a continuization technique and identify an optimal incremental algorithm that provides strong evidence that $φ+ 1$ is the best-possible competitive ratio. Using this continuization, we obtain an improved lower bound of $2.246$ by studying a particular recurrence relation whose characteristic polynomial has complex roots exactly beyond the lower bound. Based on the optimal continuous algorithm combined with a scaling approach, we also provide a $1.772$-competitive randomized algorithm. We complement this by a randomized lower bound of $1.447$ via Yao's principle.
Insights into Software Development Approaches: Mining Q&A Repositories
Venue: arXiv cs.SE 2023
Year: 2023

Context: Software practitioners adopt approaches like DevOps, Scrum, and Waterfall for high-quality software development. However, limited research has been conducted on exploring software development approaches concerning practitioners discussions on Q&A forums. Objective: We conducted an empirical study to analyze developers discussions on Q&A forums to gain insights into software development approaches in practice. Method: We analyzed 13,903 developers posts across Stack Overflow (SO), Software Engineering Stack Exchange (SESE), and Project Management Stack Exchange (PMSE) forums. A mixed method approach, consisting of the topic modeling technique (i.e., Latent Dirichlet Allocation (LDA)) and qualitative analysis, is used to identify frequently discussed topics of software development approaches, trends (popular, difficult topics), and the challenges faced by practitioners in adopting different software development approaches. Findings: We identified 15 frequently mentioned software development approaches topics on Q&A sites and observed an increase in trends for the top-3 most difficult topics requiring more attention. Finally, our study identified 49 challenges faced by practitioners while deploying various software development approaches, and we subsequently created a thematic map to represent these findings. Conclusions: The study findings serve as a useful resource for practitioners to overcome challenges, stay informed about current trends, and ultimately improve the quality of software products they develop.
Safe Autonomous Driving in Adverse Weather: Sensor Evaluation and Performance Monitoring
Venue: arXiv cs.RO 2023
Year: 2023

The vehicle's perception sensors radar, lidar and camera, which must work continuously and without restriction, especially with regard to automated/autonomous driving, can lose performance due to unfavourable weather conditions. This paper analyzes the sensor signals of these three sensor technologies under rain and fog as well as day and night. A data set of a driving test vehicle as an object target under different weather conditions was recorded in a controlled environment with adjustable, defined, and reproducible weather conditions. Based on the sensor performance evaluation, a method has been developed to detect sensor degradation, including determining the affected data areas and estimating how severe they are. Through this sensor monitoring, measures can be taken in subsequent algorithms to reduce the influences or to take them into account in safety and assistance systems to avoid malfunctions.
Towards a better labeling process for network security datasets
Venue: arXiv cs.CR 2023
Year: 2023

Most network security datasets do not have comprehensive label assignment criteria, hindering the evaluation of the datasets, the training of models, the results obtained, the comparison with other methods, and the evaluation in real-life scenarios. There is no labeling ontology nor tools to help assign the labels, resulting in most analyzed datasets assigning labels in files or directory names. This paper addresses the problem of having a better labeling process by (i) reviewing the needs of stakeholders of the datasets, from creators to model users, (ii) presenting a new ontology of label assignment, (iii) presenting a new tool for assigning structured labels for Zeek network flows based on the ontology, and (iv) studying the differences between generating labels and consuming labels in real-life scenarios. We conclude that a process for structured label assignment is paramount for advancing research in network security and that the new ontology-based label assignation rules should be published as an artifact of every dataset.
A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space
Venue: arXiv cs.CG 2023
Year: 2023

We propose a data structure in $d$-dimensional hyperbolic space that can be considered a natural counterpart to quadtrees in Euclidean spaces. Based on this data structure we propose a so-called L-order for hyperbolic point sets, which is an extension of the Z-order defined in Euclidean spaces. Using these quadtrees and the L-order we build geometric spanners. Near-linear size $(1+ε)$-spanners do not exist in hyperbolic spaces, but we are able to create a Steiner spanner that achieves a spanning ratio of $1+ε$ with $\mathcal O_{d,ε}(n)$ edges, using a simple construction that can be maintained dynamically. As a corollary we also get a $(2+ε)$-spanner (in the classical sense) of the same size, where the spanning ratio $2+ε$ is almost optimal among spanners of subquadratic size. Finally, we show that our Steiner spanner directly provides a solution to the approximate nearest neighbour problem: given a point set $P$ in $d$-dimensional hyperbolic space we build the data structure in $\mathcal O_{d,ε}(n\log n)$ time, using $\mathcal O_{d,ε}(n)$ space. Then for any query point $q$ we can find a point $p\in P$ that is at most $1+ε$ times farther from $q$ than its nearest neighbour in $P$ in $\mathcal O_{d,ε}(\log n)$ time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time $\mathcal O_{d,ε}(\log n)$.
A Mobile Quad-Arm Robot ARMS: Wheeled-Legged Tripedal Locomotion and Quad-Arm Loco-Manipulation
Venue: arXiv cs.RO 2023
Year: 2023

This article proposes a mobile quad-arm robot: ARMS, which unifies wheeled-legged tripedal locomotion, wheeled locomotion, and quad-arm loco-manipulation. ARMS's four arms have different mechanisms and are partially designed to be general-purpose arms for the hybrid locomotion and loco-manipulation. One three-degree-of-freedom (DOF) arm has an active wheel, which is used for wheeled-legged tripedal walking and wheeled driving with passive wheels attached to the torso. Two three-DOF general-purpose arms are series elastic and used for wheeled-legged tripedal walking, object grasping, and manipulation. The upper two-DOF arm is used for manipulation only; its position and orientation are determined by coordinating all arms. Each motor is controlled by an angle controller and trajectory modification with angle, angular velocity, angular acceleration, and torque constraints. ARMS was verified with seven experiments involving joint control, wheeled-legged locomotion, wheeled locomotion and grasping, slope locomotion, block terrain locomotion, carrying a bag, and outdoor locomotion.
Unsupervised Feature Based Algorithms for Time Series Extrinsic Regression
Venue: arXiv cs.LG 2023
Year: 2023

Time Series Extrinsic Regression (TSER) involves using a set of training time series to form a predictive model of a continuous response variable that is not directly related to the regressor series. The TSER archive for comparing algorithms was released in 2022 with 19 problems. We increase the size of this archive to 63 problems and reproduce the previous comparison of baseline algorithms. We then extend the comparison to include a wider range of standard regressors and the latest versions of TSER models used in the previous study. We show that none of the previously evaluated regressors can outperform a regression adaptation of a standard classifier, rotation forest. We introduce two new TSER algorithms developed from related work in time series classification. FreshPRINCE is a pipeline estimator consisting of a transform into a wide range of summary features followed by a rotation forest regressor. DrCIF is a tree ensemble that creates features from summary statistics over random intervals. Our study demonstrates that both algorithms, along with InceptionTime, exhibit significantly better performance compared to the other 18 regressors tested. More importantly, these two proposals (DrCIF and FreshPRINCE) models are the only ones that significantly outperform the standard rotation forest regressor.