OpenRaiser/Intern-Atlas huggingface dataset:
SF-PATE: Scalable, Fair, and Private Aggregation of Teacher Ensembles
Venue: arXiv cs.LG 2022
Year: 2022

A critical concern in data-driven processes is to build models whose outcomes do not discriminate against some demographic groups, including gender, ethnicity, or age. To ensure non-discrimination in learning tasks, knowledge of the group attributes is essential. However, in practice, these attributes may not be available due to legal and ethical requirements. To address this challenge, this paper studies a model that protects the privacy of the individuals' sensitive information while also allowing it to learn non-discriminatory predictors. A key characteristic of the proposed model is to enable the adoption of off-the-selves and non-private fair models to create a privacy-preserving and fair model. The paper analyzes the relation between accuracy, privacy, and fairness, and the experimental evaluation illustrates the benefits of the proposed models on several prediction tasks. In particular, this proposal is the first to allow both scalable and accurate training of private and fair models for very large neural networks.
An Optimal Experimental Design Approach for Light Configurations in Photometric Stereo
Venue: arXiv cs.CV 2022
Year: 2022

This paper presents a technique for finding the surface normal of an object from a set of images obtained under different lighting positions. The method presented is based on the principles of Photometric Stereo (PS) combined with Optimum Experimental Design (OED) and Parameter Estimation (PE). Unclear by the approach of photometric stereo, and many models based thereon, is how to position the light sources. So far, this is done by using heuristic approaches this leads to suboptimal and non-data driven positioning of the light sources. But what if the optimal positions of the light sources are calculated for photometric stereo? To this end, in this contribution, the effect of positioning the light sources on the quality of the normal vector for PS is evaluated. Furthermore, a new approach in this direction is derived and formulated. For the calculation of the surface normal of a Lambertian surface, the approach based on calibrated photometric stereo; for the estimation the optimal position of the light sources the approach is premised on parameter estimation and optimum experimental design. The approach is tested using synthetic and real-data. Based on results it can be seen that the surface normal estimated with the new method is more detailed than with conventional methods.
CFA: Constraint-based Finetuning Approach for Generalized Few-Shot Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

Few-shot object detection (FSOD) seeks to detect novel categories with limited data by leveraging prior knowledge from abundant base data. Generalized few-shot object detection (G-FSOD) aims to tackle FSOD without forgetting previously seen base classes and, thus, accounts for a more realistic scenario, where both classes are encountered during test time. While current FSOD methods suffer from catastrophic forgetting, G-FSOD addresses this limitation yet exhibits a performance drop on novel tasks compared to the state-of-the-art FSOD. In this work, we propose a constraint-based finetuning approach (CFA) to alleviate catastrophic forgetting, while achieving competitive results on the novel task without increasing the model capacity. CFA adapts a continual learning method, namely Average Gradient Episodic Memory (A-GEM) to G-FSOD. Specifically, more constraints on the gradient search strategy are imposed from which a new gradient update rule is derived, allowing for better knowledge exchange between base and novel classes. To evaluate our method, we conduct extensive experiments on MS-COCO and PASCAL-VOC datasets. Our method outperforms current FSOD and G-FSOD approaches on the novel task with minor degeneration on the base task. Moreover, CFA is orthogonal to FSOD approaches and operates as a plug-and-play module without increasing the model capacity or inference time.
MIME: Adapting a Single Neural Network for Multi-task Inference with Memory-efficient Dynamic Pruning
Venue: arXiv cs.LG 2022
Year: 2022

Recent years have seen a paradigm shift towards multi-task learning. This calls for memory and energy-efficient solutions for inference in a multi-task scenario. We propose an algorithm-hardware co-design approach called MIME. MIME reuses the weight parameters of a trained parent task and learns task-specific threshold parameters for inference on multiple child tasks. We find that MIME results in highly memory-efficient DRAM storage of neural-network parameters for multiple tasks compared to conventional multi-task inference. In addition, MIME results in input-dependent dynamic neuronal pruning, thereby enabling energy-efficient inference with higher throughput on a systolic-array hardware. Our experiments with benchmark datasets (child tasks)- CIFAR10, CIFAR100, and Fashion-MNIST, show that MIME achieves ~3.48x memory-efficiency and ~2.4-3.1x energy-savings compared to conventional multi-task inference in Pipelined task mode.
Full-Spectrum Out-of-Distribution Detection
Venue: arXiv cs.CV 2022
Year: 2022

