OpenRaiser/Intern-Atlas huggingface dataset:
Visual Similarity Attention
Venue: arXiv cs.CV 2022
Year: 2022

While there has been substantial progress in learning suitable distance metrics, these techniques in general lack transparency and decision reasoning, i.e., explaining why the input set of images is similar or dissimilar. In this work, we solve this key problem by proposing the first method to generate generic visual similarity explanations with gradient-based attention. We demonstrate that our technique is agnostic to the specific similarity model type, e.g., we show applicability to Siamese, triplet, and quadruplet models. Furthermore, we make our proposed similarity attention a principled part of the learning process, resulting in a new paradigm for learning similarity functions. We demonstrate that our learning mechanism results in more generalizable, as well as explainable, similarity models. Finally, we demonstrate the generality of our framework by means of experiments on a variety of tasks, including image retrieval, person re-identification, and low-shot semantic segmentation.
Large Scale Open-Set Deep Logo Detection
Venue: arXiv cs.CV 2022
Year: 2022

We present an open-set logo detection (OSLD) system, which can detect (localize and recognize) any number of unseen logo classes without re-training; it only requires a small set of canonical logo images for each logo class. We achieve this using a two-stage approach: (1) Generic logo detection to detect candidate logo regions in an image. (2) Logo matching for matching the detected logo regions to a set of canonical logo images to recognize them. We constructed an open-set logo detection dataset with 12.1k logo classes and released it for research purposes.We demonstrate the effectiveness of OSLD on our dataset and on the standard Flickr-32 logo dataset, outperforming the state-of-the-art open-set and closed-set logo detection methods by a large margin. OSLD is scalable to millions of logo classes.
Geometric Planar Networks on Bichromatic Points
Venue: arXiv cs.CG 2022
Year: 2022

We study three classical graph problems - Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting.
Quantum Weakest Preconditions for Reasoning about Expected Runtimes of Quantum Programs (Extended Version)
Venue: arXiv cs.PL 2022
Year: 2022

We study expected runtimes for quantum programs. Inspired by recent work on probabilistic programs, we first define expected runtime as a generalisation of quantum weakest precondition. Then, we show that the expected runtime of a quantum program can be represented as the expectation of an observable (in physics). A method for computing the expected runtimes of quantum programs in finite-dimensional state spaces is developed. Several examples are provided as applications of this method, including computing the expected runtime of quantum Bernoulli Factory -- a quantum algorithm for generating random numbers. In particular, using our new method, an open problem of computing the expected runtime of quantum random walks introduced by Ambainis et al. (STOC 2001) is solved.
Fundamental Structure of Optimal Cache Placement for Coded Caching with Nonuniform Demands
Venue: arXiv cs.IT 2022
Year: 2022

This paper studies the caching system of multiple cache-enabled users with random demands. Under nonuniform file popularity, we thoroughly characterize the optimal uncoded cache placement structure for the coded caching scheme (CCS). Formulating the cache placement as an optimization problem to minimize the average delivery rate, we identify the file group structure in the optimal solution. We show that, regardless of the file popularity distribution, there are \emph{at most three file groups} in the optimal cache placement{, where files within a group have the same cache placement}. We further characterize the complete structure of the optimal cache placement and obtain the closed-form solution in each of the three file group structures. A simple algorithm is developed to obtain the final optimal cache placement by comparing a set of candidate closed-form solutions computed in parallel. We provide insight into the file groups formed by the optimal cache placement. The optimal placement solution also indicates that coding between file groups may be explored during delivery, in contrast to the existing suboptimal file grouping schemes. Using the file group structure in the optimal cache placement for the CCS, we propose a new information-theoretic converse bound for coded caching that is tighter than the existing best one. Moreover, we characterize the file subpacketization in the CCS with the optimal cache placement solution and show that the maximum subpacketization level in the worst case scales as $\mathcal{O}(2^K/\sqrt{K})$ for $K$ users.
Assessing the Robustness of Visual Question Answering Models
Venue: arXiv cs.CV 2022
Year: 2022

Deep neural networks have been playing an essential role in the task of Visual Question Answering (VQA). Until recently, their accuracy has been the main focus of research. Now there is a trend toward assessing the robustness of these models against adversarial attacks by evaluating the accuracy of these models under increasing levels of noisiness in the inputs of VQA models. In VQA, the attack can target the image and/or the proposed query question, dubbed main question, and yet there is a lack of proper analysis of this aspect of VQA. In this work, we propose a new method that uses semantically related questions, dubbed basic questions, acting as noise to evaluate the robustness of VQA models. We hypothesize that as the similarity of a basic question to the main question decreases, the level of noise increases. To generate a reasonable noise level for a given main question, we rank a pool of basic questions based on their similarity with this main question. We cast this ranking problem as a LASSO optimization problem. We also propose a novel robustness measure Rscore and two large-scale basic question datasets in order to standardize robustness analysis of VQA models. The experimental results demonstrate that the proposed evaluation method is able to effectively analyze the robustness of VQA models. To foster the VQA research, we will publish our proposed datasets.
An Empirical Study on the Intrinsic Privacy of SGD
Venue: arXiv cs.LG 2022
Year: 2022

