Anes Bendimerad
email: ahmed-anes.bendimerad@insa-lyon.fr

Jefrey Lijffijt

Marc Plantevit

Céline Robardet

Tijl De Bie

Gibbs Sampling Subjectively Interesting Tiles

Keywords: Pattern mining, Subjective interestingness, Pattern sampling, Gibbs sampling

The local pattern mining literature has long struggled with the so-called pattern explosion problem: the size of the set of patterns found exceeds the size of the original data. This causes computational problems (enumerating a large set of patterns will inevitably take a substantial amount of time) as well as problems for interpretation and usability (trawling through a large set of patterns is often impractical).

.

Unfortunately, the first research line does not reduce computational cost, while the second may miss out on the most interesting patterns. In this paper, we combine the best of both worlds for mining interesting tiles [8] from binary databases. Specifically, we propose a new pattern sampling approach based on Gibbs sampling, where the probability of sampling a pattern is proportional to their subjective interestingness [6]-an interestingness measure reported to better represent true interestingness.

The experimental evaluation confirms the theory, but also reveals an important weakness of the proposed approach which we speculate is shared with any other pattern sampling approach. We thus conclude with a broader discussion of this issue, and a forward look.

Introduction

Pattern mining methods aim to select elements from a given language that bring to the user "implicit, previously unknown, and potentially useful information from data" [START_REF] Frawley | Knowledge discovery in databases: an overview[END_REF]. To meet the challenge of selecting the appropriate patterns for a user, several lines of work have been explored: [START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF] Many constraints on some measures that assess the quality of a pattern using exclusively the data have been designed [START_REF] Boulicaut | Constraint-based data mining[END_REF][START_REF] Pei | Constraint-based sequential pattern mining: the pattern-growth methods[END_REF][START_REF] Raedt | Constraint-based pattern set mining[END_REF]; [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] Preference measures have been considered to only retrieve patterns that are non dominated in the dataset; (3) Active learning systems have been proposed that interact with the user to explicit her interest on the patterns and guide the exploration toward those she is interested in; (4) Subjective interestingness measures [START_REF] De Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF][START_REF] Kontonasios | Knowledge discovery interestingness measures based on unexpectedness[END_REF] have been introduced that aim to take into account the implicit knowledge of a user by modeling her prior knowledge and retrieving the patterns that are unlikely according to the background model.

The shift from threshold-constraints on objective measures toward the use of subjective measures provides an elegant solution to the so-called pattern explosion problem by considerably reducing the output to only truly interesting patterns. Unfortunately, the discovery of subjectively interesting patterns with exact algorithms remains computationally challenging.

In this paper we explore another strategy that is pattern sampling. The aim is to reduce the computational cost while identifying the most important patterns, and allowing for distributed computations. There are two families of local pattern sampling techniques.

The first family uses Metropolis Hastings [9], a Markov Chain Monte Carlo (MCMC) method. It performs a random walk over a transition graph representing the probability of reaching a pattern given the current one. This can be done with the guarantee that the distribution of the considered quality measure is proportional on the sample set to the one of the whole pattern set [START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF]. However, each iteration of the random walk is accepted only with a probability equal to the acceptance rate α. This can be very small, which may result in a prohibitively slow convergence rate. Moreover, in each iteration the part of the transition graph representing the probability of reaching patterns given the current one, has to be materialized in both directions, further raising the computational cost. Other approaches [5,[START_REF] Moens | Randomly sampling maximal itemsets[END_REF] relax this constraint but lose the guarantee.

Methods in the second family are referred to as direct pattern sampling approaches [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF][START_REF] Boley | Linear space direct pattern sampling using coupling from the past[END_REF]. A notable example is [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF], where a two-step procedure is proposed that samples frequent itemsets without simulating stochastic processes. In a first step, it randomly selects a row according to a first distribution, and from this row, draws a subset of items according to another distribution. The combination of both steps follows the desired distribution. Generalizing this approach to other pattern domains and quality measures appeared to be difficult.

In this paper, we propose a new pattern sampling approach based on Gibbs sampling, where the probability of sampling a pattern is proportional to their Subjective Interestingness (SI) [START_REF] De Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF]. Gibbs sampling -described in Sect. 3 -is a special case of Metropolis Hastings where the acceptance rate α is always equal to 1. In Sect. 4, we show how the random walk can be simulated without materializing any part of the transition graph, except the currently sampled pattern. While we present this approach particularly for mining tiles in rectangular databases, applying it for other pattern languages can be relatively easily achieved. The experimental evaluation (Sect. 5) confirms the theory, but also reveals a weakness of the proposed approach which we speculate is shared by other direct pattern sampling approaches. We thus conclude with a broader discussion of this issue (Sect. 6), and a forward look (Sect. 7).

Problem Formulation

Notation

# 1 2 3 4 5 1 0 1 0 1 0 2 0 1 1 0 0 3 1 0 1 0 1 4 0 1 1 1 0 5 1 1 1 1 1 6 0 1 1 1 0 7 0 1 1 1 1
Input Dataset. A dataset D is a Boolean matrix with m rows and n columns. For i ∈ 1, m and j ∈ 1, n , D(i, j) ∈ {0, 1} denotes the value of the cell corresponding to the i-th row and the j-th column. For a given set of rows I ⊆ 1, m , we define the support function supp C (I) that gives all the columns having a value of 1 in all the rows of I, i.e., supp 1 shows a toy example of a Boolean matrix, where for I = {4, 5, 6} we have that supp C (I) = {2, 3, 4}.

C (I) = {j ∈ 1, n | ∀i ∈ I : D(i, j) = 1}. Similarly, for a set of columns J ⊆ 1, n , we define the function supp R (J) = {i ∈ 1, m | ∀j ∈ J : D(i, j) = 1}. Table
Pattern Language. This paper is concerned with a particular kind of pattern known as a tile [START_REF] Geerts | Tiling databases[END_REF], denoted τ = (I, J) and defined as an ordered pair of a set of rows I ⊆ {1, ..., m} and a set of columns J ⊆ {1, ...n}. A tile τ is said to be contained (or present) in D, denoted as τ ∈ D, iff D(i, j) = 1 for all i ∈ I and j ∈ J. The set of all tiles present in the dataset is denoted as T and is defined as: T = {(I, J) | I ⊆ {1, ..., m} ∧ J ⊆ {1, ...n} ∧ (I, J) ∈ D}. In Table 1, the tile τ 1 = ({4, 5, 6, 7}, {2, 3, 4}) is present in D (τ 1 ∈ T ), because each of its cells has a value of 1, but τ 2 = ({1, 2}, {2, 3}) is not present (τ 2 / ∈ T ) since D(1, 3) = 0.

The Interestingness of a Tile

In order to assess the quality of a tile τ , we use the framework of subjective interestingness SI proposed in [START_REF] De Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF]. We briefly recapitulate the definition of this measure for tiles, denoted SI(τ ) for a tile τ , and refer the reader to [START_REF] De Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF] for more details. SI(τ ) measures the quality of a tile τ as the ratio of its subjective information content IC(τ ) and its description length DL(τ ):

SI(τ ) = IC(τ ) DL(τ ) .
Tiles with large SI(τ ) thus compress subjective information in a short description. Before introducing IC and DL, we first describe the background model-an important component required to define the subjective information content IC.

Background Model. The SI is subjective in a sense that it accounts for prior knowledge of the current data miner. A tile τ is informative for a particular user if this tile is somehow surprising for her, otherwise, it does not bring new information. The most natural way for formalizing this is to use a background distribution representing the data miner's prior expectations, and to compute the probability Pr(τ ∈ D) of this tile under this distribution. The smaller Pr(τ ∈ D), the more information this pattern contains. Concretely, the background model consists of a value Pr(D(i, j) = 1) associated to each cell D(i, j) of the dataset, and denoted p ij . More precisely, p ij is the probability that D(i, j) = 1 under user prior beliefs. In [START_REF] De Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF], it is shown how to compute the background model and derive all the values p ij corresponding to a given set of considered user priors.

