Frederic Koriche

Approximating Probabilistic Explanations via Supermodular Minimization (Corrected Version) Louenas Bounia 1

Explaining in accurate and intelligible terms the predictions made by classifiers is a key challenge of eXplainable Artificial Intelligence (XAI). To this end, an abductive explanation for the predicted label of some data instance is a subset-minimal collection of features such that the restriction of the instance to these features is sufficient to determine the prediction. However, due to cognitive limitations, abductive explanations are often too large to be interpretable. In those cases, we need to reduce the size of abductive explanations, while still determining the predicted label with high probability. In this paper, we show that finding such probabilistic explanations is NP-hard, even for decision trees. In order to circumvent this issue, we investigate the approximability of probabilistic explanations through the lens of supermodularity. We examine both greedy descent and greedy ascent approaches for supermodular minimization, whose approximation guarantees depend on the curvature of the "unnormalized" error function that evaluates the precision of the explanation. Based on various experiments for explaining decision tree predictions, we show that our greedy algorithms provide an efficient alternative to the state-of-the-art constraint optimization method.

INTRODUCTION

Basically, the classification problem is to extrapolate from a set of labeled data instances a hypothesis, or classifier, that accurately predicts the labels of new, incoming data instances. Decision trees, random forests, support vector machines, and neural nets, are common examples of classifiers for which theoretical properties have been extensively studied in the machine learning literature (see e.g. Sayed [2022] for a recent survey). The spectrum of applications for these classifiers is wide, ranging from document and image classification, to customer profiling and medical diagnosis. However, with the increasing deployment of data-driven learning models in our society comes the issue of explaining predictions in human intelligible terms. As a key topic of eXplainable Artificial Intelligence (XAI), this issue is exacerbated in sensitive domains, such as cybersecurity and healthcare, where explanations are crucial for building trust and confidence in the classifier [START_REF] Guidotti | A survey of methods for explaining black box models[END_REF][START_REF] Miller | Explanation in artificial intelligence: Insights from the social sciences[END_REF][START_REF] Samek | Explainable AI: Interpreting, Explaining and Visualizing Deep Learning[END_REF][START_REF] Molnar | Interpretable Machine Learning[END_REF].

Among the various types of explanations proposed in the XAI literature, formal explanations are particularly interesting, since their soundness can be mathematically validated [Marques-Silva and Ignatiev, 2022]. Notably, when the classifier h is a Boolean function, a common explanation for predicting the output h(x) of some data instance x is a subset-minimal collection of features I such that the restriction x I of x to I determines h(x). Such an abductive explanation [START_REF] Ignatiev | Abduction-based explanations for machine learning models[END_REF], also called sufficient reason [START_REF] Darwiche | On the reasons behind decisions[END_REF], is logically sound, because x I can be viewed as a prime implicant of the hypothesis h that covers the instance x [START_REF] Shih | A symbolic approach to explaining Bayesian network classifiers[END_REF]. Although finding an abductive explanation is NP-hard in general, tractable cases have been identified for various hypothesis classes [START_REF] Marques-Silva | Explaining naive bayes and other linear classifiers with polynomial time and delay[END_REF][START_REF] Audemard | On the computational intelligibility of boolean classifiers[END_REF][START_REF] Huang | On efficiently explaining graph-based classifiers[END_REF][START_REF] Cooper | Tractability of explaining classifier decisions[END_REF].

However, the soundness of explanations is not the only criterion for clarifying in intelligible terms the predictions made by classifiers. The conciseness property is also important, since an abductive explanation involving too many features cannot be understood by human users. Indeed, in cognitive psychology, it has long been recognized that there is an upper limit on our ability to reason about simultaneously interacting elements. As conjectured by [START_REF] Miller | The magical number seven, plus or minus two: Some limits on our capacity for processing information[END_REF], this limit is seven plus or minus two elements and, since then, it has been confirmed by many experiments in cognitive science. Thus, restricting the size of explanations appears as a constraint for ensuring their intelligibility.

Based on these considerations, how can we reduce the size of explanations while retaining much of their soundness? This is where probabilistic explanations [START_REF] Wäldchen | The computational complexity of understanding binary classifier decisions[END_REF] come into the equation. Namely, suppose we are given an abductive explanation I for a classifier h and some instance x, together with a size limit k ≤ |I|. For any candidate subset S of I, let ϵ h,x (S) denote the probability that a random instance y covered by x S is classified differently from x by h. In other words, ϵ h,x (S) is the probability of making an "explanation mistake" for inferring h(x), using x S instead of x. With this notion in hand, the main problem considered in this study is to find a probabilistic explanation S ⊆ I of size at most k such that ϵ h,x (S) is minimized.

Unfortunately, this optimization task is very expensive from a computational viewpoint. Indeed, the problem of finding a minimizer S of ϵ h,x (•) subject to some cardinality constraint |S| ≤ k is NP PP -hard for general classifiers [START_REF] Wäldchen | The computational complexity of understanding binary classifier decisions[END_REF], and NP-hard for decision trees [START_REF] Arenas | On computing probabilistic explanations for decision trees[END_REF]. As shown in the present study, this problem remains NP-hard for decision trees even in the restricted case where S is a subset of some given abductive explanation I.

In order to overcome such a computational barrier, this paper investigates the approximability of probabilistic explanations through the lens of supermodularity. As ϵ h,x (S) can be viewed as the number µ h,x (S) of mistakes induced from the choice of S, averaged over the number of instances covered by x S , our results exploit two key properties: (i) the unnormalized error function µ h,x (•) is supermodular and non-increasing, and (ii) the normalization factor is constant for all subsets S with the same size. Thus, even if ϵ h,x (•) is not supermodular, we can still use approximation algorithms for supermodular minimization, by coupling them with a level-wise selection method, in order to derive probabilistic explanations endowed with approximation guarantees.

To this point, it is well-known that the task of maximizing a non-decreasing submodular function subject to a cardinality constraint is (1 -1 e )-approximable [START_REF] Nemhauser | Best algorithms for approximating the maximum of a submodular set function[END_REF]. The situation is however different for minimizing non-increasing supermodular functions: the problem is not approximable to within a constant, unless P = NP [START_REF] Mittal | An FPTAS for optimizing a class of low-rank functions over a polytope[END_REF]. Still, approximation factors can be provided by taking into account the curvature of the objective function [START_REF] Victor | An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function[END_REF], Sviridenko et al., 2017].

In this paper, we present two conceptually simple and easyto-implement algorithms, whose approximation factors depend on the curvature c of the function µ h,x (•). Both algorithms are empirically compared with the constraint-based approach suggested in [START_REF] Arenas | On computing probabilistic explanations for decision trees[END_REF], which aims at inferring optimal probabilistic explanations for decision tree predictions. Experimental results indicate that our greedy algorithms can efficiently find accurate explanations and, unlike the constraint-based approach, they are able to scale up on high-dimensional explanation tasks. This paper is organized as follows. The main concepts relating to probabilistic explanations and supermodular minimization are introduced in Section 2 and Section 3, respectively. Our approximation algorithms are theoretically analyzed in Section 4, and empirically validated in Section 5. Finally, the related work and some perspectives of further research are discussed in Section 6.

Corrected Version. This revised version corrects several typos and provides a corrected bound for the approximation factor in the proof of Proposition 5, which was flawed in the original version [START_REF] Bounia | Approximating probabilistic explanations via supermodular minimization[END_REF].

PROBABILISTIC EXPLANATIONS

In this section, we start with some background about probabilistic explanations, and then, we examine some computational aspects related to their evaluation and optimization.

NOTATION AND PROBLEM FORMULATION

For a positive integer d, we use [d] to denote the set {1, • • • , d}. The classifiers under consideration in this study are hypotheses of the form h : {0, 1} d → {0, 1}. Thus, any input of h is d-dimensional Boolean vector x, called instance, and the output of h(x) is a Boolean value, classifying x as a negative example or a positive one. A partial instance is a vector z ∈ {0, 1, * } d , where z i = * indicates that the ith feature of z is left undefined. An instance x is covered by z, if x i = z i for all features i ∈ [d] such that z i ̸ = * . For a subset S ⊆ [d], the restriction of x to S, denoted x S , is the partial instance in {0, 1, * } d such that, for each i ∈ [d], (x S ) i = x i if i ∈ S, and (x S ) i = * otherwise. Clearly, any instance y ∈ {0, 1} d is covered by x S if and only if y S = x S .

Given a classifier h, and an instance x for which the prediction h(x) must be explained, let ϵ h,x : 2 [d] → R denote the error function given by

ϵ h,x (S) = |{y ∈ {0, 1} d : h(y) ̸ = h(x), y S = x S }| |{y ∈ {0, 1} d : y S = x S }| (1)
As indicated above, ϵ h,x (S) can be thought as the probability of making an "explanation mistake" when using the partial instance x S instead of the complete instance x. Given a precision parameter ε ∈ [0, 1], an explanation S is called