Introducing noise in the training of machine learning systems is a powerful way to protect individual privacy via differential privacy guarantees, but comes at a cost to utility. This work looks at whether the inherent randomness of stochastic gradient descent (SGD) could contribute to privacy, effectively reducing the amount of \emph{additional} noise required to achieve a given privacy guarantee. We conduct a large-scale empirical study to examine this question. Training a grid of over 120,000 models across four datasets (tabular and images) on convex and non-convex objectives, we demonstrate that the random seed has a larger impact on model weights than any individual training example. We test the distribution over weights induced by the seed, finding that the simple convex case can be modelled with a multivariate Gaussian posterior, while neural networks exhibit multi-modal and non-Gaussian weight distributions. By casting convex SGD as a Gaussian mechanism, we then estimate an `intrinsic' data-dependent $ε_i(\mathcal{D})$, finding values as low as 6.3, dropping to 1.9 using empirical estimates. We use a membership inference attack to estimate $ε$ for non-convex SGD and demonstrate that hiding the random seed from the adversary results in a statistically significant reduction in attack performance, corresponding to a reduction in the effective $ε$. These results provide empirical evidence that SGD exhibits appreciable variability relative to its dataset sensitivity, and this `intrinsic noise' has the potential to be leveraged to improve the utility of privacy-preserving machine learning.
NASA: Neural Articulated Shape Approximation
Venue: arXiv cs.CV 2022
Year: 2022

Efficient representation of articulated objects such as human bodies is an important problem in computer vision and graphics. To efficiently simulate deformation, existing approaches represent 3D objects using polygonal meshes and deform them using skinning techniques. This paper introduces neural articulated shape approximation (NASA), an alternative framework that enables efficient representation of articulated deformable objects using neural indicator functions that are conditioned on pose. Occupancy testing using NASA is straightforward, circumventing the complexity of meshes and the issue of water-tightness. We demonstrate the effectiveness of NASA for 3D tracking applications, and discuss other potential extensions.
Summary and Distance between Sets of Texts based on Topological Data Analysis
Venue: arXiv cs.CL 2022
Year: 2022

In this paper, we use topological data analysis (TDA) tools such as persistent homology, persistent entropy and bottleneck distance, to provide a {\it TDA-based summary} of any given set of texts and a general method for computing a distance between any two literary styles, authors or periods. To this aim, deep-learning word-embedding techniques are combined with these tools in order to study the topological properties of texts embedded in a metric space. As a case of study, we use the written texts of three poets of the Spanish Golden Age: Francisco de Quevedo, Luis de Góngora and Lope de Vega. As far as we know, this is the first time that word embedding, bottleneck distance, persistent homology and persistent entropy are used together to characterize texts and to compare different literary styles.
Analysis of the hands in egocentric vision: A survey
Venue: arXiv cs.CV 2022
Year: 2022

Egocentric vision (a.k.a. first-person vision - FPV) applications have thrived over the past few years, thanks to the availability of affordable wearable cameras and large annotated datasets. The position of the wearable camera (usually mounted on the head) allows recording exactly what the camera wearers have in front of them, in particular hands and manipulated objects. This intrinsic advantage enables the study of the hands from multiple perspectives: localizing hands and their parts within the images; understanding what actions and activities the hands are involved in; and developing human-computer interfaces that rely on hand gestures. In this survey, we review the literature that focuses on the hands using egocentric vision, categorizing the existing approaches into: localization (where are the hands or parts of them?); interpretation (what are the hands doing?); and application (e.g., systems that used egocentric hand cues for solving a specific problem). Moreover, a list of the most prominent datasets with hand-based annotations is provided.
Finding Optimal Triangulations Parameterized by Edge Clique Cover
Venue: arXiv cs.DS 2022
Year: 2022