Based on this model, the probability of having a tile τ = (I, J) in D is:

Pr(τ ∈ D) = Pr ⎛ ⎝ i∈I,j∈J D(i, j) = 1 ⎞ ⎠ = i∈I,j∈J p ij .
Information Content IC . This measure aims to quantify the amount of information conveyed to a data miner when she is told about the presence of a tile in the dataset. It is defined for a tile τ = (I, J) as follows:

IC(τ ) = -log(Pr(τ ∈ D)) = i∈I,j∈J -log(p ij ).
Thus, the smaller Pr(τ ∈ D), the higher IC(τ ), and the more informative τ . Note that for

τ 1 , τ 2 ∈ D : IC(τ 1 ∪ τ 2 ) = IC(τ 1 ) + IC(τ 2 ) -IC(τ 1 ∩ τ 2 ).
Description Length DL. This function should quantify how difficult it is for a user to assimilate the pattern. The description length of a tile τ = (I, J) should thus depend on how many rows and columns it refers to: the larger are |I| and |J|, the larger is the description length. Thus, DL(τ ) can be defined as:

DL(τ ) = a + b • (|I| + |J|) ,
where a and b are two constants that can be handled to give more or less importance to the contributions of |I| and |J| in the description length.

Problem Statement

Given a Boolean dataset D, the goal is to sample a tile τ from the set of all the tiles T present in D, with a probability of sampling P S proportional to SI(τ ), that is:

P S (τ ) = SI(τ)
τ ∈T SI(τ ) . A naïve approach to sample a tile pattern according to this distribution is to generate the list {τ 1 , ..., τ N } of all the tiles present in D, sample x ∈ [0, 1] uniformly at random, and return the tile

τ k with k-1 i=1 SI(τi) i SI(τi) ≤ x < k i=1 SI(τi) i SI(τi) .
However, the goal behind using sampling approaches is to avoid materializing the pattern space which is generally huge. We want to sample without exhaustively enumerating the set of tiles. In [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF], an efficient procedure is proposed to directly sample patterns according to some measures such as the frequency and the area. However, this procedure is limited to only some specific measures. Furthermore, it is proposed for pattern languages defined on only the column dimension, for example, itemset patterns. In such language, the rows related to an itemset pattern F ⊆ {1, ..., n} are uniquely identified and they correspond to all the rows containing the itemset, that are supp R (F ). In our work, we are interested in tiles which are defined by both columns and rows indices. In this case, it is not clear how the direct procedure proposed in [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] can be applied.

For more complex pattern languages, a generic procedure based on Metropolis Hasting algorithm has been proposed in [9], and illustrated for subgraph patterns with some quality measures. While this approach is generic and can be extended relatively easily to different mining tasks, a major drawback of using Metropolis Hasting algorithm is that the random walk procedure contains the acceptance test that needs to be processed in each iteration, and the acceptance rate α can be very small, which makes the convergence rate practically extremely slow. Furthermore, Metropolis Hasting can be computationally expensive, as the part of the transition graph representing the probability of reaching patterns given the current one, has to be materialized.

Interestingly, a very useful MCMC technique is Gibbs sampling, which is a special case of Metropolis-Hasting algorithm. A significant benefit of this approach is that the acceptante rate α is always equal to 1, i.e., the proposal of each sampling iteration is always accepted. In this work, we use Gibbs sampling to draw patterns with a probability distribution that converges to P S . In what follows, we will first generically present the Gibbs sampling approach, and then we show how we efficiently exploit it for our problem. Unlike Metropolis Hasting, the proposed procedure performs a random walk by materializing in each iteration only the currently sampled pattern.

Gibbs Sampling

Suppose we have a random variable X = (X 1 , X 2 , ..., X l ) taking values in some domain Dom. We want to sample a value x ∈ Dom following the joint distribution P (X = x). Gibbs sampling is suitable when it is hard to sample directly from P but known how to sample just one dimension

x k (k ∈ 1, l ) from the conditional probability P (X k = x k | X 1 = x 1 , ..., X k-1 = x k-1 , X k+1 = x k+1 , ..., X l = x l ).
The idea of Gibbs sampling is to generate samples by sweeping through each variable (or block of variables) to sample from its conditional distribution with the remaining variables fixed to their current values. Algorithm 1 depicts a generic Gibbs Sampler. At the beginning, x is set to its initial values (often values sampled from a prior distribution q). Then, the algorithm performs a random walk of p iterations. In each iteration, we sample

x 1 ∼ P (X 1 = x (i1) 1 | X 2 = x (i1) 2 , ..., X l = x (i1) l
) (while fixing the other dimensions), then we follow the same procedure to sample x 2 , ..., until x l .

Algorithm 1: Gibbs sampler

1 Initialize x (0) ∼ q(x) 2 for k ∈ 1, p do 3 draw x (k) 1 ∼ P X1 = x1 | X2 = x (k-1) 2 , X3 = x (k-1) 3 , ..., X l = x (k-1) l 4 draw x (k) 2 ∼ P X2 = x2 | X1 = x (k) 1 , X3 = x (k-1) 3 , ..., X l = x (k-1) l 5 ... 6 draw x (k) l ∼ P X l = x l | X1 = x (k) 1 , X2 = x (k) 2 , ..., X l-1 = x (k) l-1 7 return x (p)
The random walk needs to satisfy some constraints to guarantee that the Gibbs sampling procedure converges to the stationary distribution P . In the case of a finite number of states (a finite space Dom in which X takes values), sufficient conditions for the convergence are irreducibility and aperiodicity:

Irreducibility. A random walk is irreducible if, for any two states x, y ∈ Dom s.t. P (x) > 0 and P (y) > 0, we can get from x to y with a probability > 0 in a finite number of steps. I.e. the entire state space is reachable. Aperiodicity. A random walk is aperiodic if we can return to any state x ∈ Dom at any time. I.e. revisiting x is not conditioned to some periodicity constraint.

One can also use blocked Gibbs sampling. This consists in growing many variables together and sample from their joint distribution conditioned to the remaining variables, rather than sampling each variable x i individually. Blocked Gibbs sampling can reduce the problem of slow mixing that can be due to the high number of dimensions used to sample from.

Gibbs Sampling of Tiles with Respect to SI

In order to sample a tile τ = (I, J) with a probability proportional to SI(τ ), we propose to use Gibbs sampling. The simplest solution is to consider a tile τ as m + n binary random variables (x 1 , ..., x m , ..., x m+n ), each of them corresponds to a row or a column, and then apply the procedure described in Algorithm 1. In this case, an iteration of Gibbs sampling requires to sample from each column and row separately while fixing all the remaining rows and columns. The drawback of this approach is the high number of variables (m + n) which may lead to a slow mixing time. In order to reduce the number of variables, we propose to split τ = (I, J) into only two separated blocks of random variables I and J, we then directly sample from each block while fixing the value of the other block. This means that an iteration of the random walk contains only two sampling operations instead of m+n ones. We will explain in more details how this Blocked Gibbs sampling approach can be applied, and how to compute the distributions used to directly sample a block of rows or columns.

Algorithm 2: Gibbs

-SI 1 Initialize (I, J) (0) ∼ q(x) 2 for k ∈ 1, p do 3 draw I (k) ∼ P I = I | J = J (k-1) , draw J (k) ∼ P J = J | I = I (k) 4 return (I, J) (p)
Algorithm 2 depicts the main steps of Blocked Gibbs sampling for tiles. We start by initializing (I, J) (0) with a distribution q proportional to the area (|I| × |J|) following the approach proposed in [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF]. This choice is mainly motivated by its linear time complexity of sampling. Then, we need to efficiently sample from P (I = I | J = J) and P (J = J | I = I). In the following, we will explain how to sample I with P (I = I|J = J), and since the SI is symmetric w.r.t. rows and columns, the same strategy can be used symmetrically to sample a set of columns with P (J = J | I = I).