(1 -ε)-probable if ϵ h,x (S) ≤ ε.
We say that S is abductive if ϵ h,x (S) = 0, and ϵ h,x (S ′ ) > 0 for every proper subset S ′ of S. Note that (1) can be rewritten as

ϵ h,x (S) = µ h,x (S) 2 d-|S| (2)
where µ h,x (S) is the number of mistakes induced from the choice of S, that is,

µ h,x (S) = |{y ∈ {0, 1} d : h(y) ̸ = h(x), y S = x S }| (3) {1, 2} {1, 3} {2, 3} {1} {2} {3} {∅} {1, 2, 3} 0 0 1 2 1 1 2 1 1 2 1 3 4 3 3 4 3 1 2 2 5 8
5

Figure 1: The error ϵ h,x (S) (in blue) and the number of mistakes µ h,x (S) (in magenta) for each S ⊆ [3], using the classifier h given by (4) and the instance x = (1, 1, 1).

Example 1. Consider the classifier h : {0, 1} 3 → {0, 1} specified by the polynomial threshold function:

h(x) = 1 ⇔ x 1 x 2 x 3 + x 1 x 2 -x 1 -x 2 ≥ 0 (4)
Given the instance x = (1, 1, 1) for which we need to explain h(x) = 1, and using the Hasse diagram in Figure 1, it follows that {1, 2, 3} is the only abductive explanation for h and x. Yet, {1, 2} and {3} are both subset-minimal 1 2 -probable explanations for h and x.

With these notions in hand, we are now in position to formulate the main problem considered in this study.

Problem 1. Given a classifier h : {0, 1} d → {0, 1}, an instance x ∈ {0, 1} d , a set I ⊆ [d] of features, a size limit k ≤ |I|, find a subset S ⊆ I of size at most k such that ϵ h,x (S) is minimized.

EVALUATING EXPLANATION ERRORS

It is easy to see that the problem of evaluating ϵ h,x (S) is #P-hard in general. However, Izza et al. [2022a] have shown that ϵ h,x (S) can be computed in polynomial time, when h is described by a decision tree. For completeness, we show here that ϵ h,x (S) can be evaluated in linear time for decision trees, using the orthogonality of decision trees, and the fact this property is closed under conditioning.

To this end, recall that a (Boolean) decision tree is a binary tree T , each of whose internal nodes is labeled with one of d Boolean variables from

X d = {x 1 , • • • , x d },
and whose leaves are labeled 0 or 1. The value h(x) ∈ {0, 1} of a hypothesis h described by T on an instance x is given by the label of the leaf reached from the root of T as follows: at each node, go to the left or right child depending on whether the input value of the corresponding variable is 0 or 1, respectively. The size of T , denoted |T |, is given by the number of nodes in T . For illustration, a decision tree representing the classifier ( 4) is given in Figure 2.

x 1

x 2

1 0 0 1 0 x 2 0 0 x 3 0 0 1 1 1 1 Figure 2: A decision tree representation of (4).
As usual, a literal over X d is a variable x i , or its negation x i .

The negation of a literal l is given by ¬l = x i if l = x i , and ¬l = x i if l = x i . A a term is a conjunction of literals, and a Disjunctive Normal Form (DNF) formula is a disjunction of terms. Here, DNF formulas are viewed as sets of terms, and terms are viewed as sets of literals. A term is inconsistent if includes a pair {l, ¬l} of opposite literals. A DNF formula

F = {t 1 , • • • , t m } is orthogonal if t i ∪ t j is inconsistent for all pairs i, j ∈ [m] such that i ̸ = j.
The conditioning [START_REF] Darwiche | Compiling knowledge into decomposable negation normal form[END_REF] of F by a term t, denoted F | t, is the formula obtained by removing from Proof. It is well-known that T can be transformed in linear time into an equivalent orthogonal DNF formula, denoted DNF(T ), where each term corresponds to a path from the root to a leaf labeled with 1. Given an instance x ∈ {0, 1} d and a set S of features, let t x S be the term associated with the partial instance x S , that is,

{t 1 ∪ t, • • • , t m ∪ t} any term that is inconsistent. Proposition 1. Given a classifier h : {0, 1} d → {0,
t x S = d i=1 {x i : (x S ) i = 1} ∪ {x i : (x S ) i = 0}
By construction, DNF(T ) | t x S is orthogonal and hence, for decision trees, (3) can simply be rewritten as:

µ h,x (S) = t∈DNF(T )|tx S 2 d-|t| if h(x) = 1 2 d -t∈DNF(T )|tx S 2 d-|t| if h(x) = 0
The result follows from (2), together with the fact that

DNF(T ) | t x S can be derived in O(|S| • |T |) time.

MINIMIZING EXPLANATION ERRORS

The next result shows that the decision version of Problem 1 is generally hard to solve for decision trees, even when the set I of candidate features is an abductive explanation.

x 0

T 1 0 x 1 0 0 . . . 0 0 x d 0 0 1 1 1 1 1 Figure 3:
The decision tree T 2 in the proof of Proposition 2.

Proposition 2. Given a classifier h represented by some decision tree T , an instance x ∈ {0, 1} d , an abductive explanation I ⊆ [d] for h and x, an integer k ≤ |I|, and a threshold ε ∈ (0, 1), the problem of finding a subset S ⊆ I of size at most k satisfying ϵ h,x (S) ≤ ε is NP-hard.

Proof. Let P 2 denote the above problem. Our goal is to give a polynomial-time reduction of P 1 to P 2 , where P 1 is the following problem:

Given a classifier h represented by some decision tree T , an instance x ∈ {0, 1} d , and an integer k ≤ d, find a subset S ⊆ [d] such that |S| ≤ k and ϵ h,x (S) = 0.

As shown in [START_REF] Barceló | Model interpretability through the lens of computational complexity[END_REF], this problem is NP-hard. Consider an instance (T 1 , x 1 , k 1 ) of P 1 , and let h 1 be he hypothesis associated with T 1 . Without loss of generality, we assume that x 1 is the d-dimensional all-ones vector 1 and h 1 (x 1 ) = 1. We construct an instance (T 2 , x 2 , I, k 2 , ε) of P 2 in the following way. The decision tree T 2 is defined according to Figure 3. Specifically, the root node of T 2 is labeled with x 0 , the subtree rooted at the left child of x 0 is the decision tree T 1 , and the subtree rooted at the right child of x 0 is the caterpillar encoding the conjunction

x 1 ∧ • • • ∧ x d .
The remaining components of the problem instance are given as follows: x 2 is the all-ones vector

1 over {0, 1, • • • , d}, I = {1, • • • , d}, k 2 = k 1 and ε = 1 - 1 2 d+1-k
To ease the notation, we use x instead of x 2 in the remaining proof. For i ∈ {0, • • • , d}, let x 0←i be the instance in {0, 1} d+1 obtained by flipping the value x i and leaving all other values of x unchanged. Let x ′ be the instance obtained from x by flipping the value of the first entry (i.e. x ′ = x 0←0 ). Since h 2 (x) = 1, h 2 (x ′ ) = 1, and h 2 (x 0←i ) = 0 for every i ∈ {1, • • • , d}, it follows that I is an abductive explanation for h 2 and x. Now, let us decompose the error function into the left child and the right child of the root x 0 :

ϵ h2,x2 (S) = |{y ∈ {0, 1} d+1 : h 2 (y) = h 2 (x), y S = x S }| |{y ∈ {0, 1} d+1 : y S = x S }| = ϵ (l) (S) + ϵ (r) (S)
where

ϵ (l) (S) = |{y ∈ {0, 1} d+1 : h 2 (y) = h 2 (x), y S = x S , y 0 = 0}| |{y ∈ {0, 1} d+1 : y S = x S }| = |{z ∈ {0, 1} d : h 1 (z) = h 1 (x 1 ), z S = (x 1 ) S }| 2|{z ∈ {0, 1} d : z S = (x 1 ) S }| = ϵ h1,x1 (S) 2
and where

ϵ (r) (S) = |{y ∈ {0, 1} d+1 : h 2 (y) = h 2 (x), y S = x S , y 0 = 1}| |{y ∈ {0, 1} d+1 : y S = x S }| = 1 - 1 2 d+1-|S| Note that ϵ (r) is monotonically decreasing with the size of S. Notably, ϵ h2,x2 (S) > ε whenever |S| < k. Thus, ϵ h2,x2 (S) ≤ ε if and only if |S| = k and ϵ h1,x1 (S) = 0. With this result in hand, if S ⊆ I is a solution to P 2 , then S is a solution to P 1 , since I = [d].
Dually, if there are no solutions S ⊆ I of size k to P 2 , then there are no solutions S ′ ⊆ [d] of size at most k to P 1 , since ϵ h1,x1 (S) > 0 implies ϵ h1,x1 (S ′ ) > 0 whenever S ′ ⊆ S. Therefore, solving P 2 in polynomial time implies that P 1 can be solved in polynomial time, which contradicts the fact that P 1 is NP-hard.

SUPERMODULAR MINIMIZATION

The main idea of this study is to relax the requirement of finding an optimal solution to Problem 1, and instead settle for a solution that is "good enough", using supermodular minimization algorithms. In this section, we start with some basic notions about supermodularity, and then, we examine some useful properties of the mistake function.

SUPERMODULAR FUNCTIONS

Given a real-valued set function f : 2 [d] → R, the quantities

L f (i | S) = f (S \ {i}) -f (S), and
G f (i | S) = f (S ∪ {i}) -f (S)
are respectively capturing the marginal loss of removing an element i from a set S, and marginal gain of adding an element i to a set S.

A set function f is non-increasing if L f (i | S) ≥ 0 for all S ⊆ [d] and i ∈ S, and f is non-decreasing if G f (i | S) ≥ 0 for all S ⊆ [d] and i ∈ [d] \ S. A set function f is supermodular if it satisfies the diminishing loss condition L f (i | S) ≥ L f (i | T ) for all S ⊆ T ⊆ [d] and i ∈ S. Dually, f is submodular if it satisfies the diminishing gain condition G f (i | S) ≥ G f (i | T ) for all S ⊆ T ⊆ [d] and i ∈ [d] \ T . Based on the fact that L f (i | S) = -G f (i | S \ {i}) for all S ⊆ [d] and i ∈ S, f is supermodular if and only if -f is submodular. Finally, f is modular if it is both submodular and supermodular.
For a non-negative set function f and a nonempty subset

I ⊆ [d], the curvature of f over 2 I is given by c = 1-min i∈I L f (i | I) L f (i | {i}) = 1-min i∈I G f (i | I \{i}) G f (i | ∅) (5)
Clearly, c ∈ [0, 1] whenever f is non-decreasing and submodular, or non-increasing and supermodular. Note that the curvature coincides with the notion of "steepness" defined in [START_REF] Victor | An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function[END_REF]. [START_REF] Conforti | Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the radoedmonds theorem[END_REF]. Notably, in the case where f is non-increasing and supermodular, the condition c < 1 is sufficient for ensuring that the task of minimizing f subject to a cardinality constraint is approximable to within a constant [START_REF] Victor | An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function[END_REF], Sviridenko et al., 2017].