We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover ($cc$) to such problems. This parameterization occurs naturally in many problems in this setting, e.g., in the perfect phylogeny problem $cc$ is at most the number of taxa, in fractional hypertreewidth $cc$ is at most the number of hyperedges, and in treewidth of Bayesian networks $cc$ is at most the number of non-root nodes. We show that the number of minimal separators of graphs is at most $2^{cc}$, the number of potential maximal cliques is at most $3^{cc}$, and these objects can be listed in times $O^*(2^{cc})$ and $O^*(3^{cc})$, respectively, even when no edge clique cover is given as input; the $O^*(\cdot)$ notation omits factors polynomial in the input size. These enumeration algorithms imply $O^*(3^{cc})$ time algorithms for problems such as treewidth, weighted minimum fill-in, and feedback vertex set. For generalized and fractional hypertreewidth we give $O^*(4^m)$ time and $O^*(3^m)$ time algorithms, respectively, where $m$ is the number of hyperedges. When an edge clique cover of size $cc'$ is given as a part of the input we give $O^*(2^{cc'})$ time algorithms for treewidth, minimum fill-in, and chordal sandwich. This implies an $O^*(2^n)$ time algorithm for perfect phylogeny, where $n$ is the number of taxa. We also give polynomial space algorithms with time complexities $O^*(9^{cc'})$ and $O^*(9^{cc + O(\log^2 cc)})$ for problems in this framework.
An Abstraction Model for Semantic Segmentation Algorithms
Venue: arXiv cs.CV 2022
Year: 2022

Semantic segmentation classifies each pixel in the image. Due to its advantages, semantic segmentation is used in many tasks, such as cancer detection, robot-assisted surgery, satellite image analysis, and self-driving cars. Accuracy and efficiency are the two crucial goals for this purpose, and several state-of-the-art neural networks exist. By employing different techniques, new solutions have been presented in each method to increase efficiency and accuracy and reduce costs. However, the diversity of the implemented approaches for semantic segmentation makes it difficult for researchers to achieve a comprehensive view of the field. In this paper, an abstraction model for semantic segmentation offers a comprehensive view of the field. The proposed framework consists of four general blocks that cover the operation of the majority of semantic segmentation methods. We also compare different approaches and analyze each of the four abstraction blocks' importance in each method's operation.
A General Framework for Saliency Detection Methods
Venue: arXiv cs.CV 2022
Year: 2022

Saliency detection is one of the most challenging problems in image analysis and computer vision. Many approaches propose different architectures based on the psychological and biological properties of the human visual attention system. However, there is still no abstract framework that summarizes the existing methods. In this paper, we offered a general framework for saliency models, which consists of five main steps: pre-processing, feature extraction, saliency map generation, saliency map combination, and post-processing. Also, we study different saliency models containing each level and compare their performance. This framework helps researchers to have a comprehensive view of studying new methods.
Learning Selective Sensor Fusion for States Estimation
Venue: arXiv cs.CV 2022
Year: 2022

Autonomous vehicles and mobile robotic systems are typically equipped with multiple sensors to provide redundancy. By integrating the observations from different sensors, these mobile agents are able to perceive the environment and estimate system states, e.g. locations and orientations. Although deep learning approaches for multimodal odometry estimation and localization have gained traction, they rarely focus on the issue of robust sensor fusion - a necessary consideration to deal with noisy or incomplete sensor observations in the real world. Moreover, current deep odometry models suffer from a lack of interpretability. To this extent, we propose SelectFusion, an end-to-end selective sensor fusion module which can be applied to useful pairs of sensor modalities such as monocular images and inertial measurements, depth images and LIDAR point clouds. Our model is a uniform framework that is not restricted to specific modality or task. During prediction, the network is able to assess the reliability of the latent features from different sensor modalities and estimate trajectory both at scale and global pose. In particular, we propose two fusion modules - a deterministic soft fusion and a stochastic hard fusion, and offer a comprehensive study of the new strategies compared to trivial direct fusion. We extensively evaluate all fusion strategies in both public datasets and on progressively degraded datasets that present synthetic occlusions, noisy and missing data and time misalignment between sensors, and we investigate the effectiveness of the different fusion strategies in attending the most reliable features, which in itself, provides insights into the operation of the various models.
Finally, how many efficiencies supercomputers have? And, what do they measure?
Venue: arXiv cs.PF 2022
Year: 2022

Using an extremely large number of processing elements in computing systems leads to unexpected phenomena, such as different efficiencies of the same system for different tasks, that cannot be explained in the frame of classical computing paradigm. The simple non-technical (but considering the temporal behavior of the components) model, introduced here, enables us to set up a frame and formalism, needed to explain those unexpected experiences around supercomputing. Introducing temporal behavior into computer science also explains why only the extreme scale computing enabled us to reveal the experienced limitations. The paper shows, that degradation of efficiency of parallelized sequential systems is a natural consequence of the classical computing paradigm, instead of being an engineering imperfectness. The workload, that supercomputers run, is much responsible for wasting energy, as well as limiting the size and type of tasks. Case studies provide insight, how different contributions compete for dominating the resulting payload performance of a computing system, and how enhancing the interconnection technology made computing+communication to dominate in defining the efficiency of supercomputers. Our model also enables to derive predictions about supercomputer performance limitations for the near future, as well as it provides hints for enhancing supercomputer components. Phenomena experienced in large-scale computing show interesting parallels with phenomena experienced in science, more than a century ago, and through their studying a modern science was developed.
A Rule-Based Model for Victim Prediction
Venue: arXiv cs.AI 2022
Year: 2022

In this paper, we proposed a novel automated model, called Vulnerability Index for Population at Risk (VIPAR) scores, to identify rare populations for their future shooting victimizations. Likewise, the focused deterrence approach identifies vulnerable individuals and offers certain types of treatments (e.g., outreach services) to prevent violence in communities. The proposed rule-based engine model is the first AI-based model for victim prediction. This paper aims to compare the list of focused deterrence strategy with the VIPAR score list regarding their predictive power for the future shooting victimizations. Drawing on the criminological studies, the model uses age, past criminal history, and peer influence as the main predictors of future violence. Social network analysis is employed to measure the influence of peers on the outcome variable. The model also uses logistic regression analysis to verify the variable selections. Our empirical results show that VIPAR scores predict 25.8% of future shooting victims and 32.2% of future shooting suspects, whereas focused deterrence list predicts 13% of future shooting victims and 9.4% of future shooting suspects. The model outperforms the intelligence list of focused deterrence policies in predicting the future fatal and non-fatal shootings. Furthermore, we discuss the concerns about the presumption of innocence right.
MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
Venue: arXiv cs.LG 2022
Year: 2022

Adversarial training is one of the most popular ways to learn robust models but is usually attack-dependent and time costly. In this paper, we propose the MACER algorithm, which learns robust models without using adversarial training but performs better than all existing provable l2-defenses. Recent work shows that randomized smoothing can be used to provide a certified l2 radius to smoothed classifiers, and our algorithm trains provably robust smoothed classifiers via MAximizing the CErtified Radius (MACER). The attack-free characteristic makes MACER faster to train and easier to optimize. In our experiments, we show that our method can be applied to modern deep neural networks on a wide range of datasets, including Cifar-10, ImageNet, MNIST, and SVHN. For all tasks, MACER spends less training time than state-of-the-art adversarial training algorithms, and the learned models achieve larger average certified radius.
Deep Learning for Free-Hand Sketch: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

Free-hand sketches are highly illustrative, and have been widely used by humans to depict objects or stories from ancient times to the present. The recent prevalence of touchscreen devices has made sketch creation a much easier task than ever and consequently made sketch-oriented applications increasingly popular. The progress of deep learning has immensely benefited free-hand sketch research and applications. This paper presents a comprehensive survey of the deep learning techniques oriented at free-hand sketch data, and the applications that they enable. The main contents of this survey include: (i) A discussion of the intrinsic traits and unique challenges of free-hand sketch, to highlight the essential differences between sketch data and other data modalities, e.g., natural photos. (ii) A review of the developments of free-hand sketch research in the deep learning era, by surveying existing datasets, research topics, and the state-of-the-art methods through a detailed taxonomy and experimental evaluation. (iii) Promotion of future work via a discussion of bottlenecks, open problems, and potential research directions for the community.
Modeling and solving the multimodal car- and ride-sharing problem
Venue: arXiv cs.AI 2022
Year: 2022

We introduce the multimodal car- and ride-sharing problem (MMCRP), in which a pool of cars is used to cover a set of ride requests while uncovered requests are assigned to other modes of transport (MOT). A car's route consists of one or more trips. Each trip must have a specific but non-predetermined driver, start in a depot and finish in a (possibly different) depot. Ride-sharing between users is allowed, even when two rides do not have the same origin and/or destination. A user has always the option of using other modes of transport according to an individual list of preferences. The problem can be formulated as a vehicle scheduling problem. In order to solve the problem, an auxiliary graph is constructed in which each trip starting and ending in a depot, and covering possible ride-shares, is modeled as an arc in a time-space graph. We propose a two-layer decomposition algorithm based on column generation, where the master problem ensures that each request can only be covered at most once, and the pricing problem generates new promising routes by solving a kind of shortest-path problem in a time-space network. Computational experiments based on realistic instances are reported. The benchmark instances are based on demographic, spatial, and economic data of Vienna, Austria. We solve large instances with the column generation based approach to near optimality in reasonable time, and we further investigate various exact and heuristic pricing schemes.