OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Interpretable Change Point Detection
Venue: arXiv cs.LG 2023
Year: 2023

Identifying change points (CPs) in a time series is crucial to guide better decision making across various fields like finance and healthcare and facilitating timely responses to potential risks or opportunities. Existing Change Point Detection (CPD) methods have a limitation in tracking changes in the joint distribution of multidimensional features. In addition, they fail to generalize effectively within the same time series as different types of CPs may require different detection methods. As the volume of multidimensional time series continues to grow, capturing various types of complex CPs such as changes in the correlation structure of the time-series features has become essential. To overcome the limitations of existing methods, we propose TiVaCPD, an approach that uses a Time-Varying Graphical Lasso (TVGL) to identify changes in correlation patterns between multidimensional features over time, and combines that with an aggregate Kernel Maximum Mean Discrepancy (MMD) test to identify changes in the underlying statistical distributions of dynamic time windows with varying length. The MMD and TVGL scores are combined using a novel ensemble method based on similarity measures leveraging the power of both statistical tests. We evaluate the performance of TiVaCPD in identifying and characterizing various types of CPs and show that our method outperforms current state-of-the-art methods in real-world CPD datasets. We further demonstrate that TiVaCPD scores characterize the type of CPs and facilitate interpretation of change dynamics, offering insights into real-life applications.
Prophet Inequality: Order selection beats random order
Venue: arXiv cs.DS 2023
Year: 2023

