1.5.1An outline of relational learning

Relational learning is an important paradigm in the field of machine learning. Its early work can be traced back to the famous Winston program of 1970, which could learn concepts such as arches. This program uses the semantic web as a descriptive language. It takes the arches with their components and properties and considers the description of the nature of properties as a node of the semantic network. In the same year, Codd published a landmark paper on “A Relational Model of Data for Large Shared Data Banks”, which was a prelude to the idea of relational databases. This paper is cited in many applications of relational learning, as it enables data with complex internal relations to be concisely expressed.

As we know, early studies on relational learning focus on inductive logic programming (ILP) [38, 39]. Although the logical representations that are presented in Baner’s “A Language for the Description of Concepts” and in Michalski’s AQ algorithm are first applied to learning problems, the foundation of this work is the first-order predicate formula presented by Plotkin in the 1970s, which laid the theoretical foundation for the development of ILP. The thrust of Plotkin’s work is to use the “special to general” approach to obtain a conclusion; this is strictly limited in practice, as a generalization of the smallest general conclusion is not finite. Thus, Shapiro used the general to special method to research the induction problem on the Horn clause set and proposed the MIS learning system in 1983. His work clarified the relationship between the logical program and inductive learning.

Early research on ILP focuses mainly on relationship rule induction, i.e. first-order logic concept learning and logic program composition. Representative systems include CIGOL (Muggleton, 1988) [54], FOIL (Quinlan, 1990) [55], GOLEM (Muggleton, 1990) [56], and LINUS (Lavarac, Dzeroski, and Grobelnik, 1991) [57]. In recent years, the research scope of ILP has been expanded to almost all learning tasks, such as classification, regression, clustering, and correlation analysis, and has generated relational classification rules, relational regression trees, and relational learning based on distance and relationship-related rules. Representative systems include PROLOG (Muggleton, 1995) [58] and ALEPH (Srinivasan, 2000) [59]. Later, the characteristics of statistical learning theory and gradual research on Statistical Relational Learning (SRL) led to many relational learning methods based on SRL, such as SRL based on Bayesian networks, SRL based on Markov networks, SRL based on hidden Markov models, and SRL based on random grammar (Popescul, Ungar, Lawrence, & Pennock, 2003) [40, 41].

(1)SRL based on Bayesian networks

Ng and Subrahmanian proposed the first framework for Probabilistic Logic Programs (PLPs) [42] in 1992. This framework enabled the description of probabilistic information within the fixed-point semantics of PLP, which is a valuable tool for both probabilistic information and common sense reasoning. In 1997, Ngo and Haddawy combined the logic with Bayesian networks by defining probabilities based on first-order logic or relational interpretation. Their work enriched the PLP content. In 1996, Debabrata and Sumit Sarkar proposed the Probabilistic Relational Model (PRM) [43], which deals with uncertain information. They systematically described the theory of probabilistic databases and defined a series of concepts such as super keys, primary keys, candidate keys, probabilistic patterns, probabilistic relations, and probability relational databases. They also defined a whole train of operations such as projection, selection, difference, and renaming, and discussed how to realize probabilistic databases and the NULL problem. Their work also converted the partial probability distribution to the interval estimation and point estimation. PRM extended the standard Bayesian network using an entity relationship model as a basic representation framework. Today, PRM has successfully solved many problems in relational clustering, hypertext classification, and so on. In 2000, Kersting and De Raedt developed Bayesian Logic Programs (BLPs) [44] by combining logic programs with Bayesian networks. BLPs not only handle Boolean variables but also take continuous-valued variables. They can solve a number of instances of clauses that have the same head using a simplified form of the combination of rules.

(2)SRL based on Markov networks

In 2002, Taskar, Abbeel, and Koller proposed the Relational Markov Network (RMN) [45] by introducing the relationship between entities into the Markov network. RMN extended the Markov network to relational databases and has been used to classify relational data. RMN defined the groups and potential functions between attributes of related entities at the template level, thus giving an arbitrary set of examples a distribution. In 2004, Richardson and Domingos proposed a Markov logic network (MLN) [46], which is a closed Markov network generated by a first-order logic knowledge database with a weighted value as a template. The advantage of MLN is that it introduced domain knowledge into Markov networks while providing a simple description language for large-scale networks. Additionally, MLN increased the uncertainty processing capability for first-order logic and served as a unified framework for many SRL tasks.

