OpenRaiser/Intern-Atlas huggingface dataset:
Detection and Mitigation of Rare Subclasses in Deep Neural Network Classifiers
Venue: arXiv cs.LG 2021
Year: 2021

Regions of high-dimensional input spaces that are underrepresented in training datasets reduce machine-learnt classifier performance, and may lead to corner cases and unwanted bias for classifiers used in decision making systems. When these regions belong to otherwise well-represented classes, their presence and negative impact are very hard to identify. We propose an approach for the detection and mitigation of such rare subclasses in deep neural network classifiers. The new approach is underpinned by an easy-to-compute commonality metric that supports the detection of rare subclasses, and comprises methods for reducing the impact of these subclasses during both model training and model exploitation. We demonstrate our approach using two well-known datasets, MNIST's handwritten digits and Kaggle's cats/dogs, identifying rare subclasses and producing models which compensate for subclass rarity. In addition we demonstrate how our run-time approach increases the ability of users to identify samples likely to be misclassified at run-time.
When Blockchain Meets AI: Optimal Mining Strategy Achieved By Machine Learning
Venue: arXiv cs.CR 2021
Year: 2021

This work applies reinforcement learning (RL) from the AI machine learning field to derive an optimal Bitcoin-like blockchain mining strategy without knowing the details of the blockchain network model. Previously, the most profitable mining strategy was believed to be honest mining encoded in the default blockchain protocol. It was shown later that it is possible to gain more mining rewards by deviating from honest mining. In particular, the mining problem can be formulated as a Markov Decision Process (MDP) which can be solved to give the optimal mining strategy. However, solving the mining MDP requires knowing the values of various parameters that characterize the blockchain network model. In real blockchain networks, these parameter values are not easy to obtain and may change over time. This hinders the use of the MDP model-based solution. In this work, we employ RL to dynamically learn a mining strategy with performance approaching that of the optimal mining strategy by observing and interacting with the network. Since the mining MDP problem has a non-linear objective function (rather than linear functions of standard MDP problems), we design a new multi-dimensional RL algorithm to solve the problem. Experimental results indicate that, without knowing the parameter values of the mining MDP model, our multi-dimensional RL mining algorithm can still achieve the optimal performance over time-varying blockchain networks.
On model selection for scalable time series forecasting in transport networks
Venue: arXiv cs.LG 2021
Year: 2021

The transport literature is dense regarding short-term traffic predictions, up to the scale of 1 hour, yet less dense for long-term traffic predictions. The transport literature is also sparse when it comes to city-scale traffic predictions, mainly because of low data availability. In this work, we report an effort to investigate whether deep learning models can be useful for the long-term large-scale traffic prediction task, while focusing on the scalability of the models. We investigate a city-scale traffic dataset with 14 weeks of speed observations collected every 15 minutes over 1098 segments in the hypercenter of Los Angeles, California. We look at a variety of state-of-the-art machine learning and deep learning predictors for link-based predictions, and investigate how such predictors can scale up to larger areas with clustering, and graph convolutional approaches. We discuss that modelling temporal and spatial features into deep learning predictors can be helpful for long-term predictions, while simpler, not deep learning-based predictors, achieve very satisfactory performance for link-based and short-term forecasting. The trade-off is discussed not only in terms of prediction accuracy vs prediction horizon but also in terms of training time and model sizing.
Radon Sobolev Variational Auto-Encoders
Venue: arXiv cs.LG 2021
Year: 2021

The quality of generative models (such as Generative adversarial networks and Variational Auto-Encoders) depends heavily on the choice of a good probability distance. However some popular metrics like the Wasserstein or the Sliced Wasserstein distances, the Jensen-Shannon divergence, the Kullback-Leibler divergence, lack convenient properties such as (geodesic) convexity, fast evaluation and so on. To address these shortcomings, we introduce a class of distances that have built-in convexity. We investigate the relationship with some known paradigms (sliced distances - a synonym for Radon distances -, reproducing kernel Hilbert spaces, energy distances). The distances are shown to possess fast implementations and are included in an adapted Variational Auto-Encoder termed Radon Sobolev Variational Auto-Encoder (RS-VAE) which produces high quality results on standard generative datasets. Keywords: Variational Auto-Encoder; Generative model; Sobolev spaces; Radon Sobolev Variational Auto-Encoder;
Adversarially Robust Low Dimensional Representations
Venue: arXiv cs.DS 2021
Year: 2021

Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical front due to applications where reliability and security are critical. However, theoretical understanding of algorithms that are robust to adversarial perturbations is limited. In this work we focus on Principal Component Analysis (PCA), a ubiquitous algorithmic primitive in machine learning. We formulate a natural robust variant of PCA where the goal is to find a low dimensional subspace to represent the given data with minimum projection error, that is in addition robust to small perturbations measured in $\ell_q$ norm (say $q=\infty$). Unlike PCA which is solvable in polynomial time, our formulation is computationally intractable to optimize as it captures a variant of the well-studied sparse PCA objective as a special case. We show the following results: -Polynomial time algorithm that is constant factor competitive in the worst-case with respect to the best subspace, in terms of the projection error and the robustness criterion. -We show that our algorithmic techniques can also be made robust to adversarial training-time perturbations, in addition to yielding representations that are robust to adversarial perturbations at test time. Specifically, we design algorithms for a strong notion of training-time perturbations, where every point is adversarially perturbed up to a specified amount. -We illustrate the broad applicability of our algorithmic techniques in addressing robustness to adversarial perturbations, both at training time and test time. In particular, our adversarially robust PCA primitive leads to computationally efficient and robust algorithms for both unsupervised and supervised learning problems such as clustering and learning adversarially robust classifiers.
Integrating Graph Contextualized Knowledge into Pre-trained Language Models
Venue: arXiv cs.CL 2021
Year: 2021

