Xavier Insou

Lionel Quétel
email: lionel.quetel@idil.fr

Sébastien Claudot

Monique Thual

Expanded Beam Connectors for Single Mode Optical Fiber Sensor Applications in Harsh Environment

Keywords:

We propose an expanded beam micro lens in standard connectors, compliant with harsh environment connections. Low Insertion loss, high return loss and relaxed alignment tolerances compared with SMF are demonstrated in C and O band. We give two examples of harsh environment optical fiber sensor applications.

Introduction

Connections in harsh environment is a key element in the composition of the measurement line in single mode optical fiber sensors. For example, in the ASHLEY European project (Avionics Systems Hosted on a distributed modular electronics Large scale dEmonstrator for multiple tYpes of aircraft), different optical sensors will be implanted in multiple types of aircrafts. One of the biggest challenge is often to couple light through the sensor device [START_REF] Qiu | Normal free space coupling to fiber Bragg grating sensors[END_REF]. A solution to realize harsh single mode connectors is to increase the mode field diameter at the output of the fiber. This extension is generally obtained by using ball or hemispherical lenses at the end of the fibers [START_REF] Childers | Design and performance of expanded beam, multi-fiber connectors[END_REF]. This technique is interesting but not optimized in terms of insertion loss and return loss, it also needs a specific connector housing. In this article, we propose an innovative solution to increase the beam diameter with low insertion loss, low reflectance and good repeatability by using standard connectors. First, we give the concepts and principle of this solution, then we integrate it in standard connectors and measure the sensitivity to different contaminations. Finally, examples of optical fiber sensor demonstrators pointing out the interest of these expanded beam connectors are given.

Theoretical concepts and principle of the expanded beam connectors

Due to their very small mode field diameters (MFD), single mode fibers are very sensitive to contaminants, laser power and alignment defaults either lateral ∆x, axial ∆z or angular θ when injecting signal from one fiber to one another whatever the application as illustrated in Fig. 1. Expanded beam micro-lenses are very useful to relax lateral and axial positioning tolerances as can be seen in Table 1, where defaults that lead to 1 dB excess loss are calculated with equations extracted from ref [START_REF] Saruwatari | Semiconductor laser to single-mode fiber coupler[END_REF] for different kinds of expanded Gaussian beams whose MFD are 55, 113 and 340 µm, compared with SMF of 10.5 µm MFD at a wavelength of 1550 nm.

The lateral positioning tolerances is relaxed from 2.5 to 82 µm, the axial one from 57 to 59500 µm with a 340 µm MFD expanded beam compared with SMF. But the angular alignment decreases with expanded beam from 2.6 to 0.08°. Then a MFD around 55 to 110 µm is a good tradeoff to relax lateral and axial positioning tolerances without decreasing the angular ones compared with SMF. Moreover, expanded beam are less sensitive to high power and contaminants such as dust, oil and water for harsh environment applications.

A solution to achieve such an expanded beam at a SMF fiber output consists in splicing a parabolic lateral graded index fiber (GIF) to a SMF and to cut the GIF, at a length LGIopt from the splicing, where the Gaussian beam size 2ω is expanded at its maximum 2ωmax as can be seen in Fig. 2. In this case the wave front is plane at the fiber output the working distance zw is null. This configuration is appropriate for expanded beam connectors compliant with harsh conditions single mode fiber transmissions of at least 10 Gbit.s -1 as already demonstrated in 55 µm MFD LC connectors as can be seen in Fig. 3. Coupling loss as low as 0.5 dB from O to C band have been achieved for Return Loss as high as 65 dB [START_REF] Le | Reliable Expanded Beam Connector Compliant with Single-mode Fiber Transmission at 10 Gbit/s[END_REF]. Fig. 4 shows a photo of the 55 µm expanded beam at a SMF-GIF output compared with a SMF pointing out the expanded beam and the 125 µm outer diameter that remains constant, allowing the use of standard connectors (see Fig. 3). We have also pointed out the best conditions to relax lateral and axial positioning tolerances without going down to critical angle tolerances and to achieve both high coupling efficiency and low reflectance with very tolerant fabrication process of this kind of expanded beam micro lenses [START_REF] Le | Coupling Efficiency and Reflectance Analysis of Graded Index Expanded Beam Connectors[END_REF].

Those expanded beam micro lenses can also be used in optical fiber sensor applications since functions can be added in between the fibers thanks to the relaxed axial and lateral positioning tolerances. For instance 55 MFD expanded beam fibers can be separated from more than 1.5 mm with only 1 dB excess loss as can be seen in Table 1. Moreover, the micro lens can also be designed to achieve a wide range of MFD 2ω0 and working distances zw depending on the length LGI and opto geometric parameters of the GIF as can be seen in Fig. 5 where the MFD and working distance are plotted as a function of relative LGI length to LGIopt as developed in [START_REF] Le | Reliable Expanded Beam Connector Compliant with Single-mode Fiber Transmission at 10 Gbit/s[END_REF][START_REF] Le | Coupling Efficiency and Reflectance Analysis of Graded Index Expanded Beam Connectors[END_REF]. The maximum MFD is 55 µm for a null working distance but it can achieve a wide range of MFD comprised between 10.5 to 55 µm with working distances in a range of 0 up to 500 µm allowing a wide range of applications comprising optical fiber sensors.

Integration of expanded beam fibers in standard connectors

These expanded beam fibers can easily be integrated in standard connectors such as FC, ST or even a multipoint one, as can be seen in Fig. 6 showing a picture of a connector with two expanded beam fibers. The fibers are glued in connector ferrules with a standard procedure. The ferrule are polished using conventional optic fiber polishing machines compatible with mass production. This operating mode authorizes repeatability in terms of Insertion Loss and Return Loss.

Contamination effect (oil, water, dust)

The robustness of the SMF GIF interface has been evaluated over three contaminants: oil (0.03ml droplet), water (0.03ml droplet) and dust particles in comparison with SMF and MMF (OM3 multimode fiber), as shown in Fig. 7. The insertion loss deviation compared with contaminant free connections in LC connectors is plotted for 10 mating cycles each time in Fig. 7. The physical contact technology is able to exclude the liquid from the interface due to the high pressure of the spring loading which leads to good optical results in water contamination. Sometimes some liquid residue is left, leading to higher losses for a single mode interface with an oil droplet for instance. With solid particle contamination, it is a matter of statistical particle distribution over the core area; when the remaining area for passing light becomes smaller, the insertion losses increase accordingly. The results in Fig. 7 show that the SMF GIF is an interface with similar robustness compared to a MMF in the presence of contamination and better than SMF. Fig. 7: Insertion loss deviation (∆IL) recorded over oil contamination (MIL-PRF-7808), water contamination and dust particle contamination (talc powder 10 microns) compared with contaminant free connections, for a SMF GIF LC connection, a SMF LC connection and a MMF LC connection, each time with 10 mating cycles Such a behavior makes utilization of such connectors in harsh environments very useful especially in sensor applications. Moreover thanks to the high misalignment tolerances as demonstrated in paragraph 2, these expanded beam connectors are less sensitive to thermal induced mechanical expansion.

Examples of optical sensor applications where the expanded beam connectors can be used

The study of the dynamic behavior of wind turbine blades by using Fiber Bragg Gratings (FBGs) has been performed by IDIL Fibres Optiques. Arrays of FBGs sensors were used to measure temperature, elongation and pressure. The FBGs were connected to the interrogator with optical connectors. Fig. 8 represents the wind turbine equipped with FGBs arrays. These FBGs positions along the fibers are given in Fig. 9.

This work has been done during the collaborative research project AeroGust (Aeroelastic Gust Modelling) between industry and academia funded by the European Union's Horizon 2020. Humidity, salt mist, oil and vibrations make the use of the proposed expanded beam connectors unavoidable for long term reliability.

IDIL Fibres Optiques has also realized swell experiments in IFREMER Labs with a dynamic scattering processes measurement using Brillouin effect. The fiber was fixed on a neoprene film which was floating on the salt water as represented in Fig. 10. Salt water, dirt and vibrations make the use of expanded beam connectors unavoidable.

Conclusions

We have theoretically analyzed and experimentally demonstrated the use of innovative expanded beam fibers integrated in standard connectors for SM optical sensor applications with low insertion loss and low reflectance. The connectors authorize transmissions of at least 10 Gbit.s -1 , can be used in a broad range of wavelengths (>200 nm) and should also support higher power than SMF (up to 100 W expected). Due to its specifications, such connectors can be used in a large range of applications including moving pieces such as in rotating connectors.

Fig. 2 .

 2 Fig. 2. Principle of the SMF GIF expanded beam micro lens Fig. 3. Expanded beam LC connectors

Fig. 4 .

 4 Fig. 4. Optical microscope view of a SMF-GIF output compared with a SMF when illuminated by visible light

Fig. 5 :

 5 Fig. 5: (a) Analytical and BPM calculation of MFD and working distance for a given GIF profile

Fig. 6 :

 6 Fig. 6: Example of multipoint connectors with expanded beam fiber

Fig. 10

 10 Fig. 10 Optical fiber laying on the water surface

Table 1 :

 1 tolerances for 1 dB excess loss @ λ=1550nm

	MFD (µm)	θ (°)	∆x (µm)	∆z (µm)
	SMF 10.5	2.6	2.5	57
	55	0.5	13	1560
	113	0.25	26	6250
	340	0.08	82	59500

Fig. 1. Positioning defaults between two fibers


Tatiana Makhalova
email: tpmakhalova@hse.ru

Sergei O Kuznetsov
email: skuznetsov@hse.ru

Amedeo Napoli
email: amedeo.napoil@loria.fr