When I = [d], c is called the total curvature of f [Conforti

MINIMIZING EXPLANATION MISTAKES

In general, the error function ϵ h,x (•) is not supermodular or submodular, and not non-increasing or non-decreasing.

Yet, if we instead focus on the unnormalized version µ h,x (•) given in (3), then the following properties can be derived.

(i | T ) ≤ L f (i | S)
. Therefore, f is supermodular.

Algorithm 1: Greedy Descent (GD)

Input: classifier h, instance x, feature set I, integer k Set S n = I, where n = |I| For j = n downto 1 do Let i * ∈ Argmin i∈Sj µ h,x (S j \ {i}) Set S j-1 = S j \ {i * } Let S GD ∈ Argmin S∈{S0,S1,••• ,S k } ϵ h,x (S)
Return S GD Finally, L f (i | I) > 0 whenever I is a (non-empty) abductive explanation for h and x. This, together with the fact that, by supermodularity, L f (i | {i}) ≥ L f (i | I) for any i ∈ I, implies that c ∈ [0, 1).

APPROXIMATION ALGORITHMS

After providing an overview of probabilistic explanations and supermodular minimization, we now present two greedy approximation algorithms for Problem 1.

GREEDY DESCENT

A natural approach for minimizing a supermodular and non-increasing function f subject to a cardinality constraint |S| ≤ k is to start from the input set I of candidate features, and to iteratively remove from the current solution S any feature i that minimizes the marginal loss L f (i | S), until the desired size |S| = k is reached. As shown by Il'ev [2001], this greedy method achieves a e p -1 p -approximation, where p = c 1-c , and c is the curvature of f over 2 I . In the setting of our study, the error function ϵ h,x (•) in ( 2) is a normalized version of µ h,x (•), which is supermodular and non-increasing. Furthermore, the normalization factor 2 d-|S| is constant for all subsets S with the same size. Based on these properties, we can combine the above greedy descent approach for f = µ h,x (•), with a level-wise selection method that stores the subsets S 0 , S 1 , • • • , S k obtained for each size j ∈ {0, 1, • • • , k}, and that returns from this sequence the best subset S j with respect to ϵ h,x (•). A formal description is given in Algorithm 1.

Proposition 4. Let S * be an optimal solution to Problem 1, let c be the curvature of µ h,x (•) over 2 I , and assume that I is an abductive explanation for h and x. Then, the solution S GD returned by Greedy Descent (GD) satisfies:

ϵ h,x (S GD ) ≤ e p -1 p ϵ h,x (S * ) where p = c 1 -c < ∞
Proof. The fact that p < ∞ follows from Proposition 3. Let j * be the size of S * , and let S j * be the solution computed

Algorithm 2: Greedy Ascent (GA)

Input: classifier h, instance x, feature set I, integer k Let c be the curvature of µ h,x (•) over 2 I Set j = 0, S 0 = ∅ and γ = max 1 e , c Repeat Let i * ∈ Argmin i∈I\Sj-1 µ h,x (S j-1 ∪ {i}) Set S j = S j-1 ∪ {i * } Until j = k ln µ h,x (∅) γ • µ h,x (S j ) Let S GA ∈ Argmin S∈{S0,S1,••• ,Sj } ϵ h,x (S)
Return S GA by GD at the end of the step j = n -j * + 1. Note that |S * | = |S j * |. So, by application of Corollary 4 in [START_REF] Victor | An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function[END_REF], we must have

µ h,x (S j * ) ≤ e p -1 p µ h,x (S * ) Since GD is returning a minimizer of ϵ h,x (•) over the se- quence S 0 , • • • , S j * , • • • , S k , it follows that ϵ h,x (S GD ) ≤ ϵ h,x (S j * ) = µ h,x (S j * ) 2 d-j * ≤ e p -1 p µ h,x (S * ) 2 d-j * = e p -1 p ϵ h,x (S * )

GREEDY ASCENT

An alternative approach is to consider the objective function f = -µ h,x (•), which is submodular and non-decreasing.

Based on the well-known greedy method for submodular maximization [START_REF] Nemhauser | Best algorithms for approximating the maximum of a submodular set function[END_REF], we could start from S 0 = ∅, and iteratively add to the current solution S j-1 any maximizer i ∈ I \ S j-1 of the marginal gain

G f (i | S j-1 ) until |S j | = k.
Unfortunately, such a method would fail here because f is non-positive. Yet, as observed by [START_REF] Liberty | Greedy minimization of weakly supermodular set functions. In Approximation, Randomization, and Combinatorial Optimization[END_REF], this issue can be alleviated by slightly increasing the size limit k. More precisely, given a parameter γ ∈ (0, 1), the greedy method achieves a 1 1-γ -approximation, whenever it is allowed to improve its solution S j-1 until |S j | = k⌈ln ( f (∅) /γf(Sj-1))⌉. By coupling this idea with the level-wise selection method suggested above, we get a greedy ascent algorithm for minimizing ϵ h,x (•), detailed in Algorithm 2.

Proposition 5. Under the conditions of Proposition 4, the solution S GA returned by Greedy Ascent (GA) satisfies:

ϵ h,x (S GA ) ≤ 2 k⌈ln 2e 1-c ⌉-|S * | • 1 1 -γ • ϵ h,x (S * ),
where γ = max 1 e , c , and

|S GA | ≤ k 1 + ln µ h,x (∅) µ h,x (S * ) ≤ k ln 2e 1 -c
Proof. We start by providing an upper bound on the size of S GA . By application of Theorem 5 in [START_REF] Liberty | Greedy minimization of weakly supermodular set functions. In Approximation, Randomization, and Combinatorial Optimization[END_REF], we have

|S GA | ≤ k ln µ h,x (∅) γµ h,x (S * ) ≤ k 1 + ln µ h,x (∅) µ h,x (S * )
where the last inequality follows from γ ≥ 1 e . On the other hand, since I is an abductive explanation, we know that µ h,x (I) = 0 and µ h,x (I \ {i}) = 1 for every i ∈ I. Thus, the curvature of µ h,x (•) over

2 I satisfies c = 1 -min i∈I L f (i | I) L f (i | {i}) = 1 - 1 µ h,x (∅) -min i∈I µ h,x ({i})
By rearranging this equation and using the fact that min i∈I µ h,x ({i}) ≤ 1 2 µ h,x (∅), we obtain

1 1 -c = µ h,x (∅) -min i∈I µ h,x ({i}) ≥ 1 2 µ h,x (∅)
Plugging this result into the bound on the size of S GA and using the fact that µ h,x (S * ) ≥ 1, we have

|S GA | ≤ k 1 + ln µ h,x (∅) µ h,x (S * ) ≤ k ln 2e 1 -c
With this result in hand, we can now focus on ϵ h,x (S GA ). By combining Theorem 5 in [START_REF] Liberty | Greedy minimization of weakly supermodular set functions. In Approximation, Randomization, and Combinatorial Optimization[END_REF] with the fact that S GA is a minimizer of

ϵ h,x (•) over {S 0 , • • • , S j }, we have ϵ h,x (S GA ) ≤ ϵ h,x (S j ) = µ h,x (S j ) 2 d-j ≤ 1 1 -γ µ h,x (S * ) 2 d-j
Thus, using

2 d-j = (2 d-|S * | )(2 |S * |-j
) together with the upper bound found for j = |S GA |, it follows that

ϵ h,x (S GA ) ≤ 1 1 -γ µ h,x (S * ) (2 d-|S * | )(2 |S * |-j ) = 1 1 -γ 2 j-|S * | ϵ h,x (S * ) ≤ 1 1 -γ 2 k⌈ln 2e 1-c ⌉-|S * | ϵ h,x (S * )

APPLICATION TO DECISION TREES

The approximation bounds derived in Propositions 4 and 5 hold for any (Boolean) hypothesis class. However, in order to ensure that GD and GA are computationally efficient, each call to the value oracle µ h,x (•) should run in polynomial time. As emphasized in Section 2.2, this is the case for decision trees. Namely, if the input classifier h of GD is represented by a decision tree T , then by Proposition 1 and the fact that the number of calls to the value oracle is quadratic in n = |I|, implies that GD runs in O(n 3 |T |) time.

For GA, the number of calls to the value oracle is bounded by jn + n + 2, where j is the number of iterations of the main loop, and n + 2 is the number of calls required to compute c. So, GA runs in O(kn 2 (1 + ln 2 /c)|T |) time.

EXPERIMENTS

In order to validate the effectiveness of our algorithms, we have considered various instances of Problem 1, where the input classifier is described by a decision tree. The code was written using the Python language. All the experiments have been conducted on a computer equipped with a 3.1 GHz Intel(R) Core i9-9900 CPU and 64 GiB of RAM.

EXPERIMENTAL SETUP

In our experiments, we have considered B = 50 datasets, or benchmarks, from the standard repositories Kaggle, OpenML and UCI. Notably, mnist38 and mnist49 are subsets of the dataset mnist. Except for cnae, all datasets are binary classification tasks with a number of attributes ranging from 101 to 10 5 . The multi-label classification task cnae was transformed into a binary classification task by considering the dominant label versus all other labels.

For each benchmark b ∈ [B], an explanation task consists in a tuple (T , x, I, k) described as follows. T is the decision tree representation of some classifier h, which is learned from the training part of b. In our experiments, we have used a Scikit-Learn implementation of the CART algorithm for generating T . The predictive accuracy of h is measured on the test part of b. By interpreting each internal node of T as a Boolean feature, the instance x to be explained is taken from the test part of b, and binarized according to the d features occurring in T . The set I is given by the collection of features occurring in the (single) root-to-leaf path in T that is consistent with the instance x. Here, I is often referred to as a path-explanation [Izza et al., 2022b], or direct reason [Audemard et al., 2022a]. As observed in [Izza et al., 2022b], I is not necessarily minimal with respect to set inclusion. Finally, we have used k = 7 ± 2 for the size limit. The performance of explanation algorithms on a benchmark b is measured by drawing uniformly at random m instances x from the test set of b, and averaging the resulting error ϵ h,x (S) and size |S| of the output S ⊆ I. In our experiments, m was set to min{s, 150}, where s is the size of the test set of b.

To compare the performance of GD and GA with an exact solver, we have chosen the SAT-based approach in [START_REF] Arenas | On computing probabilistic explanations for decision trees[END_REF]. Namely, a SAT encoding was provided for the following task: given as input a decision tree T for some classifier h, an instance x, and two parameters k ≤ d and ε ∈ [0, 1), return as output "yes" if there is a set of features S satisfying both |S| ≤ k and ϵ h,x (S) ≤ ε, and "no" otherwise. In the setting of our experimental setup, S is a subset of the path-explanation I for x. So, the above SAT encoding was extended to the decision version of Problem 1, by adding the clause {x i : (x

I ) i = 1} ∨ {x i : (x I ) i = 0}.
For the original version of Problem 1, a binary search over the interval (0, 1] was performed in order to find a minimizer S of ϵ h,x (•) with precision of 10 -3 , which requires at most 10 calls to the SAT solver. We used a Pysat implementation of GLUCOSE 4 for the solver, with a timeout of 30 minutes per explanation task. 1

EXPERIMENTAL RESULTS

In Table 1 is reported an overview of our results on 25 of 50 benchmarks, for k = 7. The leftmost column gives the name of the dataset b. The columns acc and d are respectively giving the accuracy and the number of features of the decision tree. The rows are sorted according to the average size |I| of the path-explanation. The fifth, sixth, and seventh columns are reporting the results for the average error ϵ h,x (S) of the explanation S returned by GA, GD, and the SAT-based approach, respectively. The next three columns are reporting the average size of S for these algorithms. Finally, the last column gives the average run-times (in seconds) of the SAT-based approach. Notably, for the 7 datasets in blue, the SAT solver occasionally reaches the timeout before the end of binary search, which results in a degradation of precision.

For the 8 datasets in magenta, the solver could not perform a single run of binary search before reaching the timeout.

We have not reported the run-times of GA and GD, because they could always find a solution in less than 0.1 seconds.

In light of these results, we can observe that the performance of greedy algorithms for minimizing ϵ h,x (•) is remarkable, especially in comparison with the performance of the SAT-based approach. For the benchmarks where the SAT solver could return an optimal solution S * , the differences ϵ h,x (S GD ) -ϵ h,x (S * ) and ϵ h,x (S GA ) -ϵ h,x (S * ) are most often negligible. Moreover, for high-dimensional datasets such as dorothea, gisette and farm ads, both GA and GD remain stable by providing explanations with comparable errors in a few tenths of a millisecond. Regarding

DISCUSSION

Related Work. Clarifying in a comprehensible way the prediction h(x) made by some classifier h on an input data instance x often takes the form of a set I of features which in conjunction determine h(x) [START_REF] Túlio Ribeiro | Anchors: High-precision model-agnostic explanations[END_REF]. Such an explanation is abductive [START_REF] Ignatiev | Abduction-based explanations for machine learning models[END_REF], or sufficient [START_REF] Darwiche | On the reasons behind decisions[END_REF], precisely when I is minimal with respect to inclusion. The problem of finding abductive explanations has been a subject of extensive research, recently surveyed in [Marques-Silva and Ignatiev, 2022]. The hypothesis classes which are tractable for computing abductive explanations include, among others, decision trees [START_REF] Audemard | On the computational intelligibility of boolean classifiers[END_REF][START_REF] Huang | On efficiently explaining graph-based classifiers[END_REF], Izza et al., 2022b], Naive Bayes classifiers [START_REF] Marques-Silva | Explaining naive bayes and other linear classifiers with polynomial time and delay[END_REF], monotone threshold functions [START_REF] Cooper | Tractability of explaining classifier decisions[END_REF],