(3)RSL based on hidden Markov models

In 2002, Anderson and Domingos proposed a Relational Markov Model (RMM) [47] by introducing relations (logic) into Markov models. RMM allows state variable values to be of multiple types and uses one predicate or relationship to represent the same type of states. Thus, it overcomes the shortcoming of state variables whereby the Markov model can have only one variable. In 2003, Kersting proposed a logic hidden Markov model (LOHMM) [48] by introducing first-order logic into the Markov model. The differences from conventional Markov models are that there are two variables for the state and observation and the parameters have occurrence probabilities for each observation in addition to the transition probabilities.

(4)SRL based on random grammar

SRL [49] was proposed by Muggleton in 1996 as an extension of SLP by attaching a probability value to each clause in a random context-free grammar. In recent years, there have been many studies on SLP, such as a two-stage algorithm that learns the SLP parameters and a basic logic program proposed by Muggleton in 2000 to maximize the Bayesian posterior probability. In 2001, Cussens proposed Failure-Adjusted Maximization (FAM), which can estimate the SLP parameters on the premise that the basic logic program is given. In 2002, Muggleton proposed a method that can learn parameters and structure simultaneously. Another method based on random grammar is Programming In Statistical Modeling (PRISM) [50]. PRISM is a symbolic statistical modelling language that not only extends the probability of logic programs but also studies from examples using EM algorithms. In 1995, Sato introduced the rationale for the PRISM program through distributed semantics. In 1997, Sato and Kameya described the PRISM language and system and also gave an example to describe a hidden Markov model and Bayesian network [50]. In recent years, the study of PRISM includes a general method given by Sato in 2005. This general method first uses PRISM to write field-related logic programs, then applies the EM algorithm to learn. In 2005, Sato and Kameya proposed a new learning model based on FAM and a program conversion technique proposed by Cussens. To improve the efficiency of learning, this model adds some restrictions to the PRISM program.

1.5.2Problem introduction

The above relational learning algorithms cannot solve the learning problem of dynamic fuzzy systems. The study of relational learning has been further developed with the introduction of fuzzy theory. For example, relational learning has been enriched by fuzzy predicates [51] and a fuzzy learning algorithm called Autonomic Learning (AL) has been proposed based on fuzzy reasoning rules [52]. AL has two shortcomings: it does not consider possible noise interference in the observed data and is limited because it only considers the influence of the n th step on the n + 1th step. To solve these problems, a dynamic fuzzy relational learning (DFRL) algorithm is presented in this section.

Consider the following dynamic fuzzy inference formula:

Dynamic fuzzy rules:

$\begin{array}{l}\text{If}\left(\stackrel{\leftharpoonup }{A}{}_1,{\stackrel{\rightharpoonup }{A}}_1\right)\text{and}\left({\stackrel{\leftharpoonup }{A}}_2,{\stackrel{\rightharpoonup }{A}}_2\right)\text{and}\mathrm{...}\text{and}\left({\stackrel{\leftharpoonup }{A}}_N,{\stackrel{\rightharpoonup }{A}}_N\right)\text{then}\left(\stackrel{\leftharpoonup }{B},\stackrel{\rightharpoonup }{B}\right)\\ \text{In}\text{fact}{\left(\stackrel{\leftharpoonup }{A}{}_1,{\stackrel{\rightharpoonup }{A}}_1\right)}^{\prime }\text{and}{\left({\stackrel{\leftharpoonup }{A}}_2,{\stackrel{\rightharpoonup }{A}}_2\right)}^{\prime }\text{and}\mathrm{...}\text{and}{\left({\stackrel{\leftharpoonup }{A}}_N,{\stackrel{\rightharpoonup }{A}}_N\right)}^{\prime }\\ \text{Conclusion}{\left(\stackrel{\leftharpoonup }{B},\stackrel{\rightharpoonup }{B}\right)}^{\prime }={\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)}^{\prime }\circ \left(\stackrel{\leftharpoonup }{R},\stackrel{\rightharpoonup }{R}\right)\left(\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right),\left(\stackrel{\leftharpoonup }{B},\stackrel{\rightharpoonup }{B}\right)\right)\end{array}$