Sampling a Set of Rows I Conditioned to Columns J.

For a specific J ⊆ {1, ..., n}, the number of tiles (I, J) present in the dataset can be huge, and can go up to 2 m . This means that naïvely generating all these candidate tiles and then sampling from them is not a solution. Thus, to sample a set of rows I conditioned to a fixed set of columns J, we propose an iterative algorithm that builds the sampled I by drawing each i ∈ I separately, while ensuring that the joint distribution of all the drawings is equal to P (I = I|J = J). I is built using two variables: R 1 ⊆ {1, ..., m} made of rows that belong to I, and R 2 ⊆ {1, ..., m} \ R 1 that contains candidate rows that can possibly be sampled and added to R 1 . Initially, we have R 1 = ∅ and R 2 = supp R (J). At each step, we take i ∈ R 2 , do a random draw to determine whether i is added to R 1 or not, and remove it from R 2 . When R 2 = ∅, the sampled set of rows I is set equal to R 1 . To apply this strategy, all we need is to compute

P (i ∈ I | R 1 ⊆ I ⊆ R 1 ∪ R 2 ∧ J = J)
, the probability of sampling i considering the current sets R 1 , R 2 and J:

P (i ∈ I | R1 ⊆ I ⊆ R1 ∪ R2 ∧ J = J) = P (R1 ∪ {i} ⊆ I ⊆ R1 ∪ R2 ∧ J = J) P (R1∪ ⊆ I ⊆ R1 ∪ R2 ∧ J = J) = F ⊆R 2 \{i} SI(R1 ∪ {i} ∪ F, J) F ⊆R 2 SI(R1 ∪ F, J) = F ⊆R 2 \{i} IC(R 1 ∪{i},J)+IC(F,J) a+b•(|R 1 |+|F |+1+|J|) F ⊆R 2 IC(R 1 ,D i )+IC(F,D i ) a+b•(|R 1 |+|F |+|J|) = |R 2 |-1 k=0 1 a+b•(|R 1 |+k+1+|J|) F ⊆R 2 \{i} |F |=k (IC(R1 ∪ {i}, J) + IC(F, J)) |R 2 | k=0 1 a+b•(|R 1 |+k+|J|) F ⊆R 2 |F |=k (IC(R1, J) + IC(F, J)) = |R 2 |-1 k=0 1 a+b•(|R 1 |+k+1+|J|) |R 2 |-1 k • IC(R1 ∪ {i}, J) + |R 2 |-2 k-1 • IC(R2 \ {i}, J) |R 2 | k=0 1 a+b•(|R 1 |+k+|J|) |R 2 | k • IC(R1, J) + |R 2 |-1 k-1 • IC(R2, J) = IC(R1 ∪ {i}, J) • f (|R2| -1, |R1| + 1) + IC(R2 \ {i}, J) • f (|R2| -2, |R1| + 1) IC(R1, J) • f (|R2|, |R1|) + IC(R2, J) • f (|R2| -1, |R1|) , with f (x, y) = x k=0 ( x k ) a+b•(y+k+|J|) .
Complexity . Let's compute the complexity of sampling I with a probability P (I = I|J = J). Before starting the sampling of rows from R 2 , we first compute the value of IC({i}, J) for each i ∈ R 2 (in O(n • m)). This will allow to compute in O( 1) the values of IC that appear in

P (i ∈ I | R 1 ⊆ I ⊆ R 1 ∪ R 2 ∧ J = J), based on the relation IC(I 1 ∪ I 2 , J) = IC(I 1 , J) + IC(I 2 , J) for I 1 , I 2 ⊆ 1, m .
In addition to that, sampling each element i ∈ R 2 requires to compute the corresponding values of f (x, y). These values are computed once for the first sampled row i ∈ R 2 with a cost of O(m), and then they can be updated directly when sampling the next rows, using the following relation:

f (x -1, y) = f (x, y) - 1 a + b • (x + y + |J|) • f (x -1, y + 1).
This means that the overall cost of sampling the whole set of rows I with a probability

P (I = I|J = J) is O(n • m).
Following the same approach, sampling J conditionned to I is done in O(n • m). As we have p sampling iterations, the worst case complexity of the whole Gibbs sampling procedure of a tile τ is

O (p • n • m).
Convergence Guarantee. In order to guarantee the convergence to the stationary distribution proportional to the SI measure, the Gibbs sampling procedure needs to satisfy some constraints. In our case, the sampling space is finite, as the number of tiles is limited to at most 2 m+n . Then, the sampling procedure converges if it satisfies the aperiodicity and the irreducibility constraints. The Gibbs sampling for tiles is indeed aperiodic, as in each iteration it is possible to remain in exactly the same state. We only have to verify if the irreducibility property is satisfied. We can show that, in some cases, the random walk is reducible, we will show how to make Gibbs sampling irreducible in those cases.

Theorem 1. Let us consider the bipartite graph G = (U, V, E) derived from the dataset D, s.t., U = {1, .., m}, V = {1, ..., n}, and

E = {(i, j) | i ∈ 1, m ∧ j ∈ 1, n ∧ D(i, j) = 1}. A tile τ = (I, J) present in D corresponds to a complete bipartite subgraph G τ = (I, J, E τ ) of G.
If the bipartite graph G is connected, then the Gibbs sampling procedure on tiles of D is irreducible.

Proof. We need to prove that for all pair of tiles τ 1 = (I 1 , J 1 ), τ 2 = (I 2 , J 2 ) present in D, the Gibbs sampling procedure can go from τ 1 to τ 2 . Let G τ1 , G τ2 be the complete bipartite graphs corresponding to τ 1 and τ 2 . As G is connected, there is a path from any vertex of G τ1 to any vertex of G τ2 . The probability that the sampling procedure walks through one of these paths is not 0, as each step of these paths constitutes a tile present in D. After walking on one of these paths, the procedure will find itself on a tile τ ⊆ τ 2 . Reaching τ 2 from τ is probable after one iteration by sampling the right rows and then the right columns. Thus, if the bipartite graph G is connected, the Gibbs sampling procedure converges to a stationary distribution. To make the random walk converge when G is not connected, we can compute the connected components of G, and then apply Gibbs sampling separately in each corresponding subset of the dataset.

Experiments

We report our experimental study to evaluate the effectiveness of Gibbs-SI. Java source code is made available1 . We consider three datasets whose characteristics are given in Table 2. mushrooms and chess from the UCI repository2 are commonly used for evaluation purposes. kdd contains a set of SIGKDD paper abstracts between 2001 and 2008 downloaded from the ACM website. Each abstract is represented by a row and words correspond to columns, after stop word removal and stemming. For each dataset, the user priors that we represent in the SI background model are the row and column margins. In other terms, we consider that user knows (or, is already informed about) the following statistics: j D(i, j) for all i ∈ I, and i D(i, j) for all j ∈ J. Empirical Sampling Distribution. First, we want to experimentally evaluate how the Gibbs sampling distribution matches with the desired distribution. We need to run Gibbs-SI in small datasets where the size of T is not huge. Then, we take a sufficiently large number of samples so that the sampling distribution can be created. To this aim, we have synthetically generated a dataset containing 10 rows, 10 columns, and 855 tiles. We run Gibbs-SI with three different numbers of iterations p: 1k, 10k, and 100k, for each case, we keep all the visited tiles, and we study their distribution w.r.t. their SI values. Figure 1 reports the results. For 1k sampled patterns, the proportionality between the number of sampling and SI is not clearly established yet. For higher numbers of sampled patterns, a linear relation between the two axis is evident, especially for the case of 100k sampled patterns, which represents around 100 times the total number of all the tiles in the dataset. The two tiles with the highest SI are sampled the most, and the number of sampling clearly decreases with the SI value. Characteristics of Sampled Tiles. To investigate which kind of patterns are sampled by Gibbs-SI, we show in Fig. 2 the distribution of sampled tiles w.r.t their number of rows, columns, and their SI, for each of the three datasets given in Table 2. For mushrooms and chess, Gibbs-SI is able to return patterns with a diverse number of rows and columns. It samples much more patterns with low SI than patterns with high SI values. In fact, even if we are sampling proportionally to SI, the number of tiles in T with poor quality are significantly higher than the ones with high quality values. Thus, the probability of sampling one of low quality patterns is higher than sampling one of the few high quality patterns. For kdd, although the number of columns in sampled tiles varies, all the sampled tiles unfortunately cover only one row. In fact, the particularity of this dataset is the existence of some very large transactions (max = 180).

