OpenRaiser/Intern-Atlas huggingface dataset:
Accelerated SGD for Non-Strongly-Convex Least Squares
Venue: arXiv cs.LG 2022
Year: 2022

We consider stochastic approximation for the least squares regression problem in the non-strongly convex setting. We present the first practical algorithm that achieves the optimal prediction error rates in terms of dependence on the noise of the problem, as $O(d/t)$ while accelerating the forgetting of the initial conditions to $O(d/t^2)$. Our new algorithm is based on a simple modification of the accelerated gradient descent. We provide convergence results for both the averaged and the last iterate of the algorithm. In order to describe the tightness of these new bounds, we present a matching lower bound in the noiseless setting and thus show the optimality of our algorithm.
Revisiting Click-based Interactive Video Object Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

While current methods for interactive Video Object Segmentation (iVOS) rely on scribble-based interactions to generate precise object masks, we propose a Click-based interactive Video Object Segmentation (CiVOS) framework to simplify the required user workload as much as possible. CiVOS builds on de-coupled modules reflecting user interaction and mask propagation. The interaction module converts click-based interactions into an object mask, which is then inferred to the remaining frames by the propagation module. Additional user interactions allow for a refinement of the object mask. The approach is extensively evaluated on the popular interactive~DAVIS dataset, but with an inevitable adaptation of scribble-based interactions with click-based counterparts. We consider several strategies for generating clicks during our evaluation to reflect various user inputs and adjust the DAVIS performance metric to perform a hardware-independent comparison. The presented CiVOS pipeline achieves competitive results, although requiring a lower user workload.
Efficient Fréchet distance queries for segments
Venue: arXiv cs.CG 2022
Year: 2022

We study the problem of constructing a data structure that can store a two-dimensional polygonal curve $P$, such that for any query segment $\overline{ab}$ one can efficiently compute the Fréchet distance between $P$ and $\overline{ab}$. First we present a data structure of size $O(n \log n)$ that can compute the Fréchet distance between $P$ and a horizontal query segment $\overline{ab}$ in $O(\log n)$ time, where $n$ is the number of vertices of $P$. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment $\overline{ab}$ together with two points $s, t \in P$ (not necessarily vertices), and ask for the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$. Using $O(n\log^2n)$ storage, such queries take $O(\log^3 n)$ time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an $O(nk^{3+\varepsilon}+n^2)$ size data structure, where $k \in [1..n]$ is a parameter the user can choose, and $\varepsilon > 0$ is an arbitrarily small constant, such that given any segment $\overline{ab}$ and two points $s, t \in P$ we can compute the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$ in $O((n/k)\log^2n+\log^4 n)$ time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments. We also present two applications of our data structure: we show that we can compute a local $δ$-simplification (with respect to the Fréchet distance) of a polygonal curve in $O(n^{5/2+\varepsilon})$ time, and that we can efficiently find a translation of an arbitrary query segment $\overline{ab}$ that minimizes the Fréchet distance with respect to a subcurve of $P$.
Quadrotor Formation Flying Resilient to Abrupt Vehicle Failures via a Fluid Flow Navigation Function
Venue: arXiv cs.RO 2022
Year: 2022

This paper develops and experimentally evaluates a navigation function for quadrotor formation flight that is resilient to abrupt quadrotor failures and other obstacles. The navigation function is based on modeling healthy quadrotors as particles in an ideal fluid flow. We provide three key contributions: (i) A Containment Exclusion Mode (CEM) safety theorem and proof which guarantees safety and formally specifies a minimum safe distance between quadrotors in formation, (ii) A real-time, computationally efficient CEM navigation algorithm, (iii) Simulation and experimental algorithm validation. Simulations were first performed with a team of six virtual quadrotors to demonstrate velocity tracking via dynamic slide speed, maintaining sufficient inter-agent distances, and operating in real-time. Flight tests with a team of two custom quadrotors were performed in an indoor motion capture flight facility, successfully validating that the navigation algorithm can handle non-trivial bounded tracking errors while guaranteeing safety.
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
Venue: arXiv cs.DS 2022
Year: 2022

