OpenRaiser/Intern-Atlas huggingface dataset:
Learning to pronounce as measuring cross-lingual joint orthography-phonology complexity
Venue: arXiv cs.CL 2022
Year: 2022

Machine learning models allow us to compare languages by showing how hard a task in each language might be to learn and perform well on. Following this line of investigation, we explore what makes a language "hard to pronounce" by modelling the task of grapheme-to-phoneme (g2p) transliteration. By training a character-level transformer model on this task across 22 languages and measuring the model's proficiency against its grapheme and phoneme inventories, we show that certain characteristics emerge that separate easier and harder languages with respect to learning to pronounce. Namely the complexity of a language's pronunciation from its orthography is due to the expressive or simplicity of its grapheme-to-phoneme mapping. Further discussion illustrates how future studies should consider relative data sparsity per language to design fairer cross-lingual comparison tasks.
Nonlinear Initialization Methods for Low-Rank Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

We propose a novel low-rank initialization framework for training low-rank deep neural networks -- networks where the weight parameters are re-parameterized by products of two low-rank matrices. The most successful prior existing approach, spectral initialization, draws a sample from the initialization distribution for the full-rank setting and then optimally approximates the full-rank initialization parameters in the Frobenius norm with a pair of low-rank initialization matrices via singular value decomposition. Our method is inspired by the insight that approximating the function corresponding to each layer is more important than approximating the parameter values. We provably demonstrate that there is a significant gap between these two approaches for ReLU networks, particularly as the desired rank of the approximating weights decreases, or as the dimension of the inputs to the layer increases (the latter point holds when the network width is super-linear in dimension). Along the way, we provide the first provably efficient algorithm for solving the ReLU low-rank approximation problem for fixed parameter rank $r$ -- previously, it was unknown that the problem was computationally tractable to solve even for rank $1$. We also provide a practical algorithm to solve this problem which is no more expensive than the existing spectral initialization approach, and validate our theory by training ResNet and EfficientNet models (He et al., 2016; Tan & Le, 2019) on ImageNet (Russakovsky et al., 2015).
Random Processes with High Variance Produce Scale Free Networks
Venue: arXiv cs.DM 2022
Year: 2022

Real-world networks tend to be scale free, having heavy-tailed degree distributions with more hubs than predicted by classical random graph generation methods. Preferential attachment and growth are the most commonly accepted mechanisms leading to these networks and are incorporated in the Barabási-Albert (BA) model. We provide an alternative model using a randomly stopped linking process inspired by a generalized Central Limit Theorem (CLT) for geometric distributions with widely varying parameters. The common characteristic of both the BA model and our randomly stopped linking model is the mixture of widely varying geometric distributions, suggesting the critical characteristic of scale free networks is high variance, not growth or preferential attachment. The limitation of classical random graph models is low variance in parameters, while scale free networks are the natural, expected result of real-world variance.
Modification Problems toward Proper (Helly) Circular-arc Graphs
Venue: arXiv cs.DS 2022
Year: 2022

We present a $9^k\cdot n^{O(1)}$-time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [arXiv:2001.06867]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.
Extension: Adaptive Sampling with Implicit Radiance Field
Venue: arXiv cs.GR 2022
Year: 2022

This manuscript discusses the extension of adaptive light field sampling with implicit radiance fields.
The Role of Linear Layers in Nonlinear Interpolating Networks
Venue: arXiv cs.LG 2022
Year: 2022

This paper explores the implicit bias of overparameterized neural networks of depth greater than two layers. Our framework considers a family of networks of varying depth that all have the same capacity but different implicitly defined representation costs. The representation cost of a function induced by a neural network architecture is the minimum sum of squared weights needed for the network to represent the function; it reflects the function space bias associated with the architecture. Our results show that adding linear layers to a ReLU network yields a representation cost that reflects a complex interplay between the alignment and sparsity of ReLU units. Specifically, using a neural network to fit training data with minimum representation cost yields an interpolating function that is constant in directions perpendicular to a low-dimensional subspace on which a parsimonious interpolant exists.
Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods
Venue: arXiv cs.LG 2022
Year: 2022