MDL for FCA: is there a place for background knowledge?

The Minimal Description Length (MDL) principle is a powerful and well founded approach, which has been successfully applied in a wide range of Data Mining tasks. In this paper we address the problem of pattern mining with MDL. We discuss how constraints -background knowledge on interestingness of patterns -can be embedded into MDL and argue the benefits of MDL over a simple selection of patterns based on measures.

Introduction

Formal Concept Analysis (FCA) is a formalism that can be applied to Knowledge Discovery and Data Mining. It is used commonly for solving a wide range of tasks: from pattern mining to design of ontologies.

Even controlled application of FCA in practice may result in exponentially large output, which entails additional steps aimed at reducing / selecting a small subset of concepts. The reduction of the number of formal concepts may be done during pre-/postprocessing stages.

In this paper we propose to combine two of the most common concept filtering approaches: the Minimal Description Length principle (MDL) [START_REF] Barron | The minimum description length principle in coding and modeling[END_REF][START_REF] Grünwald | The minimum description length principle[END_REF][START_REF] Hansen | Model selection and the principle of minimum description length[END_REF][START_REF] Siebes | Mdl in pattern mining a brief introduction to krimp[END_REF] and measure-based selection [START_REF] Kuznetsov | On interestingness measures of formal concepts[END_REF]. This combination tries to take the advantages of both methods and reduces the drawbacks of each one.

The idea of MDL is to select a subset of patterns that ensures the best compression of data. It has been embedded into FCA in a number of ways: for defining how many factors to use in Boolean matrix factorization (BMF) [START_REF] Belohlavek | From-below approximations in boolean matrix factorization: Geometry and new algorithm[END_REF][START_REF] Miettinen | Model order selection for boolean matrix factorization[END_REF][START_REF] Miettinen | Mdl4bmf: Minimum description length for boolean matrix factorization[END_REF] or to get more diverse itemsets in frequent pattern mining (FIM) [START_REF] Aggarwal | Frequent pattern mining[END_REF][START_REF] Li | Minimum description length principle: Generators are preferable to closed patterns[END_REF][START_REF] Vreeken | Krimp: mining itemsets that compress[END_REF] or to select triclusters [START_REF] Yurov | Turning krimp into a triclustering technique on sets of attribute-condition pairs that compress[END_REF]. Being threshold-free, MDL provides a succinct nonredundant set of concepts. However, it has some shortcomings. Since the length minimisation is at least NP-complete, the implementation of MDL is based on heuristics. The selected itemsets cannot be interpreted easily by experts.

Unlike MDL, the selection of itemsets based of values of some measure is easy to interpret. A measure reflects the assumption on interestingness of patterns. Selecting the best itemsets w.r.t. the chosen measure one obtains patterns with the desired characteristics. However, this approach requires threshold and returns a lot of similar patterns.

In this paper we use the Krimp algorithm as an implementation of MDL principle to improve measure-based selection. Krimp is based on greedy covering of data by a set of patterns (subsets of attributes) called candidate set. The patterns in a candidate set are ordered w.r.t. the pattern length and its frequency. We propose to use different interestingness measures to order candidates. This modification allows for embedding background knowledge, i.e., our assumptions on interestingness. The aim of the ordering w.r.t. different measures is to improve measure-based pattern selection rather than to compress data the best. Using a preferable ordering one gets a good compression as well as only those patterns that satisfy defined constraints.

The rest of the paper has the following structure. In Section 2 we briefly recall the main notions of FCA. In Section 3 we describe the MDL principle and discuss how interestingness measures can be used within MDL. The benefits of our approach are discussed in Section 4, where we compare MDL-based with threshold-based measure selection. Section 5 gives the conclusion and discuss the direction of future work.

Formal Concept Analysis: Basic Notions

Here we briefly recall FCA terminology [START_REF] Ganter | Formal concept analysis: Logical foundations[END_REF]. A formal context is a triple (G, M, I), where

G = {g 1 , g 2 , ..., g n } is called a set objects, M = {m 1 , m 2 , . . . , m k } is
(A, B) ≤ (C, D) iff A ⊆ C (D ⊆ B), a pair (A, B) is a subconcept of (C, D), while (C, D) is a superconcept of (A, B).
The number of formal concepts can grow exponentially w.r.t. the size of a formal context, i.e., the number of objects in G and attributes in M . We say that a set of patterns S covers objects in G if B∈S B = G, where B ⊆ M . We are interested in a small set of patterns (intents) S that covers all objects and most of their attributes, i.e., B∈S {gIm | g ∈ B , m ∈ B} ≈ |I|.

Example. Let us consider a toy example. A formal context is given in Figure 1 (1). We consider 3 sets of itemsets (intents): S 2 = {{abc}, {bcde}, {de}, {cde}, {ac}}, S 3 = {{bc}, {de}, {ac}} and S 4 = {{c}, {de}}. The corresponding coverings of the context are given in Figure 1 (2-4). The intensity of colors is proportional to the number of times a particular "cross" is covered by intents. In our example "crosses" are covered by intents from 0 to 4 times. We count not only the number of intents, but also the number of covered "crosses", we call this value the rate of a cover relation, or RCR = |"crosses" that covered at least once|/|I|. It can be seen from the covering given in Figure 1 that S 3 (Figure 1, (3)) provides the best covering w.r.t. the number of itemsets (intents) and the rate of covered elements in the object-attribute relation. The Minimal Description Length principle allows for covering with a substantial rate of "crosses" in I by a small number of patterns. In the next section we use MDL in a more general framework, i.e., in pattern mining. Intents of formal concepts, in turn, can be considered as patterns of a special kind.

Minimal Description Length: Basic Notions

MDL is aimed to find a subset of patterns that compresses data the best. In our study we use Krimp [START_REF] Vreeken | Krimp: mining itemsets that compress[END_REF] as a practical implementation of this principle. In Section 3.1 we give a short description of it and in Section 3.2 we discuss how background knowledge can be embedded into MDL.

MDL in Practice: the Krimp Algorithm

The input of the algorithm is a dataset and a list of patterns (that are computed on the same dataset). The patterns are ordered w.r.t. their length and frequency. The result of Krimp is a two-column code table that consists of patterns and their encoding lengths (an examples of code tables are given in Figure 2). The objective of Krimp is minimization of the function

L(D, CT ) = L(D | CT ) + L(CT | D), (1)
where

L(D | CT ) is the length of the dataset D = {g | g ∈ G}
(B) = -log (u(B)/U ) is inversely proportional to the usage u(B) = |{t ∈ D | B ∈ cover(t, CT )} |.
The usage shows how many times B is used to cover objects in D, U = B∈CT u(B) is the total usage of itemsets. We leave the details on itemset storage out of scope of this paper and take into account the compression related to a particular choice of itemsets, i.e., we use the simplified version of the lengths:

L(D | CT ) = g∈D B∈cover(g,CT ) l(B) = - B∈CT u(B) log u(B) U , L(CT | D) = B∈CT l(B) + code(B).
A code table is incrementally computed. At the beginning it contains only single-attribute patterns {{m} | m ∈ M }. A set of patterns -candidates in the code table -are ordered w.r.t. their length (intent cardinality) and frequency (extent cardinality). At each step the best candidate is added to the code table if its usage allows for smaller encoding length, otherwise it is removed from the code table and the candidate set.

Example. Let us consider how Krimp selects patterns using the running example (the context is given in Figure 1, (1)). Here we represent the context as a set of transactions, see Figure 2, (1). The main stages are given in Figure 2, [START_REF] Barron | The minimum description length principle in coding and modeling[END_REF][START_REF] Belohlavek | From-below approximations in boolean matrix factorization: Geometry and new algorithm[END_REF][START_REF] Coenen | The lucs-kdd discretised/normalised arm and carm data library[END_REF]. As candidates we use intents of formal concepts with the size of intent and extent exceeding 1. We sort them first by the size of intent and then by the size of extent (in descending order). Let us consider some steps of the algorithm.

Initial state (Figure 2, (2)): the code table consists of single-attribute patterns. Usage is equal to frequency. Sets of attributes in the dataset are covered by single-attribute patterns.

First step (Figure 2, (3)): An attempt to add the top pattern from the candidate set. Pattern ac is used to cover object g 1 , g 4 and g 5 (Figure 2,(3)), the usage of single attributes a and c decreases by 3. The description length (see Formula 1) is computed for the updated code table and covering. Since the inclusion of ac into the code table provides smaller description length, ac is accepted for the code table.

Further, the top patterns one by one are used to minimize the description length.

Last step (Figure 2, (4)): The last candidate bc can cover only object g 2 (since subsets bc are partially covered by other members of the code table). It is not added since its inclusion in the code table does not provide better compression (i.e. smaller description length). The subset of MDL-optimal patterns is {{ac}, {de}}. Fig. 2. The main stages of the Krimp algorithm. "Covering" tables show the dataset with covering by itemsets from the corresponding code table above the covering, (•) depicts an itemset that covers some attributes of an object. CT is a two-column code table, where "IS" and"U" stand for itemsets and their usage in greedy covering, respectively. "CS" is a candidate set.

MDL in Practice: Compression under Constraints

The implementation of the MDL principle is based on heuristics and allows for the solution which is close to the optimal one. In practice, there exist several ways to select subsets of patterns that have almost the same size and ensure good compression. Thus, it becomes difficult to explain why a particular subset was chosen.

More than that, by selecting a subset of patterns one is interested in patterns that have particular properties, e.g., being stable w.r.t. noise, have high probability under certain condition, etc. Despite proper interpretability, the application of interestingness measures requires a threshold and results in a redundant set of patterns (quite similar patterns). As interestingness measures of concept (A, B) we took frequency f r(B) = |A|, i.e. the size of extent, length len(B) = |B|, i.e., the size of the intent, and lift lif t(B) = b∈B P r(b)/P r(B),

