A Text Scanning Mechanism Simulating Human Reading Process

1 Introduction

Previous text processing techniques focus on retrieve, extract, summarize, mine, analyze and organize symbols in text. They can be classified into three kinds. The first is based on the features of text [Radev et al., 2002], including term frequency [Luhn, 1958], positions of words or sentences [Baxendale, 1958], etc. TF-IDF is a typical technique based on term frequency [Salton and Buckley, 1988]. Some applications are implemented by using TF-IDF [Wu et al., 2008]. Some techniques represent text as a network and apply network methods to process text [Costa et al., 2007]. The second is based on training. Various models or schemas are designed and trained by well-defined data. The typical techniques include vector space models [Singhal, 2001], latent semantic analysis [Dumais, 2004], probabilistic model [Amati and Rijsbergen, 2002; Lafferty and Zhai, 2003]. The training process was improved by using natural language instead of labeled examples [Goldwasser and Roth, 2011]. The third incorporates pre-established frames or background knowledge, such as wordnet [Fellbaum, 2010], conceptual knowledge [Musat et al., 2011], ontology knowledge [Batet et al., 2011], encyclopedic knowledge [Nastase, 2008], etc.

However, previous techniques are only suitable for specific applications. A key shortcoming of previous research methods is that they neglect human reading process. Newell pointed out that the natural processes, including cognition process, can be simulated and the information in the simulations can deal with any issues about the processes [Newell, 1990].

The motivation of this paper is to build a text processing mechanism suitable for multiple applications by simulating human reading process.

From a broader perspective, human cognitive aspect has been considered as a general mechanism to effectively process information in multiple areas. A model of information foraging based on the constraints and mechanisms of human cognitive architecture was developed [Pirolli and Fu, 2003]. The decay rate of cognition was incorporated for information storage in a cognitive architecture [Anderson, 2007]. A cognitive network was used to solve complex problem based on the simulation of decomposing complex task [Bhattacharyya and Ohlsson, 2010]. The spread of information through a network of individuals based on the simulation of interaction between individual cognitive mechanisms and social dynamics was studied [Coman et al., 2012]. The agents with human-like memory which can forget and maintain information were designed [Reitter and Lebiere, 2012]. The advantages of solving problems by collecting information from human actions were reported [Kapoor, 2012].

Zhuge pointed out that reading is a process of constructing semantic link networks of concepts in reader's mind by discovering and browsing the semantic link networks of words weaved by the author [Zhuge, 2012]. A Semantic Link Network model was developed as a general method and theory for self-organized semantic networking. It was extended to semantically link objects in different spaces to study the fundamental structure of cyber-physical society and create cyber-physical-social intelligence [Zhuge, 2011]. A semantic lens mechanism based on the semantic link network and a multi-dimensional classification space was proposed to simulate semantic networking mechanism and multi-dimensional information processing mechanism of human cognition and behavior [Zhuge, 2010]. Human reading processes were considered for implementing faceted navigation on text [Xu and Zhuge, 2012a; Xu and Zhuge, 2012b].

Cognition scientists proposed some models to explain human reading process [Fauconnier, 2002], but they have not proposed any applicable method.

This paper proposes a text scanning mechanism simulating human reading process (HTSM). It inputs a text and then outputs dynamic impressions of words generated through scanning the text. It has the following characteristics:

1. Generality. The dynamic impressions of words can be used in different applications as stated in section 3.
2. Dynamicity. HTSM scans and analyzes text sentence by sentence from beginning to end to generate the dynamic impressions of the words in the text.
3. Without training or background knowledge request.

2 The Text Scanning Mechanism

2.1 Global and Local Word Impressions

Assuming that the scanning text has N sentences, and the scanning sentence is the k th sentence within a local range of size D (0<D N). The global range refers to the range from the first sentence to the k th sentence. The local range refers to the range from

1. the first sentence to the (k+D) th sentence if (k∨[1, D]),
2. the (k2D) th sentence to the (k+D) th sentence if (k ∨ [D+1, N2D]),
3. the (k2D) th sentence to the Nth sentence if (k ∨ [N2D+1, N]).

