OpenRaiser/Intern-Atlas huggingface dataset:
ConceptGraphs: Open-Vocabulary 3D Scene Graphs for Perception and Planning
Venue: arXiv cs.RO 2023
Year: 2023

For robots to perform a wide variety of tasks, they require a 3D representation of the world that is semantically rich, yet compact and efficient for task-driven perception and planning. Recent approaches have attempted to leverage features from large vision-language models to encode semantics in 3D representations. However, these approaches tend to produce maps with per-point feature vectors, which do not scale well in larger environments, nor do they contain semantic spatial relationships between entities in the environment, which are useful for downstream planning. In this work, we propose ConceptGraphs, an open-vocabulary graph-structured representation for 3D scenes. ConceptGraphs is built by leveraging 2D foundation models and fusing their output to 3D by multi-view association. The resulting representations generalize to novel semantic classes, without the need to collect large 3D datasets or finetune models. We demonstrate the utility of this representation through a number of downstream planning tasks that are specified through abstract (language) prompts and require complex reasoning over spatial and semantic concepts. (Project page: https://concept-graphs.github.io/ Explainer video: https://youtu.be/mRhNkQwRYnc )
Geodesic Regression Characterizes 3D Shape Changes in the Female Brain During Menstruation
Venue: arXiv cs.CV 2023
Year: 2023

Women are at higher risk of Alzheimer's and other neurological diseases after menopause, and yet research connecting female brain health to sex hormone fluctuations is limited. We seek to investigate this connection by developing tools that quantify 3D shape changes that occur in the brain during sex hormone fluctuations. Geodesic regression on the space of 3D discrete surfaces offers a principled way to characterize the evolution of a brain's shape. However, in its current form, this approach is too computationally expensive for practical use. In this paper, we propose approximation schemes that accelerate geodesic regression on shape spaces of 3D discrete surfaces. We also provide rules of thumb for when each approximation can be used. We test our approach on synthetic data to quantify the speed-accuracy trade-off of these approximations and show that practitioners can expect very significant speed-up while only sacrificing little accuracy. Finally, we apply the method to real brain shape data and produce the first characterization of how the female hippocampus changes shape during the menstrual cycle as a function of progesterone: a characterization made (practically) possible by our approximation schemes. Our work paves the way for comprehensive, practical shape analyses in the fields of bio-medicine and computer vision. Our implementation is publicly available on GitHub: https://github.com/bioshape-lab/my28brains.
VMT19937: A SIMD-Friendly Pseudo Random Number Generator based on Mersenne Twister 19937
Venue: arXiv cs.DC 2023
Year: 2023

Many simulation applications require the generation of long sequences of pseudo-random numbers. Linear recurrences modulo 2 are commonly used as the fundamental building block for constructing pseudo-random number generators with extended periods and excellent statistical properties. These generators consist of a lengthy binary state vector that evolves iteratively through linear transformations. One widely accepted pseudo-random generator in this category is the Mersenne twister 19937 (MT19937), proposed by Matsumoto and Nishimura, which has been implemented in numerous software libraries and numerical packages. The MT19937's popularity stems from its favorable distribution properties and the simplicity and speed of its algorithm. The linear transformation responsible for evolving the binary state vector can be expressed as a concise set of elementary bit manipulations. However, this transformation does not fully utilize the potential for parallelization through SIMD instructions available on modern hardware, limiting further speed enhancements. This paper introduces a new SIMD-friendly random number generator, which maintains the same statistical properties and period as the MT19937. It combines the random streams of multiple MT19937 instances with state vectors de-phased via jump-ahead transformations, then polls each instance in a round-robin fashion. By evolving their vector states simultaneously, the new generator achieves perfect vectorization, fully leveraging on SIMD hardware capabilities. Comprehensive test results demonstrate that the throughput of the new generator scales approximately linearly with the width of the SIMD registers used. This provides significant speed improvements, especially on modern CPUs equipped with larger SIMD registers, and allows for efficient generation of random numbers for various simulation applications.
A Direct k-Way Hypergraph Partitioning Algorithm for Optimizing the Steiner Tree Metric
Venue: arXiv cs.DC 2023
Year: 2023

Minimizing wire-lengths is one of the most important objectives in circuit design. The process involves initially placing the logical units (cells) of a circuit onto a physical layout, and subsequently routing the wires to connect the cells. Hypergraph partitioning (HGP) has been long used as a placement strategy in this process. However, it has been replaced by other methods due to the limitation that common HGP objective funtions only optimize wire-lengths implicitly. In this work, we present a novel HGP formulation that maps a hypergraph $H$, representing a logical circuit, onto a routing layout represented by a weighted graph $G$. The objective is to minimize the total length of all wires induced by the hyperedges of $H$ on $G$. To capture wire-lengths, we compute minimal Steiner trees - a metric commonly used in routing algorithms. For this formulation, we present the first direct $k$-way multilevel mapping algorithm that incorporates techniques used by the highest-quality partitioning algorithms. We contribute a greedy mapping algorithm to compute an initial solution and three refinement algorithms to improve the initial: Two move-based local search heuristics (based on label propagation and the FM algorithm) and a refinement algorithm based on max-flow min-cut computations. Our experiments demonstrate that our new algorithm achieves an improvement in the Steiner tree metric by 7% (median) on VLSI instances when compared to the best performing partitioning algorithm that optimizes the mapping in a postprocessing step. Although computing Steiner trees is an NP-hard problem, we achieve this improvement with only a 2-3 times slowdown in partitioning time compared to optimizing the connectivity metric.
Inappropriate Benefits and Identification of ChatGPT Misuse in Programming Tests: A Controlled Experiment
Venue: arXiv cs.AI 2023
Year: 2023

While ChatGPT may help students to learn to program, it can be misused to do plagiarism, a breach of academic integrity. Students can ask ChatGPT to complete a programming task, generating a solution from other people's work without proper acknowledgment of the source(s). To help address this new kind of plagiarism, we performed a controlled experiment measuring the inappropriate benefits of using ChatGPT in terms of completion time and programming performance. We also reported how to manually identify programs aided with ChatGPT (via student behavior while using ChatGPT) and student perspective of ChatGPT (via a survey). Seventeen students participated in the experiment. They were asked to complete two programming tests. They were divided into two groups per the test: one group should complete the test without help while the other group should complete it with ChatGPT. Our study shows that students with ChatGPT complete programming tests two times faster than those without ChatGPT, though their programming performance is comparable. The generated code is highly efficient and uses complex data structures like lists and dictionaries. Based on the survey results, ChatGPT is recommended to be used as an assistant to complete programming tasks and other general assignments. ChatGPT will be beneficial as a reference as other search engines do. Logical and critical thinking are needed to validate the result presented by ChatGPT.
Incompatibilities Between Current Practices in Statistical Data Analysis and Differential Privacy
Venue: arXiv cs.CR 2023
Year: 2023

The authors discuss their experience applying differential privacy with a complex data set with the goal of enabling standard approaches to statistical data analysis. They highlight lessons learned and roadblocks encountered, distilling them into incompatibilities between current practices in statistical data analysis and differential privacy that go beyond issues which can be solved with a noisy measurements file. The authors discuss how overcoming these incompatibilities require compromise and a change in either our approach to statistical data analysis or differential privacy that should be addressed head-on.
Multimodal Analysis Of Google Bard And GPT-Vision: Experiments In Visual Reasoning
Venue: arXiv cs.CV 2023
Year: 2023

Addressing the gap in understanding visual comprehension in Large Language Models (LLMs), we designed a challenge-response study, subjecting Google Bard and GPT-Vision to 64 visual tasks, spanning categories like "Visual Situational Reasoning" and "Next Scene Prediction." Previous models, such as GPT4, leaned heavily on optical character recognition tools like Tesseract, whereas Bard and GPT-Vision, akin to Google Lens and Visual API, employ deep learning techniques for visual text recognition. However, our findings spotlight both vision-language model's limitations: while proficient in solving visual CAPTCHAs that stump ChatGPT alone, it falters in recreating visual elements like ASCII art or analyzing Tic Tac Toe grids, suggesting an over-reliance on educated visual guesses. The prediction problem based on visual inputs appears particularly challenging with no common-sense guesses for next-scene forecasting based on current "next-token" multimodal models. This study provides experimental insights into the current capacities and areas for improvement in multimodal LLMs.
Joint Participation Incentive and Network Pricing Design for Federated Learning
Venue: arXiv cs.NI 2023
Year: 2023

Federated learning protects users' data privacy through sharing users' local model parameters (instead of raw data) with a server. However, when massive users train a large machine learning model through federated learning, the dynamically varying and often heavy communication overhead can put significant pressure on the network operator. The operator may choose to dynamically change the network prices in response, which will eventually affect the payoffs of the server and users. This paper considers the under-explored yet important issue of the joint design of participation incentives (for encouraging users' contribution to federated learning) and network pricing (for managing network resources). Due to heterogeneous users' private information and multi-dimensional decisions, the optimization problems in Stage I of multi-stage games are non-convex. Nevertheless, we are able to analytically derive the corresponding optimal contract and pricing mechanism through proper transformations of constraints, variables, and functions, under both vertical and horizontal interaction structures of the participants. We show that the vertical structure is better than the horizontal one, as it avoids the interests misalignment between the server and the network operator. Numerical results based on real-world datasets show that our proposed mechanisms decrease server's cost by up to 24.87% comparing with the state-of-the-art benchmarks.
How many words does ChatGPT know? The answer is ChatWords
Venue: arXiv cs.CL 2023
Year: 2023

The introduction of ChatGPT has put Artificial Intelligence (AI) Natural Language Processing (NLP) in the spotlight. ChatGPT adoption has been exponential with millions of users experimenting with it in a myriad of tasks and application domains with impressive results. However, ChatGPT has limitations and suffers hallucinations, for example producing answers that look plausible but they are completely wrong. Evaluating the performance of ChatGPT and similar AI tools is a complex issue that is being explored from different perspectives. In this work, we contribute to those efforts with ChatWords, an automated test system, to evaluate ChatGPT knowledge of an arbitrary set of words. ChatWords is designed to be extensible, easy to use, and adaptable to evaluate also other NLP AI tools. ChatWords is publicly available and its main goal is to facilitate research on the lexical knowledge of AI tools. The benefits of ChatWords are illustrated with two case studies: evaluating the knowledge that ChatGPT has of the Spanish lexicon (taken from the official dictionary of the "Real Academia Española") and of the words that appear in the Quixote, the well-known novel written by Miguel de Cervantes. The results show that ChatGPT is only able to recognize approximately 80% of the words in the dictionary and 90% of the words in the Quixote, in some cases with an incorrect meaning. The implications of the lexical knowledge of NLP AI tools and potential applications of ChatWords are also discussed providing directions for further work on the study of the lexical knowledge of AI tools.
Software-Intensive Product Engineering in Start-Ups: A Taxonomy
Venue: arXiv cs.SE 2023
Year: 2023

Software start-ups are new companies aiming to launch an innovative product to mass markets fast with minimal resources. However, most start-ups fail before realizing their potential. Poor software engineering, among other factors, could be a significant contributor to the challenges that start-ups experience. Little is known about the engineering context in start-up companies. On the surface, start-ups are characterized by uncertainty, high risk, and minimal resources. However, such a characterization isn't granular enough to support identification of specific engineering challenges and to devise start-up-specific engineering practices. The first step toward an understanding of software engineering in start-ups is the definition of a Start-Up Context Map - a taxonomy of engineering practices, environment factors, and goals influencing the engineering process. This map aims to support further research on the field and serve as an engineering decision support tool for start-ups. This article is part of a theme issue on Process Improvement.
Multi-Bellman operator for convergence of $Q$-learning with linear function approximation
Venue: arXiv cs.LG 2023
Year: 2023

We study the convergence of $Q$-learning with linear function approximation. Our key contribution is the introduction of a novel multi-Bellman operator that extends the traditional Bellman operator. By exploring the properties of this operator, we identify conditions under which the projected multi-Bellman operator becomes contractive, providing improved fixed-point guarantees compared to the Bellman operator. To leverage these insights, we propose the multi $Q$-learning algorithm with linear function approximation. We demonstrate that this algorithm converges to the fixed-point of the projected multi-Bellman operator, yielding solutions of arbitrary accuracy. Finally, we validate our approach by applying it to well-known environments, showcasing the effectiveness and applicability of our findings.
Stochastic Digital Twin for Copy Detection Patterns
Venue: arXiv cs.CV 2023
Year: 2023

Copy detection patterns (CDP) present an efficient technique for product protection against counterfeiting. However, the complexity of studying CDP production variability often results in time-consuming and costly procedures, limiting CDP scalability. Recent advancements in computer modelling, notably the concept of a "digital twin" for printing-imaging channels, allow for enhanced scalability and the optimization of authentication systems. Yet, the development of an accurate digital twin is far from trivial. This paper extends previous research which modelled a printing-imaging channel using a machine learning-based digital twin for CDP. This model, built upon an information-theoretic framework known as "Turbo", demonstrated superior performance over traditional generative models such as CycleGAN and pix2pix. However, the emerging field of Denoising Diffusion Probabilistic Models (DDPM) presents a potential advancement in generative models due to its ability to stochastically model the inherent randomness of the printing-imaging process, and its impressive performance in image-to-image translation tasks. This study aims at comparing the capabilities of the Turbo framework and DDPM on the same CDP datasets, with the goal of establishing the real-world benefits of DDPM models for digital twin applications in CDP security. Furthermore, the paper seeks to evaluate the generative potential of the studied models in the context of mobile phone data acquisition. Despite the increased complexity of DDPM methods when compared to traditional approaches, our study highlights their advantages and explores their potential for future applications.
Evaluating the Efficiency of Software-only Techniques to Detect SEU and SET in Microprocessors
Venue: arXiv cs.AR 2023
Year: 2023

This paper presents a detailed evaluation of the efficiency of software-only techniques to mitigate SEU and SET in microprocessors. A set of well-known rules is presented and implemented automatically to transform an unprotected program into a hardened one. SEU and SET are injected in all sensitive areas of a MIPS-based microprocessor architecture. The efficiency of each rule and a combination of them are tested. Experimental results show the inefficiency of the control-flow techniques in detecting the majority of SEU and SET faults. Three effects of the non-detected faults are explained. The conclusions can lead designers in developing more efficient techniques to detect these types of faults.
Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs
Venue: arXiv cs.DS 2023
Year: 2023

Given an undirected graph $G$ and a multiset of $k$ terminal pairs $\mathcal{X}$, the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether $G$ has $k$ pairwise internally vertex-disjoint paths and $k$ pairwise edge-disjoint paths, respectively, connecting every terminal pair in~$\mathcal{X}$. In this paper, we study the kernelization complexity of \VDP~and~\EDP~on subclasses of chordal graphs. For \VDP, we design a $4k$ vertex kernel on split graphs and an $\mathcal{O}(k^2)$ vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For \textsc{EDP}, we first prove that the problem is $\mathsf{NP}$-complete on complete graphs. Then, we design an $\mathcal{O}(k^{2.75})$ vertex kernel for \EDP~on split graphs, and improve it to a $7k+1$ vertex kernel on threshold graphs. Lastly, we provide an $\mathcal{O}(k^2)$ vertex kernel for \EDP~on block graphs and a $2k+1$ vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al.~[Theory Comput. Syst., 2015].
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Venue: arXiv cs.CC 2023
Year: 2023

We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst-case and average-case input models, where the input is generated by (1) choosing an arbitrary planted assignment $x^*$, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution "shifted by $x^*$" so that $x^*$ satisfies each constraint. For an $n$ variable semirandom planted instance of a $k$-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a $o(1)$-fraction of constraints, provided that the instance has at least $\tilde{O}(n^{k/2})$ constraints. This matches, up to $polylog(n)$ factors, the clause threshold for algorithms that solve fully random planted CSPs [FPV15], as well as algorithms that refute random and semirandom CSPs [AOW15, AGK21]. Our result shows that despite having worst-case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst-case, where analogous results require $O(n^k)$ constraints [AKK95, FLP16]. Perhaps surprisingly, our algorithm follows a significantly different conceptual framework when compared to the recent resolution of semirandom CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices - reminiscent of the classical spectral sparsification - which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, it suffices to obtain a weaker guarantee of absolute upper bounds on the spectral norm of related matrices.
PONG: Probabilistic Object Normals for Grasping via Analytic Bounds on Force Closure Probability
Venue: arXiv cs.RO 2023
Year: 2023

Classical approaches to grasp planning are deterministic, requiring perfect knowledge of an object's pose and geometry. In response, data-driven approaches have emerged that plan grasps entirely from sensory data. While these data-driven methods have excelled in generating parallel-jaw and power grasps, their application to precision grasps (those using the fingertips of a dexterous hand, e.g, for tool use) remains limited. Precision grasping poses a unique challenge due to its sensitivity to object geometry, which allows small uncertainties in the object's shape and pose to cause an otherwise robust grasp to fail. In response to these challenges, we introduce Probabilistic Object Normals for Grasping (PONG), a novel, analytic approach for calculating a conservative estimate of force closure probability in the case when contact locations are known but surface normals are uncertain. We then present a practical application where we use PONG as a grasp metric for generating robust grasps both in simulation and real-world hardware experiments. Our results demonstrate that maximizing PONG efficiently produces robust grasps, even for challenging object geometries, and that it can serve as a well-calibrated, uncertainty-aware metric of grasp quality.
CrossZoom: Simultaneously Motion Deblurring and Event Super-Resolving
Venue: arXiv cs.CV 2023
Year: 2023

Even though the collaboration between traditional and neuromorphic event cameras brings prosperity to frame-event based vision applications, the performance is still confined by the resolution gap crossing two modalities in both spatial and temporal domains. This paper is devoted to bridging the gap by increasing the temporal resolution for images, i.e., motion deblurring, and the spatial resolution for events, i.e., event super-resolving, respectively. To this end, we introduce CrossZoom, a novel unified neural Network (CZ-Net) to jointly recover sharp latent sequences within the exposure period of a blurry input and the corresponding High-Resolution (HR) events. Specifically, we present a multi-scale blur-event fusion architecture that leverages the scale-variant properties and effectively fuses cross-modality information to achieve cross-enhancement. Attention-based adaptive enhancement and cross-interaction prediction modules are devised to alleviate the distortions inherent in Low-Resolution (LR) events and enhance the final results through the prior blur-event complementary information. Furthermore, we propose a new dataset containing HR sharp-blurry images and the corresponding HR-LR event streams to facilitate future research. Extensive qualitative and quantitative experiments on synthetic and real-world datasets demonstrate the effectiveness and robustness of the proposed method. Codes and datasets are released at https://bestrivenzc.github.io/CZ-Net/.