Yogi Satrya Aryadinata

Anne Laurent

Michel Sala

Mining M2lgp

Level Multiple

Pat- Terns Gradual

Ickddm

M2LGP: Mining Multiple Level Gradual Patterns

Keywords:

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

RADUAL pattern mining has been recently introduced as the topic addressing the automatic discovery of gradual patterns from large databases. Such databases are structured over several attributes which domains are totally ordered, considering a relation ≤. Example 1 reports an example of such a database.

Example 1: We consider the database containing sales (number of kg) from a shop selling fruits. Each tuple from the database corresponds to a cashier ticket. Several approaches have been defined in order to extract Yogi Satrya Aryadinata, Anne Laurent, and Michel Sala are with the Montpellier Laboratory of Informatics, Robotics, and Microelectronics (LIRMM in french), Montpellier, France (e-mail: aryadinata@lirmm.fr, laurent@lirmm.fr, michel.sala@lirmm.fr).

patterns like "The greater the Pineapple, the greater the Cherries" (denoted by {(Pineapples, ↑), (Cherries, ↑)}), these work focusing on two main points pointed below.

The first point is to study how to define the support of such a pattern, i.e. the extend to which this pattern is true. In our example, the support is associated with the proportion of tickets matching some properties. Then, only frequent patterns, i.e. patterns which support is greater than a given threshold, will be considered as being relevant. In the literature, several propositions have been done. [START_REF] Koh | Mining Gradual Dependencies Based on Fuzzy Rank Correlation[END_REF] considers statistical methods (linear regression). [START_REF] Dijorio | Gradual Rules: AHeuristic Based Method and Application to Outlier Extraction[END_REF] considers a heuristic. [START_REF] Jorio | Mining Frequent Gradual Itemsets From Large Databases[END_REF] considers an exhaustive counting of the support based on precedence graphs, while [START_REF] Laurent | GRAANK: Exploiting Rank Correlations for Extracting Gradual Itemsets[END_REF] considers a counting based on rank correlation. Fuzzy approaches have been considered in [START_REF] Ayouni | Fuzzy Gradual Patterns: What Fuzzy Modality For What Result?[END_REF], [START_REF] Quintero | Fuzzy Orderings for Fuzzy Gradual Patterns[END_REF] in order to soften the approach.

For instance, it can be noticed that pineapples and cherries sold on Tickets 1, 2, 3 and 5 can be seen as increasing together. We thus have 4 tickets out of 5 on which we can claim that when the sale of pineapples grows, then the sale of cherries grows, and conversely. It is very important to note that we consider patterns and not rules, which is the reason why we consider a reversible definition.

The second point is to study how to automatically extract such patterns from large databases. Approaches can be compared regarding their efficiency. Methods have been developed by adopting pattern mining algorithms. The efficiency thus relies on the anti-monocity property which states that no frequent pattern containing n attributes can be built over a pattern containing a subset of these n attributes. For instance, if the pattern "The greater the Pineapples, the greater the RedApples" is not relevant, then there no way that the pattern "The greater the Pineapples, the greater the RedApples, the greater the Cherries" is relevant. This property allows to scan the search space in a very efficient manner, by pruning subspaces as they do not have any chance to contain relevant patterns. In [START_REF] Jorio | Mining Frequent Gradual Itemsets From Large Databases[END_REF], binary matrices are defined in order to speed up the calculation, while parallel approaches have been considered in [START_REF] Do | Efficient Parallel Mining of Closed Frequent Gradual Itemsets[END_REF], [START_REF] Quintero | Fuzzy Orderings for Fuzzy Gradual Dependencies: Efficient Storage of Concordance Degrees[END_REF].

These approaches are of great interest, they have been successfully applied on several application domains, such as psychology and biology, where discovering co-variation of gene expressions is very important, and can hardly be performed using traditional statistical methods. The number of attributes (genes) does indeed not allow to test all the possibilities. Moreover, the interesting co-variations stand among several attributes and many methods stop searching after the test of 2 attributes together (e.g., statistical correlation).

However, it may be the case that considering data at a low

G M2LGP: Mining Multiple Level Gradual Patterns

Yogi Satrya Aryadinata, Anne Laurent, and Michel Sala level of granularity does not convey sense in terms of trend analysis. For instance, it may be the case that the sales within one day cannot be regarded as containing any gradually, while the same data aggregated over days (all sales from the same day are summed) may contain gradual trends. The database being considered is thus transformed in order to merge lines. An aggregation function is considered in order to fusion the values, thus leading to the same discussions that the ones from the data warehouse framework: the data being considered (sales here) may be additive, semi-additive or non additive.

In our example, Sales are additive over all attributes and over lines (tickets).

Example 2: We consider the database from Example 1, where T1, T2 and T3 are from Monday and T4 and T5 are from Tuesday. Conversely, it may also be the case that regarding the data attribute per attribute does not convey information, while it can be the case by aggregating columns from the database.

Example 3: For instance, the first two columns may be merged. In this paper, we thus consider these two ways of building multiple level gradual patterns. This work can be linked to data warehouses and OLAP mining as we consider data mining over several attributes (dimensions) described over several levels of granularities. However our framework is not exactly the same, especially because aggregations can be performed on some attributes and not for some other ones, meaning that two attributes may be merged, while other ones are not. This kind of operation is considered as being possible from the semantic point of view because we consider ordinal scales where the value itself does not impact. It is thus possible to compare large values over one high level attribute (e.g., RedFruits) and small ones over another low level attribute (Pineapple).

The paper is organized as follows. Section II details the preliminary definitions. Section III reports existing work on gradual pattern mining and Section IV states the problem we address, while Sections V and VI introduce our contribution, namely the definitions of what Multiple Level Gradual Patterns are and how they can be extracted.

II. PRELIMINARY DEFINITION

We introduce below the definitions taken from the literature in order to define gradual pattern mining. Unfortunately, no unique notation is available in the papers, we thus propose to consider the ones given below.

Definition 1: Gradual-Attribute. A gradual attribute I is defined over a domain dom(I j ) on which an order ≤j (or simply ≤) is defined.

Definition 2: Gradual-DB. A gradual database is a set of tuples T defined over the schema S = {Id,I 1 ,...,I n } of n gradual attributes where Id is an identifier (primary key).

Example 1 shows an example of a database which schema is S = {Pineapples, RedApples, Cherries} containing 5 tuples defined over three attributes which domains are IN.

Definition 3: Gradual item. A gradual item is a pair (i, v) where i is an item and v is variation v ∈ {↑, ↓}. ↑ stands for an increasing variation while ↓ stands for a decreasing variation. For example, (Pineapples, ↑) is a gradual item.

Definition 4: Gradual Pattern (also known as Gradual Itemset). A gradual pattern is a set of gradual items, denoted by GP = {(i 1 , v 1 ), . . ., (i n , v n )}. The set of all gradual patterns that can be defined is denoted by GP.

For example, {(Pineapples,↑),(RedApples,↑)} is a gradual itemset.

Definition 5: Tuple Ordering Over a Set of Attributes A. The tuples from a gradual database are ordered by defining an order ≺ with respect to a gradual pattern GP {(i 1 , v 1 ), . . . , (i n , v n )}. Two tuples t and t′ can be ordered with respect to GP , denoted by t ∈ GP t′ if all the values of the corresponding items can be ordered with respect to the variations: for every

i k (k ∈ [1,n]), t.i k ≤′t .i k if v l =↑ and t′.i k ≤ t.i k if v l =↓.
The support of a gradual pattern indicated to which extend it can be found in the database.

Definition 6: Gradual Support. The support of a gradual pattern over a gradual database GDB is a function sup from GP to [0,1] that holds the following property: for all GP 1 , GP 2 ∈ GP, GP 1 ∈ GP 2 ∈ supp(GP 1 ) ≥ supp(GP 2 ).

III. RELATED WORK

A. Gradual Patten Mining

In the 70s, gradual patterns were used to model system behaviors. Patterns were designed by experts. A complete theoretical framework of gradual rules into the fuzzy context is given in [START_REF] Dubois | Gradual inference rules in approximate reasoning[END_REF], with a comparison of fuzzy implication for gradual dependencies. Among them the most used is RescherGaines (RG) implication.

Regarding crisp data mining approaches, the authors agree on the definition of gradual item (which couples a classical item and a variation) and gradual itemsets (set of gradual items), but have proposed several ways of defining the support.

[15] considers a regression-based definition. [START_REF] Jorio | Mining Frequent Gradual Itemsets From Large Databases[END_REF] the authors consider another definition of the support based on the maximum proportion of tuples that can be ordered according to the gradual itemset. while [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] and [START_REF] Laurent | GRAANK: Exploiting Rank Correlations for Extracting Gradual Itemsets[END_REF] consider the number of tuples that are concordant and discordant, in the idea of exploiting the Kendall's tau ranking correlation coefficient [START_REF] Kendall | The problem of m rankings[END_REF].

[15] defines gradually as a co-variation of gradual dependency, where A gradual dependency such as the more A, the more B holds if an increase in A comes along with an increase in B. In order to identify such relationships, it proposes to perform a linear regression analysis between the two attributes. The validity of the gradual tendency is evaluated from the quality of the regression. This definition and this extraction method apply to pairs of attributes. The extension proposed by [START_REF] Koh | Mining Gradual Dependencies Based on Fuzzy Rank Correlation[END_REF] to longer itemsets considers the case of fuzzy data, for which attributes contain the membership degrees of the data to modalities. It exploits this fuzzy logic framework and the fact that itemsets are interpreted as conjunction of the items they contain: a membership degree to the itemset can be computed using a tnorm, applied to the membership degrees to the items of the considered itemset. The gradual tendency is then understood as a covariance constraint between the aggregated membership degrees. Thus itemsets of length higher than 2 can be handled as itemsets of length 2.

Other works take a different point of view and interpret gradual dependencies as constraints imposed to the order induced by the attributes, and not to their numerical values: in [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] gradual dependencies are considered as generalizations of functional dependencies that replace the equality conditions by variation conditions on the values. This definition takes into account a causality relationship the itemsets. It states that the ordering induced by attribute A must be identical to that derived from attribute B. In the case of dependencies such as the more A, the less B, the constraint imposes that the orders must be reversed. [START_REF] Dijorio | Gradual Rules: AHeuristic Based Method and Application to Outlier Extraction[END_REF] proposes an approach based on conflict sets. The authors propose a heuristic to compute the support for gradual itemsets, in a level-wise process that considers itemsets of increasing lengths. It consists in discarding, at each level, the rows whose so-called conflict set is maximal, i.e. the rows that prevent the maximal number of rows to be sorted. The selection is made by random in case of several conflict sets having same size. Note that this heuristic may lead to loose some loss. Indeed, it may be the case that a raw seam to create a lot of conflicts compared to another one, but that this number of conflicts is still lower than the conflicts generated at the next level.