Tree-based models such as decision trees and random forests (RF) are a cornerstone of modern machine-learning practice. To mitigate overfitting, trees are typically regularized by a variety of techniques that modify their structure (e.g. pruning). We introduce Hierarchical Shrinkage (HS), a post-hoc algorithm that does not modify the tree structure, and instead regularizes the tree by shrinking the prediction over each node towards the sample means of its ancestors. The amount of shrinkage is controlled by a single regularization parameter and the number of data points in each ancestor. Since HS is a post-hoc method, it is extremely fast, compatible with any tree growing algorithm, and can be used synergistically with other regularization techniques. Extensive experiments over a wide variety of real-world datasets show that HS substantially increases the predictive performance of decision trees, even when used in conjunction with other regularization techniques. Moreover, we find that applying HS to each tree in an RF often improves accuracy, as well as its interpretability by simplifying and stabilizing its decision boundaries and SHAP values. We further explain the success of HS in improving prediction performance by showing its equivalence to ridge regression on a (supervised) basis constructed of decision stumps associated with the internal nodes of a tree. All code and models are released in a full-fledged package available on Github (github.com/csinva/imodels)
Retrieve-and-Fill for Scenario-based Task-Oriented Semantic Parsing
Venue: arXiv cs.CL 2022
Year: 2022

Task-oriented semantic parsing models have achieved strong results in recent years, but unfortunately do not strike an appealing balance between model size, runtime latency, and cross-domain generalizability. We tackle this problem by introducing scenario-based semantic parsing: a variant of the original task which first requires disambiguating an utterance's "scenario" (an intent-slot template with variable leaf spans) before generating its frame, complete with ontology and utterance tokens. This formulation enables us to isolate coarse-grained and fine-grained aspects of the task, each of which we solve with off-the-shelf neural modules, also optimizing for the axes outlined above. Concretely, we create a Retrieve-and-Fill (RAF) architecture comprised of (1) a retrieval module which ranks the best scenario given an utterance and (2) a filling module which imputes spans into the scenario to create the frame. Our model is modular, differentiable, interpretable, and allows us to garner extra supervision from scenarios. RAF achieves strong results in high-resource, low-resource, and multilingual settings, outperforming recent approaches by wide margins despite, using base pre-trained encoders, small sequence lengths, and parallel decoding.
Non-Stationary Dueling Bandits
Venue: arXiv cs.LG 2022
Year: 2022

We study the non-stationary dueling bandits problem with $K$ arms, where the time horizon $T$ consists of $M$ stationary segments, each of which is associated with its own preference matrix. The learner repeatedly selects a pair of arms and observes a binary preference between them as feedback. To minimize the accumulated regret, the learner needs to pick the Condorcet winner of each stationary segment as often as possible, despite preference matrices and segment lengths being unknown. We propose the $\mathrm{Beat\, the\, Winner\, Reset}$ algorithm and prove a bound on its expected binary weak regret in the stationary case, which tightens the bound of current state-of-art algorithms. We also show a regret bound for the non-stationary case, without requiring knowledge of $M$ or $T$. We further propose and analyze two meta-algorithms, $\mathrm{DETECT}$ for weak regret and $\mathrm{Monitored\, Dueling\, Bandits}$ for strong regret, both based on a detection-window approach that can incorporate any dueling bandit algorithm as a black-box algorithm. Finally, we prove a worst-case lower bound for expected weak regret in the non-stationary case.
Spectral Rank Monotonicity on Undirected Networks
Venue: arXiv cs.SI 2022
Year: 2022

We study the problem of score and rank monotonicity for spectral ranking methods, such as eigenvector centrality and PageRank, in the case of undirected networks. Score monotonicity means that adding an edge increases the score at both ends of the edge. Rank monotonicity means that adding an edge improves the relative position of both ends of the edge with respect to the remaining nodes. It is known that common spectral rankings are both score and rank monotone on directed, strongly connected graphs. We show that, surprisingly, the situation is very different for undirected graphs, and in particular that PageRank is neither score nor rank monotone.
Minimizing Expected Intrusion Detection Time in Adversarial Patrolling
Venue: arXiv cs.MA 2022
Year: 2022

In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker. The Attacker's utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs. However, in many real-world scenarios, the actual damage caused by the Attacker depends on the \emph{time} elapsed since the attack's initiation to its detection. We introduce a formal model for such scenarios, and we show that the Defender always has an \emph{optimal} strategy achieving maximal protection. We also prove that \emph{finite-memory} Defender's strategies are sufficient for achieving protection arbitrarily close to the optimum. Then, we design an efficient \emph{strategy synthesis} algorithm based on differentiable programming and gradient descent.
Distributed Ride-Matching for Shared Ridehailing Service with Intelligent City Infrastructure
Venue: arXiv cs.DC 2022
Year: 2022

High computational time is one of the most important operational issues in centralized dynamic shared ridehailing services. To resolve this issue, we propose a distributed ride-matching system that is based on vehicle to infrastructure (V2I) and infrastructure to infrastructure (I2I) communication. The application on downtown Toronto road network demonstrated that the distributed system resulted in a speed-up of 125 times in terms of computational time and showed high scalability. Moreover, the service rate in the proposed system improved by 7% compared to the centralized. However, the centralized system showed 29% and 17% improvement in wait time and detour time, respectively.
Information Extraction through AI techniques: The KIDs use case at CONSOB
Venue: arXiv cs.CL 2022
Year: 2022