Complex node interactions are common in knowledge graphs, and these interactions also contain rich knowledge information. However, traditional methods usually treat a triple as a training unit during the knowledge representation learning (KRL) procedure, neglecting contextualized information of the nodes in knowledge graphs (KGs). We generalize the modeling object to a very general form, which theoretically supports any subgraph extracted from the knowledge graph, and these subgraphs are fed into a novel transformer-based model to learn the knowledge embeddings. To broaden usage scenarios of knowledge, pre-trained language models are utilized to build a model that incorporates the learned knowledge representations. Experimental results demonstrate that our model achieves the state-of-the-art performance on several medical NLP tasks, and improvement above TransE indicates that our KRL method captures the graph contextualized information effectively.
Probing the State of the Art: A Critical Look at Visual Representation Evaluation
Venue: arXiv cs.LG 2021
Year: 2021

Self-supervised research improved greatly over the past half decade, with much of the growth being driven by objectives that are hard to quantitatively compare. These techniques include colorization, cyclical consistency, and noise-contrastive estimation from image patches. Consequently, the field has settled on a handful of measurements that depend on linear probes to adjudicate which approaches are the best. Our first contribution is to show that this test is insufficient and that models which perform poorly (strongly) on linear classification can perform strongly (weakly) on more involved tasks like temporal activity localization. Our second contribution is to analyze the capabilities of five different representations. And our third contribution is a much needed new dataset for temporal activity localization.
Towards end-to-end verifiable online voting: adding verifiability to established voting systems
Venue: arXiv cs.CR 2021
Year: 2021

Online voting for independent elections is generally supported by trusted election providers. Typically these providers do not offer any way in which a voter can verify their vote, so the providers are trusted with ballot privacy and ensuring correctness. Despite the desire to offer online voting for political elections, this lack of transparency and verifiability is often seen as a significant barrier to the large-scale adoption of online elections. Adding verifiability to an online election increases transparency and integrity, allowing voters to verify that their vote has been recorded correctly and included in the tally. However, replacing existing online systems with those that provide verifiable voting requires new algorithms and code to be deployed, and this presents a significant business risk to commercial election providers. In this paper we present the first step in an incremental approach which minimises the business risk but demonstrates the advantages of verifiability, by developing an implementation of key elements of a Selene-based verifiability layer and adding it to an operational online voting system. Selene is a verifiable voting protocol that uses trackers to enable voters to confirm that their votes have been captured correctly while protecting voter anonymity. This results in a system where even the election authority running the system cannot change the result in an undetectable way, and gives stronger guarantees on the integrity of the election than were previously present. We explore the challenges presented by adding a verifiability layer to an operational system. We describe the results of two initial trials, which obtained that survey respondents found this form of verifiability easy to use and that they broadly appreciated it. We conclude by outlining the further steps in the road-map towards the deployment of a fully trustworthy online voting system.
Improved S-AF and S-DF Relaying Schemes Using Machine Learning Based Power Allocation Over Cascaded Rayleigh Fading Channels
Venue: arXiv cs.IT 2021
Year: 2021