Example 4: The table below reports the conflicts regarding the pattern {(Pineapples, ↑), (RedApples, ↓)}. Note that the lines have been reordered to facilitate the reading by considering the ranking on the values over the attribute Pineapples. In the Table IV, the conflict set reports the Tickets that are in conflict with the one being considered. In [START_REF] Jorio | Mining Frequent Gradual Itemsets From Large Databases[END_REF], the support is defined as being the longest path of the precedence graph of tuples regarding a gradual pattern. For instance, we can design the graph of Tickets regarding the ordering on the gradual pattern {(Pineapples, ↑), (RedApples, ↓)} as displayed on Figure 1. It can for example be seen that T3 is only linked with T5. T3 precedes T5 as T3.Pineapples ≤ T5.Pineapples and T3.RedApples ≥ T5.RedApples. The GRAANK approach from [START_REF] Laurent | GRAANK: Exploiting Rank Correlations for Extracting Gradual Itemsets[END_REF] interprets gradual patterns in terms of ranking correlation. Binary matrices from [START_REF] Jorio | Mining Frequent Gradual Itemsets From Large Databases[END_REF] can then be considered in order to speed up the algorithms. The problem of rank correlation has been extensively studied by statisticians, and several measures have been proposed, distinguishing between two ranks and multiple rank comparison. Regarding ranking pairs, the most used measures are the Spearman correlation and the Kendall's tau. The Kendall's tau is defined as follows: given n objects to be ranked, and σ k , k = 1,2 two rankings where σ k (x) gives the rank of object x in σk ranking, the Kendall's tau relies on the definition of concordant and discordant pairs: concordant pairs (i,j) are pairs for which the rankings agree, i.e. either σ 1 (i) ≤ σ 1 (j) and σ 2 (i) ≤ σ 2 (j), or σ 1 (i) ≥ σ 1 (j) and σ 2 (i) ≥ σ 2 (j). Non concordant pairs are called discordant pairs. The Kendall's tau is then defined as the proportion of discordant pairs, i.e. the frequency of pair-wise inversions.

Example 5: For instance, from Example 1, when considering the gradual pattern {(Pineapples, ↑), (RedApples, ↓)}.

-T1 and T2 are concordant -T1 and T3 are discordant -T1 and T4 are concordant -T1 and T5 are concordant -T2 and T3 are discordant -T2 and T4 are concordant -T2 and T5 are concordant -T3 and T4 are concordant -T3 and T5 are concordant -T4 and T5 are concordant Fuzzy extensions have been defined in order to deal with real life applications where data and knowledge are often not crisp. [START_REF] Ayouni | Fuzzy Gradual Patterns: What Fuzzy Modality For What Result?[END_REF], [START_REF] Ayouni | Genetic Programming for Optimizing Fuzzy Gradual Pattern Discovery[END_REF] study the possibility that the graduality is not over all the attribute but may be hidden somewhere in the domain of values. For instance, when mining gene expression, it may be the case that there is no pattern such as "The more/less the expression of gene G i , the more the expression of gene G j " but that it is rather the case that the pattern "The more/less the expression of gene G i is almost 0.2, the more the expression of gene G j is almost 0.8". The proposal proposes a definition of such fuzzy patterns and algorithms based on genetic programming in order to discover the most relevant parts of the universe (e.g. almost 0.2 and almost 0.8 in the above example).

[17], [START_REF] Quintero | Fuzzy Orderings for Fuzzy Gradual Patterns[END_REF] propose to consider fuzzy orders instead of crisp orders so as to tackle the problem of data where differences between values may not always convey a crisp decision. For instance, it may be the case that an expression of gene of 0.1887 may not be that lower than an expression of gene of 0.1888. The work is based on the definitions given by [START_REF] Bodenhofer | Orderings Fuzzy Sets Based on Fuzzy Orderings Part I: The Basic Approach[END_REF]- [START_REF] Bodenhofer | Towards Robust Rank Correlation Measures for Numerical Observations on the Basis of Fuzzy Orderings[END_REF].

B. OLAP Mining and Hierarchical Data Mining

When dealing with hierarchies in databases, the main works have been done in the framework on data warehouses and OLAP (On-Line Analytical Processing). Data warehousing refers to the process of constructing and exploiting of the data warehouse. Data warehousing thus includes the integration of the data from multiple sources into a unified schema at a single location to facilitate data analysis for decision making. Thus, the construction of a data warehouse includes data integration, data cleansing, data consolidation and OLAP [START_REF] Chaudhuri | An overview of data warehousing and OLAP technology[END_REF], [START_REF] Codd | Providing OLAP (OnLine Analytical Processing) to user-analysts: An it mandate[END_REF]. OLAP systems are constructed in a data warehouse environment that serves as a repository of the data to be processed. Data are organized over measures (e.g., number of sales) studied with respect to dimensions (e.g., product, month, city) which can be organized with hierarchies (e.g., month-quarter-year). OLAP operations are defined to help end-users to navigate through the data. Some of the operations are dedicated to the management of hierarchies: roll-up allows to go from data described at a low level of granularity (e.g., month) to data given at a higher level of granularity (e.g., quarter).

OLAP Mining has been first introduced in 1997 by Jiawei Han as a mechanism which integrates OLAP with data mining so that mining can be performed in different portions of databases or data warehouses and at different levels of abstraction at users finger tips.

However, authors have considered multiple level data mining before studying intensively data warehouses. In [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF], the beginnings of the hierarchy management in the extraction of association rules and sequential patterns are proposed. The authors suppose that the hierarchical relations between the items are represented by a set of taxonomies. They make it possible to extract association rules or sequential reasons according to several levels of hierarchy. They modify the transactions by adding for each item all of its ancestors in associated taxonomy. Then, they generate the frequent sequences while trying to filter with the maximum redundant information and by optimizing the process using several properties. However, this approach cannot be scalable in a multidimensional context. Indeed, to add on each dimension the list of the ancestors of one item in taxonomy, for each transaction, is unthinkable.

That would be equivalent, in the worst case, to multiply the size of the database by the maximum depth of a hierarchy and this for each dimension of analysis, scan of this basis would be then too much expensive.

The approach of J. Han et al. [START_REF] Han | Mining multiple-level association rules in large databases[END_REF] is quite different. The authors tackle the association rule extraction problem, but this approach can be adapted to sequential pattern extraction.

Starting at the highest level of the hierarchy, they extract the rules on each level while lowering the support when going down in the hierarchy. The process is reiterated until no rules can be extracted or until the lowest level of the hierarchy. However, this method does not make it possible to extract rules containing items of different levels. For example wine and drinks cannot cohabit in such a rule. This method thus proposes the extraction of intra level of hierarchy association rules. It thus does not make it possible to answer the general problems of extraction of the sequences on various levels of hierarchy. Furthermore, the implementation of this approach in a multidimensional context can be discussed. If several taxonomies exist (one by dimension), does one have to move on the same levels of hierarchy on various taxonomies or to combine these levels? This type of extraction can be expensive in time, because the mechanism of extraction of knowledge can be reiterated several times (depth of taxonomy), which is not inconsiderable.

[19] introduces multiple level sequential patterns. As it is proven that finding out all sequential patterns from a database is an np-complete problem, the authors propose to consider convergent and divergent sequential patterns. When considering convergent patterns, the levels of granularity of the patterns along the sequence decreases (e.g. from county to city). When considering divergent patterns, the levels of granularity of the patterns along the sequence increases (e.g. from city to county). Such patterns are of the form < (coke, Paris)(soda, Paris) > meaning that in many cases, there has been coke sold in Paris and then soda (higher level compared to coke) sold in Paris. The authors highlight the interest of extracting the "most specific" patterns, i.e. the patterns such as there does not exist any pattern included within it (either because some items can be deleted, or because some items can be expressed at a lower level of granularity) which is frequent. Looking for search patterns is interesting as patterns at high level of granularity are often already known and do not convey relevant knowledge for the end-users.

In this section, we have presented the works related to our proposal. In the next session, we introduce our contribution M2LGP standing for Mining Multiple Level Gradual Patterns.

IV. M2LGP: PROBLEM STATEMENTS

Starting from the definitions from Section II consolidated from the existing works, we state an original framework. We claim that many data are equipped with hierarchies, and we want to define:

-how multiple level gradual databases can be defined; -how multiple level gradual patterns can be defined; -how the support on multiple level gradual patterns can be defined; -how multiple level gradual patterns can be extracted. For this purpose, we rely on the existing work for defining two main ways of considering multiple level data. Indeed, data can be aggregated over lines (horizontal aggregation) or columns (vertical aggregation).

Considering the first case, when lines are aggregated, the problem is to define how the values are aggregated over every attribute. It should be noted that lines can be aggregated over one or several attributes, but that it may be the case that some attributes are not aggregated. In this case, all the lines remain in the database but some values change in order to represent data at a higher level of granularity.

Example 6: For instance, data from Example 1 can be merged as shown above, where the 5 lines are merged into 2 lines (Monday and Tuesday). They may also be merged for certain attributes but not for all. For instance, below is the dataset transformed by aggregating over lines for attribute Pineapples.

This kind of operation may be interesting when some attributes are not relevant at a low granularity level while some other ones are. It could thus be compared to a kind of semantic normalization. Such a partial aggregation is noted with parenthesis on the values of aggregated attributes (Pineapples here). Considering the case where columns are merged, the main issue to address is the definition of the hierarchies. In the case of complex hierarchies, it may indeed be the case that some values can be grouped into different super-partitions.

Example 7: For instance, PineApples and RedApples are considered as being WithoutKernel and thus grouped, but we may also consider that RedApples and Cherries can be grouped in order to build the "RedFruit" group.

V. M2LGP: DEFINITIONS

A multiple level attribute MLA is an attribute equipped with a hierarchy. This hierarchy is defined as a set of levels where every level is represented as a partition, all the partitions being embedded.

Definition 7: Level of Granularity. Given a domain D of an attribute. A level of Granularity L i (D) is defined as a partition P i (D) of D and a set of labels describing every element of the partition, this set of label being the domain dom(L i ) of the level.