In this paper we report on the initial activities carried out within a collaboration between Consob and Sapienza University. We focus on Information Extraction from documents describing financial instruments. We discuss how we automate this task, via both rule-based and machine learning-based methods and provide our first results.
VOS: Learning What You Don't Know by Virtual Outlier Synthesis
Venue: arXiv cs.LG 2022
Year: 2022

Out-of-distribution (OOD) detection has received much attention lately due to its importance in the safe deployment of neural networks. One of the key challenges is that models lack supervision signals from unknown data, and as a result, can produce overconfident predictions on OOD data. Previous approaches rely on real outlier datasets for model regularization, which can be costly and sometimes infeasible to obtain in practice. In this paper, we present VOS, a novel framework for OOD detection by adaptively synthesizing virtual outliers that can meaningfully regularize the model's decision boundary during training. Specifically, VOS samples virtual outliers from the low-likelihood region of the class-conditional distribution estimated in the feature space. Alongside, we introduce a novel unknown-aware training objective, which contrastively shapes the uncertainty space between the ID data and synthesized outlier data. VOS achieves competitive performance on both object detection and image classification models, reducing the FPR95 by up to 9.36% compared to the previous best method on object detectors. Code is available at https://github.com/deeplearning-wisc/vos.
A Hybrid Compartmental Model with a Case Study of COVID-19 in Great Britain and Israel
Venue: arXiv cs.CY 2022
Year: 2022

Given the severe impact of COVID-19 on several societal levels, it is of crucial importance to model the impact of restriction measures on the pandemic evolution, so that governments are able to take informed decisions. Even though there have been countless attempts to propose diverse models since the raise of the outbreak, the increase in data availability and start of vaccination campaigns calls for updated models and studies. Furthermore, most of the works are focused on a very particular place or application and we strive to attain a more general model, resorting to data from different countries. In particular, we compare Great Britain and Israel, two highly different scenarios in terms of vaccination plans and social structure. We build a network-based model, complex enough to model different scenarios of government-mandated restrictions, but generic enough to be applied to any population. To ease the computational load we propose a decomposition strategy for our model.
Training Semantic Descriptors for Image-Based Localization
Venue: arXiv cs.CV 2022
Year: 2022

Vision based solutions for the localization of vehicles have become popular recently. We employ an image retrieval based visual localization approach. The database images are kept with GPS coordinates and the location of the retrieved database image serves as an approximate position of the query image. We show that localization can be performed via descriptors solely extracted from semantically segmented images. It is reliable especially when the environment is subjected to severe illumination and seasonal changes. Our experiments reveal that the localization performance of a semantic descriptor can increase up to the level of state-of-the-art RGB image based methods.
PolarDenseNet: A Deep Learning Model for CSI Feedback in MIMO Systems
Venue: arXiv cs.IT 2022
Year: 2022

In multiple-input multiple-output (MIMO) systems, the high-resolution channel information (CSI) is required at the base station (BS) to ensure optimal performance, especially in the case of multi-user MIMO (MU-MIMO) systems. In the absence of channel reciprocity in frequency division duplex (FDD) systems, the user needs to send the CSI to the BS. Often the large overhead associated with this CSI feedback in FDD systems becomes the bottleneck in improving the system performance. In this paper, we propose an AI-based CSI feedback based on an auto-encoder architecture that encodes the CSI at UE into a low-dimensional latent space and decodes it back at the BS by effectively reducing the feedback overhead while minimizing the loss during recovery. Our simulation results show that the AI-based proposed architecture outperforms the state-of-the-art high-resolution linear combination codebook using the DFT basis adopted in the 5G New Radio (NR) system.
Introduction to The Dynamic Pickup and Delivery Problem Benchmark -- ICAPS 2021 Competition
Venue: arXiv cs.AI 2022
Year: 2022

The Dynamic Pickup and Delivery Problem (DPDP) is an essential problem within the logistics domain. So far, research on this problem has mainly focused on using artificial data which fails to reflect the complexity of real-world problems. In this draft, we would like to introduce a new benchmark from real business scenarios as well as a simulator supporting the dynamic evaluation. The benchmark and simulator have been published and successfully supported the ICAPS 2021 Dynamic Pickup and Delivery Problem competition participated by 152 teams.
Age Distribution in Arbitrary Preemptive Memoryless Networks
Venue: arXiv cs.IT 2022
Year: 2022