We study several questions related to diversifying search results. We give improved approximation algorithms in each of the following problems, together with some lower bounds. - We give a polynomial-time approximation scheme (PTAS) for a diversified search ranking problem [Bansal et al., ICALP 2010] whose objective is to minimizes the discounted cumulative gain. Our PTAS runs in time $n^{2^{O(\log(1/ε)/ε)}} \cdot m^{O(1)}$ where $n$ denotes the number of elements in the databases. Complementing this, we show that no PTAS can run in time $f(ε) \cdot (nm)^{2^{o(1/ε)}}$ assuming Gap-ETH; therefore our running time is nearly tight. Both of our bounds answer open questions of Bansal et al. - We next consider the Max-Sum Dispersion problem, whose objective is to select $k$ out of $n$ elements that maximizes the dispersion, which is defined as the sum of the pairwise distances under a given metric. We give a quasipolynomial-time approximation scheme for the problem which runs in time $n^{O_ε(\log n)}$. This improves upon previously known polynomial-time algorithms with approximate ratios 0.5 [Hassin et al., Oper. Res. Lett. 1997; Borodin et al., ACM Trans. Algorithms 2017]. Furthermore, we observe that known reductions rule out approximation schemes that run in $n^{\tilde{o}_ε(\log n)}$ time assuming ETH. - We consider a generalization of Max-Sum Dispersion called Max-Sum Diversification. In addition to the sum of pairwise distance, the objective includes another function $f$. For monotone submodular $f$, we give a quasipolynomial-time algorithm with approximation ratio arbitrarily close to $(1 - 1/e)$. This improves upon the best polynomial-time algorithm which has approximation ratio $0.5$ by Borodin et al. Furthermore, the $(1 - 1/e)$ factor is tight as achieving better-than-$(1 - 1/e)$ approximation is NP-hard [Feige, J. ACM 1998].
Improving Health Mentioning Classification of Tweets using Contrastive Adversarial Training
Venue: arXiv cs.AI 2022
Year: 2022

Health mentioning classification (HMC) classifies an input text as health mention or not. Figurative and non-health mention of disease words makes the classification task challenging. Learning the context of the input text is the key to this problem. The idea is to learn word representation by its surrounding words and utilize emojis in the text to help improve the classification results. In this paper, we improve the word representation of the input text using adversarial training that acts as a regularizer during fine-tuning of the model. We generate adversarial examples by perturbing the embeddings of the model and then train the model on a pair of clean and adversarial examples. Additionally, we utilize contrastive loss that pushes a pair of clean and perturbed examples close to each other and other examples away in the representation space. We train and evaluate the method on an extended version of the publicly available PHM2017 dataset. Experiments show an improvement of 1.0% over BERT-Large baseline and 0.6% over RoBERTa-Large baseline, whereas 5.8% over the state-of-the-art in terms of F1 score. Furthermore, we provide a brief analysis of the results by utilizing the power of explainable AI.
Why adversarial training can hurt robust accuracy
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning classifiers with high test accuracy often perform poorly under adversarial attacks. It is commonly believed that adversarial training alleviates this issue. In this paper, we demonstrate that, surprisingly, the opposite may be true -- Even though adversarial training helps when enough data is available, it may hurt robust generalization in the small sample size regime. We first prove this phenomenon for a high-dimensional linear classification setting with noiseless observations. Our proof provides explanatory insights that may also transfer to feature learning models. Further, we observe in experiments on standard image datasets that the same behavior occurs for perceptible attacks that effectively reduce class information such as mask attacks and object corruptions.
Nonlinear predictive models computation in ADPCM schemes
Venue: arXiv cs.SD 2022
Year: 2022

Recently several papers have been published on nonlinear prediction applied to speech coding. At ICASSP98 we presented a system based on an ADPCM scheme with a nonlinear predictor based on a neural net. The most critical parameter was the training procedure in order to achieve good generalization capability and robustness against mismatch between training and testing conditions. In this paper, we propose several new approaches that improve the performance of the original system in up to 1.2dB of SEGSNR (using bayesian regularization). The variance of the SEGSNR between frames is also minimized, so the new scheme produces a more stable quality of the output.
Design requirements to improve laparoscopy via XR
Venue: arXiv cs.HC 2022
Year: 2022

Laparoscopic surgery has the advantage of avoiding large open incisions and thereby decreasing blood loss, pain, and discomfort to patients. However, on the other side, it is hampered by restricted workspace, ambiguous communication, and surgeon fatigue caused by non-ergonomic head positioning. We aimed to identify critical problems and suggest design requirements and solutions. We used user and task analysis methods to learn about practices performed in an operating room by observing surgeons in their working environment to understand how they performed tasks and achieved their intended goals. Drawing on observations and analysis from recorded laparoscopic surgeries, we have identified several constraints and design requirements to propose potential solutions to address the issues. Surgeons operate in a dimly lit environment, surrounded by monitors, and communicate through verbal commands and pointing gestures. Therefore, performing user and task analysis allowed us to better understand the existing problems in laparoscopy while identifying several communication constraints and design requirements, which a solution has to follow to address those problems. Our contributions include identifying design requirements for laparoscopy surgery through a user and task analysis. These requirements propose design solutions towards improved surgeons' comfort and make the surgical procedure less laborious.
User-Level Membership Inference Attack against Metric Embedding Learning
Venue: arXiv cs.LG 2022
Year: 2022