Example 8: We consider the Date attribute with dom(Date) ={01JAN2012-8:00,02JAN2012-11:00, 05AUG2012-07:00, 27SEP2013-09:00, 30SEP2013-05:00, 30SEP2013-08:30}.

We may define three levels: L 0 = DateDay, L 1 = DateMonth, L 2 = DateYear, where :

-dom(DateDay) = dom(Date), dom(DateMonth) = {JAN2012, AUG2012, SEP2013}, dom(DateYear) = {2012, 2013} -DateMonth={{01JAN2012-8:00,02JAN2012-11:00 },{05AUG2012-07:00,{27SEP2013-09:00},30SEP2 013-05:00,30SEP2013-08:30} Definition 8: Embedded Levels of Granularity. Two levels of granularity L i and L j are said to be embedded (L i ∈ L j ) if L j defines a partition of L i .

Definition 9: ML-Attribute. An ML-Attribute MLA is defined by:

-a label, -a domain dom(MLA), -a set of embedded levels of granularity L = L 0 (MLA),...,L g (MLA) such as every domain dom(L i ) is ordered with a relation ≤L i . Example 9: Temporal attributes are a particular case of attributes. Although not being numeric, dates can be aggregated when lines are merged in an adequate manner. For instance, days can be regrouped into months. The attribute Date with domain dom(Date) and levels .given above dom(DateDay) is ordered as: 01JAN2012 -8 : 00 ≤ 02JAN2012 -11 : 00 ≤ 05AUG2012-07 : 00 ≤ 27SEP2013 -09 : 00 ≤ 30SEP2013 -05 : 00 ≤ 30SEP2013 -08 : 30. dom(DateMonth) is ordered as JAN2012 ≤ AUG2012 ≤ SEP 2013. dom(DateYear) is ordered as 2012 ≤ 2013.

Remark 1: This definition does not allow complex hierarchies as they can be found in data warehouses, although such complex hierarchies could allow to manage the example shown above where there are two incompatible levels of granularity (With/Without kernel and NotRed/Red).

Given an ML-attribute MLA, an aggregation function Agg is defined over the values taken by this attribute that allows to compute the aggregated value when going from one level of granularity up to another one. The attribute is said to be additive if values can be summed up.

Definition 10: ML-DB. A multiple level gradual database is a set of tuples T defined over the schema S = {Id,A 1 ,...,A n } of n+1 multiple level gradual attributes (ML-Attributes).

Remark 2: Note that the identifier attribute Id is an MLattribute. This allows to manage vertical aggregation.

A gradual database can be displayed at several levels of granularity. It is said to be additive if all attributes are additive, semi-additive if at least one but not all attributes are additive, and non-additive if none of the attributes is additive.

Definition 11: ML-DB-Disp. A gradual database displayed is given by an ML-DB and a set of levels {L 1 ,...,L n } associated with every attribute from the schema. For instance, the information is displayed at different levels of granularity in the previous tables.

Remark 3: It should be noted that based on this definition, the number of items can change when the display is changed.

Definition 12: ML-Item. Given an ML-DB, an ML-Item is a pair (I, variation) where I ∈ U A∈S U LI∈LA dom A (L i ), and variation is ↑ or ↓.

Example 10: For instance, (RedFruit, ↓), (Pineapples, ↑) are ML-Items.

Definition 13: Compatible ML-Item. Two ML-Items are said to be compatible if none of their first part I is the value taken from an upper hierarchy level.

Example 11: For instance, (RedFruit, ↓) and (Pineapples, ↑) are compatible, while (RedFruit, ↓) and (Cherries, ↑) are not.

Definition 14: ML-Pattern. An ML-Pattern is a set of compatible ML-items.

Definition 15: ML-Pattern Inclusion. A pattern P 1 is said to be "ML-included" in another pattern P 2 (P 1 ∈ MLP 2 ). if for every ML-Item I k 1 of P 1 , there exists an item I l 2 from P 2 such as either I k 1 = I l 2 or I l 2 is an item from an upper level and the variation is the same.

Example 12: For instance P = {(Date, DateDay, ↑), (Fruit, RawFruit, ↓)} is P′ = {(Date,DateDay,↑),(Fruit,ColorFruit,↓)}.

Definition 16: Multiple Level Gradual Support. Given an ML-DB-Disp MLDBD and an ML-Pattern P, the support of P over MLDBD is a function sup from GP to [0,1] that holds the following property: for all P 1 , P 2 ∈ GP, P 1 ∈ MLP 2 ∈ supp(P 1 ) ≥ supp(P 2 ).

On the basis of the two support definitions, the main point to observe is that they are strongly related to the number of lines from the database.

When performing a horizontal aggregation (merging columns), the number of lines does not change, although it is changed when lines are merged. However, the gradual pattern being considered has changed (as the columns changed).

When performing a vertical aggregation (merging lines), the number of lines may change, either for one or for all the attributes.

Whatever the aggregation, the support can still be computed using either the longest path or the rank correlation.

VI. M2LGP: EFFICIENT MINING

Although aggregating the columns and/or lines may be seen as a reduction, it is not the case that it simplifies the complexity of the algorithm. Indeed, the reduction is true only at one level of granularity while all levels may be considered.

In order to address the problem of navigating through this huge search space, we define the following strategies and discuss their pros and cons.

A. Building the search space: MLGP Operators and MLGP Lattice

The navigation through candidate patterns is performed via operators that allow to apply horizontal and vertical (dis)aggregation. These operators are connected to the OLAP roll-up and drill-down operators, although not being exactly identical.

B. Navigating Through the Search Space: Defining Strategies

Considering these operations and the resulting lattice representing the search space, we consider several strategies.

Given an ML-DB-Disp D, we can aggregate or disaggregate this database over lines or columns.

Definition 17: ML-HAgg. An H-Aggregation consists in merging several lines with respect with a line hierarchy (given a source level and a target level), regarding one or several attributes. The value taken on these attributes are aggregated. Such an aggregation is denoted by () Example 13: For instance, lines of Ticket1 to Ticket3 one the one hand, and of Ticket4 and Ticket5 on the other hand have been merged over the Pineapples attribute, which is then denoted by (Pineapples), the values being themselves enclosed within parenthesis.

Remark 4: Although having been merged, the lines may remain separated if some attributes are not concerned with the ML-HAgg operation, which is a major difference with OLAP roll-up. The aggregated value is repeated on all the lines, which is not problematic as we consider equal values as being comparable in both ways (≤).

Example 14: In our example, the lines are merged over the Pineapples attribute but not over the other attributes.

Definition 18: ML-HDisagg. An ML-HDisagg with respect with a hierarchy (given a source level and a target level), regarding one or several attributes, consists in drilling down by generating several lines from one line and by recomposing (from the raw data) the unmerged values. The value taken on these attributes are aggregated.

Definition 19: ML-VAgg. A vertical aggregation consists in merging several columns with respect with a hierarchy (given a source low level and a target high level).

Definition 20: ML-VDisagg. A vertical disaggregation consists in splitting one column into several columns with respect with a hierarchy (given a source high level and a target low level).

Definition 21: Most Specific ML-Pattern. Given a minimum support threshold minsup, an ML-pattern P 1 is said to be the "most specific" pattern if there does not exist any P 2 such as P 2 ∈ ML P 1 and supp(P 2 ) ≥ minsup.

Taking these operations into account, the lattice representing the search space is based on the classical lattice of all the parts of the n items and variations, which is enriched by levels.

The first strategy is to explore all the search space. Instead of having a lattice composed by 2 n nodes in the case of n attributes, the search space is then composed of 2 l where l is the sum of all numbers of levels. For instance, we may consider the attribute Fruit with 2 levels (raw level, and Color Level). Moreover, a strategy should be followed in order to navigate through the levels. However, there is no useful monotonicity between levels, which prevents from pruning the space in an efficient way. It can thus be the case that exploring this search space is not possible. This is the reason why other methods can be considered.

Convergent and divergent patterns have been proposed in the sequential pattern mining framework [START_REF] Plantevit | Mining Multidimensional and Multiple-Level Sequential Patterns[END_REF], where items are naturally organized as they are ordered over time. In the context of multiple level gradual patterns, it is unfortunately not the case that we can go up or down while going through attributes.

The last proposal is thus to use a heuristic. In our framework, we propose to compute all the supports for all multiple level gradual patterns of size 2 (containing 2 ML-items) and to consider the levels that maximize the support at this step. Note that this also holds for the horizontal aggregation in order to decide to which extend lines must be merged.

Example 15: For instance, if considering the dataset structured over the schema Date, Fruits, all the possibilities of levels and crossing will be considered: (DateDay, RawFruits),(DateMonth, RawFruits), (DateYear, RawFruits), (DateDay, ColorFruits), DateMonth, ColorFruits) (DateYear, ColorFruits) and the most successful regarding the support will be chosen.

Note that pairs of such ML-items may be incompatible. For instance, it may be the case that Fruits is considered at the RawFruits level when being combined with Date but considered at the ColorFruits level when combined with another attribute. In this case, we propose to choose between two strategies: keep all levels or choose the one optimizing the support.

VII. M2LGP: ALGORITHMS AND EXPERIMENTS

Our algorithms are based on the decomposition of the database in order to deal with all the hierarchies, as described in the algorithms below. We then run experiments using existing implementations of gradual pattern mining algorithms. Experiments have been run on both synthetic and real data reporting expressions of gene in the case of cancer. As can be seen on Fig. 2, the presence of the hierarchies makes the problem difficult to tackle as it exponentially increases the search space. We thus aim at using parallel programming in further work.

VIII. CONCLUSION AND FUTURE WORKS

In this paper, we propose the original method M2LGP for mining multiple level gradual patterns. Such patterns allow to take into account the natural structures of the information that can often be considered at different levels of granularity. The paper proposes a formal framework for redefining all the concepts in this particular framework, including a discussion on the computation of the support. The topic is of great importance since data mining has been pointed as a key challenge, especially when dealing with big data. The problematic is not easy, since multiple level gradual patterns are similar to existing frameworks (gradual patterns, multiple level association rules, OLAP Mining) but are still an original approach as they contain specificities that are difficult to manage.

Future work include the study of fuzzy partitions for defining fuzzy multiple level gradual patterns and their support. We will also further investigate the algorithms for extracting the multiple level gradual patterns. The efficient implementation of this proposal will be based on the existing parallel softwares (such as [START_REF] Do | Efficient Parallel Mining of Closed Frequent Gradual Itemsets[END_REF]).