where P r(•) = |(•) |/|G|.
In our study we combine the measure-based selection with Krimp to get a threshold-free approach that provides a small non-redundant subset of patterns having desired properties. The modified approach works as follows. First, all patterns are sorted w.r.t. chosen interestingness measures. Then the ordered set is considered as a candidate set. The greedy covering strategy (Krimp) is applied to select the most interesting and diverse patterns. The original workflow and the adapted version that is used in the paper are given in Figure 3. Apply greedy strategy to cover data length and frequency

Compute closed (frequent) patterns

Reorder patterns w.r.t.

Apply greedy strategy to cover data an interestingness measure Fig. 3. The workflow for pattern mining by the original Krimp and its adapted version.

In the next section we show how the embedding of background knowledge (i.e. reordering of patterns w.r.t. interestingness measures) affects the results of pattern mining.

MDL in Closed Itemset Mining

In the worst case a concept lattice contains an exponential number of partially ordered intents (concepts), the application of MDL allows for the selection of a small subset of intents. Our experiments show that the application of the MDL principle allows for significant reduction in the number of patterns (up to 5% of the formal concepts, see Table 2). In the context of measure-based pattern mining, the application of MDL makes the measure-based selection threshold-free. More than that, a set of the MDL-optimal patterns has better characteristics than the top-n patterns. First of all, almost the same concepts (intents) are removed from the set of selected patterns. In our experiments we call this property "non-redundancy". For a set of patterns to be "non-redundant" means to have the following characteristics: differ from the most similar pattern in the set (i.e., distance to the 1st nearest neighbor), make shallow hierarchy by inclusion B 1 ⊂ B 2 ⊂ . . . ⊂ B n (i.e., average length of the longest paths built from partially ordered itemsets) and do not have a lot of more general patterns B i ⊂ B, i ∈ [1, k] (the rate of patterns with children).

If we compare the sets of top-n and MDL-optimal patterns of the same size we will see, as a side effects of the "non-redundancy", that MDL-optimal patterns cover in total more data ("crosses" in a formal context) being diverse and interesting w.r.t. a given measure.

It is clear to see that MDL approach not only dispenses from predefined thresholds but also filter out similar interesting patterns and provides more comprehensive data description.

We examine the following orders of patterns: area f r lif t(B) = f r(B) • lif t(B), area len f r(B) = len(B) • f r(B), area len lif t(B) = len(B) • lif t(B) and sequential ordering by len and f r, len and lif t, lif t and len (the patterns 4). An example of ordering for frequent closed itemsets (frequency is greater than 2) for the running example is given in Table 1.

Table 1. Values of interestingness measures and ordering of patterns for the running example from Figure 1, ( 1). An alternative ordering is given in (•), to select one ordering among the altervative ones additional rules are required to set. The discretized datasets from LUCS-KDD repository [START_REF] Coenen | The lucs-kdd discretised/normalised arm and carm data library[END_REF] were used in the study, the parameters of the datasets are given in Table 2. We split each dataset into 10 parts and in each of 10 experiments we use 9 of them as a training set and one part as a test set.

Concepts

In this section we compare characteristics of MDL-optimal with top-n itemsets, patterns in both sets are ordered w.r.t. the same interestingness measure. The size of a set of top-n itemsets is equal to the size of a set of MDL-optimal patterns. The scheme of computing these sets is given in Figure 4. We compare the sets of patterns within the following properties: non-redundancy, data covering and representativeness.

Non-redundancy

By redundant set of patterns we mean a set of patterns that contains a lot of similar itemsets. We measure redundancy by three parameters: average distance to the 1st nearest neighbor, average length of the longest paths built from partially ordered itemsets, and average number of itemsets that have at least one more general itemset (child).

Distance to the 1st nearest neighbor. To compute this parameter we represent patterns as binary vectors and take into account the smallest Euclidean distance between each pattern and the remaining patterns in the pattern set. The average value for a pattern set is taken as the average distance to the 1st nearest neighbor. A set containing a lot of similar patterns will have low average values, see Figure 5 (1) for an example. As it can be seen from Figure 6 (1), the MDL principle provides much more distinctive itemsets. Top-n concepts have a lot of similar patterns, while MDLoptimal ones are pairwise distinctive (w.r.t. Euclidean distance).

Average length of the longest paths built from partially ordered itemsets. The patterns can be partially ordered by inclusion, i.e. B 1 ⊂ B 2 ⊂ . . . ⊂ B n , where B n is the most specific patters and B 1 is the most general one. We call this ordered sequences paths. If B n ⊆ g then B i ⊆ g is guaranteed for all i ∈ [1, n -1]. Longer paths contain more patterns describing the same objects. Thus, a long path can be considered as an indicator of redundancy. In other words, these patterns characterize the same objects at different levels of abstraction and contain only a few new details w.r.t. the nearest neighbors in the path. Short paths correspond to "flat" structures with more varied patterns. An example of comparison of two tiny pattern sets is given in Figure 5,(2).

As we see in Figure 6 (b), for ordering w.r.t. len (see len f r and len lif t) the MDL priciple does not provide any benefits, while its application to area len sep and area sep lif t, lif t len f r allows for more flattened structures, even more flattened than with len. It means that pattern mining with area len sep and area sep lif t, lif t len f r can be significantly improved by the application of MDL. The rate of pattern with children is 3/5. (3) The rate of patterns with children (i.e. more general / short patterns). Fig. 5. Non-redundancy measures computed for patterns set given in Figure 1. The set S3 (column 1) is better than S2 (column 2) w.r.t. all the parameters: the average distance is higher, the average length of the longest paths and the rate of patterns with children are smaller.

S3

(1) Distance to the 1NN (2) The average path lengths

(3) Rate of patterns with children.

Fig. 6. Non-redundancy parameters: (1) the average distance to the 1st nearest neighbor for itemsets selected with MDL and top-n itemsets; (2) the average length of the longest paths computed on the chain of itemsets formed by inclusion of its attributes;

(3) the average rate of itemsets with children. On the X-axis is different orderings of patterns, on the Y -axis is the values of the listed above non-redundancy parameters for MDL-optimal set (blue) and top-n (green) set of the same size.

Average number of itemsets with children (more general itemsets). This parameter characterizes the uniqueness of patterns in a set, absence of the second pattern B 2 ⊂ B 1 that characterizes the same subset as a more specific one. This parameter is related to the previous measure, but it indicates just an amount of itemsets having at least one more general itemset. An example of computing this parameter is given on Figure 5, (3). The results of experiments (see Figure 6, (c)) show that the MDL principle selects more distinctive itemsets than top-n itemsets.

Data coverage

A subset of selected patterns can be considered as a concise representation of a dataset. Thus, it is important to know how much information is lost by compression. We measure this parameter by the rate of covered attributes. Values close to 1 correspond to the lossless compression.

The average covering rate is given in Figure 7 (1). With the same number of patterns MDL ensures better covering. For area f r lif t, area len f r and area len lif t MDL-optimal set covers much more data than top-n patterns.

Itemset typicality (representativeness)

In our experiments we also address typicality of patterns. In this study we measure it by the usage of patterns. To compute usage we consider the ordered It should be noted that it is not obvious which values are better. The usage serves to characterize a subset of patterns. The high values correspond to a subset of common patterns, while low values indicates that a subset contains less typical, but still interesting (w.r.t. interestingness measures) patterns.

Figure 7(2) shows the average usage for MDL-optimal and top-n patterns. The usage of MDL-optimal patterns is almost the same for different orders while the usage of top-n is dependent on ordering.

Conclusion

In the paper we propose a new approach to the measure-based pattern mining. It can be considered as an "implementation of the MDL principle under constrains" or "embedding of background knowledge (on interestingness) into MDL". We took the Krimp algorithm as a basic implementation of MDL and studied a range of interestingness measures within it.

The proposed approach is a threshold-free method for the selection of a small set of patterns having desired properties. The chosen patterns are diverse and varied, they cover almost all attributes of objects.

The studied Krimp algorithm can be changed further to improve (closed) pattern mining as follows. The greedy strategy may be relaxed, i.e., overlapping patterns can be used to cover an object. Some additional mechanism may be proposed to deal with noisy data (missed values).

  called a set attributes and I ⊆ G × M is a relation called incidence relation, i.e. (g, m) ∈ I if the object g has the attribute m. The derivation operators (•) are defined for A ⊆ G and B ⊆ M as follows: A = {m ∈ M | ∀g ∈ A : gIm} B = {g ∈ G | ∀m ∈ B : gIm} A is the set of attributes common to all objects of A and B is the set of objects sharing all attributes of B. An object g is said to contain a pattern (set of items or itemset) B ⊆ M if B ⊆ g . The double application of (•) is a closure operator, i.e. (•) is extensive, idempotent and monotone. Sets A ⊆ G, B ⊆ M , such that A = A and B = B , are said to be closed. A (formal) concept is a pair (A, B), where A ⊆ G, B ⊆ M and A = B, B = A. A is called the (formal) extent and B is called the (formal) intent of the concept (A, B). A formal concept is said to cover set of objects A and set of attributes B. A partial order is defined on the set of concepts as follows:

Fig. 1 .

 1 Fig. 1. Formal context and its coverings.

  A formal context from Figure 1, (1) represented as a set of transactions Covering (a)(b)(c) (b)(c)(d)(e) (d)(e) (a)(c)(d)(e) (a)(c) (2) Initial state. Covering (ac)(b) (b)(c)(d)(e) (d)(e) (ac)(d)(e) (ac) (3) The state after adding ac to the code table.

  Covering(ac)(b) (b)(c)(de) (de) (ac)(de) (ac) (4)The last step. bc is not added to the code table.