where

$\begin{array}{l}{\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)}^{\prime }={\left({\stackrel{\leftharpoonup }{A}}_1,{\stackrel{\rightharpoonup }{A}}_1\right)}^{\prime }\wedge {\left({\stackrel{\leftharpoonup }{A}}_2,{\stackrel{\rightharpoonup }{A}}_2\right)}^{\prime }\wedge \mathrm{...}\wedge {\left({\stackrel{\leftharpoonup }{A}}_n,{\stackrel{\rightharpoonup }{A}}_n\right)}^{\prime },\\ {\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)}^{\prime }={\left({\stackrel{\leftharpoonup }{A}}_1,{\stackrel{\rightharpoonup }{A}}_1\right)}^{\prime }\wedge {\left({\stackrel{\leftharpoonup }{A}}_2,{\stackrel{\rightharpoonup }{A}}_2\right)}^{\prime }\wedge \mathrm{...}\wedge {\left({\stackrel{\leftharpoonup }{A}}_n,{\stackrel{\rightharpoonup }{A}}_n\right)}^{\prime },\end{array}$

$\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right),{\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)}^{\prime },\left(\stackrel{\leftharpoonup }{B},\stackrel{\rightharpoonup }{B}\right)$ are the DFSs on the universe $\left(\stackrel{\leftharpoonup }{U},\stackrel{\rightharpoonup }{U}\right),\left(\stackrel{\leftharpoonup }{U},\stackrel{\rightharpoonup }{U}\right),\left(\stackrel{\leftharpoonup }{V},\stackrel{\rightharpoonup }{V}\right),$ respectively. $\left(\stackrel{\leftharpoonup }{R},\stackrel{\rightharpoonup }{R}\right)\left(\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right),\left(\stackrel{\leftharpoonup }{B},\stackrel{\rightharpoonup }{B}\right)\right)$ defines the dynamic fuzzy relation between $\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)\text{and}\left(\stackrel{\leftharpoonup }{B},\stackrel{\rightharpoonup }{B}\right),$ abbreviated as $\left(\stackrel{\leftharpoonup }{R},\stackrel{\rightharpoonup }{R}\right)$

In a complex objective world, it is often difficult to determine (̄R, ̄R) based on existing fuzzy inference rules. We propose a DFRL algorithm to learn (̄R, ̄R) samples or other data obtained by means such as expert experience or monitoring system behaviour.

Given the observed data $\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right)\text{of}\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right),\left(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b}\right)\text{of}\left(\stackrel{\leftharpoonup }{B},\stackrel{\rightharpoonup }{B}\right)$ we have:

or

$\begin{array}{l}Wherej=1,2,\mathrm{...},M,(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a})\in {[(\stackrel{\rightharpoonup }{0},\stackrel{\rightharpoonup }{0}),(\stackrel{\leftharpoonup }{1},\stackrel{\rightharpoonup }{1})]}^N,(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b})\in {[(\stackrel{\rightharpoonup }{0},\stackrel{\rightharpoonup }{0}),(\stackrel{\leftharpoonup }{1},\stackrel{\rightharpoonup }{1})]}^M,\\ (\stackrel{\leftharpoonup }{R},\stackrel{\rightharpoonup }{R})\in {[(\stackrel{\rightharpoonup }{0},\stackrel{\rightharpoonup }{0}),(\stackrel{\leftharpoonup }{1},\stackrel{\rightharpoonup }{1})]}^N\times {[(\stackrel{\rightharpoonup }{0},\stackrel{\rightharpoonup }{0}),(\stackrel{\leftharpoonup }{1},\stackrel{\rightharpoonup }{1})]}^M.\end{array}$

The above can also be expressed as

where $\left({\stackrel{\leftharpoonup }{b}}_j,{\stackrel{\rightharpoonup }{b}}_j\right)$ is regarded as a result of applying some nonlinear transformation $\left({\stackrel{\leftharpoonup }{r}}_j,{\stackrel{\rightharpoonup }{r}}_j\right)\text{to}\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right).$