Quality of the Sampled Tiles.

In this part of the experiment, we want to study whether the quality of the top sampled tiles is sufficient. As mining exhaustively the best tiles w.r.t. SI is not feasible, we need to find some strategy that identifies high quality tiles. We propose to use LCM [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF] to retrieve the closed tiles corresponding to the top 10k frequent closed itemsets. A closed tile τ = (I, J) is a tile that is present in D and whose I and J cannot be extended anymore. Although closed tiles are not necessarily the ones with the highest SI, we make the hypothesis that at least some of them have high SI values as they maximize the value of IC function. For each of the three real world datasets, we compare between the SI of the top closed tiles identified with LCM and the ones identified with Gibbs-SI. In Table 3, we show the SI of the top-1 tile, and the average SI of the top-10 tiles, for each of LCM and Gibbs-SI.

Unfortunately, the scores of tiles retrieved with LCM are substantially larger than the ones of Gibbs-SI, especially for mushrooms and chess. Importantly, there may exist tiles that are even better than the ones found by LCM. This means that Gibbs-SI fails to identify the top tiles in the dataset. We believe that this is due to the very large number of low quality tiles which trumps the number of high quality tiles. The probability of sampling a high-quality tile is exceedingly small, necessitating a practically too large sample to identify any.

Discussion

Our results show that efficiently sampling from the set of tiles with a sampling probability proportional to the tiles' subjective interestingness is possible. Yet, they also show that if the purpose is to identify some of the most interesting patterns, direct pattern sampling may not be a good strategy. The reason is that the number of tiles with low subjective interestingness is vastly larger that those with high subjective interestingness. This imbalance is not sufficiently offset by the relative differences in their interestingness and thus in their sampling probability. As a result, the number of tiles that need to be sampled in order to sample one of the few top interesting ones is of the same order as the total number of tiles.

To mitigate this, one could attempt to sample from alternative distributions that attribute an even higher probability to the most interesting patterns, e.g. with probabilities proportional to the square or other high powers of the subjective interestingness. We speculate, however, that the computational cost of sampling from such more highly peaked distributions will also be larger, undoing the benefit of needing to sample fewer of them. This intuition is supported by the fact that direct sampling schemes according to itemset support are computationally cheaper than according to the square of their support [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF].

That said, the use of sampled patterns as features for downstream machine learning tasks, even if these samples do not include the most interesting ones, may still be effective as an alternative to exhaustive pattern mining.

Conclusions

Pattern sampling has been proposed as a computationally efficient alternative to exhaustive pattern mining. Yet, existing techniques have been limited in terms of which interestingness measures they could handle efficiently.

In this paper, we introduced an approach based on Gibbs sampling, which is capable of sampling from the set of tiles proportional to their subjective interestingness. Although we present this approach for a specific type of pattern language and quality measure, we can relatively easily follow the same scheme to apply Gibbs sampling for other pattern mining settings. The empirical evaluation demonstrates effectiveness, yet, it also reveals a potential weakness inherent to pattern sampling: when the number of interesting patterns is vastly outnumbered by the number of non-interesting ones, a large number of samples may be required, even if the samples are drawn with a probability proportional to the interestingness. Investigating our conjecture that this problem affects all approaches for sampling interesting patterns (for sensible measures of interestingness) seems a fruitful avenue for further research.

Fig. 1 .

 1 Fig. 1. Distribution of sampled patterns in synthetic data with 10 rows and 10 columns.

Fig. 2 .

 2 Fig. 2. Distributions of the sampled patterns w.r.t. # rows, # columns and SI.

Table 1 .

 1 Example of a binary dataset D.

Table 2 .

 2 Dataset characteristics.

	Dataset	# rows # columns Avg. |row|
	mushrooms 8124	120	24
	chess	3196	76	38
	kdd	843	6159	65.3

Table 3 .

 3 The SI of the top-1 tile, and the average SI of the top-10 tiles, found by LCM and Gibbs-SI in the studied datasets.

		Mushrooms	Chess		KDD
		Top 1 SIAvg(top 10 SI)Top 1 SIAvg(top 10 SI)Top 1 SIAvg(top 10 SI)
	Gibbs sampling0.12	0.11	0.015	0.014	0.54	0.54
	LCM	3.89	3.20	0.40	0.40	0.83	0.70

http://tiny.cc/g5zmgz.

https://archive.ics.uci.edu/ml/.

Acknowledgements. This work was supported by the ERC under the EU's Seventh Framework Programme (FP7/2007-2013)/ERC Grant Agreement no. 615517, the Flemish Government under the "Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen" programme, the FWO (project no. G091017N, G0F9816N, 3G042220), and the EU's Horizon 2020 research and innovation programme and the FWO under the Marie Sklodowska-Curie Grant Agreement no. 665501, and by the ACADEMICS grant of the IDEXLYON, project of the Université of Lyon, PIA operated by ANR-16-IDEX-0005.


Xiaofeng Tang
email: tangxf@aiofm.ac.cn

Xuejun Gu

Xiaoxiao Lin

Weijun Zhang

Gustavo A Garcia
email: gustavo.garcia@synchrotron-soleil.fr

Christa Fittschen

Jean-Christophe Loison

Krisztina Voronova

Bálint Sztáray

Laurent Nahon

Vacuum ultraviolet photodynamics of the methyl peroxy radical studied by double imaging photoelectron photoion coincidences

The vacuum ultraviolet (VUV) photoionization of the methyl peroxy radical, CH 3 O 2 , and unimolecular dissociation of internal energy selected CH 3 O 2 + cations were investigated in the 9.7-12.0 eV energy range by synchrotron-based double imaging photoelectron photoion coincidence (i 2 PEPICO). A microwave discharge flow tube was employed to produce CH 3 O 2 via the reaction of methyl radicals (CH 3 ) with oxygen gas. After identifying and separating the different sources of CH 3 + from photoionization of CH 3 or dissociative photoionization of CH 3 O 2 , the high resolution slow photoelectron spectrum (SPES) of CH 3 O 2 was obtained exhibiting two broad bands superimposed with a complex vibrational structure. The first band of the SPES is attributed to the X 3 A″ and a 1 A′ overlapped electronic states of CH 3 O 2 + and the second is assigned to the b 1 A′ electronic state with the help of theoretical calculations. The adiabatic ionization energy (AIE) of CH 3 O 2 is derived as 10.215 ± 0.015 eV, in good agreement with high-accuracy theoretical data from the literature. The vertical ionization energy of the b 1 A' electronic state is measured to be 11.5 eV and this state fully dissociates into CH 3 + and O 2

fragments. The 0 K adiabatic appearance energy (AE 0K ) of the CH 3 + fragment ion is determined to be 11.1548 ± 0.020 eV.

I. INTRODUCTION