and Boolean functions compiled into deterministic Decomposable Negation Normal Form (dDNNF) [START_REF] Audemard | On tractable XAI queries based on compiled representations[END_REF], Huang et al., 2022]. Actually, even when the problem of finding an abductive explanation is NP-hard, empirical results indicate that it can often be solved in practice using SAT-based approaches [START_REF] Ignatiev | SAT-based rigorous explanations for decision lists[END_REF], Izza and Marques-Silva, 2021, Ignatiev et al., 2022].

However, due to cognitive limitations, a major weakness of abductive explanations is their uncontrollable size. In order to circumvent this issue, a common approach is to seek for abductive explanations of minimum size. Unfortunately, the corresponding optimization problem is NP-hard for decision trees [START_REF] Barceló | Model interpretability through the lens of computational complexity[END_REF], and Σ p 2 -hard in general [Audemard et al., 2022b]. Furthermore, even if shortest abductive explanations could be found in a reasonable amount of time, their size remains uncontrollable.

By capturing a natural trade-off between conciseness and precision, probabilistic explanations have been a subject of growing research in the past two years [START_REF] Blanc | Provably efficient, succinct, and precise explanations[END_REF], Izza et al., 2021[START_REF] Wäldchen | The computational complexity of understanding binary classifier decisions[END_REF][START_REF] Wang | Probabilistic sufficient explanations[END_REF][START_REF] Arenas | On computing probabilistic explanations for decision trees[END_REF], Izza et al., 2022a[START_REF] Wäldchen | Towards Explainable Artificial Intelligence -Interpreting Neural Network Classifiers with Probabilistic Prime Implicants[END_REF]. Recall that a size-k (1-ε)-probable explanation for a classifier h and an instance x is a subset S ⊆ [d] such that |S| ≤ k and ϵ h,x (S) ≤ ε. Finding such explanations is NP PP -hard in general [START_REF] Wäldchen | The computational complexity of understanding binary classifier decisions[END_REF][START_REF] Wäldchen | Towards Explainable Artificial Intelligence -Interpreting Neural Network Classifiers with Probabilistic Prime Implicants[END_REF], and NP-hard for decision trees [START_REF] Arenas | On computing probabilistic explanations for decision trees[END_REF]. In the present study, we have shown that this problem remains NP-hard for decision trees, even under the assumption that S is a subset of some given abductive explanation I.