Fig. 1

 1 Fig. 1 Precedence Graph for {(Pineapples, ↑), (RedApples, ↓)}

  Output : Set of G D G D ← ; TransformDB(DB); for each transformed database D do AlgoGP(D); end

Fig. 2

 2 Fig. 2 Runtime regarding the number of attributes


David R Bickel
email: dbickel@uottawa.ca

Testing prediction algorithms as null hypotheses: Application to assessing the performance of deep neural networks

Keywords: big data, data science, deep learning, deep neural network, model predictive distribution, model predictive p value, regression

Bayesian models use posterior predictive distributions to quantify the uncertainty of their predictions. Similarly, the point predictions of neural networks and other machine learning algorithms may be converted to predictive distributions by various bootstrap methods. The predictive performance of each algorithm can then be assessed by quantifying the performance of its predictive distribution. Previous methods for assessing such performance are relative, indicating whether certain algorithms perform better than others. This paper proposes performance measures that are absolute in the sense that they indicate whether or not an algorithm performs adequately without requiring comparisons to other algorithms. The first proposed performance measure is a predictive p value that generalizes a prior predictive p value with the prior distribution equal to the posterior distribution of previous data. The other proposed performance measures use the generalized predictive p value for each prediction to estimate the proportion of target values that are compatible with the predictive distribution. The new performance measures are illustrated by using them to evaluate the predictive performance of deep neural networks when applied to the analysis of a large housing price data set that is used as a standard in machine learning.

Today's challenges of interpreting and using big data sets create many opportunities for the development of machine learning algorithms and other methods of statistical data analysis. Examples of big data include records of customer purchases and interactions on web sites used to suggest purchases, email messages used to detect spam, and voice recordings used to interpret speech. Since 2012, deep learning algorithms in the form of deep neural networks have often dramatically outperformed more conventional machine learning algorithms, where "deep" refers to the multiplicity of hidden layers of parameters fit to data (e.g., [START_REF] Charniak | Introduction to Deep Learning[END_REF][START_REF] Krohn | Deep Learning Illustrated: A Visual, Interactive Guide to Artificial Intelligence[END_REF][START_REF] Wani | Advances in Deep Learning[END_REF].

In spite of the successes of data science, uncertainty in classification and prediction performance measures is usually neglected. That is unfortunate since performance uncertainty can be substantial even with big data. The reason is that a data set that is large when measured by how much disk space it requires can be small in terms of its effective sample size, even without a strong dependence between variables. For example, the first large-scale studies of gene expression measured gene expression over thousands of genes-in a single individual.

An advantage of Bayesian models is that they not only make predictions but also quantify the uncertainty in those predictions. That is accomplished in the form of a posterior predictive distribution, from which error bars and utility-maximizing decisions may be derived. Ideally, non-Bayesian prediction algorithms would also generate distributions of predictions rather than a single prediction. Simple ways to generate predictive distributions from point predictions are reviewed in Section 2.

The performance of each algorithm's predictive distribution may then be measured in such a way as to discourage both suppressing the uncertainty on one hand and exaggerating it on the other hand. Previous measures of the performance of predictive distributions (e.g., [START_REF] Quiñonero-Candela | Evaluating predictive uncertainty challenge[END_REF] are comparative in the sense that they indicate whether one prediction model performs better than another. An absolute measure, by contrast, could indicate whether a predictive distribution performs adequately or whether alternative prediction models should be considered.

The difference between relative and absolute measures of predictive performance is analogous to relative and absolute measures of evidence used in hypothesis testing. In Bayesian hypothesis testing, the posterior probability that the null hypothesis is true cannot be considered without simultaneously considering the probability that the null hypothesis is false. The posterior probability of the null hypothesis depends on the Bayes factor, a comparative measure of how much the evidence favors the truth of the null hypothesis compared to how much it favors the falsity of 1 the null hypothesis. On the other hand, in null hypothesis significance testing, a sufficiently low p value indicates a problem with the null hypothesis without comparing it to other hypotheses.

The problem could be that the value of the parameter of interest differs from the null value or that the assumptions behind the statistical test are violated. How low is low enough to indicate a problem and other pragmatic issues are debated [START_REF] Benjamin | Redefine statistical significance[END_REF]. In any case, the p value is an absolute measure of the compatibility of the null hypothesis with the data in a way that the posterior probability is not. While Bayesian model selection is certainly ideal in the presence of enough information about the hyperprior distribution over the models, null hypothesis significance testing arguably plays important roles in its absence. That is largely due to the ability of a p value to test a null hypothesis without specifying distributions under alternative hypotheses.

The p value concept is generalized in Section 3 to serve as an absolute measure of the predictive performance of a frequentist or Bayesian regression model, a neural network, or another machine learning algorithm. It is intended to answer the question of whether a statistical model or algorithm predicts well or not rather than the usual question of whether it predicts well relative to other methods.

Absolute performance measures are also useful when multiple methods are available. When all methods tried initially perform poorly, ranking them in terms of relative performance is of little value. Absolute measures of performance would in that case indicate that other methods should be considered. In addition, when it is advantageous to average the predictions of multiple methods, absolute measures of performance provide feedback on the performance of the average. With one generalized p value per prediction, multiple p values may be used together to generate additional measures of absolute predictive performance. Those proposed in Section 4 apply to neural networks and many other models, where the term "model" is much broader than a statistical model in the sense of a parametric family of distributions. The term prediction model refers to any mathematical construct that can make predictions about future data on the basis of data already observed. Following [START_REF] Breiman | Statistical modeling: The two cultures (with comments and a rejoinder)[END_REF], there are two broad types of prediction models: data models are mathematical expressions specifying possible distributions of data; and algorithmic models are other mathematical expressions that make predictions on the basis of data. Whereas data models are associated with parametric and nonparametric statistical inference, algorithmic models are associated with data science in general and machine learning in particular. Both data models and algorithmic models include prediction models with and those without prior distributions. The former are called Bayesian models, and all other prediction models are called prior-free models.

For example, a data model may be parametric or nonparametric, prior-free or Bayesian. Successful algorithmic models include random forests, support vector machines, prior-free neural networks, and Bayesian neural networks.

Even after deciding on a neural network of a certain structure as the type of prediction model, one must set many hyperparameters before it can fit its adaptive parameters to the data. Such A data set often used in machine learning has 13 independent variables used to predict the value of houses in an area of Boston. There is considerable uncertainty about the type of prediction model to use to predict the value of houses from the independent variables, whether the prediction model is a data model or an algorithmic model. In Section 5, the data are analyzed using three deep neural networks to illustrate the proposed measures of predictive performance.

A predictive distribution for each prediction model

Let mdl denote an integer serving as the index of a prediction model. The ith of n observations consists of y i , a value of the dependent variable, and of x i , a vector of m independent variables. Given x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ), the predictive probability density for predicting y n +1 by y n +1 on the basis of

x n +1 is f prdct mdl y n +1 ; (x , y) , x n +1 . The corresponding probability density function f prdct mdl (•; (x , y) , x n +1
) is called the model predictive distribution of mdl.

Example 1. According to data model mdl, y was drawn from a probability density function

f mdl (•| x , θ, λ mdl )
, where θ is a vector of unknown parameter values of interest and λ mdl a nuisance parameter consisting of all other relevant unknowns. If mdl is a Bayesian model, then the pair (θ, λ mdl ) has a prior distribution represented as a probability density π mdl (θ, λ mdl ). The posterior predictive distribution is the probability density function defined by

f prdct mdl y n +1 ; (x , y) , x n +1 = f mdl y n +1 | x n +1 , θ, λ mdl π mdl (θ, λ mdl | (x , y)) dθdλ mdl ,
where π mdl (θ, λ mdl | (x , y)) is the posterior probability density determined by Bayes's theorem.

Example 2. Consider the prediction y mdl,n +1 = η mdl ((x , y) , x n +1 ) of y n +1 , where η mdl is a function determined by prediction model mdl. For example, if mdl is a prior-free data model with the f mdl (•| x , θ, λ mdl ) of Example 1, then y n +1 could be predicted by its expected value as

y mdl,n +1 = η mdl ((x , y) , x n +1 ) = y ′ n +1 f mdl y ′ n +1 | x n +1 , θ (x , y) , λ mdl (x , y) d y ′ n +1 ; (1) θ (x , y) , λ mdl (x , y) = arg sup (θ,λ mdl ) f mdl (y | x , θ, λ mdl ) .
To define a model predictive distribution, generate x (b) , y (b) , the bth of B bootstrap samples by taking n independent draws, with replacement, from the observations (x 1 , y 1 ) , . . . , (x n , y n ).

The bootstrap samples x (1) , y (1) , . . . , x (B) , y (B ) in turn generate the bootstrap predictions

y (1) mdl,n +1 , . . . , y (B )
mdl,n +1 , where y

(b) mdl,n +1 = η mdl x (b) , y (b) , x n +1 .
In parametric bootstrapping (e.g., [START_REF] Harris | Predictive fit for natural exponential families[END_REF], the bootstrap predictions then estimate the parameter values of another distribution. The probability density function fitted to the bootstrap predictions, called the bootstrap predictive distribution, is then used as f prdct mdl (•; (x , y) , x n +1 ). A simple case is N µ mdl , σ 2 mdl , the normal distribution that has a mean of µ mdl , the sample mean of the bootstrap predictions, and a variance equal to σ 2 mdl , the usual unbiased estimate of the variance of the bootstrap predictions. When considered as a point prediction, µ mdl is an example of what [START_REF] Breiman | Bagging predictors[END_REF] 1) , y (1) , . . . , x (B) , y (B) results in the B trained models η mdl x (1) , y (1) , • , . . . , η mdl x (B ) , y (B ) , • . Applying them to

