Knowledge Guided Learning of Structural Descriptions

KNOWLEDGE-GUIDED LEARNING OF STRUCTURAL DESCRIPTIONS

Mark S. Fox and D. Raj Reddy Computer Science Departmentt Carnegie-Mellon University Pittsburgh, Pa. 15213

INTRODUCTION

14e de!IDnstrate how the use of domain dependent knowledge can reduce the combinatorics of learning structural descriptions, using as an example the creation of alternative pronunciations from examples of spoken words. Briefly, certain learning problems (\hnston, 1970; Fox & HayesRoth, 1976) can be solved by presenting to a learning program exemplars (training data) representative of a class. The program constructs a characteristic representation (CR) of the class that best fits the training data. Learning can be viewed as search in the space of representations. Applied to complex domains the search is highly combinatorial due to the: 1) Number of alternative CRs. 2) Size of training set. 3) Size of the exemplars.

,PROBLEH.

An important aspect of speech understanding (Reddy, 1976) research is the creation of word pronunciation dictionaries. The dictionary entry for a word must contain the salient features and variations of how a word may be pronounced. The performance of a speech system depends directly upon the validity of this dictionary. Presently, a trained person constructs a dictionary by examining speech data, laboriously testing and modifying a dictionary many times. The goal of this work is to automate this process.

The training data is a set of segmented spoken words. Each exemplar is a varying length sequence of segments. A segment is a t1me partition of the speech signaf that is labeled by an array of phoneme-weight pairs. The weight specifies how closely the segment matches the corresponding phoneme. The phoneme array for our application usually contains 100 7 entries and the average exemplar segment length is seven. Thus each exemplar depicts approximately 100 pronunciations (1.e., paths through the phoneme­ segment matrix). The segment label's weight assignment is errorful. A segment is correctly classified (i.e. 1 correct label is best rated) only 42% of the time \Goldberg, 1976). Another problem is the segmentation process. An exemplar that contains possibly 10 segments may only represent 4 contiguous phonemes. Thus all possible combinations (partitions) of contiguous segments must be constructed, and the labels that best describe the partitions must be determined.

The target CR is a network whose nodes represent phonemes and whose arcs represent allowable transitions between nodes. This network must be small due to space limitations.

The learning problem can be viewed as three separate phases: 1) Learning of a minimal state representation for each exemplar of a word class. 2) Combining the exemplars of a word class into a minimal state network. 3) Modify the networks as a result of near miss analysis between word classes.

KNOWLEQGE-G!!IDED LEARNING

Typical attempts at including knowledge in the learning process are generally ad hoc. We believe another important method of adding knowledge is to recognize where in the learning problem knowledge is critical in reducing the search space and emphasizing salient aspects of the exemplars. Then examine the domain for this critical knowledge. The importance of knowledge is primarily measured in terms of the reduction in search space. We believe that there exists a set of rules that can aid in the recognition and determination of this critical knowledge. The following is a partial list of domain independent rules we have used to recognize relevant domain knowledge.

This work was supported in part Advanced Research Projects by the Defense Agency under and monitored of Scientific first author was National Research Scholarship. contract no. F44620-73-C-0074 by the Air Force Office Research. In addition, the partially supported by a Council of Canada Postgraduate

1. Bounds on Representation: Information can narrow the minimum and maximum size ·bounds of the learned representation. For example: The number of syllables (local maximum amplitude) in the example wave form provide a minimum size on the single exemplar learning.
2. .Feature Focusin2: Certain features of an exemplar convey more information than others and should appear in the final learned representation. For example: Acoustic characteristics of stressed syllables exhibit less ambiguity therefore are more reliable.
3. .Pi fference Focusing: It is important to emphasize features that differentiate between two similar classes (near miss analysis (Wins ton, 19 70)). For example: Compare CRs and speech signal to derive differences.
4. Result Confi rma ti on: There may exist a model of expectation of how the resulting CR should look. For example: 1) Each word can be described as a sequence of nasal, vowel, consonant, noise and silence type sounds.

AN EXAMfLE

Figure 1 depicts an exemplar of the word MENTION. Figure 2 depicts the best partition for two exemplars (single exemplar learning). The partition size was bounded below by the number of syllables and above by the abstract expectation model. The second exemplar was confirmed by the expectation. Figure 3 contains the resulting network constructed from the exemplars. Herging and separation of nodes was guided by both abstract models and signal level information.

DISCUSSION

Learning in complex domains entails a large combinatorial search. The research described here attempts to solve two problems: Generally! where to look in a domain for knowledge that wi 1 help reduce the search space. Specifically, how to automatically generate word dictionaries for speech understanding systems both efficiently and accurately. At the t1me of writing the approach taken here appears to be fruitful. One idea that we see occurring repeatedly in this and other work (e.g.i vision) is the importance of models at various evels of abstraction in both the pruning and verification of learned representations.

R EFERENCf:S

• Fox M.S. and F. Hayes-Roth, 1976, "Approximation Techniques for the Learning of sequential patterns". Third Int. Joint Conf. on Pattern Recognition Coronado Calif., Nov. 1976.
• Goldberg, H.G., 1976, "Segmentation and Labeling of Speech: A Comparative Performance Evaluation", (Ph.D. Thesis, Carnegie-Mellon Univ.), Tech. Report, Computer Science Dept., Carnegie­ Mellon University, Pittsburgh PA.

Reddy, D.R., 1976, "Speed1 Recognition by !1achine: a review". Proc. of the IEEE, (April 19 76).

Winston P., 1970, "Learning Structural Descriptions from examples", Tech. Report AI TR-231, MIT AI Lab., Cambridge, Mass ··

M EH2 UH NX ZH SH NX EM NX EM AES DX N SH ZH N NX EM AYX AE4 0\42 EN PH PH DX M M UW3 AE AH2 M s G EN EYR M1 OYL AYR IHS M1 T IX t1 IH2 EYR

FIGURE 1: Example of the word MENTION.

Ex.1:M(1) EH2(2) N(3:4) ZH(5:6) NX(7:9) Ex.2:M1(1) EH2(2) EN(3) SH(4) IH5(5) N(6:7) Model: Nasal Vowel Nasal Noise Vowel Nasal

FIGURE 2: Highest rated partitioning for single exemplar learning. *(n:m) describes a partition where * denotes the best label that describes the partition, and (n:m) denotes the partition contains segments n through m. (Ex.1 is from Fig 1)

M EH2 N

ZH

N

IHS FIGURE 3: CR representing exemplars 1 and 2.