Heuristic approaches to probabilistic explanations have been considered in [Izza et al., 2021[Izza et al., , 2022a]]. The optimization task is symmetric to that of Problem 1: given a hypothesis h, an instance x, a set of features I and an error parameter ε, the goal is to find a (1 -ε)-probable explanation S ⊆ I that minimizes |S|. For this task, the authors have proposed a greedy algorithm that runs in polynomial time, when h is described by a decision tree T , and I is a path-explanation for x and T . However, this algorithm does not provide any approximation guarantee with respect to the optimal size.

To the best of our knowledge, approximation approaches to probabilistic explanations have only been investigated in [START_REF] Blanc | Provably efficient, succinct, and precise explanations[END_REF]. Again, the problem under consideration is to find a (1 -ε)-probable explanation S that minimizes |S|. Based on some results on implicit learning, the authors gave a PAC-style polynomial-time algorithm that takes as input a classifier h, an instance x, a confidence parameter δ, and a precision parameter ε, and that returns as output a set S ⊆ [d] with the following guarantees: (i) |S| is polynomial in d, 1 /δ and 1 /ε, and (ii) if x is drawn uniformly at random over {0, 1} d , then ϵ h,x ≤ ε with probability at least (1 -δ). However, this algorithm is mainly of theoretical interest, since |S| is in O ( 1 /δ) 9 ( 1 /ϵ) 12 and, more importantly, the instances to be explained in practical applications are rarely picked at random according to the uniform distribution.

Perspectives. In our study, probabilistic explanations have been examined through the prism of supermodular minimization. Inspired from results in [Il'ev, 2001, Liberty andSviridenko, 2017], we have proposed two greedy approximation algorithms for minimizing explanation errors subject to a cardinality constraint, whose performance essentially depends on the curvature c of the unnormalized error function µ h,x (•). Importantly, our approximation results hold for any (Boolean) hypothesis class, and hence, our greedy algorithms are computationally efficient whenever µ h,x (•) can be evaluated in polynomial time. Beyond decision trees, which have been examined in this paper, (ordered) binary decision diagrams [START_REF] Hu | Optimizing binary decision diagrams with MaxSAT for classification[END_REF] and dDNNF representations [START_REF] Huang | Tractable explanations for d-dnnf classifiers[END_REF] are examples of classifiers satisfying this condition.

This work leaves open several questions. Notably, (i) what is the optimal approximation factor for minimizing the error of probabilistic reasons under a cardinality constraint? A partial answer might come from [START_REF] Sviridenko | Optimal approximation for submodular and supermodular optimization with bounded curvature[END_REF], who gave a near-optimal algorithm for minimizing a nonincreasing supermodular function subject to a matroid constraint. But this method is mainly of theoretical interest, as its computational complexity is prohibitive. So, (ii) can we find alternative, near-optimal approximation algorithms which are computationally efficient? Finally, (iii) using sam-pling methods, can we extend approximation algorithms to hypothesis classes for which the problem of evaluating µ h,x (•) is intractable?

  1} represented by some decision tree T , an instance x ∈ {0, 1} d , and a set of features S ⊆ [d], evaluating ϵ h,x (S) can be done in O(|S| • |T |) time.

Proposition 3 .

 3 Let h : {0, 1} d → {0, 1} be a classifier, x ∈ {0, 1} d be an instance, and I ⊆ [d] be any nonempty set of features. Then, µ h,x (•) is supermodular and non-increasing. Furthermore, if I is an abductive explanation for h and x, then the curvature c of µ h,x (•) over 2 I satisfies c < 1.Proof. Let f be the function µ h,x (•), and N be the set of instances y ∈ {0, 1} d such that h(x) ̸ = h(y). For any subset S ⊆ [d], let C(x S ) denote the set of instances y ∈ {0, 1} d covered by x S , and for any feature i ∈ S, let C(x S\{i} ) denote the set C(x S\{i} ) \ C(x S ). The fact that f is non-increasing directly follows from the observation that L f (i | S) = |C(x S\{i} ) ∩ N | ≥ 0 for any S ⊆ [d] and any i ∈ S. Now, given any superset T of S, we have C(x T \{i} ) ⊆ C(x S\{i} ). It follows that C(x T \{i} ) ∩ N ⊆ C(x S\{i} ) ∩ N , and hence, L f

Table 1 :

 1 Experimental results on 25 benchmarks for decision tree explanations, using k = 7.the conciseness of explanations, we can see that |S GD | is on average smaller than |S * |. Interestingly, |S GA | is on average smaller than the size limit k = 7, which indicates that the upper bound on |S GA | in Proposition 5 is rarely attained in practice. Finally, GA and GD could efficiently reduce pathexplanations I which are not always abductive. In other words, both algorithms are, in practice, robust enough to handle some explanation tasks for which the curvature c of the unnormalized error function is close to or equal to 1.

		Benchmark				ϵ h,x (S)			|S|		Time (s)
	name	acc	d	|I|	GA	GD	SAT	GA	GD	SAT	SAT
	meta-data	87.42	44	5.09	0.08 (±0.11) 0.08 (±0.11) 0.08 (±0.11)	3.10 3.10 3.10	12.14
	glass	78.46	31	5.38	0.26 (±0.11) 0.26 (±0.11) 0.26 (±0.11)	2.14 2.14 2.14	2.36
	student perf.	91.79	30	5.41	0.26 (±0.11) 0.26 (±0.11) 0.26 (±0.11)	2.00 2.00 2.00	2.16
	primary tumor 84.31	23	6.23	0.09 (±0.09) 0.09 (±0.09) 0.09 (±0.08)	4.22 4.22 4.22	3.58
	liver disorders 75.96	58	6.38	0.18 (±0.09) 0.18 (±0.08) 0.18 (±0.08)	4.00 4.00 4.00	27.33
	schizophrenia	80.39	33	6.39	0.37 (±0.24) 0.37 (±0.24) 0.37 (±0.24)	1.27 1.27 1.27	4.79
	hungarian	62.92	13	6.65	0.12 (±0.12) 0.12 (±0.12) 0.11 (±0.10)	3.58 3.56 3.56	1.68
	horse colic	75.68	40	6.73	0.14 (±0.07) 0.13 (±0.07) 0.13 (±0.07)	4.03 4.06 4.06	11.56
	indian liver	64.57	84	8.21	0.10 (±0.09) 0.10 (±0.09) 0.16 (±0.12)	5.08 4.89 6.12	176.28
	pima indians	75.32	97	8.30	0.15 (±0.14) 0.15 (±0.14) 0.16 (±0.12)	5.85 5.84 6.58	484.6
	loan eligibility 74.31	68	8.47	0.19 (±0.13) 0.18 (±0.13) 0.20 (±0.14)	5.60 5.70 6.82	42.87
	patient treat.	66.01	10	8.92	0.05 (±0.09) 0.03 (±0.06) 0.03 (±0.08)	5.63 5.94 5.94	24.08
	wine	69.58	11	9.03	0.09 (±0.10) 0.09 (±0.09) 0.09 (±0.12)	5.59 5.64 5.62	36.32
	employee attr.	82.45	63 10.56	0.06 (±0.09) 0.06 (±0.09) 0.20 (±0.11)	6.41 6.39 6.98	1017.24
	contraceptive	51.36	90 10.84	0.06 (±0.08) 0.06 (±0.08) 0.39 (±0.17)	4.27 4.26 5.95	1096.07
	compas	67.60	40 10.95	0.03 (±0.07) 0.04 (±0.08) 0.05 (±0.09)	5.68 5.83 6.78	1082.32
	fetal health	91.85	93 11.33	0.12 (±0.06) 0.12 (±0.06) 0.23 (±0.11)	5.59 5.59 6.00	930.61
	dorothea	91.88	10 5 12.90	0.25 (±0.10) 0.25 (±0.10)	-	6.70 6.70	-	-
	bank market.	89.49	882 13.11	0.29 (±0.08) 0.29 (±0.07)	-	6.99 6.99	-	-
	mnist49	95.99	784 15.57	0.37 (±0.14) 0.37 (±0.14)	-	6.97 6.89	-	-
	spambase	92.11	236 16.09	0.24 (±0.11) 0.23 (±0.09)	-	6.87 6.87	-	-
	mnist38	96.42	784 17.89	0.37 (±0.13) 0.38 (±0.14)	-	6.93 6.93	-	-
	cnae	92.59	856 19.07	0.32 (±0.25) 0.32 (±0.25)	-	5.97 5.97	-	-
	gisette	94.10	5000 21.42	0.32 (±0.11) 0.32 (±0.11)	-	6.88 6.88	-	-
	farm ads	80.78 54877 23.15	0.13 (±0.17) 0.13 (±0.17)	-	6.31 6.31	-	-