We investigate the performance of a dual-hop intervehicular communications (IVC) system with relay selection strategy. We assume a generalized fading channel model, known as cascaded Rayleigh (also called n*Rayleigh), which involves the product of n independent Rayleigh random variables. This channel model provides a realistic description of IVC, in contrast to the conventional Rayleigh fading assumption, which is more suitable for cellular networks. Unlike existing works, which mainly consider double-Rayleigh fading channels (i.e, n = 2); our system model considers the general cascading order n, for which we derive an approximate analytic solution for the outage probability under the considered scenario. Also, in this study we propose a machine learning-based power allocation scheme to improve the link reliability in IVC. The analytical and simulation results show that both selective decode-and-forward (S-DF) and amplify-and-forward (S-AF) relaying schemes have the same diversity order in the high signal-to-noise ratio regime. In addition, our results indicate that machine learning algorithms can play a central role in selecting the best relay and allocation of transmission power.
FlowNet3D++: Geometric Losses For Deep Scene Flow Estimation
Venue: arXiv cs.CV 2021
Year: 2021

We present FlowNet3D++, a deep scene flow estimation network. Inspired by classical methods, FlowNet3D++ incorporates geometric constraints in the form of point-to-plane distance and angular alignment between individual vectors in the flow field, into FlowNet3D. We demonstrate that the addition of these geometric loss terms improves the previous state-of-art FlowNet3D accuracy from 57.85% to 63.43%. To further demonstrate the effectiveness of our geometric constraints, we propose a benchmark for flow estimation on the task of dynamic 3D reconstruction, thus providing a more holistic and practical measure of performance than the breakdown of individual metrics previously used to evaluate scene flow. This is made possible through the contribution of a novel pipeline to integrate point-based scene flow predictions into a global dense volume. FlowNet3D++ achieves up to a 15.0% reduction in reconstruction error over FlowNet3D, and up to a 35.2% improvement over KillingFusion alone. We will release our scene flow estimation code later.
Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning has started to be deployed in fields such as healthcare and finance, which propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks. Our 4PC protocol tolerating at most one malicious corruption is practically efficient as compared to the existing works. We use the protocol to build an efficient mixed-world framework (Trident) to switch between the Arithmetic, Boolean, and Garbled worlds. Our framework operates in the offline-online paradigm over rings and is instantiated in an outsourced setting for machine learning. Also, we propose conversions especially relevant to privacy-preserving machine learning. The highlights of our framework include using a minimal number of expensive circuits overall as compared to ABY3. This can be seen in our technique for truncation, which does not affect the online cost of multiplication and removes the need for any circuits in the offline phase. Our B2A conversion has an improvement of $\mathbf{7} \times$ in rounds and $\mathbf{18} \times$ in the communication complexity. The practicality of our framework is argued through improvements in the benchmarking of the aforementioned algorithms when compared with ABY3. All the protocols are implemented over a 64-bit ring in both LAN and WAN settings. Our improvements go up to $\mathbf{187} \times$ for the training phase and $\mathbf{158} \times$ for the prediction phase when observed over LAN and WAN.
A Game-Theoretic and Experimental Analysis of Energy-Depleting Underwater Jamming Attacks
Venue: arXiv cs.NI 2021
Year: 2021

Security aspects in underwater wireless networks have not been widely investigated so far, despite the critical importance of the scenarios in which these networks can be employed. For example, an attack to a military underwater network for enemy targeting or identification can lead to serious consequences. Similarly, environmental monitoring applications such as tsunami prevention are also critical from a public safety point of view. In this work, we assess a scenario in which a malicious node tries to perform a jamming attack, degrading the communication quality of battery-powered underwater nodes. The legitimate transmitter may use packet level coding to increase the chances of correctly delivering packets. Because of the energy limitation of the nodes, the jammer's objective is twofold: disrupting the communication and reducing the lifetime of the victim by making it send more redundancy. We model the jammer and the transmitter as players in a multistage game, deriving the optimal strategies. We evaluate the performance in a model-based scenario and using real experimental data, performing a sensitivity analysis to evaluate the performance of the strategies if the real channel model is different from the one they use.
VideoDG: Generalizing Temporal Relations in Videos to Novel Domains
Venue: arXiv cs.CV 2021
Year: 2021

This paper introduces video domain generalization where most video classification networks degenerate due to the lack of exposure to the target domains of divergent distributions. We observe that the global temporal features are less generalizable, due to the temporal domain shift that videos from other unseen domains may have an unexpected absence or misalignment of the temporal relations. This finding has motivated us to solve video domain generalization by effectively learning the local-relation features of different timescales that are more generalizable, and exploiting them along with the global-relation features to maintain the discriminability. This paper presents the VideoDG framework with two technical contributions. The first is a new deep architecture named the Adversarial Pyramid Network, which improves the generalizability of video features by capturing the local-relation, global-relation, and cross-relation features progressively. On the basis of pyramid features, the second contribution is a new and robust approach of adversarial data augmentation that can bridge different video domains by improving the diversity and quality of augmented data. We construct three video domain generalization benchmarks in which domains are divided according to different datasets, different consequences of actions, or different camera views, respectively. VideoDG consistently outperforms the combinations of previous video classification models and existing domain generalization methods on all benchmarks.
Similarity Caching: Theory and Algorithms
Venue: arXiv cs.NI 2021
Year: 2021

