1,721,006 research outputs found
Casual and trustworthy machine learning: methods and applications
Get PDFThis work focuses on the intersection of machine learning and causal inference and the way in which the two fields can enhance each other by sharing ideas: utilizing machine learning techniques for the computation of causal quantities, the use of ideas from causal inference for invariant predictions under unseen treatment regimes, and the exploration of topics in trustworthy machine learning, including interpretability and fairness, with a causal lens. In each one of the presented works, we grappled with the strength of assumptions needed to utilize causal inference techniques and relax portions of them when possible.
In Chapter 1, we introduce the motivation behind the works and the challenges that sparked this plan of study. Chapter 2 provides a foundation on basic topics in causal machine learning and trustworthy machine learning. In Chapter 3, we introduce a causal effect estimation method under partial causal graph knowledge. In Chapter 4, we look at causal effect estimation in complex data settings, such as images, text, and gene expression networks, and propose an invariant estimation approach utilizing crude interventions. In Chapter 5, we provide a causal perspective on explainable machine learning, unifying existing works and providing a sound and complete algorithm involving the concepts of sufficiency and necessity. Finally, in Chapters 6 and 7, we introduce methods and investigations in fair machine learning
Risk bounds for improper prediction procedures
Get PDFStatistical Learning Theory studies the problem of learning an unknown relationship between observed input-output pairs sampled independently from
some unknown and arbitrary probability distribution. The quality of the
inferred relationship is judged by its excess risk -- a measure of prediction
capability on unseen data compared to the best predictor in some predefined
reference class of functions. A learning procedure is said to be improper if
it is allowed to output a prediction rule outside the chosen reference class.
This thesis presents four contributions to analyzing the prediction
performance of improper learning algorithms.
Our first result contributes to developing the mathematical machinery
suitable for the analysis of improper learning procedures. We obtain
exponential-tail excess risk bounds in terms of offset Rademacher complexity
for which only in-expectation guarantees were previously obtained.
Our second result shows that offset Rademacher complexity yields upper
bounds on the excess risk of iterative regularization schemes characterized
by mirror descent algorithms. Moreover, by providing a unified analysis, our proposed
proof technique circumvents the limitations of some previous analyses
tailored to exploit the exact form of specific iterative schemes.
Our third contribution concerns the analysis of the constrained linear least
squares algorithm. We find that this classical and widely studied statistical
estimator is suboptimal, with dimension-dependent excess risk improvements
offered via known improper procedures.
In our fourth contribution, we investigate improperness in the linear
regression problem with the squared loss, without imposing any
assumptions on the distribution of the covariates and imposing a minimal
assumption on the conditional distribution of the response variable. We first
establish the in-expectation optimality of the truncated least squares
estimator and then, we show that it can fail with constant probability. We
conclude by proposing a deviation-optimal procedure. The considered setup
admits heavy-tailed distributions while falling outside the scope of the
typically studied procedures for heavy-tailed linear regression
Identifying and exploiting structures for reliable deep learning
Get PDFDeep learning research has recently witnessed an impressively fast-paced progress in a wide range of tasks including computer vision, natural language processing, and reinforcement learning. The extraordinary performance of these systems often gives the impression that they can be used to revolutionise our lives for the better. However, as recent works point out, these systems suffer from several issues that make them unreliable for use in the real world, including vulnerability to adversarial attacks (Szegedy et al. [243]), tendency to memorise noise (Zhang et al. [286]), being over-confident on incorrect predictions (miscalibration) (Guo et al. [99]), and unsuitability for handling private data (Gilad-Bachrach et al. [88]). In this the- sis, we look at each of these issues in detail, investigate their causes, and propose computationally cheap algorithms for mitigating them in practice.
To do this, we identify structures in deep neural networks that can be exploited to mitigate the above causes of unreliability of deep learning algorithms. In Chapter 4, we show that minimising a property of matrices, called stable rank, for individual weight matrix in a neural network reduces the tendency of the network to memorise noise without sacrificing its performance on noiseless data.
In Chapter 5, we prove that memorising label noise or doing improper representation learning makes achieving adversarial robustness impossible. Chapter 6 shows that a low-rank prior on the representation space of neural networks increases the robustness of neural networks to adversarial perturbations without inducing any tradeoff with accuracy in practice.
In Chapter 7, we highlight the use of focal loss, which weights loss components from individual samples differentially by how well the neural network classifies each of them, as an alternative loss function to cross-entropy for minimising miscalibration in neural networks.
In Chapter 8, we first define a new framework called Encrypted Prediction As A Service (EPAAS) along with a set of computational and privacy constraints. Then we propose the use of a Fully Homomorphic Encryption [84] scheme which can be used with a Binary neural network [61], along with a set of algebraic and computational tricks, to satisfy all our conditions for EPAAS while being computationally efficient
Tracking adversarial targets
No full textWe study linear control problems with quadratic\ud
losses and adversarially chosen tracking targets.\ud
We present an efficient algorithm for this problem\ud
and show that, under standard conditions on\ud
the linear system, its regret with respect to an optimal\ud
linear policy grows as O(log^2 T), where T\ud
is the number of rounds of the game. We also\ud
study a problem with adversarially chosen transition\ud
dynamics; we present an exponentiallyweighted\ud
average algorithm for this problem, and\ud
we give regret bounds that grow as O(sqtr\ud
p\ud
T)
Competitive analysis of k-server variants and metrical task systems
Get PDFIn the online k-server problem, an algorithm controls k mobile servers in a metric space. One by one, requests arrive at points of the space, and the algorithm must serve each request by selecting a server to visit it. The goal is to minimize the total distance traveled by all servers. In the framework of competitive analysis, we study two variants of the k-server problem, the infinite server problem and the k-taxi problem, and the more general metrical task systems problem.
The infinite server problem is the variant of the k-server problem where the number of servers is infinite, initially all starting at the same point. We obtain a surprisingly tight connection between the infinite server problem and the resource augmentation version of the k-server problem. Using this connection, we also improve the known lower bounds for the resource augmented k-server problem.
The k-taxi problem generalizes the k-server problem in that a request consists not of one point, but two points s and t, representing the start and destination of a taxi request. To serve such a request, a server (taxi) must move first to s and then to t. This problem becomes particularly difficult when the cost is defined as the distance of empty runs only. Indeed, we show an exponential gap between the competitive ratio of the k-taxi problem and that of the k-server problem. A main positive result is an O(2k log n)-competitive algorithm for arbitrary n-point metrics.
Metrical task systems are a general framework subsuming many other online problems, including the k-server problem. Here, the algorithm suffers two kinds of costs, movement and service costs. For HST metrics, using an entropy regularization approach, we obtain tight bounds on the refined guarantees, i.e., movement and service costs are simultaneously optimally competitive against the optimal total cost. This also improves the refined guarantees for general metrics
Computationally bounded rationality from three perspectives: precomputation, regret tradeoffs, and lifelong learning
Get PDFWhat does it mean for a computer program to be optimal? Many fields in optimal decision making, from game theory to Bayesian decision theory, define optimal solutions which can be computationally intractable to implement or find. This is problematic, because it means that sometimes these solutions are not physically realizable. To address this problem, bounded rationality studies what it means to behave optimally subject to constraints on processing time, memory and knowledge. This thesis contributes three new models for studying bounded rationality in different contexts.
The first model considers games like chess. We suppose each player can spend some time before the game precomputing (memorizing) strong moves from an oracle, but has limited memory to remember these moves. We show how to analytically quantify how randomly optimal strategies play in equilibrium, and give polynomial- time algorithms for computing a best response and an ε-Nash equilibrium. We use the best response algorithm to empirically evaluate the chess playing program Stockfish.
The second model takes place in the setting of adversarial online learning. Here, we imagine an algorithm receives new problems online, and is given a computational budget to run B problem solvers for each problem. We show how to trade off the budget B for a strengthening of the algorithm’s regret guarantee in both the full and semi-bandit feedback settings. We then show how this tradeoff implies new results for Online Submodular Function Maximization (OSFM) (Streeter and Golovin, 2008) and Linear Programming. We use these observations to derive and benchmark a new algorithm for OSFM.
The third model approaches bounded rationality from the perspective of lifelong learning (Chen and Liu, 2018). Instead of modelling the final solution, lifelong learning models how a computationally bounded agent can accumulate knowledge over time and attempt to solve tractable subproblems it encounters. We develop models for incrementally accumulating and learning knowledge in a domain agnostic setting, and use these models to give an abstract framework for a lifelong reinforcement learner. The framework attempts to make a step towards making the best of analytical performance guarantees, while still being able to make use of black box techniques such as neural networks which may perform well in practice
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