Fig. 4 .

 4 Fig. 4. The principle of computing MDL-optimal and top-n sets of patterns

  of the longest paths is 1.

  of the longest paths is 2.5.(2) The longest paths built on partially ordered patterns (by inclusion).

Fig. 7 .

 7 Fig. 7. Pattern set parameters: (1) the average covering rate of itemsets (i.e. the rate of crosses covered by patterns); (2) the average itemset usage (reflects typicality/representativeness of patterns). On the X-axis is different orderings of patterns, on the Y -axis is the covering rate and the average itemset usage for MDL-optimal set (blue) and top-n (green) set of the same size.

  encoded with the code table CT and L(CT | D) is the length of the code table CT computed w.r.t. D. The objects are encoded by disjoint patterns in a greedy manner, i.e., starting from the top elements of CT. The length of pattern B is computed using an optimal prefix code given by Shannon entropy, i.e., the length l

Table 2 .

 2 Characteristics of datasets

	dataset	nmb. of	nmb. of	nmb. of	Number of MDL-optimal area area area len len	lift
		obj.	attr.	concepts	fr lift	len fr	len lift	fr	lift	len
	breast	699	16	702 36.0 32.2	20.4 37.3 37.3 33.5
	car	1 728	25	12 420 868.4 849.2 138.6 714.6 847.7 698.3
	ecoli	336	29	690 58.8 55.9	16.4 64.9 65.6 55.9
	iris	150	19	183 31.1 28.9	12.9 34.8 34.6 26.3
	led7	3 200	24	3 808 108.0 118.3	64.2 108.7 108.7 130.3
	pima	768	38	2 769 110.1 106.3	35.9 120.6 112.1 101.7

  Euclidean distances to the 1st nearest neighbors. The average distance for S3 is longer then for S4, thus S3 contains for diverse patterns.

	binary representation (abcde) bc 01100 de 00011 ac 10100 The average distance is (2 + 2 nearest neighbor Euclidean distance ac √ 2 bc(ac) 2 bc √ 2 √ 2)/3.	S2 bcde 01111 binary representation (abcde) cde 00111 abc 11100 ac 10100 de 00011 The average distance is nearest neighbor cde bcde (de) ac abc cde √ 2.	Euclidean distance √ 2 √ 2 √ 2 √ 2 √ 2
	(1)


Tatiana Makhalova
email: tpmakhalova@hse.ru

Sergei O Kuznetsov
email: skuznetsov@hse.ru

Amedeo Napoli
email: amedeo.napoil@loria.fr

A First Study on What MDL Can Do for FCA

Formal Concept Analysis can be considered as a classification engine able to build classes of objects with a description or concepts and to organize these concepts within a concept lattice. The concept lattice can be navigated for selecting significant concepts. Then the problem of finding significant concepts among the potential exponential number of concepts arises. Some measures exist that can be used for focusing on interesting concepts such as support, stability, and other. MDL (minimum description length) is also a good candidate that was rarely used in FCA by now for such objective. In this paper we argue that MDL can give FCA practitioners a good measure for selecting significant and representative concepts.

Introduction

Formal concept analysis (FCA) plays an important role in Data Mining and Machine Learning. Concept lattices support mainly unsupervised settings, improving tasks such as building taxonomies and ontologies, computing implications and association rules, clustering and solving classification tasks. These tasks in practice are coupled with the problem of exponential explosion of the number of formal concepts.

By now, to tackle this issue, a lot of different approaches have been proposed, including data pre-and postprocessing, background knowledge incorporation, computing approximate concepts (see [START_REF] Kuznetsov | On interestingness measures of formal concepts[END_REF] for an overview). As a result, one expects to get a small set of interesting, meaningful, non-redundant concepts [START_REF] Buzmakov | Fast generation of best interval patterns for nonmonotonic constraints[END_REF].

In this paper, we focus on the characterization of such a small set of concepts. Instead of using an interesting measure in postprocessing step, we propose to rely on the minimum description length (MDL) principle [START_REF] Grünwald | The minimum description length principle[END_REF], which allows one to select small sets of diverse and interpretable concepts. Providing the best lossless compression of the data, the MDL optimal sets of patterns (itemsets) automatically provides a balance between the quality of fit of the data and the complexity of the model without any user-defined parameters to be set [START_REF] Aggarwal | Frequent pattern mining[END_REF].

In this paper we propose a first study on the application of the MDL principle in FCA settings. To the best of our knowledge, this is one of the first papers to study the effective use of MDL in the framework of FCA.

The rest of the paper has the following structure. In Section 2 we remind the basic definition used in FCA and discuss how FCA can be used to solve classification problem. Section 3 introduces the MDL principle. In Section 4 we discuss what MDL can bring to FCA. Section 5 gives conclusion and directions for future work.

Preliminaries

In this section we recall the main notions that are used in the paper. We study attribute sets of formal concepts, which have several alternative names, such as itemset, intent, or pattern. We discuss the application of FCA in unsupervised and supervised settings.

FCA. Basic Notions

Here we briefly recall FCA terminology [START_REF] Ganter | Formal concept analysis: Logical foundations[END_REF]. A formal context is a triple (G, M, I), where G = {g 1 , g 2 , ..., g n } is called a set objects, M = {m 1 , m 2 , . . . , m k } is called a set attributes and I ⊆ G × M is a relation called incidence relation, i.e. (g, m) ∈ I if the object g has the attribute m. The derivation operators (•) are defined for A ⊆ G and B ⊆ M as follows:

A = {m ∈ M | ∀g ∈ A : gIm} B = {g ∈ G | ∀m ∈ B : gIm}
A is the set of attributes common to all objects of A and B is the set of objects sharing all attributes of B. An object g is said to contain a pattern (set of items) B ⊆ M if B ⊆ g . The double application of (•) is a closure operator, i.e. (•) is extensive, idempotent and monotone. Sets A ⊆ G, B ⊆ M , such that A = A and B = B , are said to be closed.

A (formal) concept is a pair (A, B), where A ⊆ G, B ⊆ M and A = B, B = A. A is called the (formal) extent and B is called the (formal) intent of the concept (A, B). A partial order is defined on the set of concepts as follows:

(A, B) ≤ (C, D) iff A ⊆ C (D ⊆ B), a pair (A, B) is a subconcept of (C, D), while (C, D) is a superconcept of (A, B).
The number of formal concepts grows exponentially w.r.t. the size of a formal context, i.e. the number of objects in G and attributes in M . Thus, it becomes almost impossible to analyze and interpret the whole set of generated concepts. Pattern discovery techniques are designed to solve this problem. The goal of pattern discovery within the framework of FCA is to find a non-redundant set of concepts that are interesting w.r.t. specified constrains/interestingness criterion. The criterion can be applied to both intent and extent, whereas pattern discovery in general is related solely to the itemset assessment.

Example. Let us consider the toy example given in Table 1. We will use either D 1 or D 2 to compute classifiers and the remaining objects will be used to assess the quality of the classifiers. The set of attributes M includes columns m 1 , . . . , m 9 .

D2 D1 g1 dog × × × × + g2 cat × × × × + g3 frog × × × + g4 car × × - g5 ball × × × × - g6 chair × × × × - g7 fur coat × × × × - g8 sunflower × × - g9 fish × × × + g10 leopard × × × × + g11 table × × × × -
The additional attribute "target", i.e., class labels, is not taken into account under unsupervised settings.

Filtering concepts based on their extent and/or intent belongs to class of unsupervised problems, since any supplemental information is unavailable. In the next subsection we consider the problem of concept selection in supervised settings.

FCA under Supervised Settings: Concept-based Classifiers

In supervised settings along with the objects and their descriptions an additional attribute w is given. It specifies the class of an object. We denote the set of its values by ε.

We shall confine ourselves to two-class classification and study the simplest case, where each object belongs to a single class. In the defined settings ε = {+, -}. We consider the case where a set of objects G = G + ∪ G -is divided into 2 disjoint subsets, i.e., a set of positive examples G + , negative examples G -. In practice, a set G τ of unlabeled examples appears as well. The objects are described by attributes from M and the target attribute w is defined as follows: gIw = " + " for g ∈ G + and gIw = " -" for g ∈ G -. The objects from G + ∪ G -compose training and test sets, which are used to generate concepts and to estimate quality of classifiers, respectively.

It is assumed that there exists an unknown function that maps each object g ∈ G (or its description g ⊆ M ) to an element in ε. The goal is to reconstruct as accurately as possible the unknown function using an observable subset of labeled objects. To do that, one builds classifiers, which can be constructed by means of FCA as follows.

For each concept (A, B) a class label e ∈ ε is defined by majority of labeled objects in the extent, i.e. class((A, B)) = arg max e∈ε |A e |/|A|, where A e = G e ∩ A. To classify an unlabeled object g w.r.t. a pair (B, e) we set the following classification principle: According to Formula 1, we get a non-empty response e from (B, e) if an object description g contains attribute set B. To simplify notation we will write Be instead of (B, e). In general, B could be any itemset, not necessarily closed.

(B, e)(g) = e, if B ⊆ g ∅, otherwise. (1)
The details on classification problem in terms of FCA can be found in [START_REF] Ganter | Formalizing hypotheses with concepts[END_REF][START_REF] Kuznetsov | Machine learning and formal concept analysis[END_REF].

To identify the best classifier a test set G * ⊆ G + ∪ G -is used, we will write G * + and G * -for subsets of positive and negative objects in the test set G * , i.e., for G * ∩G + and G * ∩G -, respectively. In our paper we estimate classifiers using the measures listed below and provide small examples of their usage (see Table 2). Precision measures how many correct answers are given by the classifier:

prec( Be , G * ) = g | Be (g) = e, g ∈ G * e / g | Be (g) = e, g ∈ G * . (2)
Recall measures how many objects from a target class are characterized by the classifier (i.e. whether a classifier is specific or general):

recall( Be , G * ) = g | Be (g) = e, g ∈ G * e /|G * e |. (3)
Support measures how many objects can be classified (correctly or not):

sup( Be , G * ) = g | Be (g) = e, g ∈ G * /|G * |. (4)
The accuracy takes into account examples from the remaining classes ε \ {e} unclassified by Be :

acc( Be , G * ) = g | Be (g) = e, g ∈ G * e ∪ g | Be (g) = ∅, g ∈ G * c , c ∈ ε \ {e} |G * | .
(5) However, other measures can also be examined [START_REF] Baldi | Assessing the accuracy of prediction algorithms for classification: an overview[END_REF], e.g., F1 score, AUC, etc. In the next section we consider an ensemble of classifiers based on single concept-based classifiers defined in Formula 1.

Concept-based Classifiers

A set of the classifiers S = Be j j∈J , e ∈ ε with a rule for aggregation of their responses constitute an ensemble of classifiers. We call an ensemble conceptbased classifiers (CBC) if the itemsets B are intents of formal concepts. As an aggregation rule the following principles might be chosen: class of the majority of labels, classification if responses are the same class labels, the highest priority class from the set of responses.The best CBCs are those that ensure high accuracy and have a small size of S.

Example. Let us turn back to the running example from Table 1. The supplementary information on class labels (the target attribute w) is given in column "target". We consider the following set of classifiers:

S = {({"cold-resistant"} , -), ({"4 legs", "change size"} , +)} .
As a rule for aggregation of responses we use the priority principle, let us suppose that "-" class has higher priority than "+", thus we can apply classifiers from "-" class and, if the object remains unclassified, we try to classify it with "+" class classifiers.

CBC works for g 10 as follows. A classifiers with the highest priority ("-" class) are firstly applied. Since {"cold-resistant"} ⊆ g 10 , we get an empty response and turn to the classifiers of lower priority ("+" class). {"4 legs", "change size"}⊆ g 10 , we get "+" response and classify g 10 as an member of "+" class. The object g 11 is classified as "-", since {"cold-resistant"}⊆ g 11 . g 8 remains unclassified, since we get empty responses from all classifiers in S, g 9 is misclassified by ({"cold-resistant"} , -).

Thus, a formal concept is a well-interpreted, quite intuitive and handy tool for describing subsets of objects both un-and supervised settings. However, as it was mentioned earlier, the huge number of generated concepts hampers interpretation of the results as well as its practical application.

In the next section we provide an approach that can be used to select a small set of diverse concepts.

Minimal Description Length Principle

Describing Data with MDL . Unsupervised Settings

The MDL principle in the context of pattern mining is formulated as follows: the best set of patterns is the set that best compresses the database [START_REF] Vreeken | Krimp: mining itemsets that compress[END_REF].

The main element of this approach is a code table (CT), which is composed of "some" itemsets with their length. The best code table minimizes the total length in bits

L(D, CT ) = L(D | CT ) + L(CT | D), where L(D | CT ) is the length of the dataset encoded with the code table CT and L(CT | D) is the length of the code table CT computed w.r.t. D.
To encode an object g in a dataset one needs to select a subset of disjoint itemsets that cover all attributes of g. By u(B) = | {t ∈ D | B ∈ cover(t)} | we denote the usage of itemset B in dataset D, i.e., how many times B is used to cover objects in D, where U = B∈CT u(B) is the total usage of itemsets. The principles of building code tables will be discussed further.

To define the length of an itemset we use an optimal prefix code given by Shannon entropy, i.e., l(B) = -logP r(B), where probability is defined as follows: P r(B) = u(B)/U . Thus, the itemsets with higher frequency have smaller code lengths. The details on itemset encoding and memory that is needed to store itemsets of code table are out of scope of this paper. Since we are interested in the length of the description rather than in the encoding itself (materialized codes), we consider simplified version of L(CT, D) where only terms that characterize "specificity" of itemsets for the dataset are taken into account:

L(D | CT ) = g∈D B∈cover(g) l(B) = - B∈CT u(B) log u(B) U , L(CT | D) = B∈CT code(B) + l(B),
where code(B) is the length in bits to store itemset B in a code table.

Principles of computing a code A set of candidates might be composed of any kind of patterns: arbitrary itemsets, closed ones, δ-itemsets, etc. The items in a set of candidates are sorted w.r.t. chosen interestingness measures, in particular, in Krimp [START_REF] Vreeken | Krimp: mining itemsets that compress[END_REF] patterns are ordered by the length of itemset (its size of attribute set) and frequency.

Note that the problem of computing optimal code table implies exhaustive search for the best combination of patterns, and in practice some heuristics are used.

Example. Let us consider the principle of computing a CT using the running example. The iterative process of updating a CT for class "animal" and recomputing the cover of D 2 is described in Table 3. As candidates we use the set of concepts sorted by area, i.e., frequency × length, the ordered list of candidates with their areas is given in columns "Candidate set, area". Columns "CT" correspond to the CT at each iteration. The CT contains itemsets and the number of times each itemset is used to cover objects. The covering is given in columns "Data with covering". At the beginning it consists of single-attribute itemsets. The first object m 1 m 2 m 3 m 6 is covered by four single-attribute itemsets. The first candidate is m 1 m 2 m 3 with an area equal to 6. At the next step this candidate is used to cover attributes in the dataset covered by single-attribute itemsets. With the chosen candidate, the covering for two objects is changed (compare the first two objects in columns "Data with covering" in "Step 0" and "Step 1").

Step by step a new itemset with the maximal area is added to the CT. If a new CT compresses the data better then the old one, the itemset is accepted to the CT, otherwise, it is removed from both the CT and the candidate set. If the CT is changed, the usage of itemsets in the CT and area for candidates are recomputed.

Table 3. An iterative procedure of computing a code table for class "animal" and the cover of D2. The names "i" and "u" stand for an itemset and its usage in covering

Step 0

Step

u i u m1m2m3 2 (m1m2m3)(m6) m3m4m9, 3 m1m2m3 2 (m1m2m3)(m6) m1m3m8 1 (m1m2m3)(m7) m1m3m8 1 (m1m2m3)(m7) m3, m4 1 (m1m3m8) m3m4m9 1 (m1m3m8) m6, m7, m9
1 (m3)(m4)(m9) m6, m7 1 (m3m4m9) m1, m2, m5, m8 0 m1-m5 0 m8-m9 0

MDL under Supervised Settings

Being purely unsupervised, the MDL principle can be adapted for usage in supervised settings. The idea is to find a compressed representation for objects using code tables of each target class separately. Classes have their own code tables. A code table consists of typical patterns and their lengths (the more typical patterns have shorter lengths). To classify a new object, its set of attributes is covered by itemsets from code tables of each class. Then, the encoding lengths for each class are computed and the class that corresponds to the minimal encoding length is assigned to the object. The length reflects typicality of an object for a particular class (code table ).

Example. Consider classification with code tables "CT 1 " and "CT 2 " from Table 4 that have been computed on sets D 1 and D 2 , respectively. The details on the computing of the code tables is out of the scope of this paper (see the Krimp algorithm [START_REF] Vreeken | Krimp: mining itemsets that compress[END_REF]). Each column"CT i " contains code tables CT A and CT N A for "animal" and "not animal" classes, respectively. Let us consider how an object g 9 is classified with the code tables from "CT 1 ". The main steps of the covering of g 9 are given in Table 5. To find a covering we use a greedy strategy, i.e., we start from the first itemset in a code table and then stop iterating over itemsets when all attributes of the object are covered. To cover g 9 with CT N A we take the first itemset m 1 m 4 m 5 m 8 (see Step 1 in Table 5), it does not cover g 9 , at the next step we take the second itemset m 4 m 9 , it covers a subset of g 9 and m 3 remains uncovered (see Step 2). The iterations over itemsets from CT N A continues until all the attributes of g 9 will be covered. Classification with code tables from Table 4 are given in Table 6. The objects are covered by itemsets from tables of "animal" and "not animal" as it is described in Table 5). The class where the object has the shortest length is assigned to this object.

In this section we considered how the MDL principle is used to select patterns (itemsets) in un-and supervised settings. In the next section we study how MDL works in the FCA framework. Table 4. Code tables CT1,A and CT1,NA, CT2,A and CT2,NA computed on datasets D1 and D2, respectively. The lengths of itemsets are given with their relative size. A shorter itemset is more typical, i.e., more often used to cover the data on which they had been computed.

m1m2m3 2 m1m2m3 1 m1m4m5m8 1 m3m4m9 1 m1m4m5m8 1 m1m3m8 1 m4m9 2 m1m3m8 1 m4m9 2 m1 0 m1 0 m1 0 m1 0 m2 0 m2 1 m2 0 m2 1 m3 0 m3 1 m3 0 m3 2 m4 0 m4 1 m4 0 m4 1 m5 0 m5 2 m5 0 m5 2 m6 1 m6 1 m6 1 m6 1 m7 1 m7 0 m7 1 m7 1 m8 0 m8 0 m8 0 m8 0 m9 0 m9 0 m9 0 m9 0
Table 5. The steps of the covering process of object g9 by itemsets from the code tables of classes "animal" and "not animal", CT1,A and CT1,NA, respectively. To cover g 9 with CT1,A we try to use every itemset from the top, i.e., m1m2m3, m1m3m8, m1, etc. We stop when all attributes are covered. The covering procedure for CT1,A and CT1,NA stops after m9 and m3, respectively, is being considered.