This paper focuses on similarity caching systems, in which a user request for an {object~$o$} that is not in the cache can be (partially) satisfied by a similar stored {object~$o'$}, at the cost of a loss of user utility. Similarity caching systems can be effectively employed in several application areas, like multimedia retrieval, recommender systems, genome study, and machine learning training/serving. However, despite their relevance, the behavior of such systems is far from being well understood. In this paper, we provide a first comprehensive analysis of similarity caching in the offline, adversarial, and stochastic settings. We show that similarity caching raises significant new challenges, for which we propose the first dynamic policies with some optimality guarantees. We evaluate the performance of our schemes under both synthetic and real request traces.
It Runs in the Family: Searching for Synonyms Using Digitized Family Trees
Venue: arXiv cs.IR 2021
Year: 2021

Searching for a person's name is a common online activity. However, Web search engines provide few accurate results to queries containing names. In contrast to a general word which has only one correct spelling, there are several legitimate spellings of a given name. Today, most techniques used to suggest synonyms in online search are based on pattern matching and phonetic encoding, however they often perform poorly. As a result, there is a need for an effective tool for improved synonym suggestion. In this paper, we propose a revolutionary approach for tackling the problem of synonym suggestion. Our novel algorithm, GRAFT, utilizes historical data collected from genealogy websites, along with network algorithms. GRAFT is a general algorithm that suggests synonyms using a graph based on names derived from digitized ancestral family trees. Synonyms are extracted from this graph, which is constructed using generic ordering functions that outperform other algorithms that suggest synonyms based on a single dimension, a factor that limits their performance. We evaluated GRAFT's performance on three ground truth datasets of forenames and surnames, including a large-scale online genealogy dataset with over 16 million profiles and more than 700,000 unique forenames and 500,000 surnames. We compared GRAFT's performance at suggesting synonyms to 10 other algorithms, including phonetic encoding, string similarity algorithms, and machine and deep learning algorithms. The results show GRAFT's superiority with respect to both forenames and surnames and demonstrate its use as a tool to improve synonym suggestion.
Classifying, Segmenting, and Tracking Object Instances in Video with Mask Propagation
Venue: arXiv cs.CV 2021
Year: 2021

We introduce a method for simultaneously classifying, segmenting and tracking object instances in a video sequence. Our method, named MaskProp, adapts the popular Mask R-CNN to video by adding a mask propagation branch that propagates frame-level object instance masks from each video frame to all the other frames in a video clip. This allows our system to predict clip-level instance tracks with respect to the object instances segmented in the middle frame of the clip. Clip-level instance tracks generated densely for each frame in the sequence are finally aggregated to produce video-level object instance segmentation and classification. Our experiments demonstrate that our clip-level instance segmentation makes our approach robust to motion blur and object occlusions in video. MaskProp achieves the best reported accuracy on the YouTube-VIS dataset, outperforming the ICCV 2019 video instance segmentation challenge winner despite being much simpler and using orders of magnitude less labeled data (1.3M vs 1B images and 860K vs 14M bounding boxes).
Measurement and Fairness
Venue: arXiv cs.CY 2021
Year: 2021

We propose measurement modeling from the quantitative social sciences as a framework for understanding fairness in computational systems. Computational systems often involve unobservable theoretical constructs, such as socioeconomic status, teacher effectiveness, and risk of recidivism. Such constructs cannot be measured directly and must instead be inferred from measurements of observable properties (and other unobservable theoretical constructs) thought to be related to them -- i.e., operationalized via a measurement model. This process, which necessarily involves making assumptions, introduces the potential for mismatches between the theoretical understanding of the construct purported to be measured and its operationalization. We argue that many of the harms discussed in the literature on fairness in computational systems are direct results of such mismatches. We show how some of these harms could have been anticipated and, in some cases, mitigated if viewed through the lens of measurement modeling. To do this, we contribute fairness-oriented conceptualizations of construct reliability and construct validity that unite traditions from political science, education, and psychology and provide a set of tools for making explicit and testing assumptions about constructs and their operationalizations. We then turn to fairness itself, an essentially contested construct that has different theoretical understandings in different contexts. We argue that this contestedness underlies recent debates about fairness definitions: although these debates appear to be about different operationalizations, they are, in fact, debates about different theoretical understandings of fairness. We show how measurement modeling can provide a framework for getting to the core of these debates.