We mention in passing that an SMT-based approach was recently proposed in[Izza et al.,

2022a], but the code was not available at the time of writing this paper.

Acknowledgements

Many thanks to the reviewers for their comments and suggestions. This work has benefited from the support of the AI Chair EXPEKCTATION (ANR-19-CHIA-0005-01) of the French National Research Agency. It was also partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.


Anne Schmitt
email: anne.schmitt@universite-paris-saclay.fr

Matthew Atencio
email: matthew.atencio@csueastbay.edu

Chapter THREE Parenting in School-based Sailing Programs: Gender and Social Class Reproduction

Keywords: Sailing, gender equity, social class, sports parenting, school sports, international comparison

. Thirty interviews and 113 hours of field observations with stakeholders such as coaches, teachers, youths (14 to 17 years old), and their parents frame these various lines of analysis around sailing activity.

In windsurfing, surfing and sailing, significant research has shown that gender and social class relationships can be problematic [START_REF] Olive | Surfing together: Exploring the potential of a collaborative ethnographic moment[END_REF]Wheaton, 2003). Indeed, these water-based activities have conventionally been practised and controlled by upper-class men who shape social norms that ostracise and diminish others. [START_REF] Créac'h | La formation des « habitus de navigateurs[END_REF].

In this chapter, we develop these socio-critical ideas about water sport activities, including sailing, in relationship to family involvement. This analysis emerges from an international comparative qualitative study of light sailing 1 projects based within secondary schooling sites in coastal regions of California and France. In this examination of light sailing cultures, we pay attention to the influence that parents have to promote social values, identities, and practices in this type of environment. Our perspective is that parenting is an integral aspect of youths' sporting experiences and outcomes, in the sense that parents themselves have particular attitudes and ways of being that influence youth sport contexts, including school-based sailing. Scholars have indeed noted that there is a "cultural script" that underpins contemporary parenting in which parents prioritize doing what is best for their individual children so that parenting ultimately becomes a personalized responsibility requiring intensive strategizing [START_REF] Faircloth | Intensive parenting and the expansion of parenting[END_REF]. It thus follows that as part of this parenting approach, families seek out "cultivating experiences" through children's sporting endeavors.

Youth sports, including those originating in school environments, are thus sites where parents are becoming increasing involved, and their involvement is viewed socially as a determiner of their parenting abilities.

Under this contextualization, it also remains the case that parents involved in their children's sports are beholden to particular gendered value systems and concomitantly take an active role in determining the gendered nature of their children's participation. The idea that thus underpins this chapter is that sailing parents actively install specific gendered values, beliefs, and perspectives in their own children that can then subsequently be reproduced amongst peers at the micro level of sailing. This type of parental influence mirrors gendered values within broader society, establishing the social expectations and responsibilities of young men and women and the types of participation that they should engage in or avoid.

We also describe how certain parents in our study intended to install competitive traits and other abilities, such as leadership and decision making, to obtain familial advantages over others, thereby reinforcing social class divides. These traits that adults seek to promote among youths in their sporting endeavors inevitably lead to the reproduction of social class norms. Indeed, sailing involves confronting a dangerous and unstable environment and as such requires courage, adaptation, and an intelligent perception of this environment; a sailor must learn to make correct decisions when necessary. These intellectual and character traits that are prioritized within sailing are often associated with members of higher social classes [START_REF] Pociello | Sports et sciences sociales: Histoire, sociologie et prospective[END_REF], particularly within emerging water activities "where the work of the senses can prevail over that of the muscles" (Vigarello, 1988, p.44).

These upper-class sailing attributes are simultaneously considered masculine. [START_REF] Créac'h | La formation des « habitus de navigateurs[END_REF] aver that sailing is traditionally practiced and dominated by upper-class males who most frequently establish norming social codes that determine access and legitimacy in this activity. Therefore, looking ahead to our main analysis in this chapter, an intersecting view of social class and gender implies that a dominant form of upper-class masculinity dominates sailing, including the youth version of this activity. Specifically, we shall demonstrate how school sport sailing is used by parents and their children to construct idealized versions of upper-class masculinity that reflect normative social and economic values found in both French and Californian societies.

Methods

The study that frames this chapter took place from February 2017 to July 2018.

Qualitative research involving semi-structured interviews and ethnographic field observations were implemented [START_REF] Beaud | L'usage de l'entretien en sciences sociales. Plaidoyer pour l'«entretien ethnographique[END_REF]. We conducted 60 interviews across California and Western France, encompassing approximately 200 hours of ethnographic observation. This chapter involves interrogation of data that was collected from the sailing portion of this study, which included 25 participants and 113 observation hours with coaches, teachers, and students. We conducted some interviews with two or three participants at a time and interviewed multiple participants twice.

We kept field observations of water and shore activity in an ethnographic field notebook. The first author observed coaching and teaching activities in addition to the relationships among all sailing participants. All members of the school sailing cultures, including youths (from 14 to 17 years old), coaches, teachers, parents, and program leaders, are represented in the data. Californian school sports sailing occurred within a local yacht club, and in France the sailing occurred through community centers.

We initially coded the data to identify themes and patterns [START_REF] Hsieh | Three approaches to qualitative content analysis[END_REF] that aligned with the main research thrust of analyzing how sailing could reproduce gendered and social class norms and privilege. Next, we coded key events, phrases, wordings, and patterns within the data set to construct higher-level analytical themes [START_REF] Miles | Qualitative data analysis: An expanded sourcebook[END_REF][START_REF] Stake | The art of case study research[END_REF]. In the findings section below, we outline the gendered and social class themes that eventually arose through the data analysis process.

Findings

In both France and California, most of the young sailors, coaches, and parents involved in the junior sailing programs in came from communities located on or close to wealthier coastal areas. As such, they possessed significant economic capital and cultural capital. Upper-class parents considered themselves to be heirs to the coastal areas and culture [START_REF] Créac'h | La formation des « habitus de navigateurs[END_REF]. For example, Allan1 , 46, American dock manager and Gavin's father, proudly recounted the generational roots of sailing in their family: Jimmy Buffett has a song "Son of a Son of a Sailor," I'm the son of a son of a sailor. And I'm glad Gavin can say that's his song. He is the son of a son of a sailor. That means it's natural for me. I grew up doing this and my dad grew up doing this and his dad grew up doing this, so it's our natural state. It's our normal environment; we're completely comfortable with it.

We can see that a similar viewpoint of nautical origin is held in France, where most of the sailing parents likewise came from established sailing families. These parents often referred to the fact that sailing was something "natural" to them, since they had all been on a boat from a young age. Antoine, 39, grew up sailing on a family boat. He worked in finance, his wife worked in real estate, and their only son, Fanch,14. Antoine had sailed for many years and owned a small, light, and fast sailboat. Californian parents from these privileged backgrounds explicitly wanted youths to achieve what these adults "perceive as richer, fuller lives" to "gain access to elite networks and succeed in a wide range of formal and informal assessments by upper-class gatekeepers" Stempel (2019, p. 31). In keeping with Stempel's reasoning, we illustrate here that Californian adults who encouraged their child's sailing practice also promoted reproduction within the economically dominant class (EDC) [START_REF] Bourdieu | La distinction: Critique sociale du jugement[END_REF][START_REF] Stempel | Sport, social class, and cultural capital: Building on Bourdieu and his critics[END_REF]. Through this concept of EDC, [START_REF] Stempel | Sport, social class, and cultural capital: Building on Bourdieu and his critics[END_REF] evokes the capitalist aspirations of parents whose careers fit the liberal market conception of success in American society.

For example, according to Denise, a director of a sailing program whose daughter is also a sailor, sailing is a competitive and tactical activity that prepares high school students for their academic and professional futures. Her words evoke what Fletcher (2008, p. 318) describes as intensive participation in outdoor or adventurous activities, which is considered a "standard entry ritual" into professional class endeavors:

When my kids have gone on job interviews, they've always done presentations on sailing, [or] when they have to do a presentation at school, because it's so complex. My daughter works in the field of genetics, and she was asked, "Do you know how to explain complex topics easily?" She said, "Yeah, sailing. It's like, yeah, it's so much a part of their life that they don't even realize how much you can transfer those skills to other things. Plus, you solve problems all the time. You look at the wind. You look at the water. You look at the current. It's a physics problem.

Many other Californian parents echoed Denise's opinion that school sailing provided children with skills and ways of being that would give them advantages in their future life plans outside of sports themselves [START_REF] Friedman | Playing to win: Raising children in a competitive culture[END_REF]. For instance, many parents explained that the risky sailing conditions their children sometimes faced were challenging and thus were crucial in preparing them for the future; it would teach them about what they might encounter in "real life." When asked how confronting a potentially dangerous environment could benefit their children, Mia, 43, a Californian mother, detailed the benefits of sailing in an unpredictable and risky environment: So it teaches them autonomy, fighting spirit.... Like what's going to happen in St.