In the prophet inequality problem, a gambler faces a sequence of items arriving online with values drawn independently from known distributions. On seeing an item, the gambler must choose whether to accept its value as her reward and quit the game, or reject it and continue. The gambler's aim is to maximize her expected reward relative to the expected maximum of the values of all items. Since the seventies, a tight bound of 1/2 has been known for this competitive ratio in the setting where the items arrive in an adversarial order (Krengel and Sucheston, 1977, 1978). However, the optimum ratio still remains unknown in the order selection setting, where the gambler selects the arrival order, as well as in prophet secretary, where the items arrive in a random order. Moreover, it is not even known whether a separation exists between the two settings. In this paper, we show that the power of order selection allows the gambler to guarantee a strictly better competitive ratio than if the items arrive randomly. For the order selection setting, we identify an instance for which Peng and Tang's (FOCS'22) state-of-the-art algorithm performs no better than their claimed competitive ratio of (approximately) 0.7251, thus illustrating the need for an improved approach. We therefore extend their design and provide a more general algorithm design framework, using which we show that their ratio can be beaten, by designing a 0.7258-competitive algorithm. For the random order setting, we improve upon Correa, Saona and Ziliotto's (SODA'19) 0.732-hardness result to show a hardness of 0.7254 for general algorithms - even in the setting where the gambler knows the arrival order beforehand, thus establishing a separation between the order selection and random order settings.
A Systematic Review of Ethical Concerns with Voice Assistants
Venue: arXiv cs.HC 2023
Year: 2023

Since Siri's release in 2011 there have been a growing number of AI-driven domestic voice assistants that are increasingly being integrated into devices such as smartphones and TVs. But as their presence has expanded, a range of ethical concerns has been identified around the use of voice assistants, such as the privacy implications of having devices that are always listening and the ways that these devices are integrated into the existing social order of the home. This has created a burgeoning area of research across a range of fields including computer science, social science, and psychology. This paper takes stock of the foundations and frontiers of this work through a systematic literature review of 117 papers on ethical concerns with voice assistants. In addition to analysis of nine specific areas of concern, the review measures the distribution of methods and participant demographics across the literature. We show how some concerns, such as privacy, are operationalized to a much greater extent than others like accessibility, and how study participants are overwhelmingly drawn from a small handful of Western nations. In so doing we hope to provide an outline of the rich tapestry of work around these concerns and highlight areas where current research efforts are lacking.
Active Relation Discovery: Towards General and Label-aware Open Relation Extraction
Venue: arXiv cs.CL 2023
Year: 2023

Open Relation Extraction (OpenRE) aims to discover novel relations from open domains. Previous OpenRE methods mainly suffer from two problems: (1) Insufficient capacity to discriminate between known and novel relations. When extending conventional test settings to a more general setting where test data might also come from seen classes, existing approaches have a significant performance decline. (2) Secondary labeling must be performed before practical application. Existing methods cannot label human-readable and meaningful types for novel relations, which is urgently required by the downstream tasks. To address these issues, we propose the Active Relation Discovery (ARD) framework, which utilizes relational outlier detection for discriminating known and novel relations and involves active learning for labeling novel relations. Extensive experiments on three real-world datasets show that ARD significantly outperforms previous state-of-the-art methods on both conventional and our proposed general OpenRE settings. The source code and datasets will be available for reproducibility.
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Venue: arXiv cs.DS 2023
Year: 2023

We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in $O(\log \log n)$ time. Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than $n^{o(1)}$ update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.
Machine Learning-based Framework for Optimally Solving the Analytical Inverse Kinematics for Redundant Manipulators
Venue: arXiv cs.RO 2023
Year: 2023

Solving the analytical inverse kinematics (IK) of redundant manipulators in real time is a difficult problem in robotics since its solution for a given target pose is not unique. Moreover, choosing the optimal IK solution with respect to application-specific demands helps to improve the robustness and to increase the success rate when driving the manipulator from its current configuration towards a desired pose. This is necessary, especially in high-dynamic tasks like catching objects in mid-flights. To compute a suitable target configuration in the joint space for a given target pose in the trajectory planning context, various factors such as travel time or manipulability must be considered. However, these factors increase the complexity of the overall problem which impedes real-time implementation. In this paper, a real-time framework to compute the analytical inverse kinematics of a redundant robot is presented. To this end, the analytical IK of the redundant manipulator is parameterized by so-called redundancy parameters, which are combined with a target pose to yield a unique IK solution. Most existing works in the literature either try to approximate the direct mapping from the desired pose of the manipulator to the solution of the IK or cluster the entire workspace to find IK solutions. In contrast, the proposed framework directly learns these redundancy parameters by using a neural network (NN) that provides the optimal IK solution with respect to the manipulability and the closeness to the current robot configuration. Monte Carlo simulations show the effectiveness of the proposed approach which is accurate and real-time capable ($\approx$ \SI{32}{\micro\second}) on the KUKA LBR iiwa 14 R820.
Understanding Political Divisiveness using Online Participation data from the 2022 French and Brazilian Presidential Elections
Venue: arXiv cs.CY 2023
Year: 2023

Digital technologies can augment civic participation by facilitating the expression of detailed political preferences. Yet, digital participation efforts often rely on methods optimized for elections involving a few candidates. Here we present data collected in an online experiment where participants built personalized government programs by combining policies proposed by the candidates of the 2022 French and Brazilian presidential elections. We use this data to explore aggregates complementing those used in social choice theory, finding that a metric of divisiveness, which is uncorrelated with traditional aggregation functions, can identify polarizing proposals. These metrics provide a score for the divisiveness of each proposal that can be estimated in the absence of data on the demographic characteristics of participants and that explains the issues that divide a population. These findings suggest divisiveness metrics can be useful complements to traditional aggregation functions in direct forms of digital participation.
Kalman Filter-based Sensing in Communication Systems with Clock Asynchronism
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we propose a novel Kalman Filter (KF)-based uplink (UL) joint communication and sensing (JCAS) scheme, which can significantly reduce the range and location estimation errors due to the clock asynchronism between the base station (BS) and user equipment (UE). Clock asynchronism causes time-varying time offset (TO) and carrier frequency offset (CFO), leading to major challenges in uplink sensing. Unlike existing technologies, our scheme does not require knowing the location of the UE in advance, and retains the linearity of the sensing parameter estimation problem. We first estimate the angle-of-arrivals (AoAs) of multipaths and use them to spatially filter the CSI. Then, we propose a KF-based CSI enhancer that exploits the estimation of Doppler with CFO as the prior information to significantly suppress the time-varying noise-like TO terms in spatially filtered CSIs. Subsequently, we can estimate the accurate ranges of UE and the scatterers based on the KF-enhanced CSI. Finally, we identify the UE's AoA and range estimation and locate UE, then locate the dumb scatterers using the bi-static system. Simulation results validate the proposed scheme. The localization root mean square error of the proposed method is about 20 dB lower than the benchmarking scheme.
Directional Privacy for Deep Learning
Venue: arXiv cs.LG 2023
Year: 2023

Differentially Private Stochastic Gradient Descent (DP-SGD) is a key method for applying privacy in the training of deep learning models. It applies isotropic Gaussian noise to gradients during training, which can perturb these gradients in any direction, damaging utility. Metric DP, however, can provide alternative mechanisms based on arbitrary metrics that might be more suitable for preserving utility. In this paper, we apply \textit{directional privacy}, via a mechanism based on the von Mises-Fisher (VMF) distribution, to perturb gradients in terms of \textit{angular distance} so that gradient direction is broadly preserved. We show that this provides both $ε$-DP and $εd$-privacy for deep learning training, rather than the $(ε, δ)$-privacy of the Gaussian mechanism. Experiments on key datasets then indicate that the VMF mechanism can outperform the Gaussian in the utility-privacy trade-off. In particular, our experiments provide a direct empirical comparison of privacy between the two approaches in terms of their ability to defend against reconstruction and membership inference.
An iterative approach for counting reduced ordered binary decision diagrams
Venue: arXiv cs.DS 2023
Year: 2023

For three decades binary decision diagrams, a data structure efficiently representing Boolean functions, have been widely used in many distinct contexts like model verification, machine learning, cryptography and also resolution of combinatorial problems. The most famous variant, called reduced ordered binary decision diagram (ROBDD for short), can be viewed as the result of a compaction procedure on the full decision tree. A useful property is that once an order over the Boolean variables is fixed, each Boolean function is represented by exactly one ROBDD. In this paper we aim at computing the exact distribution of the Boolean functions in $k$ variables according to the ROBDD size}, where the ROBDD size is equal to the number of decision nodes of the underlying directed acyclic graph (DAG for short) structure. Recall the number of Boolean functions with $k$ variables is equal to $2^{2^k}$, which is of double exponential growth with respect to the number of variables. The maximal size of a ROBDD with $k$ variables is $M_k \approx 2^k / k$. Apart from the natural combinatorial explosion observed, another difficulty for computing the distribution according to size is to take into account dependencies within the DAG structure of ROBDDs. In this paper, we develop the first polynomial algorithm to derive the distribution of Boolean functions over $k$ variables with respect to ROBDD size denoted by $n$. The algorithm computes the (enumerative) generating function of ROBDDs with $k$ variables up to size $n$. It performs $O(k n^4)$ arithmetical operations on integers and necessitates storing $O((k+n) n^2)$ integers with bit length $O(n\log n)$. Our new approach relies on a decomposition of ROBDDs layer by layer and on an inclusion-exclusion argument.
MACSum: Controllable Summarization with Mixed Attributes
Venue: arXiv cs.CL 2023
Year: 2023

Controllable summarization allows users to generate customized summaries with specified attributes. However, due to the lack of designated annotations of controlled summaries, existing works have to craft pseudo datasets by adapting generic summarization benchmarks. Furthermore, most research focuses on controlling single attributes individually (e.g., a short summary or a highly abstractive summary) rather than controlling a mix of attributes together (e.g., a short and highly abstractive summary). In this paper, we propose MACSum, the first human-annotated summarization dataset for controlling mixed attributes. It contains source texts from two domains, news articles and dialogues, with human-annotated summaries controlled by five designed attributes (Length, Extractiveness, Specificity, Topic, and Speaker). We propose two simple and effective parameter-efficient approaches for the new task of mixed controllable summarization based on hard prompt tuning and soft prefix tuning. Results and analysis demonstrate that hard prompt models yield the best performance on all metrics and human evaluations. However, mixed-attribute control is still challenging for summarization tasks. Our dataset and code are available at https://github.com/psunlpgroup/MACSum.
It's TEEtime: A New Architecture Bringing Sovereignty to Smartphones
Venue: arXiv cs.CR 2023
Year: 2023

Modern smartphones are complex systems in which control over phone resources is exercised by phone manufacturers, OS vendors, and users. These stakeholders have diverse and often competing interests. Barring some exceptions, users entrust their security and privacy to OS vendors (Android and iOS) and need to accept their constraints. Manufacturers protect their firmware and peripherals from the OS by executing in the highest privilege and leveraging dedicated CPUs and TEEs. OS vendors need to trust the highest privileged code deployed by manufacturers. This division of control over the phone is not ideal for OS vendors and is even more disadvantageous for the users. Users are generally limited in what applications they can install on their devices, in the privacy model and trust assumptions of the existing applications, and in the functionalities that applications can have. We propose TEEtime, a new smartphone architecture based on trusted execution allowing to balance the control different stakeholders exert over phones. More leveled control over the phone means that no stakeholder is more privileged than the others. In particular, TEEtime makes users sovereign over their phones: It enables them to install sensitive applications in isolated domains with protected access to selected peripherals alongside an OS. TEEtime achieves this while maintaining compatibility with the existing smartphone ecosystem and without relying on virtualization; it only assumes trust in a phone's firmware. TEEtime is the first TEE architecture that allows isolated execution domains to gain protected and direct access to peripherals. TEEtime is based on Armv8-A and achieves peripheral isolation using a novel mechanism based on memory and interrupt controller protection. We demonstrate the feasibility of our design by implementing a prototype of TEEtime, and by running exemplary sensitive applications.
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Venue: arXiv cs.DS 2023
Year: 2023

Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in $\mathbb{R}^d$, in the model of dynamic geometric streams, where the input $X\subseteq [Δ]^d$ is presented as a sequence of point insertions and deletions. Previously, Frahling and Sohler [STOC 2005] designed a $(1+ε)$-approximation algorithm for the low-dimensional regime, i.e., it uses space $\exp(d)$. To tackle this problem in the high-dimensional regime, which is of growing interest, one must improve the dependence on the dimension $d$, ideally to space complexity $\mathrm{poly}(ε^{-1} d \logΔ)$. Lammersen, Sidiropoulos, and Sohler [WADS 2009] proved that Euclidean Max-Cut admits dimension reduction with target dimension $d' = \mathrm{poly}(ε^{-1})$. Combining this with the aforementioned algorithm that uses space $\exp(d')$, they obtain an algorithm whose overall space complexity is indeed polynomial in $d$, but unfortunately exponential in $ε^{-1}$. We devise an alternative approach of \emph{data reduction}, based on importance sampling, and achieve space bound $\mathrm{poly}(ε^{-1} d \logΔ)$, which is exponentially better (in $ε$) than the dimension-reduction approach. To implement this scheme in the streaming model, we employ a randomly-shifted quadtree to construct a tree embedding. While this is a well-known method, a key feature of our algorithm is that the embedding's distortion $O(d\logΔ)$ affects only the space complexity, and the approximation ratio remains $1+ε$.
Enhancing Clinical Support for Breast Cancer with Deep Learning Models using Synthetic Correlated Diffusion Imaging
Venue: arXiv cs.CV 2023
Year: 2023