We study the probability distribution of age of information (AoI) in arbitrary networks with memoryless service times. A source node generates packets following a Poisson process, and then the packets are forwarded across the network in such a way that newer updates preempt older ones. This model is equivalent to gossip networks that was recently studied by Yates, and for which he obtained a recursive formula allowing the computation for the average AoI. In this paper, we obtain a very simple characterization of the stationary distribution of AoI at every node in the network. This allows for the computation of the average of an arbitrary function of the age. In particular, we can compute age-violation probabilities. Furthermore, we show how it is possible to use insights from our simple characterization in order to substantially reduce the computation time of average AoIs in some structured networks. Finally, we describe how it is possible to use our characterization in order to obtain faster and more accurate Monte Carlo simulations estimating the average AoI, or the average of an arbitrary function of the age.
Impact Analysis of Harassment Against Women Using Association Rule Mining Approaches: Bangladesh Prospective
Venue: arXiv cs.LG 2022
Year: 2022

In recent years, it has been noticed that women are making progress in every sector of society. Their involvement in every field, such as education, job market, social work, etc., is increasing at a remarkable rate. For the last several years, the government has been trying its level best for the advancement of women in every sector by doing several research work and activities and funding several organizations to motivate women. Although women's involvement in several fields is increasing, the big concern is they are facing several barriers in their advancement, and it is not surprising that sexual harassment is one of them. In Bangladesh, harassment against women, especially students, is a common phenomenon, and it is increasing. In this paper, a survey-based and Apriori algorithm are used to analyze the several impacts of harassment among several age groups. Also, several factors such as frequent impacts of harassment, most vulnerable groups, women mostly facing harassment, the alleged person behind harassment, etc., are analyzed through association rule mining of Apriori algorithm and F.P. Growth algorithm. And then, a comparison of performance between both algorithms has been shown briefly. For this analysis, data have been carefully collected from all ages.
Multi-Resolution Factor Graph Based Stereo Correspondence Algorithm
Venue: arXiv cs.CV 2022
Year: 2022

A dense depth-map of a scene at an arbitrary view orientation can be estimated from dense view correspondences among multiple lower-dimensional views of the scene. These low-dimensional view correspondences are dependent on the geometrical relationship among the views and the scene. Determining dense view correspondences is difficult in part due to presence of homogeneous regions in the scene and due to presence of occluded regions and illumination differences among the views. We present a new multi-resolution factor graph-based stereo matching algorithm (MR-FGS) that utilizes both intra- and inter-resolution dependencies among the views as well as among the disparity estimates. The proposed framework allows exchange of information among multiple resolutions of the correspondence problem and is useful for handling larger homogeneous regions in a scene. The MR-FGS algorithm was evaluated qualitatively and quantitatively using stereo pairs in the Middlebury stereo benchmark dataset based on commonly used performance measures. When compared to a recently developed factor graph model (FGS), the MR-FGS algorithm provided more accurate disparity estimates without requiring the commonly used post-processing procedure known as the left-right consistency check. The multi-resolution dependency constraint within the factor-graph model significantly improved contrast along depth boundaries in the MR-FGS generated disparity maps.
Deep Learning for Epidemiologists: An Introduction to Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Deep learning methods are increasingly being applied to problems in medicine and healthcare. However, few epidemiologists have received formal training in these methods. To bridge this gap, this article introduces to the fundamentals of deep learning from an epidemiological perspective. Specifically, this article reviews core concepts in machine learning (overfitting, regularization, hyperparameters), explains several fundamental deep learning architectures (convolutional neural networks, recurrent neural networks), and summarizes training, evaluation, and deployment of models. We aim to enable the reader to engage with and critically evaluate medical applications of deep learning, facilitating a dialogue between computer scientists and epidemiologists that will improve the safety and efficacy of applications of this technology.
An Artificial Intelligence Dataset for Solar Energy Locations in India
Venue: arXiv cs.LG 2022
Year: 2022

Rapid development of renewable energy sources, particularly solar photovoltaics (PV), is critical to mitigate climate change. As a result, India has set ambitious goals to install 500 gigawatts of solar energy capacity by 2030. Given the large footprint projected to meet renewables energy targets, the potential for land use conflicts over environmental values is high. To expedite development of solar energy, land use planners will need access to up-to-date and accurate geo-spatial information of PV infrastructure. In this work, we developed a spatially explicit machine learning model to map utility-scale solar projects across India using freely available satellite imagery with a mean accuracy of 92%. Our model predictions were validated by human experts to obtain a dataset of 1363 solar PV farms. Using this dataset, we measure the solar footprint across India and quantified the degree of landcover modification associated with the development of PV infrastructure. Our analysis indicates that over 74% of solar development In India was built on landcover types that have natural ecosystem preservation, or agricultural value.