Martin's [a future regatta], four days of racing, with winds, currents.... All alone in the middle of the sea. With sea lions, maybe whales, cruise liners and boats in every direction. You see, they learn a lot of things. They don't realize it, it's not conscious, but they learn not to be afraid, to deal with the unexpected, to be safe, to be self-sufficient, to support each other, etc. So it's really great.

Sailing regattas thus were seen as creating the educational conditions of adversity where controlled risk taking coupled with careful consideration of the environment is rewarded. The program director and most of the other parents we interviewed characterized light sailing as a place where young sailors learn to navigate a potentially hostile environment and acquire the skills necessary to optimize their academic and professional careers.

Unlike Californians, who were more focused on performance and competition, French parents tended to value the development of their child through a healthy activity that was considered beneficial for the overall physical and psychological development of the child; this has been found to be an objective regularly put forward by parents from a privileged social class [START_REF] Court | Habiller, nourrir, soigner son enfant : la fabrication de corps de classes[END_REF]. Parental goals in California also revolved around their children acquiring sailing skills so that young people could become leaders of the local marine culture. Carole is a teacher and has long served as secretary at a French sailing school.

It was there that she met her husband, Phillipe, who was a sailing instructor at the school.

Carole had always sailed and regularly surfed. She explained that she wanted her son to be healthy through sailing and enjoy the coastal environment in which he lives: If he's good and having fun in this sport and that's what I see … I'm not going to look any further, actually. Also, it fits with what we live in: it's a healthy environment…. For me, the practice of sports is important; as they say, a healthy mind and a healthy body.

Sophie, a cultural center director who sometimes sails, supports the idea that light sailing is a tool for immersing oneself in the marine culture present on the Atlantic coast. She wants her two sons and daughter to enjoy this prominent activity in the region where they live:

Well, let's just say yes, because it's a great opportunity, for sure…. Really, to live in this area and not take advantage of it, I find that almost -it's almost anachronistic. If there is a sport to be done, it is this one.

Becoming immersed and agentive within this marine culture resonates with the unconscious strategies these parents put in place to help their children acquire a certain preferred habitus [START_REF] Créac'h | La formation des « habitus de navigateurs[END_REF]. Through sailing, then, children could construct a habitus reflecting a mind-body relationship typically found in the privileged social classes [START_REF] Boltanski | Les usages sociaux du corps[END_REF].

Much like in broader society, sailing activity in our international study reflected a sexual division of labor that was reinforced by parents, who differentially invested with their children according to prevailing norms. We found that the respective Californian and French families' socialization processes were used to acquire socio-economic competitive capital and marine-oriented cultural capital, and led to various gendered practices and viewpoints. [START_REF] Coakley | The good father: Parental expectations and youth sports[END_REF] reports that in the context of youth sports, fathers tend to consult with coaches, scout opponents, provide strategic advice to their sons and generally reinforce masculine values through competitive youth sports, whereas mothers typically oversee caring aspects of their children's sports practice. Thus, there is a gendered division between fathers and mothers whose children are involved in sports; they are "shaped by gendered language and belief systems and are seen as 'natural' extensions of gendered divisions of labor in families and workplaces" (Messner, 2009, p. 25). This gendered division of tasks among parents was also apparent in the school sailing domain in terms of their practices and gender relations.

Our observations revealed that the mothers were involved in logistical and relational tasks related to the child's health, such as providing sun cream, preparing and organizing picnics, putting water bottles in the boat, bringing snacks, organizing their children's schedule, and indeed all of these tasks were menial and "behind the scenes." Consider the following statement from Lise, 41, a French mother of a sailing boy: "I think he thinks that I can't help him. Well, afterwards, I'll be there, I'll encourage him… I'll help him if he needs to prepare and clean, manage his bag and his picnic!" Lise said that her husband was frequently giving technical advice and providing debriefings.

Fathers, on the other hand, tended to invest their time, energy, and focus on productive tasks linked to technical and sporting issues: discussing the best race strategy to adopt, advising on the placement of the boat at the start of the regatta, providing information about sailboat and equipment regulations, intervening in the verification of the rigging and the hull. It was clearly the case that these tasks were perceived within this environment as quite important on a symbolic level. Allan, for instance, described the role he played during Thus, these two fathers tend to invest a coaching role during their son's regattas.

In both research contexts, we also found that there was also a sexual division at work among the young male and female sailors. This finding reflects an international patriarchal structure that underpins broader sailing culture. The gendered division is particularly visible in the distribution of the positions of helmsman and crew member, contributing to the perceived inferiority of young female sailors and the perceived legitimacy of young male sailors on the boat and in the water. There was a consensus among many of the boys that not all positions were equal and that having control over the helm of the boat legitimized their power status over others. Bryan, 16, said: I like being in control of the situation in general. I decided to be a helmsman because I want to be in control of the operation. I want to have a crew member who works well with me, but I just want to be the person who gets the final say.

Indicating a lack of trust in others, Pierre, 14, said, "When there's a lot of wind, I'd rather be at the helm." Jared, 15, echoed both Bryan and Pierre's desire to be in control: "I really just being able to be in control of this boat and just being able to go really fast and knowing it's me doing it and it's not random." Our observations confirmed that in a context of mixed crew sailing in both countries, there was a clear overrepresentation of boys in this skipper position, which was considered more prestigious that crewing. The notion of control and mastery of choices to which Bryan refers in the role of helmsman clearly positions him in a dominant posture.

Both French and Californian parents understood the hierarchy of sailing roles and thus encouraged their children to take the helm. Mia, for example said: "Especially in FJ [a type of sailing racing class], the crew is useless… [interrupted herself], really the crew is not really useful." Lise, a French mother, added: I know that if my husband would have been here -he is a sailor as well -I know that he used to say to Marin [their son, 15] -when Marin crewed, he told him 'you should drive the boat.' I have the feeling that, for Marin, being a skipper is a little better than being crew.

There was a further convergence among the male sailors who sought to reach the position of helmsman along with the attitude of parents who tended to push their sons to helm. In this way, they transmitted and reinforced this hierarchy in the division of roles on the boat. Skippering the boat offered the opportunity to manufacture and assert a dominant masculine identity. Furthermore, this type of male-dominated sailing practice socialized these young men into ways of being that aligned them with upper social class norms and behaviors.

Their sailing practice became integral to the boys' future entry into elite society.

Concomitantly, this type of gendered and social class reproduction meant that the girls internalized these masculine hierarchies and developed docility as a result (Schmitt et al., 2020a) already shown in education, girls tend to put themselves in secondary position in class [START_REF] Duru-Bellat | L'école des filles : Quelle formation pour quels rôles sociaux ?[END_REF]. Meryl, 46, a Californian mother, regretted that her daughter disengaged from this sailing position on the boat: "We were disappointed that she didn't want to be a coxswain; she always wanted to confine herself to this secondary role." The role of crew member is perceived as a secondary role, devoid of responsibility and risk-taking. The female sailors in our study frequently recounted their fears and inhibitions regarding taking the helm of a boat. June, 17, said that she was anxious about trying to lead the boat: "I'm an anxious person and jumping into something that's going to scare me is a little bit of, like, maybe I'll take a backseat on this one and go later on." Emma, 14, said: I have never asked [about taking the helm], but I'm not sure that Fanch would like to let me do it. And he is a better skipper than me, so I let him do it … it is easier … I would like sometimes but, well … I won't be comfortable to make mistakes with them [boys] on board.... They are much stronger… I think they would react [if we were skippers of the boat].

This type of self-exclusionary behavior practiced by the girls is not limited to sports; it is also present in many social contexts dominated by men [START_REF] Bourelly | Cheffe de cuisine : le coût de la transgression[END_REF][START_REF] Buscatto | Leader au féminin ? Variations autour du jazz[END_REF]. This internalization of a subjugated role was likewise promoted by the boys, who believed that the girls were prone to mistakes due to their lack of experience. Here, Marin explains that he would find it difficult to turn over the helm to someone less experienced than him: "I wouldn't want to leave the helm to someone who makes mistakes, who doesn't move forward and all that." Thus, driving the boat is mostly invested by boys who want to be in charge and do not want someone less skilled than them to drive.

In our study, both parents and the young sailors continued to justify this gendered division of labor on the boat, sometimes based on a naturalistic ideology that supported male dominance. The words of Christian, a Californian father, illustrate this idea that physical differences meant that girls and boys should have different roles on the boat: Sometimes girls are preferred as crew, just because they tend to be lighter than boys once they start to get [older] -especially in the [the sailboat]. As he gets to his size, he's going to need to have a lighter crew. A smaller crew. He's just is going into high school now. Next year, he'll be a freshman in high school.

Part of the struggle is starting up a high school team. I said, 'what you need to do is recruit some girls for crew'.