Organic peroxy radicals (RO 2 ) are key reaction intermediates in the low temperature oxidation of hydrocarbons and play an essential role in combustion and atmospheric chemistry. [START_REF] Tyndall | Atmospheric chemistry of small organic peroxy radicals[END_REF][START_REF] Orlando | Laboratory studies of organic peroxy radical chemistry: an overview with emphasis on recent issues of atmospheric significance[END_REF] In the atmosphere they are involved in the tropospheric "self-cleansing" mechanism, controlling the cycling of radicals and the formation of secondary pollutants such as ozone and secondary organic aerosols (SOA). The structure, thermochemistry and kinetics of RO 2 are of considerable importance in order to fully understand their chemistry in the atmosphere. In the past decades many advances have been made on the detection and analysis of RO 2 by the constant development of analytical methods such as absorption spectroscopy, [START_REF] Tyndall | Atmospheric chemistry of small organic peroxy radicals[END_REF][START_REF] Huang | Infrared absorption of gaseous CH 3 OO detected with a step-scan Fourier-transform spectrometer[END_REF] cavity ring down spectroscopy (CRDS), [START_REF] Assaf | The Reaction between CH 3 O 2 and OH radicals: Product yields and atmospheric implications[END_REF] chemical ionization mass spectrometry (CIMS) [START_REF] Berndt | Accretion product formation from self-and cross-reactions of RO 2 radicals in the atmosphere[END_REF] and photoionization mass spectrometry (PIMS) [START_REF] Meloni | Energy-resolved photoionization of alkylperoxy radicals and the stability of their cations[END_REF][START_REF] Wen | A vacuum ultraviolet photoionization time-of-flight mass spectrometer with high sensitivity for study of gas-phase radical reaction in a flow tube[END_REF] .

The methyl peroxy radical, CH 3 O 2 , is the simplest and most abundant alkyl peroxy radical in the atmosphere which has attracted a great deal of attention. The structure of CH 3 O 2 and its thermochemistry have been studied extensively both experimentally and with quantum-chemical methods. The neutral CH 3 O 2 at the X [START_REF] Orlando | Laboratory studies of organic peroxy radical chemistry: an overview with emphasis on recent issues of atmospheric significance[END_REF] A″ ground state has a Cs symmetry with electronic configuration of (1a′) 2 …(9a′) [START_REF] Orlando | Laboratory studies of organic peroxy radical chemistry: an overview with emphasis on recent issues of atmospheric significance[END_REF] (2a″) [START_REF] Orlando | Laboratory studies of organic peroxy radical chemistry: an overview with emphasis on recent issues of atmospheric significance[END_REF] (10a′) [START_REF] Orlando | Laboratory studies of organic peroxy radical chemistry: an overview with emphasis on recent issues of atmospheric significance[END_REF] (3a″) [START_REF] Tyndall | Atmospheric chemistry of small organic peroxy radicals[END_REF] . [START_REF] Copan | Examining the ground and first excited states of methyl peroxy radical with high-level coupled-cluster theory[END_REF] Removing an electron from the 10a′ orbital in photoionization can lead to two spin cationic states, the X 3 A″ ground electronic state and the a 1 A′ first excited state. Theoretical calculations with a complete basis set method using the atomic pair natural orbital expansion (CBS-APNO) at the QCISD(T)/CBS level of theory were performed by Meloni et al. and predicted the adiabatic ionization energy (AIE) of CH 3 O 2 at 10.21 eV. [START_REF] Meloni | Energy-resolved photoionization of alkylperoxy radicals and the stability of their cations[END_REF] Voronova et al. also carried out electronic structure calculations at the CCSD(T)/aug-cc-pVQZ//CCSD/aug-cc-pVTZ level and predicted the same theoretical value of AIE = 10.21 eV. [START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] CH 3 O 2 + cation and its kinetics were studied experimentally by mass spectrometry with electron impact ionization [START_REF] Plumb | Rate coefficient for the reaction of CH 3 O 2 with NO at 295 K[END_REF] and vacuum ultraviolet (VUV) lamp photoionization. [START_REF] Slagle | Kinetics of polyatomic free radicals produced by laser photolysis. 5. Study of the equlibrium CH 3 + O 2 --> CH 3 O 2 between 421 and[END_REF] Meloni et al. investigated the synchrotron VUV photoionization of small alkyl peroxy radicals using the multiplexed photoionization mass spectrometer (MPIMS) at the Advanced Light Source, and found that most of these cations are unstable, whereas CH 3 O 2 + is among the very few bound alkyl peroxy cations. by IR+VUV laser photoionization mass spectrometry. [START_REF] Fu | Generation and detection of alkyl peroxy radicals in a supersonic jet expansion[END_REF] Building on the capabilities of photoionization mass spectrometry (PIMS) and photoelectron spectroscopy (PES), photoelectron photoion coincidence spectroscopy (PEPICO) analyzes both the photoelectrons and photoions in coincidence, and offers richer and more accurate information on energetics. [START_REF] Tang | A threshold photoelectron-photoion coincidence spectrometer with double velocity imaging using synchrotron radiation[END_REF][START_REF] Bodi | A new double imaging velocity focusing coincidence experiment: i 2 PEPICO[END_REF][START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF] Particularly, mass-selected threshold PES (ms-TPES) can be measured, which provides high-resolution thermochemical information with structure specific insights. In this work, we present a detailed VUV photoionization and dissociative photoionization study of CH 3 O 2 by using the high energy resolution of the VUV beamline DESIRS at synchrotron SOLEIL and the state-of-the-art method of double imaging photoelectron photoion coincidence (i 2 PEPICO). [START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF][START_REF] Tang | Vacuum upgrade and enhanced performances of the double imaging electron/ion coincidence end-station at the vacuum ultraviolet beamline DESIRS[END_REF] The full slow photoelectron spectrum (SPES) of CH 3 O 2 is acquired in the 9.7-12.0 eV energy range and assigned with the help of theoretical calculations, which are indispensable as the unfavorable Franck-Condon factors (FCF) combined with the proximity of the first electronically excited state render the measurement of the AIE difficult. The high photon energy resolution combined with the slow photoelectron technique provide a more precise comparison to the existing calculations leading to an increased accuracy of the AIE. In the following sections, we will first describe the experimental setup and methodology to generate CH 3 O 2 using a microwave discharge flow tube. Then a procedure to separate the cold molecular beam and the thermal background gas components within the photoionization region is introduced and used to get positionfiltered and mass-selected SPES.

II. EXPERIMENTAL SETUP

The experiments were performed at the VUV beamline DESIRS with the i 2 PEPICO spectrometer DELICIOUS III at synchrotron SOLEIL, France. A flow tube combined with a microwave discharge generator was employed as reactor to produce radicals and initiate their reactions. The configurations of the beamline, the i 2 PEPICO spectrometer and the flow tube have already been introduced before [START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF][START_REF] Tang | Adiabatic ionization energies of the overlapped A 2 A 1 and B 2 E electronic states in CH 3 Cl + /CH 3 F + measured with double imaging electron/ion coincidence[END_REF][START_REF] Chicharro | Threshold photoelectron spectrum of the CH 2 OO Criegee intermediate[END_REF][START_REF] Tang | Vacuum upgrade and enhanced performances of the double imaging electron/ion coincidence end-station at the vacuum ultraviolet beamline DESIRS[END_REF][START_REF] Nahon | DESIRS: a state-of-the-art VUV beamline featuring high resolution and variable polarization for spectroscopy and dichroism at SOLEIL[END_REF][START_REF] Garcia | Synchrotron-based double imaging photoelectron/photoion coincidence spectroscopy of radicals produced in a flow tube: OH and OD[END_REF] and only a brief description is given here.