Breast cancer is the second most common type of cancer in women in Canada and the United States, representing over 25\% of all new female cancer cases. As such, there has been immense research and progress on improving screening and clinical support for breast cancer. In this paper, we investigate enhancing clinical support for breast cancer with deep learning models using a newly introduced magnetic resonance imaging (MRI) modality called synthetic correlated diffusion imaging (CDI$^s$). More specifically, we leverage a volumetric convolutional neural network to learn volumetric deep radiomic features from a pre-treatment cohort and construct a predictor based on the learnt features for grade and post-treatment response prediction. As the first study to learn CDI$^s$-centric radiomic sequences within a deep learning perspective for clinical decision support, we evaluated the proposed approach using the ACRIN-6698 study against those learnt using gold-standard imaging modalities. We find that the proposed approach can achieve better performance for both grade and post-treatment response prediction and thus may be a useful tool to aid oncologists in improving recommendation of treatment of patients. Subsequently, the approach to leverage volumetric deep radiomic features for breast cancer can be further extended to other applications of CDI$^s$ in the cancer domain to further improve clinical support.
Scalable Modular Synthetic Data Generation for Advancing Aerial Autonomy
Venue: arXiv cs.CV 2023
Year: 2023

One major barrier to advancing aerial autonomy has been collecting large-scale aerial datasets for training machine learning models. Due to costly and time-consuming real-world data collection through deploying drones, there has been an increasing shift towards using synthetic data for training models in drone applications. However, to increase widespread generalization and transferring models to real-world, increasing the diversity of simulation environments to train a model over all the varieties and augmenting the training data, has been proved to be essential. Current synthetic aerial data generation tools either lack data augmentation or rely heavily on manual workload or real samples for configuring and generating diverse realistic simulation scenes for data collection. These dependencies limit scalability of the data generation workflow. Accordingly, there is a major challenge in balancing generalizability and scalability in synthetic data generation. To address these gaps, we introduce a scalable Aerial Synthetic Data Augmentation (ASDA) framework tailored to aerial autonomy applications. ASDA extends a central data collection engine with two scriptable pipelines that automatically perform scene and data augmentations to generate diverse aerial datasets for different training tasks. ASDA improves data generation workflow efficiency by providing a unified prompt-based interface over integrated pipelines for flexible control. The procedural generative approach of our data augmentation is performant and adaptable to different simulation environments, training tasks and data collection needs. We demonstrate the effectiveness of our method in automatically generating diverse datasets and show its potential for downstream performance optimization.
Multistatic Sensing of Passive Targets Using 6G Cellular Infrastructure
Venue: arXiv cs.IT 2023
Year: 2023

Sensing using cellular infrastructure may be one of the defining feature of sixth generation (6G) wireless systems. Wideband 6G communication channels operating at higher frequency bands (upper mmWave bands) are better modeled using clustered geometric channel models. In this paper, we propose methods for detection of passive targets and estimating their position using communication deployment without any assistance from the target. A novel AI architecture called CsiSenseNet is developed for this purpose. We analyze the resolution, coverage and position uncertainty for practical indoor deployments. Using the proposed method, we show that human sized target can be sensed with high accuracy and sub-meter positioning errors in a practical indoor deployment scenario.