Covering with CT1 for "animals" Covering with CT1 for "not animals"

Step Used itemset (an attempt to cover)

MDL in FCA: First Steps

To show that MDL can improve the practical application of FCA, in this section we discuss the results of experiments on the embedding of MDL within FCA. We used the discretized datasets from LUCS-KDD repository [START_REF] Coenen | The lucs-kdd discretised/normalised arm and carm data library[END_REF]. We split the data into 10 parts and in each of 10 experiments we use 9 of them as a training set and one as a test set. The average performance is reported in the paper. To compute code tables and to cover objects the Krimp algorithm [START_REF] Vreeken | Krimp: mining itemsets that compress[END_REF] is used.

Descriptive Patterns. FCA in Unsupervised Settings

In unsupervised learning (where the target attribute is not given), one is interested in a small number of meaningful patterns. In our experiments we compute the set of closed itemsets and apply the MDL principle to them. For MDL we sort itemsets in the candidate set by "length" (the cardinality of intent) and "frequency" (the cardinality of extent). MDL-optimal concepts are concepts whose intents are included in a code table with a non-empty usage. The results of the experiments are given in Table 7. For instance, the "auto" dataset consists of 205 objects and 135 binary attributes. The total number of formal concepts is 67 557, 57 of them are MDLoptimal.

Our experiments show that the selected itemsets might be shorter or longer on average than the itemsets in the whole set of closed concepts (see column "avg. length of intent" in Table 7). However, around 2% (12 % at most) of the concepts are selected with the MDL-principle. Thus, MDL can be considered as a threshold-free alternative for selection of interesting itemsets. It is important to notice that the subset of MDL-optimal itemsets is composed of diverse patterns and expert assumptions on interestingness of concepts can be embedded by ordering candidates w.r.t. particular interestingness measures. Since a greedy strategy is used to make a code table, one gets a set of diverse itemsets that are in agreement with interestingness.

Classifier Comparison. FCA in Supervised Settings

In this section we study both the accuracy of ensembles of classifiers S and their basic elements B. We also compare the accuracy of the ensembles with commonly used classification methods, e.g., random forest, multilayer perceptron and support vector machine.

Comparison of single classifiers. Here we consider formal concepts as single classifiers. We study precision, recall (Formulas 2 and 3, respectively) and precision loss (Formula 6). Formula 6 is also used as a measure of overfitting, i.e., cases where accuracy on a test set is worse than on a training one. If precision loss is close to 1, we call it overfitting, the classifier makes much more errors on a test set than on a training set. If precision loss is close to 0, we get "expected" precision on a test set.

prloss( Be , G + ∪ G -) = precision( Be , G \ G * ) -precision( Be , G * ) (6)
In Figure 1 we show the performance of single concepts in the following 2dimensional spaces: "precision" and "precision loss" (blue shapes), "recall" and "precision loss" (green shapes). Due to lack of space we provide two typical kinds of distributions using results for "Breast cancer" and "Wine" datasets. Precision loss is shown on the vertical axis, recall and precision are combined in the horizontal axis. The pictures are density plots for the (sub)set of concepts in the chosen dimensions. Intense-colored regions correspond to the regions with high concentration of concepts.

Let us consider the classifiers of "Breast cancer" dataset (the first line in Figure 1). The first figure shows that most concepts have precision loss close to 0, i.e., they have similar precision both on training and test set. Classifiers with precision loss close to 0 are preferable, since they have the "expected" precision even on unobservable data. Let us consider the position on the horizontal axis. The blue shape ("precision" axis) is located close to 1, it means that most concepts have high precision on a training set. A long stretch of the green shape along the axis means that the set of classifiers consists of both specific (having relatively big intents) and general concepts (recall is from 0 to 1).

The second plot corresponds to MDL-optimal classifiers. In both spaces, i.e., "precision" and "precision loss" (blue shapes), "recall" and "precision loss" (green shapes), classifiers are concentrated in two points on the "precision loss" axis, the bottom shape is brighter than the upper one. It means that a lot of classifiers have similar precision on training and test sets, and there are several classifiers that have much smaller precision on a test set (they are overfitting classifiers). Since the blue shapes are located close to 0 on the horizontal axis, we conclude that the classifiers are very precise on a training set. The concentration of the green shapes around 0 on the horizontal axis means that most classifiers have recall close to 0, thus, the classifiers are very specific.

Classifiers of "Wine" dataset demonstrate another typical distribution of the classifiers. We can read the plots as it is done above. Here we discuss the key difference between two kinds of datasets.

In our experiments, the set of classifiers on the whole set of formal concepts was comprised of either mostly one type of classifiers with precision loss close to 0 or two types of classifiers: with precision loss close to 0 and to 1. Thus, the set of concept-classifiers contains either mostly non-overfitting (good) classifiers or non-and overfitting ones. MDL-based subset usually includes both non-and overfitted classifiers, all these classifiers are quite specific (have big intents).

A reasonable question arises: what is the accuracy of ensembles of classifiers built on such different types of concepts? In the next paragraph we examine the accuracy of ensembles of classifiers that are constituted by MLD-optimal subsets. Comparison of ensembles of classifiers In this section we compare ensembles built on a set of formal concepts ("CBC") and its MDL-optimal subset ("MDL") with commonly used classification methods like random forests (RFs), multilayer perceptrons3 (MLP) and support vector machines (SVM). We study the average accuracy on a test set, and the results are summarized in Table 8. As it was noticed above, we split our dataset into 10 folds (9:1 for train and test sets). The maximal accuracy over the 10 folds is also reported in the table. We pay our attention to the number of classifiers that constitute an ensemble. The smaller the number of classifiers the faster one can obtain the response and the better this response can be interpreted.

Our experiments show that among itemset-based classifiers (CBC, MDL, RF) MDL-based approach demonstrate quite good performances and have a much smaller set of classifiers. An ensemble with a small number of classifiers performs faster and is better interpretable. Thus, it is easier to classify with MDL-ensembles and understand the obtained results as well.

Conclusion

In this paper we have addressed the problem of selecting meaningful, nonredundant sets of formal concepts. We have proposed to use the MDL principle and to show how the expert understanding of interestingness might be incorporated into it.

The MDL principle ensures a good compression even when the set of formal concepts is huge (for example, 24 MDL-optimal among 6 432 concepts for "Breast cancer", 392 among 176 537 concepts for "nursery" dataset). In supervised settings, MDL principle tends to choose the specific classifiers, some of them have a precision loss close to 0.9. However, the MDL principle ensures high classification accuracy.

One interesting direction for future work is to study how some interestingness measures, such as stability, might be embedded into the MDL approach. Another interesting direction is to study connection between the MDL principle and Pareto optimality.

CT1 g 8 =

 8

Fig. 1 .

 1 Fig. 1. Precision loss of the whole set of concepts (CBC), MDL-optimal subsets of classifiers for "Breast cancer" (top row) and "Wine" (bottom row) datasets

Table 1 .

 1 An example of dataset.

	data	partitions	objects	m1 : 4 legs	m2 : hairs	m3 : change	size	m4 : cold-	resistant	m5 :do not	release CO2	m6 : black-	white	m7 : yellow-	brown	m8 : green	m9 : gray	target w:	animal

Table 2 .

 2 The values of quality measures (Formulas 2-5) for classifiers {"cold-resistant"} -and {"4 legs", "change size"} + from the running example in Table 1. The attribute sets of the classifiers are intents of formal concepts computed on D1. The set {g8, g9, g10, g11} is used to assess classifiers.

	classifier/ measure	{"cold-resistant"} -{"4 legs", "change size"} +
	prec recall sup acc	|{g11}|/|{g9, g11}| = 1/2 |{g11}|/|{g8, g11}| = 1/2 |{g9, g11}|/|G * | = 1/2 |{g10, g11}|/|G * | = 1/2	|{g10}|/|{g10}| = 1 |{g10}|/|{g9, g10}| = 1/2 |{g10}|/|G * | = 1/4 |{g10}|/|G * | = 1/4

  table. A code table is computed in an incremental manner: starting from a set of single-attribute patterns, i.e. {{m} | m ∈ M }. The optimization procedure is based on adding a new itemset to the code table, correcting the information about usage of the other itemsets in the code table, recomputing the itemset lengths and re-encoding the data. At each iteration a new pattern can be added or not to the code table.

Table 6 .

 6 Classification with code tables (MDL-based approach) from Table4. The class of the code table where an object has the shortest encoding length is assigned to the object

	Encoding with itemsets	animal	Encoding with itemsets not animal decision

Table 7 .

 7 The parameters of sets of formal concepts and their proper MDL-subsets.

	dataset	nmb. of obj.	nmb. of attr.	nmb. of concepts total MDL total MDL avg. length of intent	dataset	nmb. of obj.	nmb. of attr.	nmb. of concepts total MDL total MDL avg. length of intent
	auto	205	135 67 557	57 8.83 19.26 horse colic	368	83 173 808 101 6.96 3.92
	breast	699	16	642	24 7.36 9.04 iris	150	19	107	13 3.08 3.92
	car	1 728	25 12 617	94 5.12 3.47 led7	3 200	24	1 937 152 4.60 6.80
	chess	28 056	58 152 753 1 675 4.85 4.32 mushroom	8 124	90 181 945 211 15.23 19.53
	dermatology	366	49 16 324	47 6.98 5.70 nursery	12 960	30 176 536 392 6.53 5.56
	ecoli	336	29	694	25 5.49 6.08 page blocks	5 473	44	715	45 5.79 10.27
	flare	1 389	38 16 303 106 6.82 8.64 pima indians	768	38	1 609	50 4.99 5.86
	glass	214	46	4 704	50 5.06 4.32 ticTacToe	958	29 42 685 160 5.44 4.02
	heart	303	50 36 708	54 7.14 5.09 wine	178	68 13 170	52 5.14 3.90
	hepatitis	155	52 199 954	44 8.14 5.59 zoo	101	42	4 563	17 7.34 12.24