On the DESIRS beamline, synchrotron photons emitted from a variable polarization undulator were dispersed by a 6.65 m normal incidence monochromator equipped with four gratings to cover the energy range of 5-40 eV. [START_REF] Nahon | DESIRS: a state-of-the-art VUV beamline featuring high resolution and variable polarization for spectroscopy and dichroism at SOLEIL[END_REF] In our experiments the 200 l.mm -1 grating providing high photon flux was used and the photon energy resolution was set at ~3 meV. A gas filter filled with Ar was adopted to suppress high-order harmonics and the absolute photon energy was calibrated on-line with an accuracy of ±1 meV using the resonant absorption lines of Ar. [START_REF]NIST Atomic Spectra Database[END_REF] The flow tube was composed of a main tube with an inner diameter of 2.5 cm and a collinear sliding injector, installed inside the source chamber of SAPHIRS, the permanent molecular beam endstation on the beamline. [START_REF] Tang | Vacuum upgrade and enhanced performances of the double imaging electron/ion coincidence end-station at the vacuum ultraviolet beamline DESIRS[END_REF][START_REF] Garcia | Synchrotron-based double imaging photoelectron/photoion coincidence spectroscopy of radicals produced in a flow tube: OH and OD[END_REF] The microwave discharge generator running at 2.45 GHz (Sairem GMP 03 KSM) was mounted perpendicularly to the gas flow and initiated radical reactions in the flow tube. The pressure inside the flow tube was measured by a gauge (Varian CDG 500) and maintained at 1-10 Torr by a closedloop feedback throttle valve. [START_REF] Garcia | Synchrotron-based double imaging photoelectron/photoion coincidence spectroscopy of radicals produced in a flow tube: OH and OD[END_REF] After passing through the flow tube, the gas mixture was sampled and expanded through two skimmers (1 mm diameter) into the ionization chamber of SAPHIRS.

The gas mixture crossed the photon beam at the center of the i 2 PEPICO spectrometer. [START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF] Electrons and ions produced in photoionization were extracted and accelerated in opposite directions towards an electron velocity map imaging (VMI) [START_REF] Eppink | Velocity map imaging of ions and electrons using electrostatic lenses: Application in photoelectron and photofragment ion imaging of molecular oxygen[END_REF] device and an ion modified Wiley-McLaren TOF 3D-momentum imaging analyzer. A position sensitive detector (PSD, DLD 80, Roentdek) was mounted to collect electron images which were filtered with ion mass-and momentum-selection in coincidence. An Abel inversion algorithm, pBasex, was used to analyze electron images to get PES or SPES. [START_REF] Garcia | Two-dimensional charged particle image inversion using a polar basis function expansion[END_REF][START_REF] Poully | Photoionization of 2pyridone and 2-hydroxypyridine[END_REF] A custom-made PSD (40 mm diameter) was used for ion detection whose 3D momentum distribution was determined by TOF and transverse position measurements.

III. RESULTS AND DISCUSSION

Two

F + CH 4 → CH 3 + HF (1)
The second experiment was carried out by adding a large amount of oxygen into the flow tube (600 sccm, Air Liquide) to enhance the production of CH 3 O 2 via the reaction 7

CH 3 + O 2 + M → CH 3 O 2 + M (2)
where M represents molecules removing the internal energy of the nascent CH 3 O 2 by collisions. For both experiments, helium was added as carrier gas and the overall flow rate was fixed at 1740 sccm with the pressure inside the flow tube at 1.6 Torr.

A. Time-of-Flight Mass Spectra and Ion Images

The photoionization mass spectrum in the absence of oxygen was measured at hν = 12.0 eV and is presented in Fig. 1 The ion images of CH 3 + and CH 3 O 2 + were acquired with the time-focusing mode of DELICIOUS III [START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF] and are displayed in Fig. 2, together with their intensity projections along the y-axis direction. In this mode, the final position on the detector is a convolution of the initial position and particle velocity. Parent ions, such as the ones shown in Fig. 2, possess narrow velocity distributions, especially for the ions formed in the molecular beam (MB), so that the dispersion seen in the ion positions is mainly related to the size of the interaction region. Parent ions formed in the MB will also have a net velocity along the MB's direction, as seen in Fig. 2, where MB propagates from east to west along the xaxis direction, and the propagation direction of synchrotron radiation (SR) is along the yaxis. Therefore, unlike VMI, [START_REF] Eppink | Velocity map imaging of ions and electrons using electrostatic lenses: Application in photoelectron and photofragment ion imaging of molecular oxygen[END_REF] the time-focusing mode is utilized to map the photoionization region allowing the separation of ions from MB and the thermal background, plus the selection of on-axis ions to increase the ion mass and ion and electron kinetic energy resolution, which can be viewed as an adjustable virtual skimmer. [START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF][START_REF] Tang | Vacuum upgrade and enhanced performances of the double imaging electron/ion coincidence end-station at the vacuum ultraviolet beamline DESIRS[END_REF] The ion images and their intensity projections can be divided into two parts: the region of interest (ROI) from MB and the "Back" from the background gas in the photoionization region. In the ROI and as mentioned above, the ions from MB have a defined velocity along the MB direction and are therefore shifted from the image center. [START_REF] Tang | Vacuum upgrade and enhanced performances of the double imaging electron/ion coincidence end-station at the vacuum ultraviolet beamline DESIRS[END_REF][START_REF] Garcia | Synchrotron-based double imaging photoelectron/photoion coincidence spectroscopy of radicals produced in a flow tube: OH and OD[END_REF] For the Back, the ions from the thermal background gas do not have velocity along the MB direction and appear at the image center. With the coincidence scheme we can get the position-filtered electron and ion signals correlating only to the cold ROI or the thermal ions of a given mass. [START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF][START_REF] Garcia | Synchrotron-based double imaging photoelectron/photoion coincidence spectroscopy of radicals produced in a flow tube: OH and OD[END_REF] Note that this scheme also reduces the false coincidences, because for an event to be considered the ion needs to arrive at the expected TOF and at the expected position, similar to the scheme reported by Sztáray et

B. CH 3 + from Photoionization or Dissociative Photoionization

Mass-selected photoelectron kinetic energy matrices show the photoelectron signal as a function of photon energy and electron kinetic energy for a particular mass (presently only including the ROI part in Fig. 2). [START_REF] Chicharro | Threshold photoelectron spectrum of the CH 2 OO Criegee intermediate[END_REF][START_REF] Tang | Double imaging photoelectron photoion coincidence sheds new light on the dissociation of state-selected CH 3 F + ions[END_REF] From these matrices the SPES is extracted by integrating the photoelectron signal along a constant ionic state (diagonal line), up to a maximum value, KE max , according to the expression,

𝑆𝑃𝐸𝑆(ℎ𝜈) = ∫ 𝐴(ℎ𝜐 + 𝐾𝐸, 𝐾𝐸)𝑑𝐾𝐸 𝐾𝐸 𝑚𝑎𝑥 0 (3)
where 𝐴(ℎ𝜐, 𝐾𝐸) is the photoelectron kinetic energy matrix as plotted in Figure 3.

