-
Identifying regions of importance in wall-bounded turbulence through explainable deep learning
Authors:
Andres Cremades,
Sergio Hoyas,
Rahul Deshpande,
Pedro Quintero,
Martin Lellep,
Will Junghoon Lee,
Jason Monty,
Nicholas Hutchins,
Moritz Linkmann,
Ivan Marusic,
Ricardo Vinuesa
Abstract:
Despite its great scientific and technological importance, wall-bounded turbulence is an unresolved problem in classical physics that requires new perspectives to be tackled. One of the key strategies has been to study interactions among the energy-containing coherent structures in the flow. Such interactions are explored in this study for the first time using an explainable deep-learning method.…
▽ More
Despite its great scientific and technological importance, wall-bounded turbulence is an unresolved problem in classical physics that requires new perspectives to be tackled. One of the key strategies has been to study interactions among the energy-containing coherent structures in the flow. Such interactions are explored in this study for the first time using an explainable deep-learning method. The instantaneous velocity field obtained from a turbulent channel flow simulation is used to predict the velocity field in time through a U-net architecture. Based on the predicted flow, we assess the importance of each structure for this prediction using the game-theoretic algorithm of SHapley Additive exPlanations (SHAP). This work provides results in agreement with previous observations in the literature and extends them by revealing that the most important structures in the flow are not necessarily the ones with the highest contribution to the Reynolds shear stress. We also apply the method to an experimental database, where we can identify completely new structures based on their importance score. This framework has the potential to shed light on numerous fundamental phenomena of wall-bounded turbulence, including novel strategies for flow control.
△ Less
Submitted 19 February, 2024; v1 submitted 2 February, 2023;
originally announced February 2023.
-
Auditing and Achieving Intersectional Fairness in Classification Problems
Authors:
Giulio Morina,
Viktoriia Oliinyk,
Julian Waton,
Ines Marusic,
Konstantinos Georgatzis
Abstract:
Machine learning algorithms are extensively used to make increasingly more consequential decisions about people, so achieving optimal predictive performance can no longer be the only focus. A particularly important consideration is fairness with respect to race, gender, or any other sensitive attribute. This paper studies intersectional fairness, where intersections of multiple sensitive attribute…
▽ More
Machine learning algorithms are extensively used to make increasingly more consequential decisions about people, so achieving optimal predictive performance can no longer be the only focus. A particularly important consideration is fairness with respect to race, gender, or any other sensitive attribute. This paper studies intersectional fairness, where intersections of multiple sensitive attributes are considered. Prior research has mainly focused on fairness with respect to a single sensitive attribute, with intersectional fairness being comparatively less studied despite its critical importance for the safety of modern machine learning systems. We present a comprehensive framework for auditing and achieving intersectional fairness in classification problems: we define a suite of metrics to assess intersectional fairness in the data or model outputs by extending known single-attribute fairness metrics, and propose methods for robustly estimating them even when some intersectional subgroups are underrepresented. Furthermore, we develop post-processing techniques to mitigate any detected intersectional bias in a classification model. Our techniques do not rely on any assumptions regarding the underlying model and preserve predictive performance at a guaranteed level of fairness. Finally, we give guidance on a practical implementation, showing how the proposed methods perform on a real-world dataset.
△ Less
Submitted 8 June, 2020; v1 submitted 4 November, 2019;
originally announced November 2019.
-
On Restricted Nonnegative Matrix Factorization
Authors:
Dmitry Chistikov,
Stefan Kiefer,
Ines Marušić,
Mahsa Shirmohammadi,
James Worrell
Abstract:
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times d$ matrix $W$ and a nonnegative $d \times m$ matrix $H$. Restricted NMF requires in addition that the column spaces of $M$ and $W$ coincide. Finding the minimal inner dimension $d$ is known to be NP-hard, both for NMF and restricted NMF. We show…
▽ More
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times d$ matrix $W$ and a nonnegative $d \times m$ matrix $H$. Restricted NMF requires in addition that the column spaces of $M$ and $W$ coincide. Finding the minimal inner dimension $d$ is known to be NP-hard, both for NMF and restricted NMF. We show that restricted NMF is closely related to a question about the nature of minimal probabilistic automata, posed by Paz in his seminal 1971 textbook. We use this connection to answer Paz's question negatively, thus falsifying a positive answer claimed in 1974. Furthermore, we investigate whether a rational matrix $M$ always has a restricted NMF of minimal inner dimension whose factors $W$ and $H$ are also rational. We show that this holds for matrices $M$ of rank at most $3$ and we exhibit a rank-$4$ matrix for which $W$ and $H$ require irrational entries.
△ Less
Submitted 23 May, 2016;
originally announced May 2016.
-
Nonnegative Matrix Factorization Requires Irrationality
Authors:
Dmitry Chistikov,
Stefan Kiefer,
Ines Marušić,
Mahsa Shirmohammadi,
James Worrell
Abstract:
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times d$ matrix $W$ and a nonnegative $d \times m$ matrix $H$. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix $M$ always has an NMF of minimal inner dimension $d$ whose factors $W$ and $H$ are also rati…
▽ More
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times d$ matrix $W$ and a nonnegative $d \times m$ matrix $H$. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix $M$ always has an NMF of minimal inner dimension $d$ whose factors $W$ and $H$ are also rational. We answer this question negatively, by exhibiting a matrix for which $W$ and $H$ require irrational entries.
△ Less
Submitted 22 March, 2017; v1 submitted 22 May, 2016;
originally announced May 2016.
-
Minimisation of Multiplicity Tree Automata
Authors:
Stefan Kiefer,
Ines Marusic,
James Worrell
Abstract:
We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require a breakthrough in the complexity of polynomial identity testing by proving that the latter problem…
▽ More
We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require a breakthrough in the complexity of polynomial identity testing by proving that the latter problem is logspace equivalent to the decision version of minimisation. The developed techniques also improve the state of the art in multiplicity word automata: we give an NC algorithm for minimising multiplicity word automata. Finally, we consider the minimal consistency problem: does there exist an automaton with $n$ states that is consistent with a given finite sample of weight-labelled words or trees? We show that this decision problem is complete for the existential theory of the rationals, both for words and for trees of a fixed alphabet rank.
△ Less
Submitted 27 March, 2017; v1 submitted 20 October, 2014;
originally announced October 2014.
-
Complexity of Equivalence and Learning for Multiplicity Tree Automata
Authors:
Ines Marusic,
James Worrell
Abstract:
We consider the complexity of equivalence and learning for multiplicity tree automata, i.e., weighted tree automata over a field. We first show that the equivalence problem is logspace equivalent to polynomial identity testing, the complexity of which is a longstanding open problem. Secondly, we derive lower bounds on the number of queries needed to learn multiplicity tree automata in Angluin's ex…
▽ More
We consider the complexity of equivalence and learning for multiplicity tree automata, i.e., weighted tree automata over a field. We first show that the equivalence problem is logspace equivalent to polynomial identity testing, the complexity of which is a longstanding open problem. Secondly, we derive lower bounds on the number of queries needed to learn multiplicity tree automata in Angluin's exact learning model, over both arbitrary and fixed fields.
Habrard and Oncina (2006) give an exact learning algorithm for multiplicity tree automata, in which the number of queries is proportional to the size of the target automaton and the size of a largest counterexample, represented as a tree, that is returned by the Teacher. However, the smallest tree-counterexample may be exponential in the size of the target automaton. Thus the above algorithm does not run in time polynomial in the size of the target automaton, and has query complexity exponential in the lower bound.
Assuming a Teacher that returns minimal DAG representations of counterexamples, we give a new exact learning algorithm whose query complexity is quadratic in the target automaton size, almost matching the lower bound, and improving the best previously-known algorithm by an exponential factor.
△ Less
Submitted 27 November, 2014; v1 submitted 2 May, 2014;
originally announced May 2014.