Existing out-of-distribution (OOD) detection literature clearly defines semantic shift as a sign of OOD but does not have a consensus over covariate shift. Samples experiencing covariate shift but not semantic shift are either excluded from the test set or treated as OOD, which contradicts the primary goal in machine learning -- being able to generalize beyond the training distribution. In this paper, we take into account both shift types and introduce full-spectrum OOD (FS-OOD) detection, a more realistic problem setting that considers both detecting semantic shift and being tolerant to covariate shift; and designs three benchmarks. These new benchmarks have a more fine-grained categorization of distributions (i.e., training ID, covariate-shifted ID, near-OOD, and far-OOD) for the purpose of more comprehensively evaluating the pros and cons of algorithms. To address the FS-OOD detection problem, we propose SEM, a simple feature-based semantics score function. SEM is mainly composed of two probability measures: one is based on high-level features containing both semantic and non-semantic information, while the other is based on low-level feature statistics only capturing non-semantic image styles. With a simple combination, the non-semantic part is cancelled out, which leaves only semantic information in SEM that can better handle FS-OOD detection. Extensive experiments on the three new benchmarks show that SEM significantly outperforms current state-of-the-art methods. Our code and benchmarks are released in https://github.com/Jingkang50/OpenOOD.
On the Generalization of BasicVSR++ to Video Deblurring and Denoising
Venue: arXiv cs.CV 2022
Year: 2022

The exploitation of long-term information has been a long-standing problem in video restoration. The recent BasicVSR and BasicVSR++ have shown remarkable performance in video super-resolution through long-term propagation and effective alignment. Their success has led to a question of whether they can be transferred to different video restoration tasks. In this work, we extend BasicVSR++ to a generic framework for video restoration tasks. In tasks where inputs and outputs possess identical spatial size, the input resolution is reduced by strided convolutions to maintain efficiency. With only minimal changes from BasicVSR++, the proposed framework achieves compelling performance with great efficiency in various video restoration tasks including video deblurring and denoising. Notably, BasicVSR++ achieves comparable performance to Transformer-based approaches with up to 79% of parameter reduction and 44x speedup. The promising results demonstrate the importance of propagation and alignment in video restoration tasks beyond just video super-resolution. Code and models are available at https://github.com/ckkelvinchan/BasicVSR_PlusPlus.
Deep Reinforcement Learning Based Semi-Autonomous Control for Robotic Surgery
Venue: arXiv cs.RO 2022
Year: 2022

In recent decades, the tremendous benefits surgical robots have brought to surgeons and patients have been witnessed. With the dexterous operation and the great precision, surgical robots can offer patients less recovery time and less hospital stay. However, the controls for current surgical robots in practical usage are fully carried out by surgeons via teleoperation. During the surgery process, there exists a lot of repetitive but simple manipulation, which can cause unnecessary fatigue to the surgeons. In this paper, we proposed a deep reinforcement learning-based semi-autonomous control framework for robotic surgery. The user study showed that the framework can reduce the completion time by 19.1% and the travel length by 58.7%.
GPU Parallel algorithm for the generation of polygonal meshes based on terminal-edge regions
Venue: arXiv cs.DC 2022
Year: 2022

