A Basic Model for Learning Systems

1. INTRODUCTtCJN

The inductive process mus~ he realized by the learning system so that it can improve the hypothesis or the knowledge structure as it acquires the new instances from the environ­ ment. The total information that the learning system must store increases quite rapidly in the course of the learning process, and the intelligence of the system depends mostly upon the knowledge structure which is constructed from this large and unorganized set of infor­ mation. The problem to be solved in the design of the learning system is, therefore, how to construct the representation space, the set of possible knowledge structures, and how to LS/0. The details of the LS/0 and the basic theory of the learning systems will be reported in the subsequent papers.

2. THE LEARNING SITUATION

We shall consider the sequence of question­ answer pairs. This is called an environment (EV).

EV · ( (Ql,A1),(Q2,A2),(Q3,A3), ···· ) where Qt and At are strings on the alphabet ~. the set of alphanumeric characters except "#", and are called the question and the answer, respectively. Fig. 1 shows a typical example of the environment. We shall denote the environment by EV1 hereinafter.

The interaction is an information exchange bet­ ween the learning system and the environment. It consists of three phases: Q, Rand A. In the phase Q, the environment gives a question string Qt to the system. In the phase R, the system must reply a response string Rt to the question Qt. In the phase A, the environment shows the system an answer string ~ as the correct reap­ once to the question Qt. An interaction at time t can be represented by (Qt· Rt, At ).

The system infinitely iterates the interactions with the environment. ~e infinite sequence of interactions is called the question-response­ answer process (Q-R-A process) or the learning process (LP).

LP · [ (Ql,Rl,Al),(Q2,R2,A2),(Q3,R3,A3), ··· ) Fig. 2 shows an example of the learning process, which is the sequence of in.teractions between the LS/0 and the EV1, and is called LP1 herein­ after.

The interaction is said to be successful when the response and the answer strings are the same. The system is evaluated by the rate of successful interactions in the Q-R-A process.

3. THE LEARNING SYSTEM

A system which operates under the sttuatl.on described in section 2 is designed in this paper. This is called LS/0 and is implemented on a computer as a FORTRAN program. The system LS/0 is composed of three elements: the execution element, the learning element and the memory element. The execution element receives a ques­ tion string and generates a response string by utilizing the knowledge acquired so far in the memory element. The learning element makes spec­ ific changes in the knowledge in the memory elemerit to improve the future responses. The memory element stores the learned knowledge, which is often called the state of the system.

The learned knowledge in the memory element of the LS/0 is mainly represented by the network­ like structure called the label net. The exam­ ples of the label net is shown in Fig. 3 (1)-(8). The lab~l net is reviewd briefly in ~hat follows. The details were reported in [1]. The label net can represent much wider variety of structures than the Fig. 3 shows.

The label net consists of finite vertices and finite labels. Each vertex corresponds to a set of strings and each label represents the rela­ tion between the set of strings. Strictly speak­ ing, the label net is a set of equations with the variables of sets of strings.

Fig. 2 The learnins 12rocess LP1 between the LS/0 and the EV1

The meaning of the label net is well explained by the following example. The label between Vl and V2 in Fig. 3 (4) means that the set of Vl contains the string "a.=?lla.=a." if the set of V2 contains the string "a.". The two labels pointing toward V2 in Fig. 3 (4) means that the set of V2 contains "DOG" and "CAT". These relations deter­ mine the set of Vl, S(Vl), and the set of V2, S(V2).

S(Vl) S(V2) DOG=?/IDOG=DOG, CAT=?IICAT=CAT DOG, CAT }

The knowledge stored in the lable net is utiliz­ ed during the course of the learning process through the vertex Vl. when there exists a string "a.#S" in the set of Vl, the structure implies that the string "8" may be the correct response to the question string "a".

4. THE LEARNING PROCESS OF THE LS/0

In order to show how the LS/0 interacts with the environment and how tt improves its knowledge structure, the learning process LP1 in Fig. 2 and the state change of the LS/0 during the learning process are described in the following.

The system LS/0 starts with the initial state shown d.n Fig. 3 ( t).

(1-Q) ···.· DOG·?

The first question is given to the LS/0 by the EV1· The question is "DOG=?".

(1-R) ..... ???

The state (1) in Fig. 3 indicates the LS/0 has no knowledge on the EV1. The LS/0 was designed to reply "???" when it fails to find any strings to the given question.

(1-A) .···. DOG·DOG

The string "DOG· DOG" is given to the LS/0 as the answer. After this interaction, the LS/0 changes the state from (1) to (2) in Fig. 3. The state (2) means that "DOG=DOG" is the correct response to "DOG=?".

(2-Q) · · · · · CAT=?

(2-R) ····· ???

The clue which the LS/0 has at this p.oint is only the knowledge (2). The LS/0 replies "???" again.

(2-A) ···.. CAT=CAT

The interaction at time 2 causes the state change from (2) to (3). The structure (3) Stores information gained from the interactions at time 1 and 2 separately. The learning element of the LS/0 further tries to organize the structure and gains the state (4). The vertex V2 was newly generated. The learning element assumes that the set of V2 might be equal to the set E*, the set of all strings of any length including zero

length one. This changes the state from (4) to (5).

(3-Q) ····· LION·?

(3-R) ····· LION·LION

The state (5) enables the LS/0 to reply the st­ ring "LION·LION".

(3-A) ····· LION·LION

The response is found to be correct. The state changes to (6).

(4-Q) ····· L(l2,4)·?

(4-R) ·.··· L(l2,4)·L(l2,4)

This response is generated by the execution element utilizing the structure (6).

(4-A) ..... 12

The answer string at time 4 shows the correct response is not "L(l2,4)·L(l2,4)" but "12". The LS/0 stores this information in (7).

(5-Q) L(34,45)·7

(5-R) ····· L(34,45)·L(34,45)

(5-A) ..... 34

After storing the new information to (7) by adding the labels ''LC34~4S),..?/134" and "L(34,45)" to Vl and V4, respectively,the LS/0 tries to reorganize it and constructs the structure (8).

(6-Q) ..... L(876,6)·7

(6-R) ..... 876

The LS/0 utilizes the structure (8) and generates the response "876".

(6-A) ..... 876

This interaction is found to be The information gained at time 6 by adding the same label "876/16" and V6. successful .. is stored to both V5

(7-Q) R(34,67)·?

(7-R) .... . R(34,67)·R(34,67)

(7-A) .... . 67

The answer string of the EV1 again forces the LS/0 to reorganize its knowledge struc­ ture. The learning process between the LS/0 and the EV1 continues infinitely in this manner.

REFERENCE

[1] Akama, K. and Ichikawa, A. "Represen­ tation of Set of Symbol Strings for Learning Systems." Trans. Institute of Electronics and Comuniaation Engir.eers of Japan. J61-D No.9 (1978)