The left part of Figure 1 is an example of the global range and local range.

Readers have impressions of words, which keep changing while reading. Two kinds of impressions of words are distinguished in HTSM: Global Word Impression (GWI) and Local Word Impression (LWI). GWIk(i) represents the impression of word i generated within the global range while scanning the k th sentence. LWIk(i) represents the impression of word i generated within the local range while scanning the k th sentence. GWI and LWI are dynamic because HTSM constantly gets LWIs of words from the moving local range and accumulate the LWIs on the GWI of the words during scanning. The initial GWIs of words are set as 0.

HTSM calculates and records GWIs and LWIs of all words during scanning.

2.2 WordsÕ Global Relevancy and Local Relevancy

The calculation of GWIs and LWIs is based on the relevancy between words. Empiricists like David Hume think that people believe things are relevant when the things frequently appear in succession at logic, space, or time. In line with this idea, two words are regarded as relevant within a text if the two words frequently emerge in a common text unit (e.g., phrase, sentence, paragraph, chapter). We regard sentences as the basic units because words in a common sentence have greater relevancy than they are in different sentences. The following are two kinds of relevancy between words.

Definition 1. The global relevancy between two words, w1 and w2, GRk(w1, w2), represents the relevancy between the two words in the global range while scanning the k th sentence. It is measured by the number of sentences containing w1 and w2 in the global range.

Human also focus on local range while reading. So, two words may be weakly relevant in a local range while they have strong global relevancy. For example, given a text on play "Romeo and Juliet" and two words "Romeo" and "Juliet" have strong global relevancy, if there is a local range that only introduces Romeo and his families, the relevancy between "Romeo" and "Juliet" is weak within the local range. The local relevancy is defined as follows:

Definition 2. The local relevancy between two words w1 and w2, LRk,D(w1, w2), represents the relevancy between the two words in the local range while scanning the k th sentence. LRk,D(w1, w2) is calculated by the following equations:

where Nk,D denotes the ratio of local relevancy and global relevancy; NumSx,y(w1,w2) denodes the number of sentences containing w1 and w2 from the x th sentence to the y th sentence; Min() is a function that returns the smaller value; and r is an integer.

Equaltion 2 represents that the more times two words emerge within a local range, the bigger LR the two words have. The maximum value of two words' local relevancy is limited by the corresponding global relevancy. Meanwhile, the increase of local relevancy is fast if the corresponding global relevancy is high.

2.3 Two-Layer Word Network

HTSM is performed on a two-layer word network.

One layer is Global Word Network, formally described as GWNk(Vk, Ek, GWIk[], GRk[]), where k denotes the scanning sentence. Vk denotes a set of words from the global range. Two words w1 and w2 have an undirected link if GRk(w1, w2) is bigger than zero and Ek denotes the set of links. Every link in GWNk has a weight that equals to the corresponding global relevancy and GRk[] records the links' weights. Every word in GWNk has a weight within [0,+ ) that equals its GWI and GWIk[] records the words' weights.

The other layer is Local Word Network, formally described as LWNk (Vk, Ek, LWIk[], LRk[], D). k and D denote the local range. Vk in LWNk denotes the set of words in the local range. There is an undirected link between two words w1 and w2 if LRk,D(w1, w2) is bigger than zero and Ek in LWNk denotes the set of links. Every link in LWNk has a weight that equals to the corresponding local relevancy and LRk[] records the links' weights. Every word in LWNk has a weight within [0,+ ) that equals its LWI and LWIk[] records the words' weights.

GWN and LWN are fully connected. Figure 1 shows an example of a two-layer word network while scanning the k th sentence.

In HTSM, only nouns are considered because nouns directly reflect objects while the other types of words render objects.

Local word network

Figure 1. A two-layer word network generated from global range and local range.

2.4 Recall, Association and Forget Processes