x n +1 yields y In some cases, parametric bootstrap predictive distributions and nonparametric bootstrap predictive distributions (e.g., [START_REF] Fushiki | Nonparametric bootstrap prediction[END_REF] have the frequentist properties needed to qualify as predictive confidence distributions [START_REF] Schweder | Confidence, Likelihood, Probability: Statistical Inference with Confidence Distributions[END_REF]. For other ways to generate a predictive confidence distribution as f prdct mdl (•; (x , y) , x n +1 ), see [START_REF] Shen | Prediction with confidence -a general framework for predictive inference[END_REF]. The predic-tive likelihood methods described in [START_REF] Eklund | Forecast combination and model averaging using predictive measures[END_REF] might also be used to generate

f prdct mdl (•; (x , y) , x n +1 ).
For concision, this paper presents y as continuous. Applying the proposed framework to discrete dependent variables would require using a probability mass function as f prdct mdl (•; (x , y) , x n +1 ) and approximating integrals by sums.

P values for assessing predictive performance

Consider a data model mdl with the f mdl (•| x , θ, λ mdl ) of Example 1. Recall that for testing the null hypothesis that θ = θ H 0 , an observed test statistic T (y, θ H 0 ) and its random counterpart

T (Y , θ H 0 ) together define the p value p mdl ((x , y) , θ H 0 ) = Prob Y ∼f mdl (•| x ,θH 0 ,λ mdl ) (T (Y , θ H 0 ) ≥ T (y, θ H 0 )) .
Analogously, for checking a more general prediction model mdl by testing the null hypothesis that the data-generating distribution is the model predictive distribution f prdct mdl (•; (x , y) , x n +1 ), a measure of data-model discrepancy D x n +1 , y n +1 , mdl and its random counterpart D ((x n +1 , Y n +1 ) , mdl) together define the model predictive p value

p x n +1 , y n +1 , mdl = Prob Y n +1∼f prdct mdl (•;(x ,y),x n +1) D ((x n +1 , Y n +1 ) , mdl) ≥ D x n +1 , y n +1 , mdl . (2)
Example 4. With Example 1's posterior predictive distribution as f prdct mdl (•; (x , y) , x n +1 ), the model predictive p value reduces to a special case of the Bayesian p value defined by equation (2.28) of [START_REF] Carlin | Bayes and Empirical Bayes Methods for Data Analysis[END_REF]. That is closely related to two other Bayesian p values. First, in considering the posterior distribution π mdl (•| (x , y)) from the analysis of (x , y) as the prior distribution for predicting y n +1 from x n +1 , we thereby consider f prdct mdl (•; (x , y) , x n +1 ) as a prior predictive distribution. From that viewpoint, p x n +1 , y n +1 , mdl is a prior predictive p value; see Ghosh et al. (2006, §6.5). Second, when "predicting" the observed y instead of y n +1 , the Bayesian "p value" p ((x , y) , mdl) is instead a posterior predictive p value (Carlin and Louis, 2000, (2.27)). Since the same data in that case are used for the model predictive distribution and the value "predicted," posterior predictive p values require calibration [START_REF] Hjort | Post-processing posterior predictive p values[END_REF].

Example 5. Let F mdl denote the cumulative distribution function of f prdct mdl (•; (x , y) , x n +1 ). A sim-1q x n +1 , y n +1 , mdl , where q x n +1 , y n +1 , mdl = 2 min F mdl y n +1 , 1 -F mdl y n +1 .

Whereas

F mdl y n +1 = y n +1 -∞ f prdct mdl y ′ n +1 ; (x , y) , x n +1 d y ′ n +1
and 1 -F mdl y n +1 are one-sided predictive p values, q x n +1 , y n +1 , mdl is a two-sided predictive p value for checking mdl. Plugging that D x n +1 , y n +1 , mdl into equation ( 2) yields

p x n +1 , y n +1 , mdl = Prob Y n +1∼f prdct mdl (•;(x ,y),x n +1) 1 -q ((x n +1 , Y n +1 ) , mdl) ≥ 1 -q x n +1 , y n +1 , mdl = Prob Y n +1∼f prdct mdl (•;(x ,y),x n +1) q ((x n +1 , Y n +1 ) , mdl) ≤ q x n +1 , y n +1 , mdl = q x n +1 , y n +1 , mdl ,
with the last step following from the fact that q

((x n +1 , Y n +1 ) , mdl) ∼ U (0, 1) if Y n +1 ∼ f prdct mdl (•; (x , y) , x n +1 )
, where U (0, 1) is the standard uniform distribution.

4 Measures of predictive performance based on multiple predictions

Relative predictive performance based on multiple predictions

Just as testing θ = θ H 0 can be informative even when θ cannot be exactly equal to θ H 0 [START_REF] Cox | The role of significance tests[END_REF], checking mdl on the basis of a single model predictive p value can be informative even though it is known that y n +1 was not drawn from f prdct mdl (•; (x , y) , x n +1 ). However, a model predictive p value from checking mdl given a number n prdct of predicted values may be worthless as a measure of absolute performance since it is guaranteed to generate very small model predictive p values whenever n prdct is sufficiently large. On the other hand, such a p value may serve as a measure of the performance of a prediction model relative to other prediction models. Alternatively, model predictive p values may empower the fiducial averaging of prediction models in analogy with Bickel (2018)'s use of prior predictive p values for the fiducial averaging of Bayesian models.

There are two ways to generate a model predictive p value p x prdct , y prdct , mdl on the basis of mdl's performance in predicting y prdct = y n +1 , . . . , y n + n prdct given x prdct = (x n +1 , . . . , x n + n prdct ) after fitting its parameters to (x , y):

1. First, such a model predictive p value may be defined by replacing x n +1 , y n +1 , and Y n +1 with x prdct , y prdct , and Y prdct in equation ( 2), where Y prdct is the random n prdct -vector of a model predictive distribution f prdct mdl •; (x , y) , x prdct .

2. The second way is to combine equation (2)'s model predictive p values

p x n +1 , y n +1 , mdl , . . . , p x n + n prdct , y n + n prdct , mdl (3)
that are generated individually from predicting y n +1 given x n +1 , predicting y n +2 given

x n +2 , etc. Each of the methods of p value combination listed by [START_REF] Folks | 6 combination of independent tests[END_REF] and [START_REF] Singh | Combining information from independent sources through confidence distributions[END_REF] would generate a different p x prdct , y prdct , mdl . For example, Fisher's method of combining p value has stood the test of time.

Absolute predictive performance based on multiple predictions

The model predictive p values (3) can also generate absolute measures of predictive performance.

Let p (i, mdl) = p x n +i , y n +i , mdl for i = 1, . . . , n prdct . As an idealization, suppose some proportion π 0 of the n prdct predicted data points were drawn from f prdct mdl (•; (x , y) , x n +i ) for i = 1, . . . , n prdct . Then an estimate of π 0 could serve as a measure of how well mdl predicts without necessarily comparing its performance to that of other prediction models.

The literature has many complex methods for estimating the proportion of null hypotheses that are true on the basis of a vector of p values (e.g., [START_REF] Nguyen | On estimating the proportion of true null hypotheses for false discovery rate controlling procedures in exploratory dna microarray studies[END_REF][START_REF] Broberg | A comparative review of estimates of the proportion unchanged genes and the false discovery rate[END_REF][START_REF] Langaas | Estimating the proportion of true null hypotheses, with application to dna microarray data[END_REF][START_REF] Lai | A statistical method for estimating the proportion of differentially expressed genes[END_REF][START_REF] Lai | A moment-based method for estimating the proportion of true null hypotheses and its application to microarray gene expression data[END_REF][START_REF] Jin | Estimating the null and the proportion of nonnull effects in large-scale multiple comparisons[END_REF][START_REF] Jiang | Estimating the proportion of true null hypotheses for multiple comparisons[END_REF][START_REF] Cai | Optimal rates of convergence for estimating the null density and proportion of nonnull effects in large-scale multiple testing[END_REF]. While they could be used to estimate π 0 with p (1, mdl) , . . . , p n prdct , mdl as the vector of p values and with

f prdct mdl (•; (x , y) , x n +1 ) , . . . , f prdct mdl (•; (x , y) , x n + n prdct )
as the null hypothesis distributions, two simpler approaches suffice for the purpose of measuring predictive performance. They begin by estimating the ith prediction's achieved nonlocal false discovery rate (NFDR) by

NFDR (i, mdl) = min p (i, mdl) n prdct # n prdct j=1 (p (j, mdl) ≤ p (i, mdl))
, 1 , the denominator of which tells how many of the n prdct model predictive p values are less than or equal to p (i, mdl).

Next, let (i) denote the index of the ith smallest NFDR (i, mdl), thereby ordering the estimates by NFDR ((1) , mdl) ≤ • • • ≤ NFDR n prdct , mdl . The bias in NFDR (i, mdl) as an estimate of the local false discovery rate (LFDR) may be corrected by either of these two LFDR estimates [START_REF] Bickel | Correcting false discovery rates for their bias toward false positives[END_REF]Bickel, 2020, chapter 6):

CFDR ((i) , mdl) = i k=1 1 i -k + 1 NFDR ((i) , mdl) ; (4) RFDR ((i) , mdl) =        NFDR (([1.6i]) , mdl) if [1.6i] ≤ n prdct 1 if [1.6i] > n prdct , (5)
where the square brackets indicate rounding to the nearest integer. Those two LFDR estimates are called the corrected false discovery rate (CFDR) and the re-ranked false discovery rate (RFDR).

Since the LFDR of a null hypothesis is a posterior probability that the null hypothesis is true, the expected value of the LFDR of a randomly selected null hypothesis is a posterior expected value of the proportion of null hypotheses that are true. That suggests estimating π 0 by

The housing data

The data analyzed are from the Boston Standard Metropolitan Statistical Area in 1970 (Belsley et al., 1980, App. 4A). Each observation in the data set consists of the values of 13 scalar independent variables and 1 dependent variable, the logarithm of the median value of the houses occupied by In the data analysis of Section 5.3, the entire TrainingData set was used as (x , y) to train each neural network. In the notation of Example 3, the trained models are η 10 ((x , y) , •), η 8 ((x , y) , •), and η 5 ((x , y) , •) for Net 10, Net 8, and Net 5. The entire TestData set was used as the x prdct , y prdct of Section 4 to assess the performance of the model predictive distribution generated by each neural network. are more interpretable as absolute measures of performance, according to these considerations:

Assessing each neural network's predictive performance

1. All three of the combined p values are low enough to reject the joint null hypothesis (that all 168 predictions come from the predictive distributions of the neural networks) at the α = 10 -5 level of statistical significance. As that joint null hypothesis is of little relevance, the combined p value of a neural network only serves as a measure of performance relative to that of the other neural networks.

2. By contrast, for each neural network considered without comparison to other neural networks, the farther its π CFDR 0 or π RFDR 0 is from 1, the more room there is for improving its predictive performance.

For reference, the last panel of Figure 1 displays log 10 p x prdct , y prdct , mdl , π CFDR 0 , and π RFDR 0 for a simulated case of π 0 = 1. The bottom of each plot provides "log 10 p," the base-10 logarithm of the combined p value using Fisher's method ( §4.1) followed by two estimates of the proportion of observations consistent with the predictive distribution: "CFDR" is π CFDR 0 , the average of the 168 CFDRs; and "RFDR" is π RFDR 0 , the average of the 168 RFDRs ( §4.2). In the three plots labeled by "Net," each predictive p value corresponds to an observation from the test data set of Section 5.2. Each number followed by "Net" above a plot identifies a neural network by its value of a hyperparameter, as explained in Section 5.1. The plot labeled "100% true null hypotheses" serves as a control for reference. It is the empirical distribution function of 168 independent variates of U (0, 1), for that is the distribution of a p value under the truth of a null hypothesis. The graphical method is essentially that of [START_REF] Schweder | Plots of P-values to evaluate many tests simultaneously[END_REF].

  hyperparameters include the distributions of random initial parameter values and the number of layers of adaptive parameters in the network. Each combination of hyperparameter values corresponds to a different prediction model. Models of different types and of different hyperparameter values may be assessed for predictive performance according to the proposed measures.

  calls a "bagging predictor." Many variations of parametric bootstrapping are possible. Here is one: Example 3. As an alternative to the MLE-based approach of equation (1), let y mdl,n +1 = η mdl ((x , y) , x n +1 ) denote the prediction of y n +1 according to a neural network or another an algorithmic model. In this context, (x , y) is called the training set to distinguish it from x n +1 , y n +1 , called the validation set or test set, depending on whether or not it is used to select another algorithmic model for additional predictions. With (x , y) fixed, the function η mdl ((x , y) , •) is then considered to be a trained model. Training the model on the bootstrap samples x (

  +1 as the bootstrap predictions of y n +1 . The bootstrap predictive distribution used as f prdct mdl (•; (x , y) , x n +1 ) is the probability density function of N y mdl,n +1 , σ 2 mdl . That is not a special case of the bootstrap predictive distributions of Example 2, which would have µ mdl in place of y mdl,n +1 .

  the means of CFDR ((1) , mdl) , . . . , CFDR n prdct , mdl and of RFDR ((1) , mdl) , . . . , RFDR n prdct , mdl .5 Application to deep neural networks5.1 The deep neural networksNet 10 will refer to the neural network that is defined on https://reference.wolfram.com/ language/tutorial/NeuralNetworksRegression.html (accessed 18 October 2019) by the codeNetChain[{LinearLayer[15],BatchNormalizationLayer[], ElementwiseLayer[Ramp],LinearLayer[10],BatchNormalizationLayer[],ElementwiseLayer[Ramp],LinearLayer[1]},"Input"->13,"Output"->"Scalar"] in the language of[START_REF] Research | [END_REF]. It is 7 layers deep. Its second linear layer has an output of 10 numbers, which is why it is called Net 10. Net 8 and Net 5 are exactly the same except for their values of that hyperparameter; their second linear layers have outputs of 8 and 5 numbers, respectively.

  owners.[START_REF] Research | [END_REF] divides the data into a TrainingData set of 338 observations and a TestData set of 168 observations associated with its command ExampleData[{"MachineLearning", "BostonHomes"}]. The data are also available as boston_housing in the Keras Python deep learning library according to https://keras.io/datasets/ (accessed 18 October 2019), which cites StatLib as its source.

  Recall that the three neural networks used to analyze the data of Section 5.2 are labeled Net 10, Net 8, and Net 5, where the number is the value of a hyperparameter explained in Section 5.1. The bootstrap method of Example 3 was used to generate the model predictive distributions, and the measure of discrepancy proposed in Example 5 was used to determine the model predictive p values. The empirical distributions of the model predictive p values are plotted in Figure 1.

Figure 1

 1 Figure 1 also reports three measures of predictive performance for each neural network:

Figure 1 :

 1 Figure 1: Each plot is the empirical distribution function of 168 model predictive p values.The bottom of each plot provides "log 10 p," the base-10 logarithm of the combined p value using Fisher's method ( §4.1) followed by two estimates of the proportion of observations consistent with the predictive distribution: "CFDR" is π CFDR

Acknowledgments

This research was partially supported by the Natural Sciences and Engineering Research Council of Canada (RGPIN/356018-2009).


Gianluca Perniciano
email: g.perniciano@gmail.com

Reduction Energy in Warped Region in Alcubierre Warp Drive

A solution of general relativity is presented that describes an Alcubierre [1] propulsion system in which it is possible to travel at superluminal speed while reducing the energy, by an arbitrary value.

Introduction:

Alcubierre [1] in 1994 proposed a solution of the equations of general relativity which provides the only viable means to accelerate a spaceship up to superluminal velocities without using wormholes.

A problem was soon identified: Pfenning [4] showed that the required energy is comparable to the total energy of the universe and that it is negative.We presented a way to reduce the amount of energy, involved and its spacial distribution within the warp bubble.

Note: In the following we adopt the notation used by Landau and Lifshitz in the second volume ("The Classical Theory of Fields") of their well known Course of Theoretical Physics [START_REF] Landau | The Classical Theory of Fields[END_REF].

Computazion with MAPLE 18,grTensor II.

We propose the use of the metric

ds 2 = ( 1-v 2 f ( x , y , z-k (t)) 2 a (x , y , z -k (t )) 2 ) dt 2 +2 v f ( x , y , z -k (t)) a (x , y , z-k ( t)) dt dz -dx 2 -dy 2 -dz 2 (1)
or in implicit form:

ds 2 =dt 2 -[ dz-v f ( x , y , z-k (t )) a( x , y , z-k (t )) dt ] 2 -dx 2 -dy 2 (2)
while Miguel Alcubierre solutions [1] is:

ds 2 =dt 2 -[dz-v f ( x , y , z-k (t)) dt ] 2 -dx 2 -dy 2 (3)
and dk (t) dt =v=const

Einstein Equation:

G ik = 8 π G c 4 T ik T ik (energy-impulse tensor) [12] ( 4
)
1 Computation of the negative energy in the Pfenning zone, its comparison with the Casimir effect (plane-parallel condenser).

The energy is:

E= ∫∫∫ (-g ) 1/ 2 T tt dx 3 (5)
where the triple integral extends over all the volume and the energy density ρ is:

ρ=T tt =k G tt ( 6
)
(g determinant of the spacial metric) and k =c 4 /8π G .

in Alcubierre form:

ρ=T tt =k G tt =-k 1 4 v 2 x 2 + y 2 r 2 ( ∂ h ∂ r ) 2 (7)
where

h=h (r )= f (r ) a(r ) (8)
and k =c 4 /8π G ; c is the speed of light and G is Newton's gravitational constant;

G tt =- 1 4 v 2 x 2 + y 2 r 2 g (r ) (9)
where g ( r ) is given by :

g ( r )=[ 1 a (r ) 2 ( df (r ) dr ) 2 +( f ( r ) 2 a (r ) 4 )( da (r ) dr ) 2 -2 df ( r ) dr f ( r ) a (r ) 3 da (r ) dr ] (10)
1.1 The energy E in the Pfenning (warped region) zone in our case (see [4] for an example):

The energy given by :

E=- 8 π k v 2 32 π ∫ x 2 + y 2 r 2 g ( r) dx 3 (11)
• 1)-inside the warp bubble f (r )=1 and a (r )=1

• 2)-outside the warp bubble f (r )=0 and a (r )=1

