Corpus-Based Chinese-Korean Abstracting Translation System

1 Introduction

Automatic Abstracting System is a very attractive, historical and difficult topic of Natural Language Proc­ essing. Its aim is to identify and select the central con­ tent or user inquired content from the given original texts to form the summarized output with the sentences identical to the original input text or new generated. There are three kinds of methods on developing Ab­ stracting System: the first one is based on the surface­ clues of the current context such as the word frequency [Luhn, 1958], sentence position, word clue or indica­ tion , title sentence[Watanabe,l996], word association or rhetorical relations[Ono et al., 1994] and linear heu­ ristic sentence weighting function [Zechner, 1996] .Its advantages are simple and domain unconstrained, its shortcoming is inaccuracy in sentence abstracting due to the uncertain valve of word frequency for key words, varied distribution of important sentences and heuristic function itself. The second one is based on the knowledge-based natural language processing techniques, such as Script-based summarization system for given texts with multilingual outp~t[Tait, 1985]_. C?­ based domain constrained abstracting system wtth m­ complete syntactic and semantic analysis [Dejong, 1979], rule-based summarization system with forward and backward scanning schema [Danilo,J982]etc .. Its advantages are more accurate and in depth language analysis and generation. Its shortcomings are domain constrained and difficulty in knowledge base mainte­ nance. The third one is the corpus based methods [Li and Wang, 1995; Li, 1995]. The corpus based sentence segmentation, non-linear sentence weighting functi~n , collocation computation based word and sentence Im­ portance analysis and efficient raw corpus and text indexing method, give this method a prospective fu­ ture.

Example Based Machine Translation system(EBMT) is essentially translation-by-analogy: given a source­ language passage S and a collection of aligned source/target text(or sentence) pairs, find the "best" match for S in the source -language half of the text collection, and accept the target-language half of that match as the translation[ Brown, 1996].

In this paper, we firstly introduce the methodology of Automatic Abstracting System and Example~based MT system, and then in section 2, a corpus indexi~g method called Natural Hierarchical Network(NHN) IS illustrated. In section 3, the corpus based word seg­ mentation algorithm is introduced. In section 4, the word weighting function and sentence weighting func­ tion as well as abstract generation algorithms are intro­ duced in detail. In section 5, an EBMT system called EBMT/CK is illustrated which is to translate Chinese abstracts into Korean. Finally the experimental results and conclusion are given in the section 6 and 7.

2 Natural Hierarchical Network

Natural Hierarchical Network(NHN), shown as Figure I, is a hierarchical weighted direct graph. Let ~i· i= 1,2, ... ,n, denotes the collection of members of level I. The elements in Ti is denoted as tii· Now, we define a set of mappings fi : Ti+l xN ~ Ti, i = 1, ... ,n-1, where N is the natural number. For 'V ti+li e Ti +I· tike Ti, fi(ti+li· wip)= tik represents that tik is the wip -th component of ti+li· and 3 til· ti2, .· · , tim e Ti, ti+l i= til,tiz··· tiwip·l tiwipti. wip+l ... tim·

Since f ;(t;+li· w;)= t;k corresponds to an weighted edge E( ( t;k, ti+lj) , W;p) in NHN. In general , Let (tmk> Wm, tm+li· wm+h .. ·· w ·. J,tnl) be a path from tmk to tnh then it can be represented by a vector (1, w ·. J, ... , Wm+h Wm,tmk), wher~ tmk e T m· t.1e T ·· W; is the weight of edge(t;k> t;+li), IE [m,n-1 ].

!he meaning of NHN is that every language umt(character, word, sentence, paragraph) have a vec­ ~or to corresponds to its every occurrence in texts, and m turn, the texts(or raw corpus) can be indexed and represented by all the occurrences of elements in a certain level m (say character level) represented by the vectors as above. Certainly, we can omit some levels to make the vector shorter, however that will lose some useful information of text structure and language us­ age.