Three processes occur while scanning: recall process, association process and forget process.

The previous memory of a word will be recalled if it is mentioned. So, a word's previous GWI will be regained in the recall process if a new sentence contains the word. Given a sentence which is the k th sentence and contains a word w, the GWI of w will reach the maximum value of GWIs in previous scanning process. The steps of recall process are as follows, where Max() is a function that returns the biggest value.

The recall process of k th sentence. Input: GWIk-1[] GWIs of nodes in GWNk-1, s the k th sentence Output: RPk-1[] GWIs of nodes in GWNk-1 after recall process Steps: For each element GWIk-1(i) in GWIk-1[] If (word i is in s) RPk-1(i)= Max(GWI1(i), GWI2(i),…, GWIk-1(i)); Else RPk-1(i)= GWIk-1(i); Return RPk-1[]

The maximum GWI will be regained after several times of appearances of the word. The recall process of words within a text is very fast during reading. So, the appearance times of regaining a word's maximum GWI is set as 1.

In the association process, words' LWIs influence each other through words' local relevancy. If two words have local relevancy and one of them is mentioned in text, human mind will associate the other word and the LWIs of both words are enhanced. For example, given a text describing Romeo and Juliet, the two words "Romeo" and "Juliet" have local relevancy, so that the LWI of "Juliet" increases once "Romeo" is mentioned. Figure 2 shows the association process of the k th sentence by using the text on the second world war (http://en.wikipedia.org/wiki/WWII).

Assuming that the k th sentence which contains words w1, w2,…, and wn, the association process is described as follows, where � is set as the number of nouns in the k th sentence.

The association process of the k th sentence. Input: the k th sentence containing words w1,w2,…,wn Output: LWIk[] (W[i] denotes the weight of word i) Steps: Set nodes in LWNk unassociated and their weights as 0. Set two node sets T and R; For each nodes t in {w1,w2,…,wn} W[t] = W[t] +�; Add t into T and set t associated; While (T is not empty) For each node i in T //find the nodes that will receive weight If (the weight of i is bigger than MIN) For each node j in the neighbors of i If (j is unassociated) Add j into R; Set j associated; For each node i in T //propagate weight For each node j in R If (LRk(i, j)>0) W[j] = W[j]+ PW(i j); //PW(i j) is calculated in equation 3. Else continue; W[i] = W[i]*(1/Υ); //Υ is remain ratio. T=R; Clear R; Output LWIk[] as the weights of nodes W[];

In equation 3, j denotes a neighbor word of i; PW(i j) denotes the weight propagated from i to j; LRk,D(i, j) denotes the local relevancy between i and j after scanning the k th sentence. MIN is a threshold that the propagated weight lower than MIN will be ignored. Υ is a remain ratio that a word will keep 1/Υ weight and propagate (1-1/Υ) weight to neighbors. Υ is usually set as 2.

Forget process refers to the following phenomenon: A word's GWI gradually fades out if the word is not mentioned in a certain time.

The following are three factors determining a word's forget process: (1) Forget time, which refers to the number of sentences from the sentence containing the word scanned last time to the scanning sentence. For example, assuming that the i th sentence and the (i+j) th sentence contain a common word w and the sentences between the two sentences do not contain w, then w's forget time is j21 when HTSM scans the (i+j21) th sentence and is 0 when HTSM scans the (i+j) th sentence. The bigger the forget time is, the smaller GWI of a word has. (2) Repeating times, which refers to the number of sentences containing the word before the scanning sentence. Words will not be forgotten quickly if it has been mentioned many times. (3) Link diversity, which refers to the number of links between the word and its neighbors. In psychology, a thing is hardly forgotten if it is linked to many other things and easy to fade out if it has few links to other things. Therefore, in GSTM, a word will be hardly forgotten if its link diversity is high and will quickly fade out if its link diversity is low.

Combined the three factors, the forget process of word i is calculated by the following equations:

and

In equation 4, FT denotes the forget time; CForget is the coefficient that reflects the speed of forget process. � determines the lowest value of CForget. For example, CForget is within [1/2, 1) when �=2 and CForget is within [1/4, 1) when �=4. If FT=0, the forget process does not occur. In equation 5, NLk(i) denotes the number of links between i and its neighbors after scanning the k th sentence. There is a smallest value of � (denoted as MIN�) because people do not forget things immediately after seeing them. The usual value of MIN� is 5.

Equation 4 depicts that the impression of a word fades slowly at first, then become faster with the growth of FT, and slows down at last. Figure 3 shows the change of CForget with different �. The bigger � is, the bigger FT is needed to get into fast forget speed. So the impression of a word fades slowly with the growth of �.

Equation 5 implies the influence of repeating times and link diversity because of the following reasons:

1. Once a sentence contains word i, the global relevancies between i and some of its neighbors will increase. In equation 5, the numerator increases much faster than the denominator when some links' global
2. relevancies are enhanced. Therefore � increases when repeating times increases.
3. Given a fixed value of �GRk(i, j) in equation 5, the more links word i has, the bigger �(1+GRk(i, j)) is and it grows much faster than NLk(i). Therefore � increases when link diversity increases.

Combined the three processes in HTSM, the integrated calculation is shown in Figure 4.

Equation 6 calculates words' GWIs. Notice that the values in LWIk[] are greater than or equal to 0 and the values in WFk[] are less than or equal to 0.

2.5 GWI Curve and GWIV Curve

A word's global word impression curve (GWIC) is a curve that records the word's GWIs under the co-influence of recall process, association process and forget process. Figure 5 shows an example of GWIChitler on word "Hitler" from an article in http://en.wikipedia.org/wiki/WWII. The remaining GWI of a word after a certain number of sentences without mentioning the word increases with the mention times of the word. For example, in Figure 5, the GWIs around B are bigger than the GWIs around A. Based on GWIC, global word impression variation curve (GWIVC) depicts the variation of GWIC and can be defined as follows:

Where GWIVCi(k) denotes the value of GWIVC on word i after scanning the k th sentence.

Figure 6 illustrates an example of GWIVC on word "Hitler" in the article.

The calculation of HTSM is fast because: (1) it is not iterative and each weight propagation process will terminate soon; and, (2) it does not need re-scanning the previous sentences while scanning a new sentence. The time complexities of recall process and forget process are less than the time complexity of association process. So, the upper bound of time complexity of HTSM is O(3*N*W*logΥ(W/MIN)), where N is the total number of sentences in a text; W is the number of words in the longest sentence in the text; Υ and MIN are the coefficients in equation 3. W, Υ and MIN can be approximately considered as constant. So, the time complexity is approximately linear and is acceptable in most applications.

3 Applications

3.1 Information Extraction Based on Keywords

A useful application of HTSM is information extraction. Users can obtain needed information from text by inputting several keywords representing their preferences. This issue can be handled by the comparison of different contributions from each sentence to the keywords' GWIVC. A method based on HTSM is as follows:

1. Calculate the GWIVC of every keyword.
2. Obtain the integrated GWIVC on the keyword set. The horizontal coordinates of integrated GWIVC are sentences; the longitudinal coordinates are summation of the values in every keywords' GWIVCs.
3. Find the first N values in the integrated GWIVCs and extract the corresponding sentences as output (N is the extraction ratio that can be adjusted by users).

An experiment is designed to verify the effectiveness of the method. 100 pieces of news on different topics are randomly chosen from DUC05 and DUC06 (http://www-nlpir.nist.gov/projects/duc/data.html). For each piece of news, five nouns with the top-five highest frequencies are chosen to be the keywords of the piece of news. Each piece of news can be considered as an ideal result of an extraction by using its corresponding keywords. 100 extractions are performed. The extraction ratio of an extraction is set as n while extracting a piece of news containing n sentences. The match ratio of an extraction is defined as: MR = the number of common sentences in the ideal result and the extracted result / the number of sentences in the ideal result. Figure 7 shows the MRs of 100 extractions.

In Figure 7, most values are above 80% and the average value is 87.3%. The extracted pieces of news basically match the ideal results. So, the method of information extraction based on HTSM is effective.

In HTSM, different values of D lead to different effects. The effect can be studied by setting different values. Considering the following cases:

(1) D equals to the number of sentences in a text. Words' weights are inclined to be propogated between words with high global relevancies. It may be inappropriate with the meaning of text. For example, given a text that contains 200 sentences and describes three person A, B and C, the first 90 sentences describe the things happened between A and B, 91-120 sentences describe things happened between A and C, 121-200 sentences describe things happened between A and B. So, when a sentence mentions A within 91-120 sentences, the weight of A should mainly flow to C compared to B. However, if D equals to the number of sentences, the weight from A will mainly flow to B according to equation 3. More generally, the inappropriate weight flow occurs when D is too big to reflect the content's meaning.

(2) D equals to 1. In this case, weights is only propagated between words in common sentences which limits the association process. The inappropriate weight flow occurs when D is too small.

A suitable D exists between the two extreme situations. We perform an experiment on the first 20 pieces of news with different values of D. Figure 8 shows the average match ratios while giving D a value from 1 to 400. We can see that the average match ratios are higher than others when D approximately equals 20. The best result is 92.3% when D equals to 18. The average match ratios become low, unstable and irregular when D is from 50 to 400 because D may or may not reflect the meaning of text. Figure 9 shows the results of another experiment on re-picked 20 pieces of news. The best result is 91.7% when D equals to 25. Therefore, different values of D are suitable for different text and generates different effects for an application. D can be adjusted to reach the best result in an application.

3.2 Keyword Extraction

Keyword extraction is to extract important words from text. In HTSM, the importance of a word is measured by the summation of its GWIs as follows:

Where IMk(i) denotes the importance of word i after scanning the k th sentence. Thus, the keywords can be extracted by sorting their importance.

The proposed method has the following characteristics: (1) The extracted keywords change with the scanning process. (2) The importance of a word increases when the frequency of the word increases. (3) Given a text and two words i and j with same frequency, despite other factors, i should be more important than j if j is concentrated in some areas within the text and i is evenly distributed over the text. Equation 8 implies the characteristic because the recall process on i will bring more importance compared to the recall process on j. (4) The importance of a word increases when the local relevancy between the word and its neighbors increase because the word receives weight from other words through association process.

An experiment is designed to demonstrate the effectiveness of the proposed method. Three groups of text are chosen. Group 1 includes 20 technical papers on AI; group 2 includes 20 web pages from Wikipedia on different topics; group 3 includes 20 pieces of news from DUC06 on different topics. Annotators manually label each article with 15 keywords which is considered as the ideal results. The label words must be nouns in the text. Three methods are tested: tf, tf-idf, and ours. tf denotes the method that extracts keywords according to their term frequencies. tf-idf can distinguish a word's importance to a text in a set of texts. In the experiment, tf-idf is separately performed on the three groups. 15 keywords are extracted for each text. The match ratio of keywords of a text is defined as: MRkeyword = the number of words in the intersection of the ideal result and the extracted keywords / the number of words in the ideal result. Figure 10 shows the results of the experiment.

The experiments show that HTSM is much better than tf and is similar to tf-idf. So it is effective for keyword extraction. Compared to tf-idf, HTSM can eliminate keywords with concentrated distributions because of the third characteristic and discover important keywords with low frequencies because of the fourth characteristic.

4 Conclusions and Future Work

This paper proposes a text scanning mechanism for generating the dynamic impressions of words in text by simulating human reading process. It incorporates recall, association and forget processes involved in reading. Experiments show that it is effective in different applications. The mechanism provides a new method for intelligent text processing. We are working on a methodology for applying it to general text processing applications.

Acknowledgement

Research supported by National Science Foundation of China (61075074) and fundings from Nanjing University of Posts and Telecommunications. * Correspondence author.