This paper presents a GPU parallel algorithm to generate a new kind of polygonal meshes obtained from Delaunay triangulations. To generate the polygonal mesh, the algorithm first uses a classification system to label each edge of an input triangulation; second it builds polygons (simple or not) from terminal-edge regions using the label system, and third it transforms each non-simple polygon from the previous phase into simple ones, convex or not convex polygons. We show some preliminary experiments to test the scalability of the algorithm and compare it with the sequential version. We also run a very simple test to show that these meshes can be useful for the virtual element method.
A Web-Scale Analysis of the Community Origins of Image Memes
Venue: arXiv cs.HC 2022
Year: 2022

Where do the most popular online cultural artifacts such as image memes originate? Media narratives suggest that cultural innovations often originate in peripheral communities and then diffuse to the mainstream core; behavioral science suggests that intermediate network positions that bridge between the periphery and the core are especially likely to originate many influential cultural innovations. Research has yet to fully adjudicate between these predictions because prior work focuses on individual platforms such as Twitter; however, any single platform is only a small, incomplete part of the larger online cultural ecosystem. In this paper, we perform the first analysis of the origins and diffusion of image memes at web scale, via a one-month crawl of all indexible online communities that principally share meme images with English text overlays. Our results suggest that communities at the core of the network originate the most highly diffused image memes: the top 10% of communities by network centrality originate the memes that generate 62% of the image meme diffusion events on the web. A zero-inflated negative binomial regression confirms that memes from core communities are more likely to diffuse than those from peripheral communities even when controlling for community size and activity level. However, a replication analysis that follows the traditional approach of testing the same question only within a single large community, Reddit, finds the regression coefficients reversed -- underscoring the importance of engaging in web-scale, cross-community analyses. The ecosystem-level viewpoint of this work positions the web as a highly centralized generator of cultural artifacts such as image memes.
Make The Most of Prior Data: A Solution for Interactive Text Summarization with Preference Feedback
Venue: arXiv cs.AI 2022
Year: 2022

For summarization, human preference is critical to tame outputs of the summarizer in favor of human interests, as ground-truth summaries are scarce and ambiguous. Practical settings require dynamic exchanges between human and AI agent wherein feedback is provided in an online manner, a few at a time. In this paper, we introduce a new framework to train summarization models with preference feedback interactively. By properly leveraging offline data and a novel reward model, we improve the performance regarding ROUGE scores and sample-efficiency. Our experiments on three various datasets confirm the benefit of the proposed framework in active, few-shot and online settings of preference learning.
A Reinforcement Learning Approach for Electric Vehicle Routing Problem with Vehicle-to-Grid Supply
Venue: arXiv cs.AI 2022
Year: 2022

The use of electric vehicles (EV) in the last mile is appealing from both sustainability and operational cost perspectives. In addition to the inherent cost efficiency of EVs, selling energy back to the grid during peak grid demand, is a potential source of additional revenue to a fleet operator. To achieve this, EVs have to be at specific locations (discharge points) during specific points in time (peak period), even while meeting their core purpose of delivering goods to customers. In this work, we consider the problem of EV routing with constraints on loading capacity; time window; vehicle-to-grid energy supply (CEVRPTW-D); which not only satisfy multiple system objectives, but also scale efficiently to large problem sizes involving hundreds of customers and discharge stations. We present QuikRouteFinder that uses reinforcement learning (RL) for EV routing to overcome these challenges. Using Solomon datasets, results from RL are compared against exact formulations based on mixed-integer linear program (MILP) and genetic algorithm (GA) metaheuristics. On an average, the results show that RL is 24 times faster than MILP and GA, while being close in quality (within 20%) to the optimal.
Galactic Token Sliding
Venue: arXiv cs.CC 2022
Year: 2022