Membership inference (MI) determines if a sample was part of a victim model training set. Recent development of MI attacks focus on record-level membership inference which limits their application in many real-world scenarios. For example, in the person re-identification task, the attacker (or investigator) is interested in determining if a user's images have been used during training or not. However, the exact training images might not be accessible to the attacker. In this paper, we develop a user-level MI attack where the goal is to find if any sample from the target user has been used during training even when no exact training sample is available to the attacker. We focus on metric embedding learning due to its dominance in person re-identification, where user-level MI attack is more sensible. We conduct an extensive evaluation on several datasets and show that our approach achieves high accuracy on user-level MI task.
CGN: A Capacity-Guaranteed Network Architecture for Future Ultra-Dense Wireless Systems
Venue: arXiv cs.IT 2022
Year: 2022

The sixth generation (6G) era is envisioned to be a fully intelligent and autonomous era, with physical and digital lifestyles merged together. Future wireless network architectures should provide a solid support for such new lifestyles. A key problem thus arises that what kind of network architectures are suitable for 6G. In this paper, we propose a capacity-guaranteed network (CGN) architecture, which provides high capacity for wireless devices densely distributed everywhere, and ensures a superior scalability with low signaling overhead and computation complexity simultaneously. Our theorem proves that the essence of a CGN architecture is to decompose the whole network into non-overlapping clusters with equal cluster sum capacity. Simulation results reveal that in terms of the minimum cluster sum capacity, the proposed CGN can achieve at least 30% performance gain compared with existing base station clustering (BS-clustering) architectures. In addition, our theorem is sufficiently general and can be applied for networks with different distributions of BSs and users.
TransMUSE: Transferable Traffic Prediction in MUlti-Service EdgeNetworks
Venue: arXiv cs.NI 2022
Year: 2022

The Covid-19 pandemic has forced the workforce to switch to working from home, which has put significant burdens on the management of broadband networks and called for intelligent service-by-service resource optimization at the network edge. In this context, network traffic prediction is crucial for operators to provide reliable connectivity across large geographic regions. Although recent advances in neural network design have demonstrated potential to effectively tackle forecasting, in this work we reveal based on real-world measurements that network traffic across different regions differs widely. As a result, models trained on historical traffic data observed in one region can hardly serve in making accurate predictions in other areas. Training bespoke models for different regions is tempting, but that approach bears significant measurement overhead, is computationally expensive, and does not scale. Therefore, in this paper we propose TransMUSE, a novel deep learning framework that clusters similar services, groups edge-nodes into cohorts by traffic feature similarity, and employs a Transformer-based Multi-service Traffic Prediction Network (TMTPN), which can be directly transferred within a cohort without any customization. We demonstrate that TransMUSE exhibits imperceptible performance degradation in terms of mean absolute error (MAE) when forecasting traffic, compared with settings where a model is trained for each individual edge node. Moreover, our proposed TMTPN architecture outperforms the state-of-the-art, achieving up to 43.21% lower MAE in the multi-service traffic prediction task. To the best of our knowledge, this is the first work that jointly employs model transfer and multi-service traffic prediction to reduce measurement overhead, while providing fine-grained accurate demand forecasts for edge services provisioning.
Deep Lexical Hypothesis: Identifying personality structure in natural language
Venue: arXiv cs.CL 2022
Year: 2022

Recent advances in natural language processing (NLP) have produced general models that can perform complex tasks such as summarizing long passages and translating across languages. Here, we introduce a method to extract adjective similarities from language models as done with survey-based ratings in traditional psycholexical studies but using millions of times more text in a natural setting. The correlational structure produced through this method is highly similar to that of self- and other-ratings of 435 terms reported by Saucier and Goldberg (1996a). The first three unrotated factors produced using NLP are congruent with those in survey data, with coefficients of 0.89, 0.79, and 0.79. This structure is robust to many modeling decisions: adjective set, including those with 1,710 terms (Goldberg, 1982) and 18,000 terms (Allport & Odbert, 1936); the query used to extract correlations; and language model. Notably, Neuroticism and Openness are only weakly and inconsistently recovered. This is a new source of signal that is closer to the original (semantic) vision of the Lexical Hypothesis. The method can be applied where surveys cannot: in dozens of languages simultaneously, with tens of thousands of items, on historical text, and at extremely large scale for little cost. The code is made public to facilitate reproduction and fast iteration in new directions of research.
Learning Category-Level Generalizable Object Manipulation Policy via Generative Adversarial Self-Imitation Learning from Demonstrations
Venue: arXiv cs.RO 2022
Year: 2022