The fuzzy relational learning algorithm model proposed in [50] is as follows:

where δθ(n) is a correctional term and n, n + 1 represent successive steps of learning. The correctional term depends on the loss function l(̄x, θ). Let the input vector be $a^{\ast }=\left[a_1^{\ast },a_2^{\ast },\dots ,a_N^{\ast }\right]$ and the expected output vector be $b^{\ast }=\left[b_1^{\ast },b_2^{\ast },\dots ,b_M^{\ast }\right].$ Thus, $\tilde{x}=\left[a^{\ast },b^{\ast }\right],\theta ={\left[r_{ij}\right]}_{N\times M}i=1,2,\dots ,N,j=1,2\dots ,M,\theta$ is defined as an element of all fuzzy relationships R in vector form. ̄c is a positive matrix of size NM × NM, which usually is a unit matrix. ∈ is a small positive number. ̄d(xk,) is a search direction vector computed from ̄x and θ.

The above model is very limited because it predicts the learning of step n + 1 from step n alone. Hence, it cannot effectively guarantee the correctness and convergence of learning. In this section, we present a solution that takes the previous k steps of learning into account and effectively deals with noise. The value of k can be determined according to the scale of the learning and the requirements of the system.

1.5.3DFRL algorithm

From the previous analysis, we should adjust the learning recursive formula and loss function of model (1.34). Thus, we can define the follow learning recursive formula:

where $\left({\stackrel{\leftharpoonup }{w}}_i,{\stackrel{\rightharpoonup }{w}}_i\right)$ is a coefficient representing the influence level of step i on step n + 1; its value depends on the error generated in step i. The smaller the coefficient, the greater the error, and the coefficient should satisfy ${\displaystyle \sum _{i=n-k+1}^{nn}\left({\stackrel{\leftharpoonup }{w}}_i,{\stackrel{\rightharpoonup }{w}}_i\right)}=$$\left(\stackrel{\leftharpoonup }{1},\stackrel{\rightharpoonup }{1}\right).$ Assuming that the error in the step i learning is $\left({\stackrel{\leftharpoonup }{e}}_i,{\stackrel{\rightharpoonup }{e}}_i\right),$ we have $\left({\stackrel{\leftharpoonup }{w}}_i,{\stackrel{\rightharpoonup }{w}}_i\right)=\frac{[{\displaystyle \sum _{i=n-k+1}^n\left({\stackrel{\leftharpoonup }{e}}_i,{\stackrel{\rightharpoonup }{e}}_i\right)]-\left({\stackrel{\leftharpoonup }{e}}_i,{\stackrel{\rightharpoonup }{e}}_i\right)}}{\left(k-1\right){\displaystyle \sum _{i=n-k+1}^n\left({\stackrel{\leftharpoonup }{e}}_i,{\stackrel{\rightharpoonup }{e}}_i\right)}}.$ The value of k (1 ≤ k ≤ n)) can be determined according to the scale of the learning and the requirements of the system. $\left(\stackrel{\leftharpoonup }{\theta },\stackrel{\rightharpoonup }{\theta }\right)=$${\left[\left({\stackrel{\leftharpoonup }{r}}_{ij},{\stackrel{\rightharpoonup }{r}}_{ij}\right)\right]}_{N\times M}i=1,2,\dots ,N,j=1,2,\dots ,M.\left(\stackrel{\leftharpoonup }{c},\stackrel{\rightharpoonup }{c}\right)$ is a positive matrix of size NM × NM, which is usually a unit matrix. $\left(\stackrel{\leftharpoonup }{\epsilon },\stackrel{\rightharpoonup }{\epsilon }\right)$ is a small positive number. Other variables and functions are defined as in (1.34).

When the observed data contain noise, the model can be expressed as follows:

$\{\begin{array}{c}(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a})={(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a})}^{*}+n(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a})\\ (\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b})={(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b})}^{*}+n(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b})\end{array},$