In practice, according to the sentence and sub­ sentence ending symbols(i.e., punctuation such as ". : ? I") d th f f ' ' ' . . an e ormat o text(such as wrltlng rules or cust?m of paragraph, chapter , title and subtitle), the mput text can be automatically converted into a series of vectors as (pp, pa, sn, ss, wd, ct, c;), where pp, pa,sn, ss, wd and ct are respectively represent the sequential numbers of paper, paragraph, sentence, sub­ ~entence, word and character that character c; appears 1n. ·

F~r Chinese(similar to Japanese and Korean), on in­ dexmg the non-segmented texts, the "wd" element of the above vector will always be 1 if this element is considered useful for the later application, otherwise we may just omit the "wd" element.

Algorithm createNHN(t)

/*~iven a input t~xt t, transform it into NHN represen­ tatiOn by analyzmg text structure and yield NHN for each charac.ter and sentence and store them into data base.

*I

. St~p 0. Initialization. Assign the paper number pp an tdentlcal value for the current input text. Let paragraph number pa= l,sentence number sn= 1, sub-sentence number ss= 1, word number wd= l,character number ~t= I. Let sentence buffer be empty. Read the input text mto memory.

Step I. let Ch be the current processing character .

Step 2. If the character is a sentence ending symbol such as ". ? ! " , store the current sentences and its NHN vector (pp,pa,sn,ss) into the sub-sentential indexing data file. then if there is no line return symbol fol­ lows it, it means this is the end of the sentence, and let sn=sn+ l,ss= 1, wd= l,ct= l, to prepare for the next sentence process ; Otherwise, it implies that this is the end of the paragraph, then let pa=pa+ 1, sn= I, ss= I, wd=l, ct=l .

Step 3. If the character is a subsentence ending sym­ bol such as " , ; : " , store the current sub-sentences in the sentence buffer and its NHN(pp,pa,sn,ss) into the sub-sentential indexing data file. Then let ss=ss+ 1 ;wd= 1 ;ct= 1.

Step 4. If the character is a blank character, which means that the current word ends, then let wd=wd+ l ;ct= 1.

Step 5. If the character is not the above punctua­ tions, and it is a normal language character, then store the character and its NHN(pp,pa,sn,ss, wd,ct) into char­ acter indexing data base.

Step 6. If there are still characters unprocessed, go to Step I.

}

3 Corpus-Based Word Segmentation

Algorithm Segment(s) { /* given a string s(initially is the whole sentence), segment it into some words. *I Step 0. Initialization. Let max represents the current maximum weight value, initially max=O; Step 1. Computing weights of all the substrings in s. Step 2. Pick up the string with the greatest weight, say s', which is the current abstracted word and store it. If s' equals to s ,then exit, otherwise go to step 3. Step 3. Segment(s-s'),s-s' is the left strings. } Algorithm Weighting(s) { /*~iven a string s = c 1 c 2 ... c ·· in order to compute we1ghts of all strings in s, it is necessary to build a collocation matrix A, where A(i,j) represents the fre­ quency of string from character i to j, then the weight ~f that string can be calculated by the weighting func­ tion W(c; c;.1 ... ci)=F(c; c;.1 ... ci)*U-i+l)c, where F(c; ~ i+l ... c i ) i~ th~ _frequency of string c; c ;.1 ... c i , and tts length IS U-t+ 1 ), c is a constant power of length, c> 1. In practice when c equals 3, the words abstracted are more probable to be correct; *I Step 0. Initialization. Search the data base to find out NHN set T; of each c; i= l, .. n. Step I. For U= 1 ;j<=n- i ;j++) Step 2. For (i=l;i<=j-l;i++){ Step 3. T;i=T;.i.1"Ti; II to compute collocatoin of column j in matrix A Step 4. A(i,j-1)= W(c; c i+l ... c i)=IT i.i-11*0-i)c; //to weight the string c; c;.1 ... ci-l · } where, T;i is the NHN set of c;c;.1 ... ci· T;i=T;.i.1"Ti= ((((T;"T;.I)"T;.2)" ... )"Ti , """ means collocation com­

putation. For example, .let (pp"pa"sn"ss" wd"ct1) e T;,

(pp2,pa!,sn2,ss2, wdz,ct2)E Ti+l ,if( (PP·=PP2)&& (pa1=pa2) &&(sn1=sn2) && (ss1=ss2) && (wd1=wd!) && (ct1+1=ct2)), then it means that c; and ci+l collocate once with c; appearing to the left side of ci+l. let (pp2,pa2,sn2,ss2, wd!,ct2)E T;"Ti+I=T;,i+l·

In practice, multiple segmentation technique is util­ ized with first scanning of segmentation being based on the computation of string frequency in context to find the unknown words and solving ambiguous segmen­ tation and second scanning of segmentation being based on the frequency in corpus to segment common words.

4 Word and Sentence Weighting Function and Abstract Generation

4.1 Word Weighting Function

The words in context have different importance and contribution for the theme. In general, functional words(such as proposition, pronoun, conjunction) are less important than the content words(such as noun and verb). The characteristics of functional words are high frequency of usage and shorter length, while the con­ tent words are just the opposite, with a lower frequency of usage and longer length. In addition, the important words(often called key words), often have a certain higher frequency of appearance in context and lower frequency of appearance in the corpus, while the func­ tional words have higher frequency of occurrence in both the context and the corpus. Based on these char­ acteristics, the word weighting function is designed as follows:

T(w)=( F1(w)/F2(w))*(L (w)) 0 ,

where F1(w) is the frequency of w in context, F2(w) is the frequency of win corpus, L(w) is the length of w, c is a constant power of length, in practice c=3.

The purpose of using L(w) is to give the longer word a higher weight than the shorter words because longer words with a relatively same high frequency as shorter words in the context often indicate more important than shorter words. By this weighting function, the important words will be gained higher weight.

4.2 Sentence Weighting Function

The important sentences generally illustrate themes or topics of contexts in a condensed and conclusive way, such as title and subtitle sentences, topic sentences and other conclusive sentences. The characteristics of im­ portant sentences are generally to contain more impor­ tant words (or key words) and have a shorter sentence length and few number of sub-sentences. Therefore, the sentence weighting function is designed as follows :

P(s)=( T(w1)+ T(w2)+ ... + T(w.))/(L(s)*N(s)),

where s is a sentence and w; is a word of s, T(w;), i= I , .. n, is the weight of w; , L(s) is the length of sen­ tence s, N(s) is the number of sub-sentences in s.

According to this function the shorter sentences with more important words will be given higher weight, so title and subtitle sentences, topic sentences and most of the conclusive sentences will have more chance to obtain higher weights than the other unimportant sen­ tences.

There are also other interesting factors such as digi­ tal numbers, sentence locations and word clues. this kind of factors is often user- oriented and text style related, and if used properly, it will make good effect.

4.3 Abstract Generation

The abstracts(or summaries) are generated by selecting the important sentences with higher sentence weight from the input text, and keeping their original sequen­ tial orders in the text.

Algorithm Abstract(t, r)

{

/* t is a input source text, r is the summarizing rate, then generate the abstract A (t) oft *I

Step I. Initialization. Let the length of abstract L(A(t))=O; Let the sentences of t be reordered in a queue, s1 s2 , ... ,s ·. according to their weight with the former sentences having higher weight than the later sentences in the queue. Let counter i=l.

Step 2. Select a sentence s;, if L(A(t)) + L(s;) <=

L(t)*r, then put into A(t) and i=i+ I; otherwise exit.

Step 3. Go to step 2.

5 Example-Based Chinese-Korean Machine Translation System

The purpose of the EBMT/CK system is to translate the abstracts produced by the above Abstracting Sys­ tem into target language. In practice, we use Chinese as the source language and Korean as the target language. The sentences and words in· the abstracts have been segmented and weighted by the previous modules, then the main tasks for EBMT/CK is to select pattern sen­ tences from bilingual sentential-alignment example corpus and conduct word-alignment as well as generate target translations.

EBMT/CK uses essentially no knowledge about its source or target language. Its three knowledge sources are: a sententially-aligned bilingual example corpus; a bilingual dictionary; a Chinese-Korean Character Transforming Table.

5.1 Pattern Sentences and Optimal Cover Set Finding

Algorithm OptimalCoverSet(S)

{

/*Given a segmented source sentence, S= w1w2 .. . wm, w; is the segmented words or phrases. Let W(w;) is the weight of w;, computed by the same word weighting function as in section 3, W(w;)=F(w;)*L(w;}", however, the difference is that the word frequency is computed in Bilingual corpus. Let T(w;) be NHN vectors col­ lection of w;. Then, we compute weight of each sen­ tence that corresponds to a NHN vector in T(w;),and select a set of example sentences in T(w;) to cover the sentence S. *I

Step 1. Compute weight of each NHN vector in T(w;) which corresponds to a example sentence in Bi­ lingual corpus,i=l , ... ,m; if w;.,w;2, ... and W;t occur in the example sentence(say e1) , represented by a vector

(pp,pa,sn,ss) then P(e1) = (W(wi1) + + W(wik))IL(e1),and let C(e1)={wihwiz, ... ,wikl·

Step 2. Select the sentence with the greatest weight, let it be e1.

Step 3. If { w~ow2 , ... ,wm}-C(e1)!=<1>, then continue to select the sentence greatest weight from the left sen­ tences, until we get a set of sentences { e~oe2 , ·.. ,ek}, and C(e1) uC(ez) u ... uC(ek);;;!{wh····wml·

Step 4. Output { e~o .. . ed as the optimal cover set of sentence S, and e1 is the pattern example sentence be­ cause of its greatest weight.

}

5.2 W ord-Aiignment

Word alignment uses an approximate match approach, because 60% of the Korean words(most of them are noun and verb with word length greater than or equal to 2) are originated from Chinese with the same or similar meanings and lengths but written in the form of Korean pronunciation(Hangul) character.

Therefore, we firstly translate every Chinese char­ acter in pattern sentence into corresponding Korean pronunciation character by utilizing a Chinese-Korean Character Transformation Table in which every Chi­ nese character has a corresponding Korean pronuncia­ tion representation such as Chinese character "$" in Chinese GB code corresponds to Korean pronunciation representation " 0 ]" in Korean KSC code. Then ap­ proximate word matching between the transformed words and the words in Korean example sentence of the pattern sentence pair is conducted by using the following word similarity function:

S(w~ow2 )=(the number of characters in both words)*2/( L(w1)+ L(w2)).

In this way, more than 60% of the words can be aligned, most of them are the Korean words originated from Chinese. Some unknown words such as the name of people, organization and so on ,can also be aligned; Besides, one-to-many, many-to-one and one-to-one associations can also be solved by using the following word alignment algorithm.

Algorithm WordAlignment(p1,p2)

{/* p1= w11wl2···wlm and p2= w21w22 ... w2· is an exam­ ple sentence pair, p1 is Chinese(source language) half, while p2 is Korean( target language) half of the pair, wli and w2i are words or phrases, ie [ l,m], je [ l,n]. */