Christian's son Jared, 15, added to this idea: "They're a lot more flexible, so it's a lot easier in that current crewing position...." Thus, a logic of natural physical difference was drawn upon to divide tasks during sailing, further reinforcing the idea that boys should lead while the women should play support roles.

Discussion

Social class distinction is a critical element in broader sailing culture, since this activity caters to upper-class participants and occurs within wealthier coastal areas. It requires expensive equipment and participation fees that preclude others from participating [START_REF] Créac'h | Les usages sociaux des voiliers : enjeux culturels des modes d'appropriation de la navigation[END_REF][START_REF] Pociello | Sports et sciences sociales: Histoire, sociologie et prospective[END_REF]. In terms of social class reproduction of sporting habitus, it has been claimed that sailing is generally a "sport of the monied classes" and this activity arose during the rise of industrial capitalism (Crawley, 1998, p. 35). Moreover, scholars have explained that the distinction of one's authentic sailing habitus usually relies upon being socially integrated within an upper-class sailing culture. Sailing thus implies a relationship to the body that is specific to privileged social groups [START_REF] Pociello | Sports et sciences sociales: Histoire, sociologie et prospective[END_REF]. This specific social class contextualization of sailing thus compelled us to analyze how adults, including parents and school program members, reproduced certain social class belief systems and ideologies in the context of school-based practice. In France, parents tended to value the reproduction of a marine cultural habitus through school sailing. French school sailing remains an activity perceived as culturally distinctive by and for coastal families with a high cultural status; these parents wanted their children to be exposed to both this cultural and natural context so that they could access this distinction reserved for sailing heirs (Créac'h & Sébileau, op. cit.). Therefore, sailing is seen as a way for French families to transmit distinctive cultural capital that reflects a healthy relationship between mind and body [START_REF] Bourdieu | La distinction: Critique sociale du jugement[END_REF].

In our study, the Californian parents' investment in their children's sports was guided by the belief that sports maximizes young people's personal development. This parental belief is consistent with an ideal of "personal responsibility" born of the advent of neoliberalism in the 1980s and 1990s [START_REF] Stempel | Sport, social class, and cultural capital: Building on Bourdieu and his critics[END_REF]. This parenting strategy is particularly present in American youth sports, which is typically "highly expensive and performanceoriented, and heavily dependent on parental involvement" (Coakley, 2006, p. 159). Under these conditions, "where competition and individualism are highly valued, some people become competitive when they claim their moral value as parents" (Coakley,op. cit.,p. 160). Thus, Californian sailing has been viewed and used in the same way as other sports activities that have been researched in the United States. [START_REF] Friedman | Playing to win: Raising children in a competitive culture[END_REF] suggests that in these environments, parents prioritize learning to compete to ensure the presence of sometimes limited academic and professional opportunities in neo-liberal American society. Risk-taking in adult-controlled competitions is thus particularly valued. For example, [START_REF] Fletcher | Living on the edge: The appeal of risk sports for the professional Middle Class[END_REF] identifies risk-taking and perseverance in adventurous activities as a key attribute of the "professional class:" "for one can never be certain that the long road from education to employment will ultimately prove fruitful, but one must undertake the journey anyway" (p. 318) Displayed sailing attributes such as risk-taking, leadership, and perseverance are also frequently considered desirable masculine traits. This type of positioning of desirable attributes as masculine, can also be found in other fields of activity outside of sport, for instance, jazz band, cooking chefs and the air transport industry, where women are often considered as secondary participants and lack full participation [START_REF] Barnier | L'initiative individuelle face à ses obstacles. Genre et formation professionnelle dans le transport aérien[END_REF][START_REF] Bourelly | Cheffe de cuisine : le coût de la transgression[END_REF][START_REF] Buscatto | Leader au féminin ? Variations autour du jazz[END_REF].

Going back to sailing, we can see that this activity largely exists as male-dominated in terms of actual practice and its accompanying symbolic representations [START_REF] Bricknell | The trouble with feelings[END_REF]Crawley, 1988;[START_REF] Bars | Les navigatrices de course au large. Une socialisation professionnelle spécifique[END_REF]. Here, men are most often considered as capable of handling the technical duties and mental stresses of this activity (Bricknell, 1999, p. 430).

Autonomy, initiative, risk-taking, technical mastery of the elements related to navigation, in addition to combativeness and tactical finesse during regattas, are dispositions with strong masculine connotation.

Conclusion

Thus, sailing in a potentially dangerous marine environment remains a man's world still built around an ideal of seemingly masculine characteristics [START_REF] Bricknell | The trouble with feelings[END_REF][START_REF] Bars | Les navigatrices de course au large. Une socialisation professionnelle spécifique[END_REF]. Given this masculine characterization of sailing, Bourdieu's writing (2001) around masculine domination that is reproduced through institutionalized endeavors such as sports and education became useful to analyze gendered sailing practice. A Bourdieusian perspective implies that "roles are not biologically determined but result from a social construction, systematically ranking the masculine and the feminine (Guérandel and Mennesson, 2007, p. 168). Sporting and educational organizational cultures, such as school sport sailing programs, have particular social features and interactions that influence the nature of gendered participation and identity formation [START_REF] Mennesson | Hard' women and 'soft' women: The social construction of identities among female boxers[END_REF]. The findings presented in this chapter revealed that the position of helmsman is strongly valued by male sailors and parents, and it is also associated with the role of captain, having full powers and taking responsibility for his crew. This hierarchy underpins light sailing in California, where sailing is considered preparatory activity for the eventual economic and professional ascendency of young people, especially boys, within a patriarchal society. Further analysis could include analysis of how carnal knowledge is understand within this context, and thus shed light upon how sailing is specifically embodied and reproduced amongst wealthy families [START_REF] Wacquant | Body & soul: Notebooks of an apprentice boxer[END_REF]. This approach allows children to acquire social dispositions in line with the liberal socio-economic ideal [START_REF] Stempel | Sport, social class, and cultural capital: Building on Bourdieu and his critics[END_REF]. Differentiated parental and gender roles were observed across both study sites, in the fathers' investment into everything linked to the technical, logistical, and organizational elements of their child's sailing activity, while the mothers remained on the periphery doing menial tasks. This gendered division of tasks on the boat was also reinforced by girls eliminating themselves from the function of helmsman while the boys took over this position, which is symbolically associated with decisionmaking power. In France, masculine-dominated sailing was considered a way for local children to appropriate and become leaders within a distinctive local marine culture in terms of cultural capital (Créach, 2003;[START_REF] Stempel | Sport, social class, and cultural capital: Building on Bourdieu and his critics[END_REF]. At the same time, future study is warranted to understand the phenomenon of cultural blurring as it pertains to sporting activities such as sailing, as symbolic and practical differences that we observed could now be shifting due to the increased globalization of sport discourses.

  Antoine and Fanch regularly go out on the family boat and this serves as an opportunity for Antoine to pass on what he knows about sailing to his son: "It's usually a fairly pleasant trip; we go for a walk, more or less. It's an opportunity to learn things and to test what we can do on the boat." This orientation to family and the closeness between parents and children during sailing practice paint a picture of what Créac'h and Sébileau (2004) consider the inheritance process among sailing members. Sailing parents particularly wanted to transmit this type of sailing identity to their children by taking them sailing on the family boat; learning to sail was not all about developing a skill per se, since it also involved families' cultural reproduction.

  his son's racing: My role has changed over time, from the beginning when I helped Gavin rig his Optimist boat for him, I put it in the water for him and I pushed him out there and between every race I tried to talk to him and tell him what I think he needed to do, to do better and, you know, to not be frustrated since he rarely did what I thought he needed to do. Antoine attaches great importance to Fanch's technical progress under his guidance: When we come back, every time, from sailing, I ask [Fanch] 'What did you do? What did you do? And that's it.... What kind of exercise? I want to know everything.' (Laughs.) Because... I'm interested in this sport, on the one hand, and then I'm interested in knowing what he learned, how he did it. And if he succeeded in performing well in what he did, so.... I'm interested to know if he succeeded in being first place for the day, or if he missed three starts, to understand that.

All participants' names mentioned in this chapter are pseudonyms.

Notes

1. Dinghy and catamaran sailing are often characterized as "light" sailing, in contrast to activities such as yachting, and we refer to this description throughout this paper.

FIVE KEY READINGS

 [START_REF] Bricknell | The trouble with feelings[END_REF]. The Trouble with Feelings. Journal of Sport and Social Issues, 23(4), 421-438. Friedman, H.L. (2013). Playing to win: Raising children in a competitive culture. Berkeley, CA: University of California Press. Schmitt, A., Atencio, M., & Sempé, G. (2020a). "If I'm sailing with a girl, I get identified as a 'marshmallow':" Gendered practices of school sport sailing in Western France and California. International Review for the Sociology of Sport, 56(1), 114-132. Wheaton, B. (2003). Lifestyle sport magazines and the discourses of sporting masculinity.

The Sociological Review. https://doi.org/10.1111/j. 1467-954x.2003.tb03612.x