Table 8 .

 8 Performance of ensembles of classifiers Dataset name Classifier Avg. accuracy Max. acc. Avg. rule numb. Max. rule numb

	breast cancer ecoli iris	CBC MDL RF MLP SVM CBC MDL RF MLP SVM CBC MDL RF MLP SVM	0,86 ± 0,04 0,94 ± 0,03 0,93 ± 0,04 0,94 ± 0,03 0,93 ± 0,03 0,84 ± 0,05 0,77 ± 0,10 0,77 ± 0,05 0,84 ± 0,03 0,86 ± 0,04 0,93 ± 0,07 0,94 ± 0,06 0,95 ± 0,07 0,93 ± 0,07 0,93 ± 0,07	0,90 0,99 0,99 0,99 0,99 0,94 394,70 ± 14,47 355,00 ± 7,10 27,80 ± 0,98 30,60 ± 4,48 --0,85 37,30 ± 2,10 0,85 1236,40 ± 532,54 0,88 -0,94 -1,00 113,20 ± 5,57 1,00 18,50 ± 1,36 1,00 169,40 ± 192,45 1,00 -1,00 -	361 30 37 --410 40 1830 --119 20 531 --

Tatiana Makhalova, Sergei O. Kuznetsov, and Amedeo Napoli

We select the configuration that ensures the best accuracy among the following ones: (100:50:50),(100:50:25),(50:50:50)

Acknowledgements

The work was supported by the Russian Science Foundation under grant 17-11-01294 and performed at National Research University Higher School of Economics, Moscow, Russia.


Peter C Young

A Janot

Efficient Parameterization of Nonlinear System Models: a Comment on Nöel and Schoukens (2018)

Keywords: system identification, silverbox system, nonlinear modelling, continuous-time model, efficient parameterization

Nöel and Schoukens (2018) discuss a methodology for the discrete-time state-space identification of nonlinear systems and apply this to experimental data from the well known Silverbox nonlinear circuit, producing a model characterised by 13 parameters. This model explains the data very well but the parameter estimates are not well defined in the optimization results, with the very large confidence bounds suggesting that the model is over-parameterized. This comment shows that this is indeed the case and that the data can be explained equally well by an alternative continuous-time, State-Dependent Parameter (SDP) transfer function model with only 6 parameters, the estimates of which are well defined with very tight confidence bounds. The comment also raises questions about how the model form for nonlinear systems such as the Silverbox should be identified and suggests that the Data-Based Mechanistic (DBM) approach to modelling has some advantages in this regard.

Introduction

In their paper Grey-box State-space Identification of Nonlinear Mechanical Vibrations, [START_REF] Nöel | Grey-box state-space identification of nonlinear mechanical vibrations[END_REF] introduce a powerful method of 'grey-box' nonlinear modelling based on a general discrete-time state-space model form and show how a 13 parameter model of this type is able to explain experimental data from the Silverbox benchmark system (see e.g. [START_REF] Wigren | Recursive prediction error identification and scaling of non-linear state space models using a restricted black-box parameterization[END_REF]Schoukens 2013, Marconato et al. 2012) very well and in a parametrically more efficient manner than previous models. This paper prompted us to look at the data analysed by the authors and the present comment follows from our own analysis of these data. It shows that it is possible to achieve still greater parametric efficiency by following the Data-Based Mechanistic (DBM) approach to modelling nonlinear dynamic systems using a continuous-time State Dependent Parameter Transfer Function (SDPTF) model. The main modelling results are outlined in this comment but the full details of the analysis are available in an associated technical note [START_REF] Young | Efficiently parameterized models of the Silverbox nonlinear circuit[END_REF] 1 .

2 Re-examination of the [START_REF] Nöel | Grey-box state-space identification of nonlinear mechanical vibrations[END_REF] Model [START_REF] Nöel | Grey-box state-space identification of nonlinear mechanical vibrations[END_REF] prescribe the equation of motion for the Silverbox system on the basis that the circuit is intended to mimic the behaviour of a mechanical system and suggest the following equation,

M d 2 y(t) dt 2 +C v dy(t) dt + Ky(t) + c 1 y 2 (t) + c 2 y 3 (t) = p(t) (1)
that reflects this mechanical engineering heritage. For later reference, however, this equation can be written in the alternative 'reduced form':

d 2 x(t) dt 2 + a 1 dx(t) dt + k 1 x(t) + k 2 x 2 (t) + k 3 x 3 (t) = u(t); y(k) = x(k) + ξ (k) (2)
where

a 1 = C v /M, k 1 = K/M, k 2 = c 1 /M, k 3 = c 2 /M, u(t) = p(t)
and y(k) is the sampled measurement of x(t), with ξ (k) representing the model error and any noise on the measurement. One assumes that this differential equation is the initial hypothesis about the nature of the model and expects initially that the modelling will proceed on the basis of this equation. But this is not the case; rather the authors immediately move away from this standard SISO differential equation to a discrete-time state-space alternative, following a modelling approach they have described previously in the paper. It is reasonable ask, therefore, whether the parameterization of the resulting model is satisfactory in relation to the initially hypothesised model (2). Here, the term 'parameterization' is being used to mean the number and location of the parameters in the model structure, so that the term 'efficient parameterization' in the title of this comment means that the model is explained by as few, statistically well-defined, parameters as are necessary to explain the data well and meet the objectives of the modelling study.

The full details of the Nöel and Schouken's 13 parameter state space model are not specified in their paper but, on request, Dr. Nöel kindly supplied these. The model has the following form:

x(k + 1) = Ax(k) + Bu(k) + E x 2 (k) x 3 (k) y(k) = Cx(k) + Du(k) (3)
This was simulated in Simulink TM and used as a basis for nonlinear least squares optimization, using the Matlab TM routine lsqnonlin, based on the first 10000 samples from the data set but omitting the first 2500 samples to avoid the quite long-term initial condition effects. The resulting optimized parameters do not change very much from those supplied by Dr.

D = .002649 (4)
It is clear that this model performs very well in explaining the data. But is it efficiently parameterized in the above sense? One clue to answering this question is to consider the confidence bounds provided by the confint routine in Matlab TM based on the results from the lsqnonlin optimization. Unfortunately, although the specially designed input stimulus u(k) is clearly sufficient to ensure identifiability, the Jacobian returned by confint indicates conditioning problems and these bounds are extremely wide. This is hardly surprising because it is well known that linear and nonlinear state space models (see e.g. [START_REF] Ljung | System Identification. Theory for the User[END_REF][START_REF] Wigren | Recursive prediction error identification and scaling of non-linear state space models using a restricted black-box parameterization[END_REF]) are inherently over-parameterized unless specified in some canonical form (particularly if, as in [START_REF] Nöel | Grey-box state-space identification of nonlinear mechanical vibrations[END_REF], the optimization is initiated using a completely black box, nonlinear subspace method of model identification that does not yield a model in such a canonical form).

In order to both investigate the possibility of over-parameterization and compare the results from this type of model with those obtained later in section 3 using an alternative continuous-time transfer function model, it makes sense to develop and optimize a similar nonlinear state space model in differential equation form. This model explains the data to about the same level as the discrete-time model, with R2 T = 0.99998; and, as expected, the confidence bounds provided by the confint routine are again extremely wide, suggesting that the 13 parameters are not well defined statistically and that the model is overparameterized.

In order to solve this over-parameterization problem, the most obvious approach is to consider a canonical form for the continuous-time state space model where, in the linear part of the state equations, the second state is defined as the derivative of the first state. This not only reduces the number of parameters, it also provides a model where these parameters and the associated state variables have an immediate, more physical interpretation. The 8 optimized parameters in this case are as follows1 :

A = -0.01744 -0.03134 1.0 0.0 ; B = 1.0 0.03086 E = 0.2458 -3.8966 0.1236 -2.0637 ; C = -0.01631 0.03106 ;
(5) with D=0, i.e. no direct effect of the input on the output (note that the discrete-time and unconstrained continuous-time state space models have a very small values for this parameter). The explanation of the data is virtually the same as in the unconstrained model case, with R 2 T = 0.99998, even though the number of parameters is reduced almost 40%, from 13 to 8. Moreover, the confidence bounds obtained from the confint routine are now very tight around the estimates and the associated standard errors on the parameters are very small indeed, demonstrating how well they are defined in statistical terms. The model ( 5) is admirable in explaining the Silverbox data with only 8 parameters. In this section, however, it is shown that there are other State Dependent Parameter Transfer Function (SDPTF) model forms that are even more efficiently parameterized and, just as importantly in this example, have associated differential equation descriptions that relate directly to the originally hypothesised differential equation model form (2).

