NEURAL NETWORKS FOR
NATURAL LANGUAGE PROCESSING
A Thesis submitted fo r th e awa i・(1 of the Degi・ce Of
Doctor of Philosophy
By
B. Krishna Murthy
Department of Mathematics
Indian I 簸 stitute of Technology, Delhi
August 1996
CERTIFICATE
This is to certify that the thesis entitled Neura' Networks for Natural Lau- guage P!・ocessing which is being submitted by Mr. 13. Krishna Mui・t by 釦r the award ofDoctor of Philosophy to the Indian Institute of Technology, Ddhi is a bonaffide record of research work under my guidance and supervision
Tbc thesis has reached the standard offuiffihling the requirements ofthe regu-- lations relating to the degree. The results obtained in this thesis have not been submitted to any university or Institute 拓r the award of any degree or diploma.
曳B・ek…八1」h一 Dr.(Mrs,)13.Chandra Associate Pro飽s s o r Computer Applications Group Department of Mathematics Indian Institute of Technology
New Delhi
AcknowIedgements
With great pleasure arid deep sense of gratitude, I acknowledge the invaluable guidance ofDr. (Mrs)13. Chandra, my thesis supervisor. It was she who introduced me to the area of "Neural Networks for Natural Language Processing". In spite of her busy schedule, she could ffind time to provide precious guidance. She was always kind, cooperative and helped me whenever I needed. Her never ending patience and hard work inspired me to work. I am extremely grateflul to her for fulfilling my dream. She was always friendly, cooperative and inspired me to cultivate new research ideas. I express my profound gratitude to her. I am deeply indebted to her
I express my sense of indebtedness to the Dean, V G. Studies; Head, and other・Iマao- ulty members of D叩artrnent ofMathematics for the support they have providedおr pursu- ing my research.
i express my sincere thanks to Sh.S.S.Oberoi, Adviser; Sh.R,K.Arora, Senior Director; Sh. Deshpande, Sh. A,B. Patki, Dr. Om \Tikas, Directors; Sh. G.V. Raghunathan, Sh. R.G. Gupta, Addi. Diretors and other friends ofDoE for their support and cooperation
I acknowledge the moral support given by my friends Mr. BVC Rao, Mr. A Duraga Prasad, Mr, Sumeer Goyal, Mr. NSC Babu, Mr. DYL Somayajulu and others.
Last but not the least, I would thank my wife (Padmasri), my brothers, sisters, in-laws and relatives for their emotional support and constant encourage my course work.
il
Abstract
The thesis aims at development of Neural Ne加ork models for N如rai Language Processing (NLP). NLP involves development of computer models for syntactic and sema耐ic analyses. Through this research it has been shown that Neural Network models arc a promising tool for NLP. Parsing is an essential part of any NLP system.
This research work introduces Neural Networks for Indian language processing Indian ian即ages are inflectional and relatively free word ordered. An e拒cient technique is lacking for p町ing ofindian languages. So far pars郎ba面on only convention討techniques have been developed. The ad皿n昭e ofusing Neural Networks for NLP is th航it is a one面e processing 団'ort.
Cascading ofBackprop昭ation (BP) netwo水s has been introduced in this thesis. Bas加 on this, models have been designed and implemented for processing oftwo Indian languages namely, Tamil and Telu即；Highly successifiul results have been achieved. Concepts ofくienetic Algorithms have been employed in training Multilayered Neural Networks for indian la鴫uage processing, The genetic operators have beentransformed to Neural Network parameters. The a由antages of加th Genetic嶋orithms and Neural Networks have been b吋utilised. The models have been designed in such a way that they can be used for processing any language.
Jn order to eliminate the hidden layer in a Multilayered Neural Network,Radial Basis Function (RBF) networks have also been designed for parsing. A new distance measure viz.
1面caldist加ce，顧ted for natural language processing has been硫roduced. A model for sy批み血C an町sisu面g multistage heterogeneous netwo水s namely, a面xture ofRBF and Bac印ropag甜。
V'I
networks has been desi即ed. Evolution町lea而ng algorithm has been desi即ed for RBF networks which allow class迅cation of patterns belon即ng to more than one class・
In order to speed up the computation記 time for trai証ng, models have aiso been designed using Functional Link Networks (FLN) for category prediction. lt has been observed that FLN takes around 1/1 0th of the computational time taken for training using l3ackprop昭ation network. it has been shown that FLN is useful for Example Based Machine Translation，句designing ofa system for t葺inslation ofsimple sentences什om one indian langu昭e to another.
v'li
Contents
Abstract 1. tntroduction
1.i Artifficial Neural Networks I。i . I Introduction
1 . i .2 Biological and Artifficial Neural Systems 1.1.3 Le柳ing, Recall and memo印
i .2 Overview ofNeural networks I . 2. I Backpropagation Networks 1.2.2 Counterpropagation Network i.2'3 Hopffield Network
i, 2.4 Hamming Network
1.2,5 Kohonen's Self O稽anising Feature Map i . 2.6 Carpenter (rossberg Network
I .2.7 Radial Basis Function (RBF) Networks 1.2,8 Functional Link Networks
1.3 Natura' Language Under就andi昭
I .3 . i . Natural Language Processing (NLP) I .3 .2 Natural Language Parsing
i .3.3 Various Parsing Techniques i A NLP for Indian Languages
i .4. 1 Parsing Based on Pani血an Grammar 1.42 NLP ofBengali based on LFG
RJ コー nU l hL ォ什 く一 一b ワ1 0一 （U l つ一 hj J什 べ】 べ〕・・ 1 1 1 1 1 1 1 1
1 2 つ」 つ一 2 2 2 2
111
i .43 Parsing of臣ndi Sentences using Tree Adjoining Grammar Natural Language Processing using Neural Networks
sation of the Thesis
2・ Natural Language Parsi皿g Using Mult競町e肥d Neural Networ島 32
2. 1 Introduction 32
2.2 Multilayered Feedforward Neural Networks 35
2,2. 1 Backpropagatiori 川gorithm 37
2.2.2 Pattern Update 38
2.2.3 Session Update 42
21.4 improvements in Backpropagation Algorithm 44 2. 3 Verbphrase Analysis Using Multilayered Neural Networks 45 2,3.I Some Features of an Indian Language (Tamil) 46 2.3.2 Desi即and Implementation ofMNNs for VerbPhrase Analysis 49 2.4 Multilayered Neural Networks for Parsing 50 2.4. 1 Some Linguistic Features ofTelugu 52
2.4.2 Design Issues 58
2.4.3 Illustrations Sc)
2.4.4 Implementation and Results 60
25 Conclusions ) 67
3, Ge眼etic Algorithms and Neural Networ柵for Processing of lidian Languages
1.1 1批roduction
3.2 Genetic Algorithms for Neural Networks 3.2.1 Preliminaries of Genetic Algorithms
00 0凸 nU I 一b 一6 7■ 71
一へ一 KU 11 11 AU 一6 00 2 つー つ一
叫 06 09 09
117
I i 8
nソ 1 つ」 つー ワ1 Cソ nV へ1一 1 2 つー つー つー つ一 「j へj
11山 111 11上 一111 『11A 111 「11 111
135 135 137 3 .2.2 Applications of Genetic Algorithms 74 3.2.3 Gen航ic Algorit加s for Training ofMultilayered Neural Netwo虚s 75 3.3 Genetic Algorithms and Neural Networks for Language Processing 81
3.3.i Model Design 81.
3.3.2 Some Linguistic Features ofan Indian Language (Telugu) 86
3,3.3 Implementation and Illustration 90
3.4 Discussions and Conclusions 104
4. Syntactic Analysis usi鳳g Hetrogenous Neura' Ne加or恥 4. 1 Introduction
4.2 Preliminaries of RBF Networks
4.2. 1 Radial Basis Function (RBF) Networks 4.3 Syntactic Analysis Using Hetrogenous Networks
4.3. i Category Stage 4.3.2 Morphological Stage 4.3,3 Phrase Stage
4.3.4 Syntactic Net
4, 4 Implementation and Illustrations
4.5 Evolutionary Learning Algorithm forRBF Networks 4.5. I Problem Deffiriition
4 . 5 .2 Design of Evolutionary RBF Network 4.6 Conclusions
5. Parsing using Functional Link Networks 5.i Introduction
5.2 Overview ofFunctioiial Link Networks
5.2. i Training of Functional Link Network I 40 5.3 Design ofFunctional Link Network拓rNLP 142
5.3.i Implementation and Results i 43
5.4 Application of FLN for Example Based Machine Translation I 54
5.4. 1 Illustration i 58
5.5 Conclusions 160
6. Comparison with Traditional Parsers, Conclusions and Future Work
6. 1 Comparison with Traditional Parsers
6 .I Parsers Based on Augmented Transition Network (ATN) 6 .2Parsers Based on Lexical Functional Grammar
6 .3 Parsers Based on Tree Adjoining Grammar 6 .4 Parser Based on Paninian Grammar
6.2 Discussions and Conclusions 6.3 Futurework
（つ 「コ くJ 一0 nU つー ヘコ nリ 6 にU 一0 一D 「 1
1 ．ノ 「1 ア1
1-IL 1111 一ー上 」11 dlt且 ■1111 ■esl 『IIJ
Bibliography
List of Papers Published/Commuぬicated
VI