Step I. Transform p1 = w11 w12 ... w I m into p' 1 = w'11w'12 ... w'1m by looking up Chinese Character Trans­ formation Table.

Step 2. For every ie [l,m], je [l,n]. Compute S(w'1j,Wzj)

Step 3. For a given ie [ l,m], if exist k~o ... kh, h>= I, for every je [I ,n]- [k1,.., kh] , S(w' lit Wzkh) = ... =S(w'1i,w2kh) >S(w'li,wzj)>O, then w'1i is aligned by { Wzklo ... , Wzkh}.

Step 4. Otherwise, if no such k exists( i.e. for every je [ l,n], S(w'1i, w2i)=0), then look up w1i in a bilingual dictionary of common words, let the translations of wli be w1i 11 , ··· ,w1ik> , k>=l,then for every je[l,n], he [ l ,k]. compute S(wli<h> , w2 i). If exist { j 1, ··· , jp)e[l,n) and { h~o .... h~)e[l,k], S(w11 1 h 1 >, Wzj 1)= .. . = S(w1ilhpl , Wzjp) > S(w1/h , w2j)>0, where he [ l,k)- { h~o · · ·· hp}, je[l ,n]-{ j 1, ··· , jp}, then w1i is aligned by { wzjh···· Wzjp} .

Step 5. If wli is not listed in dictionary and for every je [ l,n], S(w' li· w2i)=0, then w1i is aligned with { Wzklo ... ,wzkh}, where Wzki(j=l, .. ,h) has no association with w1i , ie [I ,m). }

5.3 Target Sentence Generation

Based on the pattern sentence and word alignment, the target sentence is generated by replacing some of the words in pattern sentence so that the modified pattern sentence becomes identical to the input source sen­ tence.

Algorithm TargetSentenceGeneration(s, p1 ,p2)

{/* s is the source sentence, p1 and pz are pattern sen­ tence pair, p1 is the Chinese example sentence, and p2 is the Korean translation of p1· To generate the Korean translation of s by modifying pattern sentence pair.*/

Step I. Align sand p1· If there are k words (say, w" w2, ... ,wk ) appear in both s and p1· Let s= t1w1t2w2 ··· wktk+h p1= t1 1 w1 t2 1 wz ... wktk+1 1 , then for ie [I ,k], ti is aligned with ti 1 , where ti and ti 1 are words, phrases or blank.

Step 2. After calling WordAiignment(p~op2), using ti to replace ti 2 e p2 which associate with ti 1 ·

Step 3. Translate ti(ie [ l,k])by first converting them into Korean by using the Transformation Table and then looking up dictionary.

}

There is one exception to the above procedure for retrieving and aligning chunks. If any of the chunks cover the entire input string and the entire source­ language half of a corpus sentence pair, then all other chunks are discarded and target-language half of the pair is produced as the translation.

6 Experiment

6.1 Corpus Indexing

In practice, we give each character an entry and its every occurrence in texts is described by a vector as (paper number, paragraph number, sentence number, sub-sentence number, word number and character number), the indexing speed by algorithm Cre­ ateNHN(t) is about 2000 characters/sec on IBM PC486. Apparently, storage space for the NHN data is about the six times of the original texts data space.

6.2 Word Segmentation

The corpus used for word segmentation is a collection of texts without restrictions on domain, style and length.

One experiment shows that the number of abstracted words by using algorithm Segment(s) is increased along with the size increment of corpus, for example when the size of corpus is 27000 characters, the aver­ age coverage rate of abstracting(which is calculated by (number of characters in abstracted words )/(number of characters in tested texts)) is about 86%, while most of the left 14% of unprocessed strings are already words, therefore further increment of the corpus size will not increase the coverage rate too much, and in general, the size of corpus around 50000 characters is enough to obtain a realistic and steady coverage rate of ab­ stracting.

Another experiment shows that the correctness of abstracting (which is calculated by !-(the number of wrong abstracted words)/(the number of total ab­ stracted words)) is about 98% with the above coverage rate of abstracting and does not changed too much when the coverage rate of abstracting go beyond 80%.

An comparison of 30000 word dictionary based Backwards Maximum Matching(BMM) algorithm and the Non-dictionary Word Segmentation(NWS) algo­ rithm, shows that the number of wrong segmented words of BMM is four times of that of NWS for open test.

The running speed is 2000 characters/min for the corpus with 40000 characters. The computational com­ plexity of time for the algorithm is O(m*n), m is the size of input text, n is the size of the corpus .

6.3 Abstract Generation

In order to evaluate the machine-made abstracts, we selects tens of articles from different domains with different styles and lengths.

One experiment shows that 90% of the abstracts of these articles with 5%-l 0% abstracting( or summariz­ ing) rate can contain the title sentence and some sub­ title sentences and topic sentences, although we do not give particular attentions and weights to those sen­ tences in our word and sentence weighting function.

Another experiment shows that 90% of the important sentences neither title sentences nor topic sentences can also be abstracted by the abstracting rates less than 20%.

We have test our system on Chinese and Korean lan­ guage texts, although most of the above experiments are conducted to Chinese texts, the Korean texts proc­ essing have the similar results on a small scale of test, since the methods we used are not language oriented.

6.4 Example-Based Abstracting Translation

We use a bilingual example corpus with 5000 Chinese­ Korean sentence pairs, a Chinese-Korean dictionary of 5000 most frequently used words and a Chinese - Korean Character Transformation Table with each entry corresponding to a Chinese character.

An experiment shows that based on a small scale of text data, the correctness of word alignment is 80% and more than 70% of the important words can be correctly translated.

7 Conclusion

we have illustrated the detailed algorithms of Abstract­ ing Translation System(ATS) and shown some of the experimental data. The key techniques include the NHN(Natural Hierarchical Network) raw corpus(and text) indexing method, the corpus- based word segmen­ tation and word weighting function, dynamic sentence weighting function, and abstract generation algorithm, an Example-Based Chinese-Korean MT system with algorithms in pattern sentence finding, important word oriented word alignment and target sentence genera­ tion, etc .. The algorithms and ideas of our system are also quite meaningful for Multilingual Information Retrieval and Corpus-based Natural Language Process­ ing.

Acknowledgment

This project has been supported by China National High -Tech Development Plan "863" on Automatic Abstracting System and Center of AI Research of Ko­ rea Advanced Institute of Science and Technology on Chinese-Korean MT system.

References:

[Watanabe, 1996] Hideo Watanabe. A Method for Abstracting Newspaper Articles by Using Surface Clues.COLING96:947-979, Copenhagen, Denmark, Aug. 5-9, 1996.

[Zechner, 1996] Klaus Zechner. Fast Generation of Abstracts from General Domain Text Corpora By Ex­ tracting Relevant Sentences. COLING96:986-989, Copenhagen, Denmark,Aug.5-9, 1996.

[Luhn, 1958] Luhn,H.P .. The Automatic Creation of Literature Abstracts. IBM Journal of Research and Development, Vol.2, No.2:159-l65,1958.

[Dejong, 1979] G. Dejong. Prediction and Substantia­ tion : Two Processes That Comprise Understanding. Proceedings of IJCAI-79, Tokyo, Jan., 1979.

[Tait, 1985] J .I. Tait. Generating Summaries Using a Script-Based Language Analyzer. Progress of Artificial Intelligence, 1985.

[Danilo Fum. et al, 1982] . Danilo Fum. et al. Forward and Backward Reasoning in Automatic Abstracting. COLING82.

[Ono eta!., 1994] Kenji Ono, Kazuo Sumita and Seiji Miike. Abstract Generation Based on Rhetorical Struc­ ture Extraction. COLING94, Vol. I :344-348, Kyoto, Aug. 5-9,1994.

[Li and Wang, 1995] JunJie Li and KaiZhu Wang. Study and Implementation of Non-dictionary Chinese Segmentation. NLPRS'95,Seoul,Korea,Dec., 1995.

[Li, 1995] Li Junjie. Research and Implementation of Unconstrained Chinese Automatic Abstracting System. Ph.D. dissertation, Harbin Institute of Technology, P.R.China. Au!!: .. l995 .

[Brown, 1996] Ralf D. Brown. Example-Based Ma­ chine Translation in the Pangloss System. COLING.96: 169-174,Copenhagen,Denmark,Aug.59,1996.