SDP modelling evolved many years ago [START_REF] Young | Adaptive pitch autostabilization of an air-surface missile[END_REF][START_REF] Mendel | A priori and a posteriori identification of time varying parameters[END_REF][START_REF] Young | A second generation adaptive autostabilization system for airborne vehicles[END_REF] and [START_REF] Priestley | State-dependent models: A general approach to non-linear time series analysis[END_REF], who first used the name. The more advanced SDP methods used in the the present technical note were developed in the 1990s (see e.g. [START_REF] Young | Stochastic, dynamic modelling and signal processing: time variable and state dependent parameter estimation[END_REF][START_REF] Young | The identification and estimation of nonlinear stochastic systems[END_REF], Young et al. 2001) and, since then, these have been applied successfully to a large number of practical systems, in diverse areas of study. The SDP modelling procedure consists of three main steps. First, the sdp routine in CAPTAIN exploits optimal fixed interval smoothing estimation to identify, in non-parametric (graphical) terms, the nonlinear model structure, as defined by the location and nature of the statistically significant SDP nonlinearities. This is then followed by the parameterization of the identified SDP nonlinearities, using whatever method is most appropriate, if possible one that is transparent and has a useful physical interpretation. Finally, the parameters in the parameterized model are optimized in a similar manner to those of the state space models discussed in the previous section.

The non-parametric estimation results for the present Silverbox example are reported fully in [START_REF] Young | Efficiently parameterized models of the Silverbox nonlinear circuit[END_REF]. The parameterized SDPTF model structure is identified from these non-parametric results and takes the following form:

x(t) = b 0 s + b 1 s 2 + a 1 s + a sd p u(t); a sd p = k 1 + k 2 x(t) + k 3 x 2 (t) (6)
or, in a differential equation form that can be linked directly to the initially hypothesised model (2),

d 2 x(t) dt 2 + a 1 dx(t) dt + k 1 x(t) + k 2 x 2 (t) + k 3 x 3 (t) = b 0 du(t) dt + b 1 u(t) (7)
From this, we see that the only difference is in the terms associated with the input variable (i.e. the numerator of the SDPTF model) and, in particular, the need for a du(t)/dt term.

For convenience, the optimization of the model was carried out using the Simulink model with a normalised sampling interval of unity. Also, in order to avoid the initial transient behaviour and the associated need to remove the first 2500 samples, the initial conditions I 1 and I 2 on the two integrators in the model were optimized simultaneously with the model parameters. The resulting estimates are given below with the estimated standard errors in parentheses: â1 = 0.01751(1.62 × 10 -6 ); b0 = -0.1684(0.00015) b 1 = 0.03111(2.49 × 10 -6 )); k1 = 0.03136(7.72 × 10 -7 ) k2 = -0.007884(9.17 × 10 -6 ); k3 = 0.1231(1.96 × 10 -5 ) Î1 = -0.06827(2.91 × 10 -5 ); Î2 = 0.03045(0.00037) (8) Note that the estimate of b0 = -0.1684 shows that the model has significant non-minimum phase characteristics. As this makes a quite large improvement to the explanatory power of the model, it appears to represent an important element in the system dynamics that, as far as we know, has not been recognised explicitly in previous Silverbox modelling studies. However, as J. P Nöel has pointed out to us (personal communication, 26th June, 2018), it is probably the reason why better estimation performance was obtained by [START_REF] Paduart | Identification of nonlinear systems using polynomial nonlinear state space models[END_REF] when they considered adding a multivariate polynomial in both the state and input variables, rather than a simpler description based on the states alone.

Finally, although the sampled residual error ξ (k) = y(k)x(k) in the model ( 7) is very small, it has significant serial correlation and is also correlated with the sampled input variable u(k). If ξ (k) is investigated further, the Akaike Information Criterion (AIC) identifies a very high AR(88) model that characterises ξ (k) very well, with serially uncorrelated, white residuals e(k) (one-step-ahead prediction errors) and very small residual variance. On the other hand, e(k) is still correlated with the sampled input variable u(k). This suggests that there is probably an additional, extremely low level of nonlinearity present in the data that has not been captured by the SDP nonlinear model (or, it would appear, by any previous models of the Silverbox). This is supported to some degree by the initial non-parametric SDP analysis (see the full details in Young 2018) which identifies some evidence of similar nonlinear effects in the first SDPTF denominator parameter a 1 (see next sub-section 3.1).

It might be argued theoretically that, because e(k) is still correlated with the sampled input variable u(k), the covariance matrix returned by the confint routine is not a valid representation of the uncertainty in the estimated parameters and so the standard error bounds in (8) are not strictly accurate estimates. Even if this argument is accepted, however, these bounds illustrate the relative uncertainties in the parameters and there is no doubt at all that they are very small indeed.

3.1 Is there justification for a more complex model?

Given the nature of the residual error in the 6 parameter SDP model, it makes sense to investigate whether the introduction of state-dependency into a 1 results in any significant improvement in the explanatory ability of the resulting parametric model (providing, of course, that there is no sign of overparameterization that might question any such improvement). The full details of this analysis are given in [START_REF] Young | Efficiently parameterized models of the Silverbox nonlinear circuit[END_REF], so it will suffice here to report that the optimized parameters in the resulting 8 parameter model are very well defined, with no signs of over-parameterization, and there is a small improvement in the variance of the model error when compared with the 6 parameter model ( 7) and the two state space models (3) and ( 5). Once again, however, this residual series ξ (k), as well as the white residual e(k) of an associated, AIC identified, AR(87) noise model, are still correlated with the input variable u(k).

Disappointingly, therefore, we cannot claim that the enlargement of the model has purged much additional nonlinearity from the residual series, although the small improvement in the explanatory ability arising from the additional two parameters means that the resulting 8 parameter model is the best of all the models considered here in this regard.

It would be possible to continue to look for other SDP components in the model in order to try to explain the remaining, extremely small level of unexplained nonlinearity in the data. However, it seems reasonable to conclude that we have reached a stage of diminishing returns. To paraphrase Karl [START_REF] Popper | The Logic of Scientific Discovery[END_REF], we would contend that these DBM SDPTF models are conditionally validated and can be considered satisfactory for the most modelling objectives until they may be falsified by further experiment and analysis.

The physical nature of the SDPTF model

There are several advantages to the SDPTF model ( 7). For instance, although it exploits 'black-box methodology, it does this using a DBM modelling approach, where the objective is to obtain a model that can be interpreted in the mechanistic terms that are most appropriate to the nature of the dynamic system. In this sense, therefore, the finally estimated model is the equivalent of a 'white-box' model because the optimized differential equation ( 7) relates directly to the original hypothesised model (1) and can be interpreted in these terms. Importantly, however, this model has been identified by a process direct inference from the experimental data without any prior assumptions about the model, other than it is in the form of a differential equation. This approach has been referred to as Hypothetico-Inductive Data-Based Mechanistic (HI-DBM) modelling (see e.g. Young 2013). One interesting and useful interpretation of the SDPTF model is obtained by considering the statedependent effect on specified physical properties of the system. For example, the natural frequency ω n , damping ratio ζ and steady state gain G can be computed as for a linear system but defined by the SDPs and so dependent on the output x(t). This is illustrated in Fig. 1, which shows plots of the resulting state dependent characteristics ω n {x(t)}, ζ {x(t)} and G{x(t)}, based on the actual sampling interval of 1/2441 secs. The value of these properties at any value of x(t) effectively provides a 'snapshot' of the system in these terms that describes the small perturbation behaviour of the system at this output level. Also shown by the red dash-dot lines are the underlying values of these properties defined by the linear part of the model. Extracting this kind of information would not be nearly so easy in the case of a discrete-time state space model and it would be even more difficult in the case of most full black-box models.

Conclusions

Different modelling objectives often demand different types of model, so there is rarely only one model of a dynamic system. This is certainly the case with the Silverbox system, where [START_REF] Marconato | Identification of the silverbox benchmark using nonlinear state-space models[END_REF] list and discuss 8 models of different types ranging from two 'white box' models with 5 and 10 parameters, respectively, to 'grey-box' and 'black-box' models with between 12 and in excess of 700 parameters! Given that the silverbox is an electronic circuit constructed specially to mimic the behaviour of a single input, single output mechanical system, however, we assume that the most desirable model should be a nonlinear differential equation that can be related directly to the mechanical system model (2), which represents the original modelling hypothesis.

Such a mechanistically meaningful model can be identified in various ways. For instance, because the Silverbox circuit was developed in part to simulate a mechanical system, an identification methodology developed specially for such systems could be used. A companion technical note [START_REF] Janot | On the identification of the silverbox system in a electromechanical context[END_REF] uses this approach to model the Silverbox system, based on the 'inverse dynamic model' (IDM) identification methodology developed in [START_REF] Janot | Identification and control of electro-mechanical systems using state-dependent parameter estimation[END_REF]. The present comment has outlined an alternative databased mechanistic modelling approach to the identification of a 'direct dynamic model' (DDM), where the specific objective is to obtain a state-dependent parameter differential equation that can be interpreted directly in terms of the originally hypothesised differential equation model form (2).

The resulting SDPTF models are not only efficiently parameterized and simple to understand, they are also interpretable directly in terms of this original model, as required. We believe that these models are, therefore, not only more consistent with the original aims behind the construction of the Silverbox circuit system, but are also in a form that is more immediately understandable and useful to many practicing engineers working on electro-mechanical systems than the discrete-time, state space model identified by [START_REF] Nöel | Grey-box state-space identification of nonlinear mechanical vibrations[END_REF]. Of course, this does not negate the more general utility of such an alternative model and the powerful modelling methodology that underlies its identification.

3

  State-Dependent Parameter Transfer Function (SDPTF) Modelling

This can be downloaded from the 'Publication Downloads' section of http://captaintoolbox.co.uk/Captain_Toolbox. html/Captain_Toolbox.html: PCY Technical Report

TN5

Taylor & Francis and I.T. Consultant

Note that the parameter estimates shown here are rounded to four significant figures and this degrades the R

T .

Note that the b

= 0.03086 is not optimized because it only controls the gain of the system and can be set arbitrarily to any value, here to a value that relates to the transfer function modelling described in section