OpenRaiser/Intern-Atlas huggingface dataset:
A Simple Approximation Algorithm for Vector Scheduling and Applications to Stochastic Min-Norm Load Balancing
Venue: arXiv cs.DS 2021
Year: 2021

We consider the Vector Scheduling problem on identical machines: we have m machines, and a set J of n jobs, where each job j has a processing-time vector $p_j\in \mathbb{R}^d_{\geq 0}$. The goal is to find an assignment $σ:J\to [m]$ of jobs to machines so as to minimize the makespan $\max_{i\in [m]}\max_{r\in [d]}( \sum_{j:σ(j)=i}p_{j,r})$. A natural lower bound on the optimal makespan is lb $:=\max\{\max_{j\in J,r\in [d]}p_{j,r},\max_{r\in [d]}(\sum_{j\in J}p_{j,r}/m)\}$. Our main result is a very simple O(log d)-approximation algorithm for vector scheduling with respect to the lower bound lb: we devise an algorithm that returns an assignment whose makespan is at most O(log d)*lb. As an application, we show that the above guarantee leads to an O(log log m)-approximation for Stochastic Minimum-Norm Load Balancing (StochNormLB). In StochNormLB, we have m identical machines, a set J of n independent stochastic jobs whose processing times are nonnegative random variables, and a monotone, symmetric norm $f:\mathbb{R}^m \to \mathbb{R}_{\geq 0}$. The goal is to find an assignment $σ:J\to [m]$ that minimizes the expected $f$-norm of the induced machine-load vector, where the load on machine i is the (random) total processing time assigned to it. Our O(log log m)-approximation guarantee is in fact much stronger: we obtain an assignment that is simultaneously an O(log log m)-approximation for StochNormLB with all monotone, symmetric norms. Next, this approximation factor significantly improves upon the O(log m/log log m)-approximation in (Ibrahimpur and Swamy, FOCS 2020) for StochNormLB, and is a consequence of a more-general black-box reduction that we present, showing that a $γ(d)$-approximation for d-dimensional vector scheduling with respect to the lower bound lb yields a simultaneous $γ(\log m)$-approximation for StochNormLB with all monotone, symmetric norms.
FAIR Geovisualizations: Definitions, Challenges, and the Road Ahead
Venue: arXiv cs.IR 2021
Year: 2021

The availability of open data and of tools to create visualizations on top of these open datasets have led to an ever-growing amount of geovisualizations on the Web. There is thus an increasing need for techniques to make geovisualizations FAIR - Findable, Accessible, Interoperable, and Reusable. This article explores what it would mean for a geovisualization to be FAIR, presents relevant approaches to FAIR geovisualizations and lists open research questions on the road towards FAIR geovisualizations. The discussion is done using three complementary perspectives: the computer, which stores geovisualizations digitally; the analyst, who uses them for sensemaking; and the developer, who creates them. The framework for FAIR geovisualizations proposed, and the open questions identified are relevant to researchers working on findable, accessible, interoperable, and reusable online visualizations of geographic information.
A Note on the Pure Nash Equilibria for Evolutionary Games on Networks
Venue: arXiv cs.GT 2021
Year: 2021

Recently, a new model extending the standard replicator equation to a finite set of players connected on an arbitrary graph was developed in evolutionary game dynamics. The players are interpreted as subpopulations of multipopulations dynamical game and represented as vertices of the graph, and an edge constitutes the relation among the subpopulations. At each instant, members of connected vertices of the graph play a 2-player game and collect a payoff that determines if the chosen strategies will vanish or flourish. The model describes the game dynamics of a finite set of players connected by a graph emulating the replicator dynamics. It was proved a relation between the stability of the mixed equilibrium with the topology of the network. More specifically, the eigenvalues of the Jacobian matrix of the system evaluated at the mixed steady state are the eigenvalues of the graph's adjacency matrix multiplied by a scalar. This paper studies the pure (strict) Nash equilibria of these games and how it connects to the network. We present necessary and sufficient conditions for a pure steady-state in coordination or anti-coordination game to be a (strict) Nash Equilibrium.
Unsupervised Action Localization Crop in Video Retargeting for 3D ConvNets
Venue: arXiv cs.CV 2021
Year: 2021