• 3)-within the Alcubierre warped region 0< f (r )<1 and a (r )≫1 they are ( 12),( 13) f (r ) is for all r (example):

f (r )=(1/2)(1-tanh @( r-R)) , (df /dr ) 2 =(1/4)(@ 2 /[(cosh @( r-R)) 4 ]) [14] (12)
a (r ) is for all r (example):

a (r )=(2 P )/[1+(tanh[@(r-R)]) 2 ] P P ≫1 [14] ( 13
)
da (r)/dr=(-P)((1/2)[1+( tanh[@(r-R)]) 2 ]) -(P +1) (@ tanh [@ (r -R)]/(cosh [@( r-R)]) 2 ) (da (r )/ dr) 2 =(-P ) 2 ((1/ 2)[1+(tanh [ @(r-R)]) 2 ]) (-2( P+1)) (@ tanh [@ (r-R)]/(cosh [@( r-R )]) 2 )
2 R radius of the warp bubble Equation [START_REF] Hiscock | Quantum effects in the Alcubierre warp drive spacetime[END_REF] :

g (r )=[ 1 a (r ) 2 ( df (r ) dr ) 2 +( f ( r ) 2 a (r ) 4 )( da (r ) dr ) 2 -2 df ( r ) dr f (r ) a (r ) 3 da (r ) dr ] g (r )=g 1 ( r)+g 2 (r )+g 3 (r ) (14
)

g 1 (r )= 1 a(r ) 2 ( df ( r) dr ) 2 =( 1 4 ) @ 2 a(r ) 2 (cosh [@( r-R)]) 4 ( 15
)
g 2 (r )=( f ( r) 2 a (r ) 4 )( da( r ) dr ) 2 ( P @) 2 (tanh [@ (r -R)]) 2 a (r ) 2 (cosh [@(r-R)]) 4 ( 16
)
g 3 (r)=-2 df (r) dr f (r ) a(r ) 3 da(r ) dr -( P @ 2 ) tanh [@(r-R)] a (r ) 2 (cosh [@(r -R)]) 4 ( 17
)
for P=280 ,@=5000 , a (r )≫1 in Alcubierre warped region, the energy density is,for equations ( 15),( 16),( 17),and paper [11], [13], [14]:

energy density =|- k 4 v 2 x 2 + y 2 r 2 g ( r )|≪1 (18)
in Alcubierre warped region.

And if R=100 m P=280 , @=5000 [14],in Alcubierre warped region (there is the source of esotic matter),the energy is,for equation ( 5):

E=- 8 π k v 2 12 ∫ 0 +∞ r 2 g( r) dr k =c 4 /8π G (19)
and for the same values of the parameters shown above the Energy is:

E-4 v 2 10 -87 joule (20)
energy is very small compared with Casimir effect (23).

And mass is :

m-4 v 2 10 -104 kg (21)
If R=100 m P=140 , @=5000 [14],in Alcubierre warped region (there is the source of esotic matter),the energy is:

E-v 2 10 -7 joule (22)
energy is compared with Casimir effect,with d=100 nm and L=1 m,equation (23).

For possibly,esotic matter see also,example [START_REF]Negative mass hydrodynamics in a spin-orbit-coupled Bose-Einstein condensate[END_REF].

A modification of parameters P, @, in a(r) and for f (r), between those chosen, determines a greater or lesser reduction of the energy density and the energy,with the same radius value R of the warp bubble that contains the spaceship,and also changes the thickness of the warped region.

1.2