where ${\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right)}^{\ast },{\left(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b}\right)}^{\ast }$ are the true values of observation data $\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right),\left(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b}\right),$ respectively. $n\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right),n\left(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b}\right)$ are the noise components contained in the observed data, respectively. The variances are ${\left(\stackrel{\leftharpoonup }{\delta },\stackrel{\rightharpoonup }{\delta }\right)}_{\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right)},{\left(\stackrel{\leftharpoonup }{\delta },\stackrel{\rightharpoonup }{\delta }\right)}_{\left(\stackrel{\leftharpoonup }{b},\stackrel{\rightharpoonup }{b}\right)},$ respectively. Thus, we can define the following loss function:

where ${\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right)}^{\prime }$ is an estimate of the true value ${\left(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}\right)}^{\ast }.$

$\begin{array}{rl}& \mathrm{\nabla }({\stackrel{\leftharpoonup }{l}}_j,{\stackrel{\rightharpoonup }{l}}_j)(({\stackrel{\leftharpoonup }{b}}_j,{\stackrel{\rightharpoonup }{b}}_j),({\stackrel{\leftharpoonup }{r}}_j,{\stackrel{\rightharpoonup }{r}}_j)(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a}))\\ & =\frac{\mathrm{\partial }}{\mathrm{\partial }({\stackrel{\leftharpoonup }{r}}_{ij},{\stackrel{\rightharpoonup }{r}}_{ij})}\{\frac{1}{2}[\left(\frac{\underset{i=1}{\stackrel{N}{max}}({\stackrel{\leftharpoonup }{a}}_i,{\stackrel{\rightharpoonup }{a}}_i{)}^{\prime }\wedge ({\stackrel{\leftharpoonup }{r}}_{ij},{\stackrel{\rightharpoonup }{r}}_{ij})-<!--\; -\; -->({\stackrel{\leftharpoonup }{b}}_j,{\stackrel{\rightharpoonup }{b}}_j)}{{(\stackrel{\leftharpoonup }{\mathrm{\delta <!--\; d\; -->}},\stackrel{\rightharpoonup }{\mathrm{\delta <!--\; d\; -->}})}_{({\stackrel{\leftharpoonup }{b}}_j,{\stackrel{\rightharpoonup }{b}}_j)}}\right)2\\ & +\left(\frac{({\stackrel{\leftharpoonup }{a}}_i,{\stackrel{\rightharpoonup }{a}}_i{)}^{\prime }-<!--\; -\; -->(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a})}{{(\stackrel{\leftharpoonup }{\mathrm{\delta <!--\; d\; -->}},\stackrel{\rightharpoonup }{\mathrm{\delta <!--\; d\; -->}})}_{(\stackrel{\leftharpoonup }{a},\stackrel{\rightharpoonup }{a})}}\right)2]\}\\ & =\frac{1}{2}{\left(\frac{\underset{i=1}{\stackrel{N}{max}}({\stackrel{\leftharpoonup }{a}}_i,{\stackrel{\rightharpoonup }{a}}_i{)}^{\prime }\wedge ({\stackrel{\leftharpoonup }{r}}_{ij},{\stackrel{\rightharpoonup }{r}}_{ij})-<!--\; -\; -->({\stackrel{\leftharpoonup }{b}}_j,{\stackrel{\rightharpoonup }{b}}_j)}{{(\stackrel{\leftharpoonup }{\mathrm{\delta <!--\; d\; -->}},\stackrel{\rightharpoonup }{\mathrm{\delta <!--\; d\; -->}})}_{({\stackrel{\leftharpoonup }{b}}_j,{\stackrel{\rightharpoonup }{b}}_j)}}\right)}^2\\ & \frac{\mathrm{\partial }}{\mathrm{\partial }({\stackrel{\leftharpoonup }{r}}_{ij},{\stackrel{\rightharpoonup }{r}}_{ij})}\underset{i=1}{\stackrel{N}{max}}({\stackrel{\leftharpoonup }{a}}_i,{\stackrel{\rightharpoonup }{a}}_i{)}^{\prime }\wedge ({\stackrel{\leftharpoonup }{r}}_{ij},{\stackrel{\rightharpoonup }{r}}_{ij})\left(1.39\right)\end{array}$