Generalizable object manipulation skills are critical for intelligent and multi-functional robots to work in real-world complex scenes. Despite the recent progress in reinforcement learning, it is still very challenging to learn a generalizable manipulation policy that can handle a category of geometrically diverse articulated objects. In this work, we tackle this category-level object manipulation policy learning problem via imitation learning in a task-agnostic manner, where we assume no handcrafted dense rewards but only a terminal reward. Given this novel and challenging generalizable policy learning problem, we identify several key issues that can fail the previous imitation learning algorithms and hinder the generalization to unseen instances. We then propose several general but critical techniques, including generative adversarial self-imitation learning from demonstrations, progressive growing of discriminator, and instance-balancing for expert buffer, that accurately pinpoints and tackles these issues and can benefit category-level manipulation policy learning regardless of the tasks. Our experiments on ManiSkill benchmarks demonstrate a remarkable improvement on all tasks and our ablation studies further validate the contribution of each proposed technique.
Abuse and Fraud Detection in Streaming Services Using Heuristic-Aware Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

This work presents a fraud and abuse detection framework for streaming services by modeling user streaming behavior. The goal is to discover anomalous and suspicious incidents and scale the investigation efforts by creating models that characterize the user behavior. We study the use of semi-supervised as well as supervised approaches for anomaly detection. In the semi-supervised approach, by leveraging only a set of authenticated anomaly-free data samples, we show the use of one-class classification algorithms as well as autoencoder deep neural networks for anomaly detection. In the supervised anomaly detection task, we present a so-called heuristic-aware data labeling strategy for creating labeled data samples. We carry out binary classification as well as multi-class multi-label classification tasks for not only detecting the anomalous samples but also identifying the underlying anomaly behavior(s) associated with each one. Finally, using a systematic feature importance study we provide insights into the underlying set of features that characterize different streaming fraud categories. To the best of our knowledge, this is the first paper to use machine learning methods for fraud and abuse detection in real-world scale streaming services.
Anatomy Studio II: A Cross-Reality Application for Teaching Anatomy
Venue: arXiv cs.HC 2022
Year: 2022

Virtual Reality has become an important educational tool, due to the pandemic and increasing globalization of education. This paper presents a framework for teaching Virtual Anatomy at the university level. Virtual classes have become a staple of today's curricula because of the isolation and quarantine requirements and the increased international collaboration. Our work builds on the Visible Human Projects for Virtual Dissection material and provides a medium for groups of students to do collaborative anatomical dissections in real-time using sketching and 3D visualizations and audio coupled with interactive 2D tablets for precise drawing. We describe the system architecture, compare requirements with those of previous development, and discuss the preliminary results. Discussions with Anatomists show that this is an effective tool. We introduce avenues for further research and discuss collaboration challenges posed by this context.
Fault-Tolerant Backup Clustering Algorithm for Smart Connected Underwater Sensor Networks
Venue: arXiv cs.NI 2022
Year: 2022

This paper addresses poor cluster formation and frequent Cluster Head (CH) failure issues of underwater sensor networks by proposing an energy-efficient hierarchical topology-aware clustering routing (EEHTAC) protocol. In this paper, fault-tolerant backup clustering (FTBC) algorithms and multi-parameter cluster formation (MPCF) model were developed for the EEHTAC operation. The MPCF model tackles the issue of poor cluster formation performance by integrating multiple parameters to achieve effective clustering process. The FTBC algorithms tackle the issue of frequent CH failures to avoid interruption in data transmission. Performance of the MPCF model was evaluated using normal, high-fault, and high routing overhead network scenarios. Performance metrics employed for this analysis are temporal topology variation ratio (TTVR), CH load distribution (CLD), and cluster stability (STB). Obtained results show that operating with a CH retention period of 90s achieves better CH duty cycling per round and improves the MPCF process with values of 25.69%, 55.56%, and 60% for TTVR, CLD, and STB respectively. Performance of the FTBC-based EEHTAC was evaluated relative to Energy-balanced Unequal Layering Clustering (EULC) protocol. Performance indicators adopted for this evaluation are routing overhead (Ω), end to end delay (Δ), CH failures recovered (CFR), CH failures detected (CFD), received packets (θ), and energy consumption (Σ). With reference to the best obtained values, EEHTAC demonstrated performance improvement of 58.40%, 29.94%, 81.33%, 28.02%, 86.65%, and 54.35% over EULC variants in terms of Ω, Δ, CFR, CFD, θ, and Σ respectively. Obtained results displayed that the MPCF model is efficient for cluster formation performance and the FTBC-based EEHTAC protocol can perform effectively well against an existing CBR protocol.