This allows both an implicitly correct hot electron subtraction, and a more relaxed in blue. [START_REF] Poully | Photoionization of 2pyridone and 2-hydroxypyridine[END_REF] The ms-SPES records the signal of photoelectrons with near-zero kinetic energy (KE max = 100 meV) and its energy resolution can be comparable to the traditional TPES. [START_REF] Chicharro | Threshold photoelectron spectrum of the CH 2 OO Criegee intermediate[END_REF][START_REF] Tang | Double imaging photoelectron photoion coincidence sheds new light on the dissociation of state-selected CH 3 F + ions[END_REF][START_REF] Briant | Ar 2 photoelectron spectroscopy mediated by autoionizing states[END_REF][START_REF] Tang | CH 3 + formation in the dissociation of energyselected CH 3 F + studied by double imaging electron/ion coincidences[END_REF] As shown in Fig. 3, the two ms-SPES mainly exhibits the same structures and their intense peaks are located at hν = 9.838 eV, corresponding to the AIE of the methyl radical. In addition, several minor peaks can be observed close to the main peak which are ascribed to the v 2 umbrella vibrational excitations in the photoionization. [START_REF] De Miranda | Threshold photoelectron spectroscopy of the methyl radical isotopomers, CH 3 , CH 2 D, CHD 2 and CD 3 : Synergy between VUV synchrotron radiation experiments and explicitly correlated coupled cluster calculations[END_REF][START_REF] Zhu | Synchrotron threshold photoelectron photoion coincidence spectroscopy of radicals produced in a pyrolysis source: The methyl radical[END_REF] In Fig. 3(b), the electron signal at the high energy part of the ms-SPES is almost zero, as seen in the 10 times magnified data in blue, due to the minute resonant photoionization possibility of the methyl radical within this energy range [START_REF] De Miranda | Threshold photoelectron spectroscopy of the methyl radical isotopomers, CH 3 , CH 2 D, CHD 2 and CD 3 : Synergy between VUV synchrotron radiation experiments and explicitly correlated coupled cluster calculations[END_REF] . (320 cm -1 ) and the CO stretch (505 cm -1 ) for the X 3 A″ ground electronic state, and the OOC bend (497 cm -1 ) and the OO stretch (1578 cm -1 ) for the a 1 A′ excited state. [START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] Voronova et al. used detailed Franck-Condon simulations to fit the TPES, in which the CH 3 -OO torsional mode was treated as a hindered rotor and obtained an AIE of CH 3 O 2 at 10.265 ± 0.025 eV. [START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] However, as their experimental spectrum was of lower resolution and lacked a clear vibrational structures, the fitting was mainly based on the overall envelope of the TPES. The main uncertainty in the AIE was attributed to the relative ratio of the singlet and triplet transition intensities and they found that Franck-Condon simulations with AIEs between 10.24 and 10.29 eV provided acceptable fits to the data. In comparison to the literature TPES 9 (see Fig. S1), owing to the high energy resolution of the DESIRS beamline and of the DELICIOUS III setup, [START_REF] Garcia | DELICIOUS III: A multipurpose double imaging particle coincidence spectrometer for gas phase vacuum ultraviolet photodynamics studies[END_REF][START_REF] Tang | Vacuum upgrade and enhanced performances of the double imaging electron/ion coincidence end-station at the vacuum ultraviolet beamline DESIRS[END_REF][START_REF] Nahon | DESIRS: a state-of-the-art VUV beamline featuring high resolution and variable polarization for spectroscopy and dichroism at SOLEIL[END_REF] the present SPES exhibits a defined vibrational structure, especially at the beginning of the first band. We have also tried to fit the overall SPES with the calculated Franck-Condon factors [START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] and cannot get a satisfying result, due to the two overlapped X 3 A″ and a 1 A′ states with a complex congested profile. So, we focused on the fitting of the vibrational peaks at the beginning of the SPES and a satisfactory Franck-Condon fitting, taking into account the contributions of both overlapped states, is obtained for the well-resolved and intense vibrational peaks below 10.6 eV, as shown in Fig. 5(b). The vibrational peaks in this region, corresponding to the beginning of the first band, are mainly attributed to the CO stretching and the OOC bending modes of the X 3 A″ ground state, and the OOC bending mode of the a 1 A′ excited state. The best match between experimental and simulated spectra is achieved assuming an AIE of CH 3 O 2 of 10.215 ± 0.015 eV, in excellent agreement with the literature high-accuracy theoretical data of 10.21 eV,. [START_REF] Meloni | Energy-resolved photoionization of alkylperoxy radicals and the stability of their cations[END_REF][START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] and the error bar mainly includes the contributions of the energy uncertainty in the Franck-Condon fitting and the synchrotron photon energy resolution. The vibrational peaks in this regionbelow 10.6 eV, corresponding to the beginning of the first band, are mainly attributed to the CO stretching and the OOC bending modes of the X 3 A″ ground state, and the OOC bending mode of the a 1 A′ excited state, as shown the assignments in Fig. 5(b), whereas the two peaks with very weak intensities at hν = 10.11 and 10.17 eV in the SPES are ascribed to the hot bands involved in the photoionization.

Fig. S1 shows a comparison between the TPES of Ref. 9 and our SPES. In the region above ~10.7 eV the TPES band is larger which is somewhat attributed to the temperature differences between the two measurements as determined from the breakdown diagrams (vide infra). The internal temperature of the free radical was determined to be 330 ± 30 K at the SLS, [START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] whereas it was 160 ± 40 K in our experiment (see Section III.D).

The second band of the ms-SPES locatesd in the 11.1-12.0 eV energy range and its vertical ionization energy (VIE) lies at ~11.5 eV, as seen in Fig. 5. The second band is assigned with the aid of theoretical calculations as the second excited electronic state, b 1 A′. Concretely, the geometry optimization and energy calculation of the ground electronic state of the neutral CH 3 O 2 radical are performed at the DFT B3LYP/6-311G* level of theory, whereas those of the excited electronic states of the CH 3 O 2 + cation are at the TDDFT B3LYP/6-311G* level of theory. All these calculations are carried out by using the Gaussian 09 program package. The theoretical calculations show that the electronic configuration of the b 1 A′ cationic state is (1a′) 2 …(9a′) 2 (2a″) 2 (10a′) 2 and its VIE is theoretically calculated to belocates at 11.56 eV at the TDDFT B3LYP/6-311G* level, [START_REF] Frisch | Gaussian 09, Revision C. 01. Gaussian[END_REF] agreeing well with the experimental value of 11.5 eV. We also calculated the AIE (VIE) of the third excited electronic state A 3 A″ at ~12.4 (14.612.9) eV with the same level of theory, i.e. beyond the present photon energy range, and hence it does not contribute to the second band. It is worth noting that we had also tried to calculate the AIE of the b 1 A′ state, but theour theoretical calculations aimed at optimizing the its equilibrium structure of the b 1 A′ state did not converge. This may indicate that the b 1 A′ electronic state is not stable, agreeing well with our experimental results, since the Interestingly, unlike the literature TPES, [START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] in the present SPES there is almost no population in the Franck-Condon gap (~11.1 eV) between the two bands (see Fig. S1).

This discrepancy could be explained by the temperature difference involved in the two experiments. The temperature difference could come from the fact that in our case we separate the weak expansion from the thermal gas using the ion ROI, as shown in Fig. 2, and only take into account the cold part of the molecular beam in the SPES. In addition, the different methods to produce the CH 3 radical could also contribute somewhat to the temperature difference. We used the reaction F + CH 4 -> CH 3 + HF to generate the CH 3 radical, since whereas the literature TPES was obtained using photolysis to initiate the reaction.generate the precursor methyl radical, followed by low-pressure expansion into vacuum which, in the absence of supersonic cooling, yielded a thermalized sample.

Therefore, the internal temperature was nearly two times higher than with the present hydrogen-abstraction method. Another explanation for this discrepancy could be the different sensitivity to autoionization resonances of both methods, which are known to affect threshold spectroscopy in general, and leads to significant transition intensities even in wide Franck-Condon gaps. This latter feature of threshold photoionization (SPES and TPES) is routinely utilized in recording breakdown curves even in photon energy regions with no appreciable peaks in the photoelectron spectrum, or to expand the spectroscopic window into the Franck-Condon gap [START_REF] Tang | Double imaging photoelectron photoion coincidence sheds new light on the dissociation of state-selected CH 3 F + ions[END_REF][START_REF] Briant | Ar 2 photoelectron spectroscopy mediated by autoionizing states[END_REF] .

D. Breakdown Diagram and the Adiabatic Appearance Energy

The X 3 A″ ground electronic state and the a 1 A′ first excited electronic state are bound, as demonstrated in the ms-SPES of the m/z = 47 ions in Fig. 5(a). Earlier theoretical calculations showed that these two states adiabatically correlate to the