Untrimmed videos on social media or those captured by robots and surveillance cameras are of varied aspect ratios. However, 3D CNNs usually require as input a square-shaped video, whose spatial dimension is smaller than the original. Random- or center-cropping may leave out the video's subject altogether. To address this, we propose an unsupervised video cropping approach by shaping this as a retargeting and video-to-video synthesis problem. The synthesized video maintains a 1:1 aspect ratio, is smaller in size and is targeted at video-subject(s) throughout the entire duration. First, action localization is performed on each frame by identifying patches with homogeneous motion patterns. Thus, a single salient patch is pinpointed per frame. But to avoid viewpoint jitters and flickering, any inter-frame scale or position changes among the patches should be performed gradually over time. This issue is addressed with a polyBezier fitting in 3D space that passes through some chosen pivot timestamps and whose shape is influenced by the in-between control timestamps. To corroborate the effectiveness of the proposed method, we evaluate the video classification task by comparing our dynamic cropping technique with random cropping on three benchmark datasets, viz. UCF-101, HMDB-51 and ActivityNet v1.3. The clip and top-1 accuracy for video classification after our cropping, outperform 3D CNN performances for same-sized random-crop inputs, also surpassing some larger random-crop sizes.
Safe Online Convex Optimization with Unknown Linear Safety Constraints
Venue: arXiv cs.LG 2021
Year: 2021

We study the problem of safe online convex optimization, where the action at each time step must satisfy a set of linear safety constraints. The goal is to select a sequence of actions to minimize the regret without violating the safety constraints at any time step (with high probability). The parameters that specify the linear safety constraints are unknown to the algorithm. The algorithm has access to only the noisy observations of constraints for the chosen actions. We propose an algorithm, called the {Safe Online Projected Gradient Descent} (SO-PGD) algorithm, to address this problem. We show that, under the assumption of the availability of a safe baseline action, the SO-PGD algorithm achieves a regret $O(T^{2/3})$. While there are many algorithms for online convex optimization (OCO) problems with safety constraints available in the literature, they allow constraint violations during learning/optimization, and the focus has been on characterizing the cumulative constraint violations. To the best of our knowledge, ours is the first work that provides an algorithm with provable guarantees on the regret, without violating the linear safety constraints (with high probability) at any time step.
A Comparative Study of Fingerprint Image-Quality Estimation Methods
Venue: arXiv cs.CV 2021
Year: 2021

One of the open issues in fingerprint verification is the lack of robustness against image-quality degradation. Poor-quality images result in spurious and missing features, thus degrading the performance of the overall system. Therefore, it is important for a fingerprint recognition system to estimate the quality and validity of the captured fingerprint images. In this work, we review existing approaches for fingerprint image-quality estimation, including the rationale behind the published measures and visual examples showing their behavior under different quality conditions. We have also tested a selection of fingerprint image-quality estimation algorithms. For the experiments, we employ the BioSec multimodal baseline corpus, which includes 19200 fingerprint images from 200 individuals acquired in two sessions with three different sensors. The behavior of the selected quality measures is compared, showing high correlation between them in most cases. The effect of low-quality samples in the verification performance is also studied for a widely available minutiae-based fingerprint matching system.
Federated Learning with Hyperparameter-based Clustering for Electrical Load Forecasting
Venue: arXiv cs.LG 2021
Year: 2021

Electrical load prediction has become an integral part of power system operation. Deep learning models have found popularity for this purpose. However, to achieve a desired prediction accuracy, they require huge amounts of data for training. Sharing electricity consumption data of individual households for load prediction may compromise user privacy and can be expensive in terms of communication resources. Therefore, edge computing methods, such as federated learning, are gaining more importance for this purpose. These methods can take advantage of the data without centrally storing it. This paper evaluates the performance of federated learning for short-term forecasting of individual house loads as well as the aggregate load. It discusses the advantages and disadvantages of this method by comparing it to centralized and local learning schemes. Moreover, a new client clustering method is proposed to reduce the convergence time of federated learning. The results show that federated learning has a good performance with a minimum root mean squared error (RMSE) of 0.117kWh for individual load forecasting.
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection
Venue: arXiv cs.DS 2021
Year: 2021

Submodular function minimization (SFM) and matroid intersection are fundamental discrete optimization problems with applications in many fields. It is well known that both of these can be solved making $\mathrm{poly}(N)$ queries to a relevant oracle (evaluation oracle for SFM and rank oracle for matroid intersection), where $N$ denotes the universe size. However, all known polynomial query algorithms are highly adaptive, requiring at least $N$ rounds of querying the oracle. A natural question is whether these can be efficiently solved in a highly parallel manner, namely, with $\mathrm{poly}(N)$ queries using only poly-logarithmic rounds of adaptivity. An important step towards understanding the adaptivity needed for efficient parallel SFM was taken recently in the work of Balkanski and Singer who showed that any SFM algorithm making $\mathrm{poly}(N)$ queries necessarily requires $Ω(\log N/\log \log N)$ rounds. This left open the possibility of efficient SFM algorithms in poly-logarithmic rounds. For matroid intersection, even the possibility of a constant round, $\mathrm{poly}(N)$ query algorithm was not hitherto ruled out. In this work, we prove that any, possibly randomized, algorithm for submodular function minimization or matroid intersection making $\mathrm{poly}(N)$ queries requires $\tildeΩ\left(N^{1/3}\right)$ rounds of adaptivity. In fact, we show a polynomial lower bound on the number of rounds of adaptivity even for algorithms that make at most $2^{N^{1-δ}}$ queries, for any constant $δ> 0$. Therefore, even though SFM and matroid intersection are efficiently solvable, they are not highly parallelizable in the oracle model.
Adding more data does not always help: A study in medical conversation summarization with PEGASUS
Venue: arXiv cs.CL 2021
Year: 2021