The energy U(d) between the two plates in a plane-parallel condenser in empty space, due to the Casimir effect, is:

U (d )=-π 2 [ ( h 2 π ) c 720d 3 ] L 2 (23)
where d is the distance between the plates and L is the side of the square conducting plate. As can be seen, the energy is negative and this implies that the force (equal to the opposite of the derivative with respect to d) is attractive, as has been experimentally found ("Lamoreaux" [START_REF] Lamoreaux | Demonstration of the Casimir Force in the 0.6 to 6 μm Range[END_REF]). In the case d =1μ m and L = 1 m (L is chosen to be quite large, but not as large as the Pfenning zone) it is found that U (d )=-4 10 -10 joule .

Conclusions

These calculations show that the modified Alcubierre propulsion system can achieve superluminal speeds,and the energy,can be reduced by an arbitrary value in the Pfenning zone, warped region, (source of esotic matter)


Nicolas Ragot
email: nicolas.ragot@esigelec.fr

Benchmark of Visual SLAM Algorithms: ORB-SLAM2 vs RTAB-Map* *

Keywords: Visual SLAM, ORB SLAM, RTAB SLAM, Localization, Mapping, Visual Odometry

. Different motion scenarios are used to test and benchmark the SLAM algorithms in various configurations: straight-line, straight-line and back, circular path with loop closure, etc.

I. INTRODUCTION

Estimating the camera trajectory while simultaneously reconstructing the environment is a key and well-know problem in robotics and computer vision. This can be achieved by the use of different measuring means (LIDAR, RADAR) and algorithms (particle filter, extended Kalman filter, Graph-SLAM). When cameras are used, SLAM techniques are named as visual SLAM (vSLAM). vSLAM algorithms have been widely proposed in the field of computer vision, robotics. Taketomi & al. [6] proposes an exhaustive survey of real-time This work is carried out as part of the INTERREG VA FMA ADAPT project "Assistive Devices for empowering disAbled People through robotic Technologies" http://adapt-project.com/index.php. The Interreg FCE Programme is a European Territorial Cooperation programme that aims to fund high quality cooperation projects in the Channel border region between France and England. The Programme is funded by the European Regional Development Fund (ERDF) vSLAM algorithms developed from 2010 to 2016. In [START_REF] Ouerghi | Embedded Architecture for Vision-based Mobile Localization[END_REF], a very exhaustive state of the art about the vSLAMis presented. Obtaining a complete vSLAM system essentially consists in adding the cartography or the geometric consistency of the visual odometry map. The pioneering approach of visual odometry was presented by Nister et al. [START_REF] Ouerghi | Embedded Architecture for Vision-based Mobile Localization[END_REF] in 2003 for monocular and stereo cases. They presented estimation within RANSAC for the first time as well as the estimation from 2D-3D matches instead of triangulating for each stereo pair which allowed to have more robustness [START_REF] Scaramuzza | Visual Odometry [Tutorial[END_REF]. Indeed, the majority of the methods follow the indirect scheme where they carry out features detection and movement estimation within RANSAC. However, direct methods have also been implemented such as SVO [START_REF] Forster | SVO: fast semi-direct monocular visual odometry[END_REF] and DSO [START_REF] Engel | Direct sparse odometry[END_REF].

Location-based on existing maps could also be done without the on-line mapping process or building a map beforehand. In recent years, specific card formats have been proposed to meet the need for prior knowledge for the autonomous car such as OpenStreetMap (OSM). Guo et al. proposed in [START_REF] Guo | Automatic lane-level map generation for advanced driver assistance systems using lowcost sensors[END_REF] a low-cost approach based on OSM maps, INS, GPS and spelling images generated from a camera. A second optimization using visual odometry is performed [START_REF] Guo | A Low-Cost Solution for Automatic Lane-Level Map Generation Using Conventional In-Car Sensors[END_REF].

Location-based on recognition of places: usually done in two phases: an off-line learning phase where a geotagged database is built and the location is done online by finding the image that most closely resembles the current one. Site recognition is also an essential part of a visual SLAM system to establish loop closures on one hand and to relocate on the other hand in the event of loss of tracking. The visual points of interest are further subdivided into two categories: those that select parts of the image and those that use the entire image without resorting to a selection step. Examples of the first category are the SIFT [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] and SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF] descriptors, and the second category global descriptors such as HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and GIST [START_REF] Oliva | Building the gist of a scene: the role of global image features in recognition[END_REF]. bag-of-words separates the point of interest space into a finite number of visual words. FabMap [START_REF] Cummins | FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance[END_REF] [START_REF] Cummins | Appearance-only SLAM at large scale with FAB-MAP 2.0[END_REF] which is a probabilistic approach that has shown its effectiveness on a trajectory of 1000 km in length. Other work has been based on global descriptors such as HOG in [START_REF] Mcmanus | Scene Signatures: Localised and Pointless Features for Localisation[END_REF] and GIST in [START_REF] Siagian | Biologically Inspired Mobile Robot Vision Localization[END_REF]. Global descriptors are more dependent on the point of view than local descriptors, but they do not work well with changes in brightness. The most representative approach in this category is SeqSLAM [START_REF] Milford | SeqSLAM: visual route-based navigation for sunny summer days and stormy winter nights[END_REF] which has demonstrated a much better performance than FabMAP under conditions of extreme atmospheric changes and brightness. SeqSLAM is based on the use of subsampled whole images by searching in a database that is built in the sequence that most closely resembles the current sequence acquired. An extension of SeqSLAM for 2D interior environments has been proposed in [START_REF] Mount | 2D visual place recognition for domestic service robots at night[END_REF].

We therefore present in this paper a benchmark comparative study between two visual SLAM approaches: ORB SLAM and RTAB SLAM. The ORB SLAM has been implemented taking into account different kinds of sensors such as monocular, stereo and RGB-D camera. The RTAB SLAM, meanwhile, it has been experimented taking into account both monocular and RGB-D images. The wheelchair has been modified to fit the developed platform. A new motor controller has been developed, the wheelchair is connected within a wireless communication system, and the instrumentation is carried out within a Realsense camera including a monocular, stereo and a RGB-D sensors. A ground truth data based VICON system is used to validate the results obtained.

This paper is organized as follows: Section 1 introduces the motivation of the paper. Section 2 presents the state of the art about SLAM. Section 3 presents the wheelchair architecture and how to control the wheelchair. Section 4 illustrates the comparison between ORB SLAM and RTAB SLAM within different kind of camera like monocular, stereo and RGB-D camera. In the same section, we present how we have validated the approach developed by comparison between SLAM localization and ground truth localization carried out by VICON system. The results obtained will be presented in Section 5. Finally, in Section 6, we will conclude this paper.

II. RELATED WORKS

The literature review suggests to classify the methods in two main categories: one is related to the indirect methods whereas the other deals with the direct ones. The indirect methods are based on the detection of points of interest in the image (features) and the establishment of 2D-3D correspondences between the points of interest and the map by matching/tracking. The pose of the camera is then obtained by solving the Perspective-n-Point (PnP) problem. It is noted that the majority of vSLAM methods assume that the camera is previously calibrated, which implies that the intrinsic parameters of the camera are previously known [START_REF] Ouerghi | Mobile Robot Localization State of the Art[END_REF].

In robotic mapping and navigation, Simultaneous Localization and Mapping (SLAM) is the computational problem of constructing or updating a map of an unknown environment while simultaneously keeping track of an agent's location within it. While this initially appears to be a chicken-and-egg problem there are several algorithms known for solving it, at least approximately, in tractable time for certain environments. Popular approximate solution methods include the particle filter, extended Kalman filter, and GraphSLAM.

Indirect methods-based feature detection belong to other subcategories of vSLAM namely filter-based SLAM and optimization-based SLAM. A pioneering method is MonoSLAM presented in 2007, allowing to simultaneously estimate the pose of the camera and the 3D structure of an unknown environment using an Extended Kalman filter (EKF) [START_REF] Davison | MonoSLAM: Real-Time Single Camera SLAM[END_REF]. The 3D camera movement (6 DOF) and the 3D positions of the features are represented by a state vector of EKF. PTAM offers an improvement by separating tracking and mapping in different threads of the CPU [START_REF] Klein | Parallel Tracking and Mapping on a Camera Phone[END_REF]. PTAM also introduced the use of keyframes for mapping as well as a feature classifier to search for the keyframe closest to the input image. ORB-SLAM can be considered as an extension of PTAM including features such as separate threads and keyframes, the detection of closing loops and the optimization of the poses graph [START_REF] Mur-Artal | ORB-SLAM: A Versatile and Accurate Monocular SLAM System[END_REF]. ORB-SLAM [START_REF] Mur-Artal | ORB-SLAM: A Versatile and Accurate Monocular SLAM System[END_REF], introduced in 2015, is the most complete indirect monocular vSLAM method and has been extended for stereo systems and RGB-D systems in ORB-SLAM2 in 2017 [START_REF] Mur-Artal | Orb-slam2: An open-source slam system for monocular, stereo, and rgb-d cameras[END_REF].

Unlike feature-based indirect methods, use directly pixel intensity of input images. A completely direct method is DTAM which, like PTAM, has two distinct parts: pose tracking and mapping [START_REF] Newcombe | DTAM: Dense tracking and mapping in real-time[END_REF]. However, PTAM tracks a set of 3D points while DTAM maintains dense depth maps for a selection of keyframes. The most representative method in the category of direct methods is LSD-SLAM (Large-Scale Direct SLAM) which is a monocular SLAM algorithm [START_REF] Engel | LSD-SLAM: Large-Scale Direct Monocular SLAM[END_REF]. The map is constructed based on keyframes composed of camera image, a map of the inverse depths (inverse depth map) and the variance of the inverse of depths.

III. ROBOTICS WHEELCHAIR ARCHITECTURE

The robotics electrical powered wheelchair from the ESIG-ELEC's lab is an Invacare, model Bora from which all the proprietary electronics has been removed and replaced by:

• Embedded PC running a Linux Ubuntu 16.04 LTS distribution • Motor driver from Roboteq • Xbox joystick in place of the original one which can be connected to the wheelchair through a USB or Bluetooth connection.

• WIFI router for getting a wireless local network on the wheelchair • Embedded HMI with a touch-screen panel The wheelchair software is fully developed under the ROS robotics middleware. Figure 1 shows the wheelchair description. An embedded computer is used as a heart of processor in the wheelchair. It possesses 8 GB of RAM and 250 GB of SSD. It runs Ubuntu 16.04 as operating system. A tactile screen is connected to the embedded computer using the HDMI cable to present the user interface to the user. A motor driver from Roboteq is used to drive motors. The wheelchair also has its own Wi-Fi router. An Xbox One joystick is used to control the wheelchair. A RealSense D435 depth camera from Intel is used for embedded vision. Figure 2 shows the hardware architecture of the wheelchair.