Given a graph $G$ and two independent sets $I_s$ and $I_t$ of size $k$, the independent set reconfiguration problem asks whether there exists a sequence of $k$-sized independent sets $I_s = I_0, I_1, I_2, \ldots, I_\ell = I_t$ such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of $k$ tokens placed on the vertices of a graph $G$, the two most studied reconfiguration steps are token jumping and token sliding. In the token jumping variant of the problem, a single step allows a token to jump from one vertex to any other vertex in the graph. In the token sliding variant, a token is only allowed to slide from a vertex to one of its neighbors. Like the independent set problem, both of the aforementioned problems are known to be W[1]-hard on general graphs. A very fruitful line of research has showed that the independent set problem becomes fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, nowhere-dense, and all the way to biclique-free graphs. Over a series of papers, the same was shown to hold for the token jumping problem. As for the token sliding problem, which is mentioned in most of these papers, almost nothing is known beyond the fact that the problem is polynomial-time solvable on trees and interval graphs. We remedy this situation by introducing a new model for the reconfiguration of independent sets, which we call galactic reconfiguration. Using this new model, we show that (standard) token sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. We believe that the galactic reconfiguration model is of independent interest and could potentially help in resolving the remaining open questions concerning the (parameterized) complexity of token sliding.
Towards Open-Set Object Detection and Discovery
Venue: arXiv cs.CV 2022
Year: 2022

With the human pursuit of knowledge, open-set object detection (OSOD) has been designed to identify unknown objects in a dynamic world. However, an issue with the current setting is that all the predicted unknown objects share the same category as "unknown", which require incremental learning via a human-in-the-loop approach to label novel classes. In order to address this problem, we present a new task, namely Open-Set Object Detection and Discovery (OSODD). This new task aims to extend the ability of open-set object detectors to further discover the categories of unknown objects based on their visual appearance without human effort. We propose a two-stage method that first uses an open-set object detector to predict both known and unknown objects. Then, we study the representation of predicted objects in an unsupervised manner and discover new categories from the set of unknown objects. With this method, a detector is able to detect objects belonging to known classes and define novel categories for objects of unknown classes with minimal supervision. We show the performance of our model on the MS-COCO dataset under a thorough evaluation protocol. We hope that our work will promote further research towards a more robust real-world detection system.
Linearly ordered colourings of hypergraphs
Venue: arXiv cs.CC 2022
Year: 2022