Medical conversation summarization is integral in capturing information gathered during interactions between patients and physicians. Summarized conversations are used to facilitate patient hand-offs between physicians, and as part of providing care in the future. Summaries, however, can be time-consuming to produce and require domain expertise. Modern pre-trained NLP models such as PEGASUS have emerged as capable alternatives to human summarization, reaching state-of-the-art performance on many summarization benchmarks. However, many downstream tasks still require at least moderately sized datasets to achieve satisfactory performance. In this work we (1) explore the effect of dataset size on transfer learning medical conversation summarization using PEGASUS and (2) evaluate various iterative labeling strategies in the low-data regime, following their success in the classification setting. We find that model performance saturates with increase in dataset size and that the various active-learning strategies evaluated all show equivalent performance consistent with simple dataset size increase. We also find that naive iterative pseudo-labeling is on-par or slightly worse than no pseudo-labeling. Our work sheds light on the successes and challenges of translating low-data regime techniques in classification to medical conversation summarization and helps guides future work in this space. Relevant code available at \url{https://github.com/curai/curai-research/tree/main/medical-summarization-ML4H-2021}.
DFC: Deep Feature Consistency for Robust Point Cloud Registration
Venue: arXiv cs.CV 2021
Year: 2021

How to extract significant point cloud features and estimate the pose between them remains a challenging question, due to the inherent lack of structure and ambiguous order permutation of point clouds. Despite significant improvements in applying deep learning-based methods for most 3D computer vision tasks, such as object classification, object segmentation and point cloud registration, the consistency between features is still not attractive in existing learning-based pipelines. In this paper, we present a novel learning-based alignment network for complex alignment scenes, titled deep feature consistency and consisting of three main modules: a multiscale graph feature merging network for converting the geometric correspondence set into high-dimensional features, a correspondence weighting module for constructing multiple candidate inlier subsets, and a Procrustes approach named deep feature matching for giving a closed-form solution to estimate the relative pose. As the most important step of the deep feature matching module, the feature consistency matrix for each inlier subset is constructed to obtain its principal vectors as the inlier likelihoods of the corresponding subset. We comprehensively validate the robustness and effectiveness of our approach on both the 3DMatch dataset and the KITTI odometry dataset. For large indoor scenes, registration results on the 3DMatch dataset demonstrate that our method outperforms both the state-of-the-art traditional and learning-based methods. For KITTI outdoor scenes, our approach remains quite capable of lowering the transformation errors. We also explore its strong generalization capability over cross-datasets.
Property Inference Attacks Against GANs
Venue: arXiv cs.CR 2021
Year: 2021

While machine learning (ML) has made tremendous progress during the past decade, recent research has shown that ML models are vulnerable to various security and privacy attacks. So far, most of the attacks in this field focus on discriminative models, represented by classifiers. Meanwhile, little attention has been paid to the security and privacy risks of generative models, such as generative adversarial networks (GANs). In this paper, we propose the first set of training dataset property inference attacks against GANs. Concretely, the adversary aims to infer the macro-level training dataset property, i.e., the proportion of samples used to train a target GAN with respect to a certain attribute. A successful property inference attack can allow the adversary to gain extra knowledge of the target GAN's training dataset, thereby directly violating the intellectual property of the target model owner. Also, it can be used as a fairness auditor to check whether the target GAN is trained with a biased dataset. Besides, property inference can serve as a building block for other advanced attacks, such as membership inference. We propose a general attack pipeline that can be tailored to two attack scenarios, including the full black-box setting and partial black-box setting. For the latter, we introduce a novel optimization framework to increase the attack efficacy. Extensive experiments over four representative GAN models on five property inference tasks show that our attacks achieve strong performance. In addition, we show that our attacks can be used to enhance the performance of membership inference against GANs.
Quadratic speedup of global search using a biased crossover of two good solutions
Venue: arXiv cs.NE 2021
Year: 2021

The minimisation of cost functions is crucial in various optimisation fields. However, identifying their global minimum remains challenging owing to the huge computational cost incurred. This work analytically expresses the computational cost to identify an approximate global minimum for a class of cost functions defined under a high-dimensional discrete state space. Then, we derive an optimal global search scheme that minimises the computational cost. Mathematical analyses demonstrate that a combination of the gradient descent algorithm and the selection and crossover algorithm--with a biased crossover weight--maximises the search efficiency. Remarkably, its computational cost is of the square root order in contrast to that of the conventional gradient descent algorithms, indicating a quadratic speedup of global search. We corroborate this proposition using numerical analyses of the travelling salesman problem. The simple computational architecture and minimal computational cost of the proposed scheme are highly desirable for biological organisms and neuromorphic hardware.
Progress in Self-Certified Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

A learning method is self-certified if it uses all available data to simultaneously learn a predictor and certify its quality with a tight statistical certificate that is valid on unseen data. Recent work has shown that neural network models trained by optimising PAC-Bayes bounds lead not only to accurate predictors, but also to tight risk certificates, bearing promise towards achieving self-certified learning. In this context, learning and certification strategies based on PAC-Bayes bounds are especially attractive due to their ability to leverage all data to learn a posterior and simultaneously certify its risk with a tight numerical certificate. In this paper, we assess the progress towards self-certification in probabilistic neural networks learnt by PAC-Bayes inspired objectives. We empirically compare (on 4 classification datasets) classical test set bounds for deterministic predictors and a PAC-Bayes bound for randomised self-certified predictors. We first show that both of these generalisation bounds are not too far from out-of-sample test set errors. We then show that in data starvation regimes, holding out data for the test set bounds adversely affects generalisation performance, while self-certified strategies based on PAC-Bayes bounds do not suffer from this drawback, proving that they might be a suitable choice for the small data regime. We also find that probabilistic neural networks learnt by PAC-Bayes inspired objectives lead to certificates that can be surprisingly competitive with commonly used test set bounds.
Real-time Emotion and Gender Classification using Ensemble CNN
Venue: arXiv cs.CV 2021
Year: 2021

Analysing expressions on the person's face plays a very vital role in identifying emotions and behavior of a person. Recognizing these expressions automatically results in a crucial component of natural human-machine interfaces. Therefore research in this field has a wide range of applications in bio-metric authentication, surveillance systems , emotion to emoticons in various social media platforms. Another application includes conducting customer satisfaction surveys. As we know that the large corporations made huge investments to get feedback and do surveys but fail to get equitable responses. Emotion & Gender recognition through facial gestures is a technology that aims to improve product and services performance by monitoring customer behavior to specific products or service staff by their evaluation. In the past few years there have been a wide variety of advances performed in terms of feature extraction mechanisms , detection of face and also expression classification techniques. This paper is the implementation of an Ensemble CNN for building a real-time system that can detect emotion and gender of the person. The experimental results shows accuracy of 68% for Emotion classification into 7 classes (angry, fear , sad , happy , surprise , neutral , disgust) on FER-2013 dataset and 95% for Gender classification (Male or Female) on IMDB dataset. Our work can predict emotion and gender on single face images as well as multiple face images. Also when input is given through webcam our complete pipeline of this real-time system can take less than 0.5 seconds to generate results.
Conditional Linear Regression for Heterogeneous Covariances
Venue: arXiv cs.LG 2021
Year: 2021

Often machine learning and statistical models will attempt to describe the majority of the data. However, there may be situations where only a fraction of the data can be fit well by a linear regression model. Here, we are interested in a case where such inliers can be identified by a Disjunctive Normal Form (DNF) formula. We give a polynomial time algorithm for the conditional linear regression task, which identifies a DNF condition together with the linear predictor on the corresponding portion of the data. In this work, we improve on previous algorithms by removing a requirement that the covariances of the data satisfying each of the terms of the condition have to all be very similar in spectral norm to the covariance of the overall condition.
A Comparison of O(1) and Cyrus-Beck Line Clipping Algorithms in E2 and E3
Venue: arXiv cs.CG 2021
Year: 2021

A comparison of a new algorithm for line clipping in E2 and E3 by convex polygon and/or polyhedron with O(1) processing complexity and Cyrus- Beck algorithm is presented. The new algorithm in E2 is based on dual space representation and space subdivision technique. The principle of algorithm in E3 is based on the projection of polyhedron to three orthogonal E2 coordinate systems. Algorithms have optimal complexities O(1) and demonstrates that preprocessing can be used to speed up the line clipping significantly. Obvious applications are for one polygon and/or polyhedron and many clipped lines. Detailed theoretical estimations and experimental results are also presented.