CH 3 + (X 1 A 1 ) + O 2 (X 3 Σ g -) and the CH 3 (X 2 A 2 ) + O 2 + (X 2 Δ g ) dissociation limits,
respectively. [START_REF] Meloni | Energy-resolved photoionization of alkylperoxy radicals and the stability of their cations[END_REF] The fractional ion abundances obtained from the ms-SPES of m/z = 47 and 15 plotted as a function of the photon energy yield the breakdown diagram, which are shown in Fig. 6. As the photon energy increases, the energy distribution of the parent cation is shifted to higher energies, thereby leading to more dissociation. Finally, when the photon energy equals the appearance energy of the fragment ion, AE 0K of CH 3 + here, the whole energy distribution is above the dissociation limit, and the ratio of the parent CH In short, the 0 K appearance energy of CH 3 + and the internal temperature of CH 3 O 2 were treated as fitting parameters. Since the dissociation is fast on the timescale of the experiment, the breakdown curves depend only on these two variables. Hence, the diagram can be used effectively as a molecular thermometer, similarly to the earlier work by Voronova et al. [START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] As these new experiments were optimized for a higher-quality photoelectron spectrum, the noise in the breakdown curve is more significant and the best fit model temperature and the 0 K appearance energy of CH 3 + is determined to be 160 ±

IV. CONCLUSIONS

The

SUPPLEMENTARY MATERIAL

See the supplementary material for the slow photoelectron spectrum SPES of CH 3 O 2 obtained at SOLEIL and its threshold photoelectron spectrum TPES at the Swiss Light Source (SLS) adapted from J. Phys. Chem. Lett. 9, 534-539 (2018).

  photoionization of CH 3 O 2 . The first experiment was performed without adding oxygen into the flow tube. The methyl radicals were produced through the hydrogen-abstraction reaction (1) of fluorine atoms with methane (30 sccm, Air Liquide), where fluorine atoms were generated in the microwave discharge of a mixture of 5% F 2 diluted in helium (10 sccm, Air Liquide).

  FIG. 1. Synchrotron photoionization time-of-flight mass spectra measured at hν = 12.0 eV (a) without oxygen and (b) adding oxygen into the flow tube.

al. 26 FIG. 2 .

 262 FIG. 2. Mass-selected ion images and their intensity projections along the y-axis corresponding to (a, c) CH 3 + and (b, d) CH 3 O 2 + , recorded at hν = 12.0 eV, where the left ROI correlates to the part of molecular beam with a distance away from the image center, and the right Back part to the background in the photoionization region.

  photoionization of the methyl radical. But, after the addition of oxygen gas into the flow tube, further weak signals can be identified with small electron kinetic energy at the lower-right corner of Fig.3(c), in the 11.2-12.0 eV photon energy range.

FIG. 3 . 9 C. SPES of CH 3 O 2

 392 FIG. 3. Mass-selected photoelectron kinetic energy matrices corresponding to CH 3 + ions acquired (a) without and (c) with adding oxygen gas into the flow tube; (b) and (d) are the corresponding mass-selected slow photoelectron spectra (ms-SPES), with 10 times magnified data in blue.

FIG. 5 .

 5 FIG. 5. (a) Mass-selected slow photoelectron spectra (SPES) corresponding to m/z = 47 and 15 ions; (b) SPES of CH 3 O 2 (black) and its partial Franck-Condon fitting (purple).

CH 3 O 2 +

 2 cations prepared in the b 1 A′ state fully dissociate into the CH 3 + and O 2 fragments, as shown in Fig. 5(a).

33 FIG. 6 . 2 +.

 3362 FIG. 6. Breakdown diagram for CH 3 O 2 + . Open symbols are experimentally measured ion abundances and lines are the statistical rate theory modeling of the data. The solid gray area represents the uncertainty in the ion temperature (160 ± 40 K), and the patterned area represents the uncertainty in the appearance energy of CH 3 + fragment ions (11.148 ± 0.020 eV).

40 K and 11 . 3 +-

 113 1548 ± 0.020 eV, respectively. The AE 0K agrees with the 11.16 ± 0.05 eV determination of Meloni et al.[START_REF] Meloni | Energy-resolved photoionization of alkylperoxy radicals and the stability of their cations[END_REF] and the 11.164 ± 0.010 eV by Voronova et al.[START_REF] Voronova | Radical thermometers, thermochemistry, and photoelectron spectra: a PEPICO study of the methyl peroxy radical[END_REF] Then, based on the thermochemical cycle, the bond dissociation energies of the parent cation CH 3 O 2 + and the neutral radical CH 3 O 2 are determined at D 0 (CH OO) = 0.93 ± 0.02 eV and D 0 (CH 3 -OO) = 1.31 ± 0.02 eV, respectively, with the AIE of CH 3 O 2 and the literature AIE of the methyl radical.

  photoionization of CH 3 or dissociative photoionization of CH 3 O 2 , the full SPES of CH 3 O 2 was obtained with a resolution of ~10 meV and exhibits two broad bands superimposed with an intricate vibrational structure. The first band of the SPES is attributed to the X 3 A″ and a 1 A′ overlapped electronic states while the second band is assigned as the b 1 A′ excited electronic states with the aid of theoretical calculations. The adiabatic ionization energy of CH 3 O 2 is determined to be AIE = 10.215 ± 0.015 eV. The vertical ionization energy of the b 1 A′ electronic state is determined for the first time and lies at around 11.5 eV. CH 3 O 2 + cations prepared at the b 1 A′ electronic state fully dissociate into CH 3 + and O 2 fragments. The 0 K appearance energy of the CH 3 + fragment ion was determined to be 11.1548 ± 0.020 eV by fitting the breakdown diagram with a CH 3 O 2 internal temperature of 160 ± 40 K, which is significantly lower than the one obtained when CH 3 is produced by the hydrogen-abstraction of CH 4 with photolytically generated Cl. As demonstrated in this work, the i 2 PEPICO combined with the continuous microwave discharge flow tube has proven to be a valuable tool for providing high-accuracy thermochemical data together with rich dynamic information regarding the VUV photoionization and dissociative photoionization of radicals. Other peroxy radicals are being investigated on DESIRS and their high-resolution VUV photodynamics will be the subject of a forthcoming manuscript.

  [START_REF] Meloni | Energy-resolved photoionization of alkylperoxy radicals and the stability of their cations[END_REF][START_REF] Meloni | Photoionization of 1-alkenylperoxy and alkylperoxy radicals and a general rule for the stability of their cations[END_REF] Using the photoionization efficiency curve (PIE) of CH 3 O 2 they determined the AIE to be 10.33 ± 0.05 eV, and the appearance energy of the CH 3 + fragment ion from the dissociative photoionization (DPI) of CH 3 O 2 was reported as 11.16 ± 0.05 eV. The PIE of CH 3 O 2 was also measured at

	Hefei synchrotron by using a VUV photoionization time-of-flight (TOF) mass
	spectrometer and its AIE was reported to be 10.32 ± 0.03 eV. 7 Bernstein et al. also
	observed CH 3 O 2	+ and obtained the rotationally resolved infrared (IR) spectrum of CH 3 O 2

ACKNOWLEDGMENTS

This work was financially supported by the National Natural Science Foundation of China (Nos. 21773249, 91961123, 91544228), the International Partnership Program of Chinese Academy of Sciences (No. 116134KYSB20170048) and the French Agence Nationale de la Recherche (ANR) under grant ANR-12-BS08-0020-02 (project SYNCHROKIN). C.F. is grateful to the Chinese Academy of Sciences President's International Fellowship Initiative (No. 2018VMA0055) and the Xu Guangqi program (No. 43270ZD). B.S. gratefully acknowledge funding by the National Science Foundation (Grant No. CHE-1665464). The authors thank J.-F. Gil, D. Schleier and A. Roeder for their assistances in the synchrotron experiments and the SOLEIL staff for smoothly running the facility and providing beamtime under proposal 20150802.