IV. VSLAM COMPARISON BETWEEN ORB-SLAM AND RTABMAP SLAM A. ORB-SLAM

ORB-SLAM2 is a real-time SLAM library for monocular, stereo and RGB-D cameras that computes the camera trajec-tory and a sparse 3D reconstruction. It is able to detect loops and re-localize the camera in real time. The system works in real-time on standard CPUs in a wide variety of environments from small hand-held indoors sequences, to drones ying in industrial environments and cars driving around a city. The back-end based on bundle adjustment with monocular and stereo observations allows for accurate trajectory estimation with metric scale. The system includes a lightweight localization mode that leverages visual odometry tracks for unmapped regions and matches to map points that allow for zero-drift localization. The main functionalities of ORB SLAM are: feature tracking, mapping, loop closure and localization.

1) Monocular ORB-SLAM 2: Monocular SLAM requires just a single camera. The ORB SLAM converts the image to grayscale for its application. The first step is to detect features and initialize the map and its position. Once it gets initialized, it starts creating map. Monocular SLAM requires a procedure to create an initial map because depth cannot be recovered from a single image. One way to solve the problem is to initially track a known structure. In the context of ltering approaches, points can be initialized with high uncertainty in depth using an inverse depth parametrization, which hopefully will later converge to their real positions. The figure below shows the flow of process in ORB-SLAM monocular.

2) Stereo ORB-SLAM 2: Stereo ORB-SLAM requires a stereo camera. The feature detection in stereo SLAM is better than monocular SLAM. The initialization is fast and has many advantages over monocular SLAM. For stereo cameras, we extract ORB in both images and for every left ORB we search for a match in the right image. This can be done very efficiently assuming stereo rectified images, so that epipolar lines are horizontal. We then generate the stereo keypoint with the coordinates of the left ORB and the horizontal coordinate of the right match, which is subpixel refined by patch correlation.

3) RGB-Depth ORB SLAM 2: RGB-D SLAM requires an RGB image with its depth image. For RGB-D cameras, we extract ORB features on the RGB image, for each feature with coordinates (uL; vL) we transform its depth value d into a virtual right coordinate:

uR = uL - f x * b d (1)
where f x is the horizontal focal length and b is the baseline between the structured light projector and the infrared camera.

The uncertainty of the depth sensor is represented by the uncertainty of the virtual right coordinate. In this way, features from stereo and RGB-D input are handled equally by the rest of the system. 4) MAP Save and Load: A feature to save the map generated by the ORB SLAM is developed. Ability to load the map for localization purpose was also developed. All keyframes, features and its descriptors are saved to a binary file. After every mapping session the algorithm asks the user whether to save the map or not. At the beginning of SLAM, the algorithm asks the user whether to load the saved map to begin localization or mapping within the environment which is already built. RTAB-Map supports both visual and lidar SLAM, providing in one package a tool allowing users to implement and compare a variety of 3D and 2D solutions for a wide range of applications with dierent robots and sensors. It uses depth image with RGB images to construct maps. The graph is created here, where each node contains RBG and depth images with corresponding odometry pose. The links are transformation between each node. When the graph is updated, RTAB-Map compares the new image with all previous ones in the graph to find a loop closure. When a loop closure is found, graph optimization is done to correct the poses in the graph. For each node in the graph, we generate a point cloud from the RGB and depth images. This point cloud is transformed using the pose in the node. The 3D map is then created [START_REF] Scaramuzza | Visual Odometry [Tutorial[END_REF].

V. RESULTS ANALYSIS

The tests were carried out in LNA lab of IRSEEM for indoor scenarios and in car parking of IRSEEM for outdoor scenarios. LNA lab is equipped with Vicon camera system for tracking the wheelchair position and will be used as ground truth to evaluate the distance measurement of SLAM.

A. ORB SLAM

ORB SLAM works perfectly except with monocular camera as it loses points during mapping and also initializes very slowly. It can estimate its odometry and track features efficiently. The ORB SLAM creates a sparse 3D map as shown in the Figure 3.

The ORB SLAM creates a sparse 3D map. ORB SLAM is successful in creating a map and generating its trajectory in the environment. It can also detect closed loops successfully. The Figure 4 shows the trajectory created by ORB SLAM in indoor environments. Figure 5 shows the trajectory in outdoor environments.

The distance estimation is also accurate to the ground truth measurement by the Vicon. The only problem with ORB SLAM with monocular camera was that it was slow at initialization and also it loses points during the mapping. Due to this the ORB SLAM loses its position and will not be able to continue with mapping. The Figure 6 shows an example where a trajectory is generated by ORB SLAM with monocular in comparison with ORB SLAM with stereo and RGBD.

The Table I below shows the distance measurement for various paths. For the indoor scenarios we have used Vicon as the ground truth and for outdoor scenarios we have used measuring tape as the ground truth (approximate distance). The ORB SLAM with monocular camera had trouble initializing and also could not complete the trajectory. This is a limitation with monocular cameras and only alternative is to use either stereo camera or RGB-D camera. From Table I we can observe the results of ORB SLAM with stereo and RGBD. In indoor scenarios, ORB SLAM was accurate with both stereo and RGBD cameras but in outdoor scenarios, stereo camera has shown better results compared to the RGBD. A comparison of trajectories in two indoor scenarios by ORB SLAM with ground truth trajectory by Vicon was done. The trajectories generated by ORB SLAM was closely accurate to that of the ground truth trajectory by Vicon. The Figure 7 shows the trajectory comparison. The Table II shows the RATBMAP SLAM measurement of distance in comparison with Vicon measurement. From above results you can see that the mapping and trajectory estimation of RTABMAP is very good but the distance measurement is not. The distance estimated by the RTABMAP is not better than that of ORB SLAM.

C. ORB SLAM vs RTABMAP

The ORB SLAM was compared with RTABAMP in same scenarios as RTABMAP was tested. The Table III shows the distance measurement comparison between two SLAM algorithms. From the above table we can say that the distance measurements by ORB SLAM are more accurate than that of RTABMAP. From the above table we can say that the distance measurements by ORB SLAM are more accurate than that of RTABMAP.

VI. CONCLUSION

In this paper, we have presented a wheelchair localization and mapping-based comparison of two vSLAM algorithms, and within both of indoor and outdoor environment. Different approaches in VSLAM were developed around ORB SLAM and RTAB SLAM. In order to improve the quality of localization and mapping obtained by the basic SLAM, we have updated the ORB SLAM to our system by taking into account some parameters. We have tested ORB SLAM using Monocular camera, Stereo camera and RGBD camera.

we also added a feature where ORB SLAM prompts the user for saving the map and loading the map for pure localization. The ORB SLAM is able to save map and later load the map for localization purpose. The ORB SLAM has also been improved to estimate an accurate trajectory and also provide accurate odometry estimations. However, ORB SLAM with Monocular camera could not provide good trajectory or distance estimations due to the limitations of Monocular camera. The RTABMAP is also tested and used to compare with ORB SLAM. The trajectory estimation by RTABMAP is accurate but the odometry estimation is not as accurate as ORB SLAM. Few tests show that RTABMAP is better at trajectory estimation when compared to ORB SLAM but when it comes to distance measurement ORB SLAM is better. We have validated the whole developments under wheelchair platform within comparison between SLAM data, RTAB data, and ground truth data-based VICON obtained in indoor environment. Other scenario was carried out in outdoor environment for the validation of the platform.

Fig. 1 .

 1 Fig. 1. ADAPT Real Wheelchair Platform.

Fig. 2 .

 2 Fig. 2. Hardware Architecture of the Wheelchair.

  B. RTABMAP SLAM RTAB-MAP stands for Real Time Appearance Based Mapping. It is distributed as an open source library since 2013. RTAB-Map started as an appearance-based loop closure detection approach with memory management (shown in below figure) to deal with large-scale and long-term online operation. It then grew to implement Simultaneous Localization and Mapping (SLAM) on various robots and mobile platforms.

Fig. 3 .Fig. 5 .

 35 Fig. 3. An example of a map created by ORB SLAM

Fig. 6 .

 6 Fig. 6. ORB SLAM trajectory comparison between Monocular, Stereo and RGBD cameras.

Fig. 7 .

 7 Fig. 7. ORB SLAM and Vicon trajectory comparison.

Fig. 8 .

 8 Fig. 8. Map and trajectory estimation by RTABMAP SLAM.

TABLE I ORB

 I SLAM AND VICON DISTANCE (IN METERS) COMPARISON.

	Scenario	Ground Truth	ORB Stereo ORB RGBD
	Indoor 1	7.82	7.69	7.16
	Indoor 2	6.98	7.38	6.81
	Indoor 3	15.05	15.49	14.32
	Indoor 4	21.75	21.17	21.31
	Indoor 5	29.69	21.47	22.13
	Indoor 6	37.69	38.84	38.79
	Outdoor 1	28	28.85	19.27
	Outdoor 2	28	27.29	17.83
	Outdoor 3	56	56.63	37.25
	Outdoor 4	92	94.55	65.87
	Outdoor 5	92	95.8	66.97
	Outdoor 6	80	84.38	66.24
	Outdoor 7	80	81.9	63.36
	Outdoor 8	160	172.6	129.41

TABLE II RTABMAP

 II DISTANCE COMPARISON WITH VICON.

	Scenario	Ground Truth	RTABMAP RGBD
	Indoor 1	6.48	11.83
	Indoor 2	24.5	37.61
	Indoor 3	23.26	31.31

TABLE III ORB

 III SLAM AND RTABMAP COMPARISON.

	Scenario	Ground Truth	RTAB	ORBSLAM	ORBSLAM
			RGBD	Stereo	RGBD
	Indoor 1	6.48	11.83	5.33	8.94
	Indoor 2	24.5	37.61	30.64	27.78
	Indoor 3	23.26	31.31	20.82	21.43

ACKNOWLEDGMENT

This research is supported by ADAPT Project (cofinanced by the European Regional Development Fund within the framework of the INTERREG VA France (Channel) England programme). Many thanks to the engineers of Autonomous Navigation Laboratory of IRSEEM for their support with VICON system. Many thanks to Technological Resources Center (TRC) of ESIGELEC for his help in testing phase.