A linearly ordered (LO) $k$-colouring of an $r$-uniform hypergraph assigns an integer from $\{1, \ldots, k \}$ to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, for $r=3$, if two vertices in an edge are assigned the same colour, then the third vertex is assigned a larger colour (as opposed to a different colour, as in classic non-monochromatic colouring). Barto, Battistelli, and Berg [STACS'21] studied LO colourings on $3$-uniform hypergraphs in the context of promise constraint satisfaction problems (PCSPs). We show two results. First, given a 3-uniform hypergraph that admits an LO $2$-colouring, one can find in polynomial time an LO $k$-colouring with $k=O(\sqrt[3]{n \log \log n / \log n})$. Second, given an $r$-uniform hypergraph that admits an LO $2$-colouring, we establish NP-hardness of finding an LO $k$-colouring for every constant uniformity $r\geq k+2$. In fact, we determine relationships between polymorphism minions for all uniformities $r\geq 3$, which reveals a key difference between $r<k+2$ and $r\geq k+2$ and which may be of independent interest. Using the algebraic approach to PCSPs, we actually show a more general result establishing NP-hardness of finding an LO $k$-colouring for LO $\ell$-colourable $r$-uniform hypergraphs for $2 \leq \ell \leq k$ and $r \geq k - \ell + 4$.
Idiomify -- Building a Collocation-supplemented Reverse Dictionary of English Idioms with Word2Vec for non-native learners
Venue: arXiv cs.CL 2022
Year: 2022

The aim of idiomify is to build a collocation-supplemented reverse dictionary of idioms for the non-native learners of English. We aim to do so because the reverse dictionary could help the non-natives explore idioms on demand, and the collocations could also guide them on using idioms more adequately. The cornerstone of the project is a reliable way of mining idioms from corpora, which is however a challenge because idioms extensively vary in forms. We tackle this by automatically deriving matching rules from their base forms. We use Point-wise Mutual Inclusion (PMI), Term Frequency - Inverse Document Frequency (TF-IDF) to model collocations, since both of them are popular metric for pairwise significance. We also try Term Frequency (TF) as the baseline model. As for implementing the reverse-dictionary, three approaches could be taken: inverted index, graphs and distributional semantics. We choose to take the last approach and implement the reverse dictionary with Word2Vec, because it is the most flexible approach of all and Word2Vec is a simple yet strong baseline. Evaluating the methods has revealed rooms for improvement. We learn that we can better identify idioms with the help of slop, wildcard and reordering techniques. We also learn that we can get the best of both PMI and TF-IDF if we use machine learning to find the sweet spot. Lastly, We learn that Idiomify could be further improved with a mixture of inverted index and distributional semantics approach. The limits aside, the proposed methods are feasible, and their benefits to the non-natives are apparent, which therefore can be used to aid the non-natives in acquiring English idioms.
Positive Feature Values Prioritized Hierarchical Redundancy Eliminated Tree Augmented Naive Bayes Classifier for Hierarchical Feature Spaces
Venue: arXiv cs.LG 2022
Year: 2022

The Hierarchical Redundancy Eliminated Tree Augmented Naive Bayes (HRE-TAN) classifier is a semi-naive Bayesian model that learns a type of hierarchical redundancy-free tree-like feature representation to estimate the data distribution. In this work, we propose two new types of positive feature values prioritized hierarchical redundancy eliminated tree augmented naive Bayes classifiers that focus on features bearing positive instance values. The two newly proposed methods are applied to 28 real-world bioinformatics datasets showing better predictive performance than the conventional HRE-TAN classifier.
The consensus problem for opinion dynamics with local average random interactions
Venue: arXiv cs.SI 2022
Year: 2022

We study the consensus formation for an agents based model, generalizing that originally proposed by Krause \cite{Kr}, by allowing the communication channels between any couple of agents to be switched on or off randomly, at each time step, with a probability law depending on the proximity of the agents' opinions. Namely, we consider a system of agents sharing their opinions according to the following updating protocol. At time $t+1$ the opinion $X_{i}\left( t+1\right) \in\left[ 0,1\right] $ of agent $i$ is updated at the weighted average of the opinions of the agents communicating with it at time $t.$ The weights model the confidence level an agent assign to the opinions of the other agents and are kept fixed by the system dynamics, but the set of agents communicating with any agent $i$ at time $t+1$ is randomly updated in such a way that the agent $j$ can be chosen to belong to this set independently of the other agents with a probability that is a non increasing function of $\left\vert X_{i}\left( t\right) -X_{j}\left( t\right) \right\vert .$ This condition models the fact that a communication among the agents is more likely to happen if their opinions are close. We prove that the system reaches consensus, i.e. as the time tends to infinity the agents' opinions will reach the same value exponentially fast.
Unsupervised Anomaly and Change Detection with Multivariate Gaussianization
Venue: arXiv cs.LG 2022
Year: 2022

Anomaly detection is a field of intense research. Identifying low probability events in data/images is a challenging problem given the high-dimensionality of the data, especially when no (or little) information about the anomaly is available a priori. While plenty of methods are available, the vast majority of them do not scale well to large datasets and require the choice of some (very often critical) hyperparameters. Therefore, unsupervised and computationally efficient detection methods become strictly necessary. We propose an unsupervised method for detecting anomalies and changes in remote sensing images by means of a multivariate Gaussianization methodology that allows to estimate multivariate densities accurately, a long-standing problem in statistics and machine learning. The methodology transforms arbitrarily complex multivariate data into a multivariate Gaussian distribution. Since the transformation is differentiable, by applying the change of variables formula one can estimate the probability at any point of the original domain. The assumption is straightforward: pixels with low estimated probability are considered anomalies. Our method can describe any multivariate distribution, makes an efficient use of memory and computational resources, and is parameter-free. We show the efficiency of the method in experiments involving both anomaly detection and change detection in different remote sensing image sets. Results show that our approach outperforms other linear and nonlinear methods in terms of detection power in both anomaly and change detection scenarios, showing robustness and scalability to dimensionality and sample sizes.