OpenRaiser/Intern-Atlas huggingface dataset:
A PTAS for Packing Hypercubes into a Knapsack
Venue: arXiv cs.DS 2022
Year: 2022

We study the d-dimensional hypercube knapsack problem where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hypercube. The goal is to find an axis-aligned non-overlapping packing of a subset of hypercubes such that the profit of the packed hypercubes is maximized. For this problem, Harren (ICALP'06) gave an algorithm with an approximation ratio of (1+1/2^d+epsilon). For d=2, Jansen and Solis-Oba (IPCO'08) showed that the problem admits a polynomial-time approximation scheme (PTAS); Heydrich and Wiese (SODA'17) further improved the running time and gave an efficient polynomial-time approximation scheme (EPTAS). Both the results use structural properties of 2-D packing, which do not generalize to higher dimensions. For d>2, it remains open to obtain a PTAS, and in fact, there has been no improvement since Harren's result. We settle the problem by providing a PTAS. Our main technical contribution is a structural lemma which shows that any packing of hypercubes can be converted into another structured packing such that a high profitable subset of hypercubes is packed into a constant number of special hypercuboids, called V-Boxes and N-Boxes. As a side result, we give an almost optimal algorithm for a variant of the strip packing problem in higher dimensions. This might have applications for other multidimensional geometric packing problems.
Polynomial Kernels for Tracking Shortest Paths
Venue: arXiv cs.DS 2022
Year: 2022

Given an undirected graph $G=(V,E)$, vertices $s,t\in V$, and an integer $k$, Tracking Shortest Paths requires deciding whether there exists a set of $k$ vertices $T\subseteq V$ such that for any two distinct shortest paths between $s$ and $t$, say $P_1$ and $P_2$, we have $T\cap V(P_1)\neq T\cap V(P_2)$. In this paper, we give the first polynomial size kernel for the problem. Specifically we show the existence of a kernel with $\mathcal{O}(k^2)$ vertices and edges in general graphs and a kernel with $\mathcal{O}(k)$ vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with $\mathcal{O}(k^4)$ vertices and edges for Tracking Shortest Paths in general graphs and a kernel with $\mathcal{O}(k^2)$ vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.
AutoCl : A Visual Interactive System for Automatic Deep Learning Classifier Recommendation Based on Models Performance
Venue: arXiv cs.LG 2022
Year: 2022

Nowadays, deep learning (DL) models being increasingly applied to various fields, people without technical expertise and domain knowledge struggle to find an appropriate model for their task. In this paper, we introduce AutoCl a visual interactive recommender system aimed at helping non-experts to adopt an appropriate DL classifier. Our system enables users to compare the performance and behavior of multiple classifiers trained with various hyperparameter setups as well as automatically recommends a best classifier with appropriate hyperparameter. We compare features of AutoCl against several recent AutoML systems and show that it helps non-experts better in choosing DL classifier. Finally, we demonstrate use cases for image classification using publicly available dataset to show the capability of our system.
Computer Aided Diagnosis and Out-of-Distribution Detection in Glaucoma Screening Using Color Fundus Photography
Venue: arXiv cs.CV 2022
Year: 2022

Artificial Intelligence for RObust Glaucoma Screening (AIROGS) Challenge is held for developing solutions for glaucoma screening from color fundus photography that are robust to real-world scenarios. This report describes our method submitted to the AIROGS challenge. Our method employs convolutional neural networks to classify input images to "referable glaucoma" or "no referable glaucoma". In addition, we introduce an inference-time out-of-distribution (OOD) detection method to identify ungradable images. Our OOD detection is based on an energy-based method combined with activation rectification.
Large Scale Passenger Detection with Smartphone/Bus Implicit Interaction and Multisensory Unsupervised Cause-effect Learning
Venue: arXiv cs.LG 2022
Year: 2022

Intelligent Transportation Systems (ITS) underpin the concept of Mobility as a Service (MaaS), which requires universal and seamless users' access across multiple public and private transportation systems while allowing operators' proportional revenue sharing. Current user sensing technologies such as Walk-in/Walk-out (WIWO) and Check-in/Check-out (CICO) have limited scalability for large-scale deployments. These limitations prevent ITS from supporting analysis, optimization, calculation of revenue sharing, and control of MaaS comfort, safety, and efficiency. We focus on the concept of implicit Be-in/Be-out (BIBO) smartphone-sensing and classification. To close the gap and enhance smartphones towards MaaS, we developed a proprietary smartphone-sensing platform collecting contemporary Bluetooth Low Energy (BLE) signals from BLE devices installed on buses and Global Positioning System (GPS) locations of both buses and smartphones. To enable the training of a model based on GPS features against the BLE pseudo-label, we propose the Cause-Effect Multitask Wasserstein Autoencoder (CEMWA). CEMWA combines and extends several frameworks around Wasserstein autoencoders and neural networks. As a dimensionality reduction tool, CEMWA obtains an auto-validated representation of a latent space describing users' smartphones within the transport system. This representation allows BIBO clustering via DBSCAN. We perform an ablation study of CEMWA's alternative architectures and benchmark against the best available supervised methods. We analyze performance's sensitivity to label quality. Under the naïve assumption of accurate ground truth, XGBoost outperforms CEMWA. Although XGBoost and Random Forest prove to be tolerant to label noise, CEMWA is agnostic to label noise by design and provides the best performance with an 88\% F1 score.
Predicting the impact of treatments over time with uncertainty aware neural differential equations
Venue: arXiv cs.LG 2022
Year: 2022

Predicting the impact of treatments from observational data only still represents a majorchallenge despite recent significant advances in time series modeling. Treatment assignments are usually correlated with the predictors of the response, resulting in a lack of data support for counterfactual predictions and therefore in poor quality estimates. Developments in causal inference have lead to methods addressing this confounding by requiring a minimum level of overlap. However,overlap is difficult to assess and usually notsatisfied in practice. In this work, we propose Counterfactual ODE (CF-ODE), a novel method to predict the impact of treatments continuously over time using Neural Ordinary Differential Equations equipped with uncertainty estimates. This allows to specifically assess which treatment outcomes can be reliably predicted. We demonstrate over several longitudinal data sets that CF-ODE provides more accurate predictions and more reliable uncertainty estimates than previously available methods.
Learning to Merge Tokens in Vision Transformers
Venue: arXiv cs.CV 2022
Year: 2022

Transformers are widely applied to solve natural language understanding and computer vision tasks. While scaling up these architectures leads to improved performance, it often comes at the expense of much higher computational costs. In order for large-scale models to remain practical in real-world systems, there is a need for reducing their computational overhead. In this work, we present the PatchMerger, a simple module that reduces the number of patches or tokens the network has to process by merging them between two consecutive intermediate layers. We show that the PatchMerger achieves a significant speedup across various model sizes while matching the original performance both upstream and downstream after fine-tuning.
Parameterized Complexity of Graph Partitioning into Connected Clusters
Venue: arXiv cs.DS 2022
Year: 2022

Given an undirected graph $G$ and $q$ integers $n_1,n_2,n_3, \cdots, n_q$, balanced connected $q$-partition problem ($BCP_q$) asks whether there exists a partition of the vertex set $V$ of $G$ into $q$ parts $V_1,V_2,V_3,\cdots, V_q$ such that for all $i\in[1,q]$, $|V_i|=n_i$ and the graph induced on $V_i$ is connected. A related problem denoted as the balanced connected $q$-edge partition problem ($BCEP_q$) is defined as follows. Given an undirected graph $G$ and $q$ integers $n_1,n_2,n_3, \cdots, n_q$, $BCEP_q$ asks whether there exists a partition of the edge set of $G$ into $q$ parts $E_1,E_2,E_3,\cdots, E_q$ such that for all $i\in[1,q]$, $|E_i|=n_i$ and the graph induced on the edge set $E_i$ is connected. Here we study both the problems for $q=2$ and prove that $BCP_q$ for $q\geq 2$ is $W[1]$-hard. We also show that $BCP_2$ is unlikely to have a polynomial kernel on the class of planar graphs. Coming to the positive results, we show that $BCP_2$ is fixed parameter tractable (FPT) parameterized by treewidth of the graph, which generalizes to FPT algorithm for planar graphs. We design another FPT algorithm and a polynomial kernel on the class of unit disk graphs parameterized by $\min(n_1,n_2)$. Finally, we prove that unlike $BCP_2$, $BCEP_2$ is FPT parameterized by $\min(n_1,n_2)$.
When is Software a Medical Device? Understanding and Determining the 'Intention' and Requirements for Software as a Medical device in EU law
Venue: arXiv cs.CY 2022
Year: 2022

The role of software in society has changed drastically since the start of the 21st century. Software can now partially or fully facilitate anything from diagnosis to treatment of a disease, regardless of whether it is psychological or pathological, with the consequence of software being comparable to any other type of medical equipment, and this makes discovering when software must comply with such rules vital to both manufacturers and regulators. In lieu of the Medical Device Regulation we expand on the idea of intention, and identify the criteria software must fulfil to be considered medical devices within EU-law.
DeepFusionMOT: A 3D Multi-Object Tracking Framework Based on Camera-LiDAR Fusion with Deep Association
Venue: arXiv cs.CV 2022
Year: 2022

In the recent literature, on the one hand, many 3D multi-object tracking (MOT) works have focused on tracking accuracy and neglected computation speed, commonly by designing rather complex cost functions and feature extractors. On the other hand, some methods have focused too much on computation speed at the expense of tracking accuracy. In view of these issues, this paper proposes a robust and fast camera-LiDAR fusion-based MOT method that achieves a good trade-off between accuracy and speed. Relying on the characteristics of camera and LiDAR sensors, an effective deep association mechanism is designed and embedded in the proposed MOT method. This association mechanism realizes tracking of an object in a 2D domain when the object is far away and only detected by the camera, and updating of the 2D trajectory with 3D information obtained when the object appears in the LiDAR field of view to achieve a smooth fusion of 2D and 3D trajectories. Extensive experiments based on the typical datasets indicate that our proposed method presents obvious advantages over the state-of-the-art MOT methods in terms of both tracking accuracy and processing speed. Our code is made publicly available for the benefit of the community.
SonOpt: Sonifying Bi-objective Population-Based Optimization Algorithms
Venue: arXiv cs.NE 2022
Year: 2022

We propose SonOpt, the first (open source) data sonification application for monitoring the progress of bi-objective population-based optimization algorithms during search, to facilitate algorithm understanding. SonOpt provides insights into convergence/stagnation of search, the evolution of the approximation set shape, location of recurring points in the approximation set, and population diversity. The benefits of data sonification have been shown for various non-optimization related monitoring tasks. However, very few attempts have been made in the context of optimization and their focus has been exclusively on single-objective problems. In comparison, SonOpt is designed for bi-objective optimization problems, relies on objective function values of non-dominated solutions only, and is designed with the user (listener) in mind; avoiding convolution of multiple sounds and prioritising ease of familiarizing with the system. This is achieved using two sonification paths relying on the concepts of wavetable and additive synthesis. This paper motivates and describes the architecture of SonOpt, and then validates SonOpt for two popular multi-objective optimization algorithms (NSGA-II and MOEA/D). Experience SonOpt yourself via https://github.com/tasos-a/SonOpt-1.0 .
Towards a Heterogeneous Smart Electromagnetic Environment for Millimeter-Wave Communications: An Industrial Viewpoint
Venue: arXiv cs.NI 2022
Year: 2022

Fifth generation (5G) and beyond communication systems open the door to millimeter Wave (mmWave) frequency bands to leverage the extremely large operating bandwidths and deliver unprecedented network capacity. These frequency bands are affected by high propagation losses that severely limit the achievable coverage. The simplest way to address this problem would be to increase the number of installed mmWave base stations (BSs), at the same time augmenting the overall network cost, power consumption and ElectroMagnetic Field (EMF) levels. As alternative direction, here we propose to complement the macro-layer of mmWave BSs with a heterogeneous deployment of Smart Electromagnetic (Smart EM) Entities - namely IAB nodes, Smart Repeaters, Reconfigurable Intelligent Surfaces (RISs) and passive surfaces - that is judiciously planned to minimize the total installation costs while at the same time optimizing the network spectral efficiency. Initial network planning results underline the effectiveness of the proposed approach. The available technologies and the key research directions for achieving this view are thoroughly discussed by accounting for issues ranging from system-level design to the development of new materials.
Situational Graphs for Robot Navigation in Structured Indoor Environments
Venue: arXiv cs.RO 2022
Year: 2022

Mobile robots should be aware of their situation, comprising the deep understanding of their surrounding environment along with the estimation of its own state, to successfully make intelligent decisions and execute tasks autonomously in real environments. 3D scene graphs are an emerging field of research that propose to represent the environment in a joint model comprising geometric, semantic and relational/topological dimensions. Although 3D scene graphs have already been combined with SLAM techniques to provide robots with situational understanding, further research is still required to effectively deploy them on-board mobile robots. To this end, we present in this paper a novel, real-time, online built Situational Graph (S-Graph), which combines in a single optimizable graph, the representation of the environment with the aforementioned three dimensions, together with the robot pose. Our method utilizes odometry readings and planar surfaces extracted from 3D LiDAR scans, to construct and optimize in real-time a three layered S-Graph that includes (1) a robot tracking layer where the robot poses are registered, (2) a metric-semantic layer with features such as planar walls and (3) our novel topological layer constraining the planar walls using higher-level features such as corridors and rooms. Our proposal does not only demonstrate state-of-the-art results for pose estimation of the robot, but also contributes with a metric-semantic-topological model of the environment
The Linear Capacity of Single-Server Individually-Private Information Retrieval with Side Information
Venue: arXiv cs.IT 2022
Year: 2022

This paper considers the problem of single-server Individually-Private Information Retrieval with side information (IPIR). In this problem, there is a remote server that stores a dataset of $K$ messages, and there is a user that initially knows $M$ of these messages, and wants to retrieve $D$ other messages belonging to the dataset. The goal of the user is to retrieve the $D$ desired messages by downloading the minimum amount of information from the server while revealing no information about whether an individual message is one of the $D$ desired messages. In this work, we focus on linear IPIR schemes, i.e., the IPIR schemes in which the user downloads only linear combinations of the original messages from the server. We prove a converse bound on the download rate of any linear IPIR scheme for all $K,D,M$, and show the achievability of this bound for all $K,D,M$ satisfying a certain divisibility condition. Our results characterize the linear capacity of IPIR, which is defined as the maximum achievable download rate over all linear IPIR schemes, for a wide range of values of $K,D,M$.
A Method for Waste Segregation using Convolutional Neural Networks
Venue: arXiv cs.CV 2022
Year: 2022

Segregation of garbage is a primary concern in many nations across the world. Even though we are in the modern era, many people still do not know how to distinguish between organic and recyclable waste. It is because of this that the world is facing a major crisis of waste disposal. In this paper, we try to use deep learning algorithms to help solve this problem of waste classification. The waste is classified into two categories like organic and recyclable. Our proposed model achieves an accuracy of 94.9%. Although the other two models also show promising results, the Proposed Model stands out with the greatest accuracy. With the help of deep learning, one of the greatest obstacles to efficient waste management can finally be removed.
On Monocular Depth Estimation and Uncertainty Quantification using Classification Approaches for Regression
Venue: arXiv cs.CV 2022
Year: 2022

Monocular depth is important in many tasks, such as 3D reconstruction and autonomous driving. Deep learning based models achieve state-of-the-art performance in this field. A set of novel approaches for estimating monocular depth consists of transforming the regression task into a classification one. However, there is a lack of detailed descriptions and comparisons for Classification Approaches for Regression (CAR) in the community and no in-depth exploration of their potential for uncertainty estimation. To this end, this paper will introduce a taxonomy and summary of CAR approaches, a new uncertainty estimation solution for CAR, and a set of experiments on depth accuracy and uncertainty quantification for CAR-based models on KITTI dataset. The experiments reflect the differences in the portability of various CAR methods on two backbones. Meanwhile, the newly proposed method for uncertainty estimation can outperform the ensembling method with only one forward propagation.
Fine-Grained Prediction of Political Leaning on Social Media with Unsupervised Deep Learning
Venue: arXiv cs.SI 2022
Year: 2022

Predicting the political leaning of social media users is an increasingly popular task, given its usefulness for electoral forecasts, opinion dynamics models and for studying the political dimension of polarization and disinformation. Here, we propose a novel unsupervised technique for learning fine-grained political leaning from the textual content of social media posts. Our technique leverages a deep neural network for learning latent political ideologies in a representation learning task. Then, users are projected in a low-dimensional ideology space where they are subsequently clustered. The political leaning of a user is automatically derived from the cluster to which the user is assigned. We evaluated our technique in two challenging classification tasks and we compared it to baselines and other state-of-the-art approaches. Our technique obtains the best results among all unsupervised techniques, with micro F1 = 0.426 in the 8-class task and micro F1 = 0.772 in the 3-class task. Other than being interesting on their own, our results also pave the way for the development of new and better unsupervised approaches for the detection of fine-grained political leaning.
TrimBERT: Tailoring BERT for Trade-offs
Venue: arXiv cs.CL 2022
Year: 2022

Models based on BERT have been extremely successful in solving a variety of natural language processing (NLP) tasks. Unfortunately, many of these large models require a great deal of computational resources and/or time for pre-training and fine-tuning which limits wider adoptability. While self-attention layers have been well-studied, a strong justification for inclusion of the intermediate layers which follow them remains missing in the literature. In this work, we show that reducing the number of intermediate layers in BERT-Base results in minimal fine-tuning accuracy loss of downstream tasks while significantly decreasing model size and training time. We further mitigate two key bottlenecks, by replacing all softmax operations in the self-attention layers with a computationally simpler alternative and removing half of all layernorm operations. This further decreases the training time while maintaining a high level of fine-tuning accuracy.
APEACH: Attacking Pejorative Expressions with Analysis on Crowd-Generated Hate Speech Evaluation Datasets
Venue: arXiv cs.CL 2022
Year: 2022

In hate speech detection, developing training and evaluation datasets across various domains is the critical issue. Whereas, major approaches crawl social media texts and hire crowd-workers to annotate the data. Following this convention often restricts the scope of pejorative expressions to a single domain lacking generalization. Sometimes domain overlap between training corpus and evaluation set overestimate the prediction performance when pretraining language models on low-data language. To alleviate these problems in Korean, we propose APEACH that asks unspecified users to generate hate speech examples followed by minimal post-labeling. We find that APEACH can collect useful datasets that are less sensitive to the lexical overlaps between the pretraining corpus and the evaluation set, thereby properly measuring the model performance.