Progress in Artificial Intelligence (2021) 10:321–332 https://doi.org/10.1007/s13748-021-00242-6 REGULAR PAPER The space of models in machine learning: using Markov chains to model transitions Vicenç Torra1,2,3 · Mariam Taha4 · Guillermo Navarro-Arribas5 Received: 4 April 2020 / Accepted: 26 March 2021 / Published online: 12 April 2021 © The Author(s) 2021 Abstract Machine and statistical learning is about constructing models from data. Data is usually understood as a set of records, a database. Nevertheless, databases are not static but change over time. We can understand this as follows: there is a space of possible databases and a database during its lifetime transits this space. Therefore, we may consider transitions between databases, and the database space. NoSQL databases also fit with this representation. In addition, when we learn models from databases, we can also consider the space of models. Naturally, there are relationships between the space of data and the space of models. Any transition in the space of data may correspond to a transition in the space of models. We argue that a better understanding of the space of data and the space of models, as well as the relationships between these two spaces is basic for machine and statistical learning. The relationship between these two spaces can be exploited in several contexts as, e.g., in model selection and data privacy. We consider that this relationship between spaces is also fundamental to understand generalization and overfitting. In this paper, we develop these ideas. Then, we consider a distance on the space of models based on a distance on the space of data. More particularly, we consider distance distribution functions and probabilistic metric spaces on the space of data and the space of models. Our modelization of changes in databases is based on Markov chains and transition matrices. This modelization is used in the definition of distances. We provide examples of our definitions. Keywords Machine and statistical learning models · Space of data · Space of models · Hypothesis space · Probabilistic metric spaces 1 Introduction models and we want to find the one that better represents our data. Here, better can correspond to the one with best Machine and statistical learning can be seen as a search prob- accuracy. Different definitions of better as well as different lem. That is, we have a state space corresponding to possible search strategies to find a good solution can be considered. From this perspective, we consider operators that permit to B Vicenç Torra transform one model into another one. In this case, a trans- vtorra@ieee.org formation is usually to improve accuracy (i.e., better = better Mariam Taha accuracy). Examples of these transformations include oper- mariamt@cs.umu.se ators that expand a node in a decision tree, update weights in Guillermo Navarro-Arribas a deep learning model, or operators that mutate a solution in guillermo.navarro@uab.cat genetic algorithms. 1 In this paper, we consider a different perspective. We con- Department Computing Science, Umeå University, Umeå, Sweden sider the space of models taking into account the space of 2 data that have generated these models. Hamilton Institute, Maynooth University, Maynooth, Ireland When we learn a model from an actual database, the 3 School of Informatics, University of Skövde, Skövde, Sweden database is just a database from the space of data. When 4 Department Computing Science, Umeå University, Umeå, databases change, we are traversing the space of data through Sweden a particular path. Different databases in this particular path 5 Dept. Information and Communications Engineering – can lead to different machine learning models. CYBERCAT, Universitat Autònoma de Barcelona, Bellaterra, Catalonia, Spain 123 322 Progress in Artificial Intelligence (2021) 10:321–332 We claim that it is necessary to study how the space of data tribution functions. That is, distance between pairs of objects interacts with the space of models. More particularly, that are not a real number but a distribution on these numbers. any decision on the space of models has to take into account This approach permits us to define a distance between pairs relationships between the space of data that generate these of models taking into account the distance between the set models. of databases that have generated these models. We consider that this perspective is of great interest in the In this paper, we propose the use of Markov chains and following areas. transition matrices to represent, respectively, sequences of changes in databases and the probability of changes taking – In model selection for statistical and machine learning In place. This representation permits the definition of proba- this area the goal is to select models that better general- bilistic metric spaces on the space of data. We use them later ize data and avoid overfitting. The study of the interaction to define distance distribution functions for the space of mod- between the space of models and the space of data can els in terms of the databases that have generated them. This increase our understanding on the models themselves, is a much simpler approach than the one introduced in [14]. and on the methods that generate the models (compar- The structure of this paper is as follows. In Sect. 2, we ing their respective mappings between the two spaces). introduce the definitions that are needed later in the paper. In particular, we think it is fundamental to understand In particular, we introduce Markov chains and probabilistic the concepts of generalization and overfitting. This also metric spaces. In Sect. 3, we introduce two definitions of met- relates to the effect of outliers and influential points in ric spaces for databases based on Markov chains and prove learning. It is important to understand generalization and some results. In Sect. 4, we introduce definitions for distance overfitting in terms of the relationship between the space distribution functions for models based on the probabilistic of models and the space of data. metric spaces introduced in Sect. 3. We provide some exam- – In privacy preserving data mining and machine learning ples of how these distances can be actually computed. The The need to study the relationship between the two spaces paper finishes with a discussion and lines for future work. was first proposed in [14] in the context of integral privacy [10,11]. In short, a model is integrally private if it can be generated by a large number of databases, and these 2 Preliminaries databases are sufficiently different (e.g., they do not share records). This is to avoid some type of privacy attacks on In this section, we review some concepts that are needed machine learning models as, e.g., membership attacks later. We begin with Markov chains and transition matrices. [12]. We also discuss probabilistic metric spaces and distances for sets of elements. We are interested in knowing when two models are similar, where similar does not correspond to a syntactic similarity of the models (e.g., if two decision trees have the same struc- 2.1 Markov chains ture), nor on a semantic similarity of the models (e.g., if two models have the same accuracy). We are interested in In this paper, we will use Markov transition matrices and knowing when models are similar because they have been Markov chains to model the space of databases. Because of generated from similar databases. that, we will review in this section a few concepts that we There are naturally different ways of understanding the need later. See e.g., [7] for details. similarity between databases. For example, one database We consider a state space S finite or enumerable. We will may be similar because it is a noisy version of the other use (e.g., an anonymized version of the original database). Here, we focus on changes in databases due to the natural pro- S = {D B1 , D B2 , D B3 , . . . } cesses a database suffers in a company. That is, we consider a database that is updated, as time passes, by means of e.g., adding and removing records. These types of changes are to denote the space of possible databases. Thus, in our case, usual when databases are in production. In addition, these a finite although extremely huge set. types of changes are also relevant in the framework of data We will consider chains defined on the state space S. That privacy [13] with the right to be forgotten and the right to is, (Z n )n∈N taking values in S, i.e., Z n ∈ S. More particularly, amend (under the GDPR). we consider Markov chains. This corresponds to chains in In [14], the authors proposed the use of probabilistic met- which the probability distribution on Z n+1 depends only on ric spaces [9] for modeling the similarity between models. the process Z n at time n and not on previous values of Z . In Informally, these spaces are defined in terms of distance dis- other words, there is no memory on previous transitions. 123 Progress in Artificial Intelligence (2021) 10:321–332 323 Formally, function d is required to satisfy the following properties: (i) positiveness, (ii) symmetry, and (iii) triangle inequality (formally, d(a, b) ≤ d(a, c) + d(c, b) for any a, b, c in S). P(Z n+1 = D B j |Z n = D Bi , Z n−1 = D Bn−1 , . . . , Z 0 = D B0 ) Also, it is usual to require that if a and b are different then the = P(Z n+1 = D B j |Z n = D Bi ). distance should be strictly positive. Special names are given when some of these conditions fail. For example, when the We consider time-homogeneous Markov chains. That is, distance does not satisfy the symmetry condition, we say the probability of transition does not depend on time. This is that (S, d) is a quasimetric space; and when the distance expressed mathematically as does not satisfy the triangle inequality, we say that (S, d) is a semimetric space. Probabilistic metric spaces are a generalization of met- P(Z n+1 = D B j |Z n = D Bi ) = P(Z m+1 = D B j |Z m = D Bi ) ric spaces. As stated above, we can informally consider that we replace the function d(a, b) by a distribution function for any n, m. F(a, b) defined on R. These functions are known as distance As the probability does not depend on n, we will not use distribution functions. Their definition follows. this index unless required. Then, we will use Pi j to denote P(Z n+1 = D B j |Z n = D Bi ) (for any n). For the sake of Definition 1 [9] A nondecreasing function F defined on R+ simplicity, we will also use P(Z n+1 = j|Z n = i) when no that satisfies (i) F(0) = 0; (ii) F(∞) = 1, and (iii) that is confusion arises. left continuous on (0, ∞) is a distance distribution function. From the explanation above, it is clear that transition + denotes the set of all distance distribution functions. depends only on the probabilities Pi j . These probabilities for all states i and j define a matrix. It is known as transition The following interpretation is usual for these functions: matrix. Formally, a transition matrix P is a S × S matrix with F(x) corresponds to the probability that the distance is less values in [0, 1] such that (for any n) than or equal to x. Note that this definition is a generalization of a distance.   In particular, we use a to denote the distance distribu- Pi j = P(Z n+1 = D B j |Z n = D Bi ) = 1. tion function that represents the classical distance a. This a D B j ∈S D B j ∈S function is just a step function at a. Its definition follows. We can prove that given a probability distribution π on Definition 2 [9] For any a in R, we define a as the function S for time 0, say probabilities P(Z 0 = i) for i ∈ S, the given by probability distribution for time 1, say probabilities P(Z 1 = j) for j ∈ S, can be expressed in matrix notation as π P.  0, −∞ ≤ x ≤ a Let us denote by P n the transition matrix defined by Pinj = a (x) = 1, a < x ≤ ∞. P(Z m+n = D B j |Z m = D Bi ). Naturally, the computation of Pinj does not depend on m. We can prove that In order to define probabilistic metric spaces we need to  consider the set of distance distribution functions, and we Pirj+t = Pikr Pkt j , need to define a condition on triples of functions in this set k∈S analogous to the triangle equality in metric spaces. This con- dition given below is based on triangle functions. Let us start or in matrix form P r +t = P r P t . This is called the Chapman– defining the triangle functions. Kolmogorov equation. Definition 3 [9] Let + be defined as above, then a binary 2.2 Probabilistic metric spaces operation on + is a triangle function if it is commutative, associative, and nondecreasing in each place, and has 0 as Probabilistic metric spaces [9] are a generalization of metric the identity. spaces in which a distance distribution function replaces the Using triangle functions we can establish the definition of role of distance functions. That is, instead of considering probabilistic metric spaces. d(a, b) as a real number, it is a distribution function on the real numbers. Definition 4 [9] Let (S, F , τ ) be a triple where S is a Recall that metric spaces are defined in terms of sets (a nonempty set, F is a function from S × S into + , τ is non-empty set) and a distance or metric for pairs of elements a triangle function; then (S, F, τ ) is a probabilistic metric in this set. Formally, we denote a metric space by (S, d), space if the following conditions are satisfied for all p, q, where S is the set and d for a, b ∈ S the distance. The and r in S: 123 324 Progress in Artificial Intelligence (2021) 10:321–332 – (i) F( p, p) = 0 For illustration, we consider only addition and deletion of – (ii) F( p, q) = 0 if p = q records from a database, and that only one addition and one – (iii) F( p, q) = F(q, p) deletion is allowed at a time. We also assume that we have – (iv) F( p, r ) ≥ τ (F( p, q), F(q, r )). access to the whole population or that we know the size of the whole population. Then, we can define a transition matrix As usual in this field, we will use F pq instead of F( p, q). based on assigning a probability of having a deletion ( pd ) This permits to express the value of the distance distribution and a probability of having an addition ( pa ). Naturally, these function at x by means of the expression: F pq (x). probabilities add less than or equal to one ( pd + pa ≤ 1). Definition 5 Let pd and pa be the probability of deleting 2.3 Metrics for sets of objects or adding a record. Then, given an arbitrary database D Bi , where D Bi is a subset of the whole population P (with |P| In order to define the distance between pairs of models, we denoting the size of this population), we define the probability will consider the set of databases that have generated these of transition from D Bi to any D B j as follows (here, pi j models. This permits to define the distance in terms of the stands for P(Z n+1 = D B j |Z n = D Bi ) as above): distance between these sets. Let us first consider the classical setting with a standard distance. ⎧ Let G be an algorithm that given a database generates a ⎪ ⎪ pd |D1Bi | if c1 &c3 ⎪ ⎪ model, then, the set of generators of a model m is defined by ⎪ 1 ⎨ pa |P|−|D Bi | if c2 &c3 Gen m = {D B|G(D B) = m}. In this case, given two models pi j = 1 if (c1 or c2 )&c4 (1) ⎪ ⎪ |P| m 1 and m 2 we define the distance between m 1 and m 2 in ⎪ ⎪ 1 − ( pd + pa ) if c5 &c3 ⎪ ⎩ terms of Gen m 1 and Gen m 2 . In order to do so, we need to 0 otherwise extend the distance for databases to sets of databases. Nevertheless, given a metric space (S, d), its extension where c1 − c5 are the following conditions: to a set of elements of S is not trivial. This is so because although several distances have been defined on sets, not all – c1 : D B j ⊂ D Bi and |D Bi \ D B j | = 1 of them satisfy the triangle inequality. This implies that they – c2 : D Bi ⊂ D B j and |D B j \ D Bi | = 1 are not valid to define a metric. – c3 : |D Bi | ∈/ {0, |P|} In [14], different types of functions are considered. The – c4 : |D Bi | ∈ {0, |P|} discussion includes the Hausdorff distance and the sum of – c5 : D Bi = D B j minimum distance (which do not satisfy the triangle inequal- ity) and the definition by Eiter and Mannila [3] that is indeed Here, c4 means that the database D Bi is either empty or no a valid definition of a distance and leads to a metric space. further records can be added to it, and c3 means that D Bi is Nevertheless, this is a very complex function to compute. not one of such extreme databases. Lemma 1 The above  definition leads to a valid transition matrix. That is, j pi j = 1 for all j. 3 Probabilistic metric spaces from Markov chains Proof Observe that given D Bi , pi j is not zero for databases D B j = D Bi that have either one additional record more (i.e., We consider that transition matrices are a suitable approach D Bi ⊂ D B j and |D B j \ D Bi | = 1) or less (i.e., D B j ⊂ to model changes on databases. In other words, we consider D Bi and |D Bi \ D B j | = 1) than D Bi . Then, in the general that for a given database there is some probability that this case, D Bi can lead to any of the |D Bi | databases that has database is transformed by means of a modification to another just one record less, or D Bi can lead to any of the |P| − database. For the sake of simplicity, we consider in this work |D Bi | databases that have exactly one additional record. So, time-homogeneous Markov chains. That is, as explained in according to Equation 1, the probability of deleting a record Sect. 2 that changes on a database only depend on what is is pd and the probability of adding a record is pa . As the currently available in the database and that it does not depend probability of D Bi not being modified is 1 − ( pd + pa ), it is on its previous values (history of the database). This assump- proved that the definition leads to a row adding to one. Then, tion can be considered simplistic, as e.g., the probability of we have conditions for the extreme cases in which D Bi is adding a record may depend on how many times has been empty or D Bi includes all records. In this case, there are |P| already present in the database and has been removed. Nev- neighboring databases with a probability of transition equal 1 ertheless, we consider that this assumption is acceptable for to |P| . Therefore, this row also adds to one. Therefore, the this initial study. matrix is a transition matrix.  123 Progress in Artificial Intelligence (2021) 10:321–332 325 In this section, we introduce two definitions of probabilis- databases D B1 and D B2 for the value t is α (i.e., P12 (t) = α) tic metric spaces for databases based on transition matrices if the probability of reaching D B2 from D B1 in less than t and Markov chains. transitions is α. The first definition considers the distance between two We can prove from this definition that Fi j (t1 + t2 ) ≥ databases in terms of the probability of being transformed Fik (t1 )Fk j (t2 ). From this property, we can prove the follow- into the second one. This approach defines the probabilis- ing theorem. See [5] for a proof. Observe that the formulation tic metric space solely based on the transition matrices. We of the following theorem in [5] uses stationary to refer to give below both symmetric and asymmetric definitions for time-homogeneous, using the notation in [2]. the distance distribution functions. See Definition 6. We call this type of space, visited database-based probabilistic metric Theorem 1 Let S, P, (Z n )n∈N and Fi j (t) be defined as in space (VD-PMS). Definition 6. Let F be the mapping from S×S into the space of The second definition considers the distance between two cumulative distribution functions defined by F(i, j) = Fi j . databases in terms of their evolution. That is, given two Then, F satisfies properties (i) and (iii) in Definition 1, and databases, will they be similar as time passes? In order to properties (i), (ii), and (iv) in Definition 4. give a formal definition, we need to consider how databases It is a non-symmetric distance distribution function satis- are being modified, and what similarity means for databases. fying (iv) under the t-norm T = Pr od (i.e., T (a, b) = ab). With respect to the later, the model presumes the existence The hitting time of a state D B j starting from state D Bi is of a standard distance function (a metric space, in fact) on the random variable defined by the space of databases. We call this type of space, database distance-based probabilistic metric space (DD-PMS). See Ti j = min{n ≥ 0 : X n = D B j } Definition 7. We consider that both types of definitions are relevant for with the minimum of the empty set defined as ∞. The prob- statistical and machine learning and, in particular, for privacy ability of hitting state D B j is defined by preserving data mining. We are interested in models that are valid today but that will be also valid in the future. So, the j h i = P(Ti j < ∞). first definition states that two models are similar if we can transit from one to the other and the second definition states Not all transition matrices lead to Markov chains with that two models are similar if they have a similar future (a probabilities of hitting a state equal to 1. If this is the case, similar machine learning model in the future). then, the Definition above will lead to a probabilistic metric space with a non-symmetric function. We establish this in 3.1 Visited database-based probabilistic metric the next theorem. spaces Theorem 2 Let S, P, (Z n )n∈N and Fi j (t) be defined as in We consider a definition of probabilistic metric spaces for Definition 6. Then, the pair (S, F) is a probabilistic metric databases based on [5]. The distance between two databases space with a non-symmetric distance function under the t- depends on the probability that one database becomes the j norm T = Pr od when h i = 1 for all i, j. second one after a sequence of changes (there is a chain between the first to the second) within a given time frame. Definition 6 gives a distance that is not necessarily sym- The definition is based on transition matrices P on the metric. Note that accessing j from i at time t does not mean space of databases. The definition follows. that it is possible to access i from j in the same time t. It is possible to define a probabilistic metric space with a Definition 6 Let S be a state space representing the space of symmetric distance function using Fi j = Fi j F ji or Fi j = databases, let P be the transition matrix for S that defines a 0.5(Fi j + F ji ). The first definition is a probabilistic metric time-homogeneous Markov chain (Z n )n∈N . Then, given two space satisfying the Menger inequality with T = Pr od and states i and j in S we define the second one satisfies the Menger inequality with T = Tm (i.e., Tm (a, b) = max(a + b − 1, 0)). Fi j (t) = P[exists a time s < t such that Z s = j|Z 0 = i]. 3.2 Computation and example Formally, let f isj denote the probability that with Z 0 = i (i.e., starting the chain from state i), the first time we visit  Definitions above use f isj , that as explained above, denotes state j is exactly at time s. Then, Fi j (t) = ts=1 f isj . the probability that with Z 0 = i the first time we visit state From the point of view of the space of databases, the j is exactly at time s when we start at Z 0 = i. For a given definition above establishes that the distance between two transition matrix P, we can compute f isj as follows. If s = 1, 123 326 Progress in Artificial Intelligence (2021) 10:321–332 the elements we need to delete to transit from D B1 to D B2 . Then, the shortest chain from D B1 to D B2 when we only consider addition and deletion of records has length t0 = |D B1 \ D B2 | + |D B2 \ D B1 | = ta + td and, therefore, F12 (t) = 0 for all t < t0 . Let us consider an arbitrary order for the ta elements we add, and an arbitrary order for the td elements we remove. Fig. 1 F13 for Example 1 according to Definition 6 Let i in {1, . . . , ta } represent the addition of the ith element according to this order and i in {ta + 1, . . . , ta + td } the f isj = Pi j . If s > 1 then we perform the following steps: (i) removal of the (i − ta )th element according to this order. Using this interpretation, it is clear that any permutation of define P̄ as P and assigning P̄r s = 0 for all pairs ( j, t) {1, . . . , ta + td } represents a valid chain with only additions and (t, j) with j ∈ S, (ii) compute P̄ s−1 , (iii) compute and deletions and with no cycles from D B1 to D B2 . So, there f i j = k∈S P̄iks−1 Pk j . Finally, (iv) using the s expression in are (ta + td )! valid chains with no cycles. Definition 6 we compute Fi j (t) as Fi j (t) = s≤t f isj . We can also prove a lemma similar to Lemma 2 when in The rationale of this definition is that in order to reach j addition to addition and deletion we allow transitions that do from i in exactly s steps (with s > 1) we need to reach any not change the database. Shortest chains will of course still other state k = j in exactly s − 1 steps without reaching j at have length ta + td , and from this it also follows: F12 (t) = 0 any moment s < s, and then move from k to j. Probabilities for all t < t0 . of reaching k = j from i in s − 1 steps without hitting j Let C12 t denote all valid chains from D B to D B with 1 2 will be computed using P̄. This computation corresponds to ta +td length t. Then, C12 will represent all shortest chains. compute P̄ s−1 as noted above. ta +td We give an example of this computation with a very small Therefore, |C12 | = (ta + td )!. It is also clear that C12 t =∅ database. The space is built from a set of 5 records. In this for t < ta + td . way, we can consider the whole database space that has a Let use denote a chain c ∈ C t by c0 , c1 , . . . , ct . Here ci size of 25 databases. will correspond to a database D Bi . Then, the probability of transiting from D B0 to D Bt through the chain c is naturally Example 1 Let D B be the set of all databases that can be generated from 5 records. That is, D B corresponds to the Pc = Pcr −1 ,cr . (2) power set of these 5 records. Let P be the transition matrix of cr ∈c D B defined according to Definition 5 using pa = pd = 0.5. Then, we can compute F13 according to Definition 6. F13 is Lemma 3 Using the notation in Lemma 2 and Pc as in Equa- the distance between databases D B1 = {a} and D B3 = {c}. tion 2, we have that when only addition and deletion are Figure 1 represents this computation. allowed, or when addition, deletion and transition without change are allowed, it holds (for ta and tb as above) 3.3 Results on the approximation of distance ta +td  distribution functions F12 (ta + td ) = f 12 = Pc ta +td c∈C12 Computation of the distance introduced in Definition 6 is  = Pcr −1 ,cr . (3) costly. Because of that we are interested in the approximation a t +td cr ∈c of this distance. We can prove the following results in relation c∈C12 to Definition 6. We can also prove that when only addition and deletions Lemma 2 Let D B1 and D B2 be two databases. Let us con- are allowed, C12 t = ∅ for any t = t + t + 1 + 2k for any a d sider the sets D B1 ∩ D B2 , D B1 \ D B2 , and D B2 \ D B1 . Let k, i.e., given a shortest chain, we can only enlarge this chain ta = |D B2 \ D B1 | be the number of elements we need to add both adding and removing k records. So, in this case, for all ta +td +2k+1 to transit from D B1 to D B2 , and let td = |D B1 \ D B2 | be k it holds f 12 = 0. 123 Progress in Artificial Intelligence (2021) 10:321–332 327 When addition, deletion and also non modification are distribution function for all D Bi ∈ S. Then, allowed as transitions between databases, we have that for t = ta +td +1+2k (for any k), the chains in C12 t are the ones in F(D Bi , D B j ) ≥ T (FD Bi ,D Ba (x), FD Ba ,D B j (x)) t−1 C12 adding a transition corresponding to non-modification (say tnm ). Let p∅ denote the probability of a non-modification is a lower bound of F D Bi ,D B j . (this corresponds to the value 1 − ( pd + pa ) in Equation 1). Let c ∈ C t be one of such chains with elements c0 , c1 , . . . , ct . Proof If T is a t-norm, then the triangle function τT generated Then, we can insert this tnm transition between any pair of by T is elements of the chain (but not at the end of the chain as we are considering that is exactly at time s that we reach the τT (F, G)(x) = T (F(x), G(x)) goal state). This means that there are t options. Given P(c), the probability of the chain c ∈ C t , the probability of any of for distance distribution functions F and G. Then, as these chains is p∅ · p(c). So, as we have t new chains for a (S, F, τT ) is a probabilistic metric space on the space of given chain c, the probability for this set of chains (say c̃) is databases, we know that for all p, q, and r it holds that p(c̃) = t p∅ p(c). Then, considering all c̃ generated from all c ∈ C t , we have that for t = ta + td + 1 + 2k F( p, r ) ≥ τT (F( p, q), F(q, r ))   P(C12t )= p(c̃) = t p∅ p(c) c∈C12 t−1 c∈C12 t−1 and, therefore, in particular for p = D Bi , q = D Ba and  r = D B j we have that t−1 = t p∅ p(c) = t p∅ P(C12 ). c∈C12 t−1 F(D Bi , D B j ) ≥ τT (F(D Bi , D Ba ), F(D Ba , D B j )) Using Expression 3, it is easy to prove the following lemma. = T (F(D Bi , D Ba ), F(D Ba , D B j )).  Lemma 4 Let D Bi and D B j be two arbitrary databases, and let R = {c}c be a set of random valid chains c ∈ R from D Bi to D B j with different lengths. Then, 3.4 Database distance-based probabilistic metric space  f isj ≥ Pc We consider an alternative way to define probabilistic metric c:|c|=s+1 spaces in which in addition to a transition matrix we use a and distance on the state space. The definition is based on [5].  Fi j (t) ≥ Pc . Definition 7 Let S be the database space, let P be the tran- c:|c|≤t+1 sition matrix for S that defines a time-homogeneous Markov chain (Z n )n∈N . Let d : S × S → R+ be a distance function This result implies that the consideration of random valid on S. Then, for any given time t ≥ 0, we define the function chains give lower bounds for Fi j (t). Therefore, any deci- Fitj (x) as follows: sion based on a threshold th on a given t (i.e., Fi j (t) ≥ th) valid for a set R will be also valid if all the set of chains is Fitj (x) = Pr [d(i, j) < x at time t] considered. ⎛ ⎞ The links between triangle functions and t-norms (see e.g.,   [1], and Def. 7.1.3 and Section 7.1 in [9]) permit us to estab- = Pikt ⎝ t ⎠ P j . lish the following lemma. This lemma establishes another k∈S :d(,k)