WoZ Simulation of Interactive Question Answering

QACIAD (Question Answering Challenge for Information Access Dialogue) is an evaluation framework for measuring interactive question answering (QA) technologies. It assumes that users interactively collect information using a QA system for writing a report on a given topic and evaluates, among other things, the capabilities needed under such circumstances. This paper reports an experiment for examining the assumptions made by QACIAD. In this experiment, dialogues under the situation that QACIAD assumes are collected using WoZ (Wizard of Oz) simulating, which is frequently used for collecting dialogue data for designing speech dialogue systems, and then analyzed. The results indicate that the setting of QACIAD is real and appropriate and that one of the important capabilities for future interactive QA systems is providing cooperative and helpful responses.

Introduction
Open-domain question answering (QA) technologies allow users to ask a question using natural language and obtain the answer itself rather than a list of documents that contain the answer (Voorhees et al.2000). While early research in this field concentrated on answering factoid questions one by one in an isolated manner, recent research appears to be moving in several new directions. Using QA systems in an interactive environment is one of those directions. A context task was attempted in order to evaluate the systems' ability to track context for supporting interactive user sessions at TREC 2001 (Voorhees 2001). Since TREC 2004, questions in the task have been given as collections of questions related to common topics, rather than ones that are isolated and independent of each other (Voorhees 2004). It is important for researchers to recognize that such a cohesive manner is natural in QA, although the task itself is not intended for evaluating context processing abilities since, as it is given the common topic, sophisticated context processing is not needed.
Such a direction has also been envisaged as a research roadmap, in which QA systems become more sophisticated and can be used by professional reporters and information analysts (Burger et al.2001). At some stage of that sophistication, a young reporter writing an article on a specific topic will be able to translate the main issue into a set of simpler questions and pose those questions to the QA system.
Another research trend in interactive QA has been observed in several projects that are part of the ARDA AQUAINT program. These studies concern scenario-based QA, the aim of which is to handle non-factoid, explanatory, analytical questions posed by users with extensive background knowledge. Issues include managing clarification dialogues in order to disambiguate users' intentions and interests; and question decomposition to obtain simpler and more tractable questions (Small et al.2003) (Hickl et al.2004).
The nature of questions posed by users and patterns of interaction vary depending on the users who use a QA system and on the environments in which it is used (Liddy 2002). The user may be a young reporter, a trained analyst, or a common man without special training. Questions can be answered by simple names and facts, such as those handled in early TREC conferences (Chai et al.2004), or by short passages retrieved like some systems developed in the AQUAINT program do (Small et al.2003). The situation in which QA systems are supposed to be used is an important factor of the system design and the evaluation must take such a factor into account. QACIAD (Question Answering Challenge for Information Access Dialogue) is an objective and quantitative evaluation framework to measure the abilities of QA systems used interactively to participate in dialogues for accessing information (Kato et al.2004a) (Kato et al.2006). It assumes the situation in which users interactively collect information using a QA system for writing a report on a given topic and evaluates, among other things, the capabilities needed under such circumstances, i.e. proper interpretation of questions under a given dialogue context; in other words, context processing capabilities such as anaphora resolution and ellipses handling.
We are interested in examining the assumptions made by QACIAD, and conducted an experiment, in which the dialogues under the situation QACIAD assumes were simulated using the WoZ (Wizard of Oz) technique (Fraser et al.1991) and analyzed. In WoZ simulation, which is frequently used for collecting dialogue data for designing speech dialogue systems, dialogues that become possible when a system has been developed are simulated by a human, a WoZ, who plays the role of the system, as well as a subject who is not informed that a human is behaving as the system and plays the role of its user. Analyzing the characteristics of language expressions and pragmatic devices used by users, we confirm whether QACIAD is a proper framework for evaluating QA systems used in the situation it assumes.
We also examine what functions will be needed for such QA systems by analyzing intelligent behavior of the WoZs.

QACIAD and the previous study
QACIAD was proposed by Kato et al. as a task of QAC, which is a series of challenges for evaluating QA technologies in Japanese (Kato et al.2004b). QAC covers factoid questions in the form of complete sentences with interrogative pronouns. Any answers to those questions should be names. Here, "names" means not only names of proper items including date expressions and monetary values (called "named entities"), but also common names such as those of species and body parts. Although the syntactical range of the names approximately corresponds to compound nouns, some of them, such as the titles of novels and movies, deviate from that range. The underlying document set consists of newspaper articles. Being given various opendomain questions, systems are requested to extract exact answers rather than text snippets that contain the answers, and to return the answer along with the newspaper article from which it was extracted. The article should guarantee the legitimacy of the answer to a given question.
In QACIAD, which assumes interactive use of QA systems, systems are requested to answer series of related questions. The series of questions and the answers to those questions comprise an information access dialogue. All questions except the first one of each series have some anaphoric expressions, which may be zero pronouns, while each question is in the range of those handled in QAC. Although the systems are supposed to participate in dialogue interactively, the interaction is only simulated; systems answer a series of questions in batch mode. Such a simulation may neglect the inherent dynamics of dialogue, as the dialogue evolution is fixed beforehand and therefore not something that the systems can control. It is, however, a practical compromise for an objective evaluation. Since all participants must answer the same set of questions in the same context, the results for the same test set are comparable with each other, and the test sets of the task are reusable by pooling the correct answers.
Systems are requested to return one list consisting of all and only correct answers. Since the number of correct answers differs for each question and is not given, a modified F measure is used for the evaluation, which takes into account both precision and recall.
Two types of series were included in the QA-CIAD, which correspond to two extremes of information access dialogue: a gathering type in which the user has a concrete objective such as writing a report and summary on a specific topic, and asks a system a series of questions related to that topic; and a browsing type in which the user does not have any fixed topic of interest. Although the QA-CIAD assumes that users are interactively collecting information on a given topic and the gatheringtype dialogue mainly occurs under such circumstances, browsing-type series are included in the task based on the observation that even when focusing on information access dialogue for writing reports, the systems must handle focus shifts appearing in browsing-type series. The systems must identify the type of series, as it is not given, although they need not identify changes of series, as the boundary is given. The systems must not look ahead to questions following the one currently being handled. This restriction reflects the fact that the QACIAD is a simulation of interactive use of QA systems in dialogues.
Examples of series of QACIAD are shown in Fig The evaluation of QA technologies based on QA-CIAD were conducted twice in QAC2 and QAC3, which are a part of the NTCIR-4 and NTCIR-5 workshops 1 , respectively (Kato et al.2004b) (Kato et al.2005). It was one of the three tasks of QAC2 and the only task of QAC3. On each occasion, several novel techniques were proposed for interactive QA.
Kato et al. conducted an experiment for confirming the reality and appropriateness of QACIAD, in which subjects were presented various topics and were requested to write down series of questions in Japanese to elicit information for a report on that topic (Kato et al.2004a) (Kato et al.2006). The report was supposed to describe facts on a given topic, rather than state opinions or prospects on the topic. The questions were restricted to wh-type questions, and a natural series of questions that may contain anaphoric expressions and ellipses was con-

Series 30002
What genre does the "Harry Potter" series belong to? Who is the author? Who are the main characters in the series? When was the first book published? What was its title? How many books had been published by 2001? How many languages has it been translated into? How many copies have been sold in Japan?

Series 30004
When did Asahi breweries Ltd. start selling their low-malt beer? What is the brand name? How much did it cost? What brands of low-malt beer were already on the market at that time? Which company had the largest share? How much low-malt beer was sold compared to regular beer? Which company made it originally?

Series 30024
Where was Universal Studio Japan constructed? What is the nearest train station? Which actor attended the ribbon-cutting ceremony on the opening day? Which movie that he featured in was released in the New Year season of 2001? What movie starring Kevin Costner was released in the same season? What was the subject matter of that movie? What role did Costner play in that movie? Figure 1: Examples of Series in QACIAD structed. Analysis of the question series collected in such a manner showed that 58% to 75% of questions for writing reports could be answered by values or names; a wide range of reference expressions is observed in questions in such a situation; and sequences of questions are sometimes very complicated and include subdialogues and focus shifts. From these observations they concluded the reality and appropriateness of the QACIAD, and validated the needs of browsing-type series in the task.
One of the objectives of our experiment is to confirm these results in a more realistic situation. The previous experiment setting is far from the actual situations in which QA systems are used, in which subjects have to write down their questions without getting the answers. Using WoZ simulation, it is confirmed whether or not this difference affected the result. Moreover, observing the behavior of WoZs, the capabilities and functions needed for QA sys-tems used in such a situation are investigated.

Setting
Referring to the headlines in Mainichi and Yomiuri newspapers from 2000 and 2001, we selected 101 topics, which included events, persons, and organizations. On each of those topics, a summary of between 800 and 1600 characters long and an abstract of around 100 characters long were constructed using a full text search system on the newspaper articles. 2 Four experts shared this preparation work. Twenty topics were selected from among the original 101 on the basis that enough information was gathered and compiled into the summary. 3 The topics consisted of 5 persons, 2 organizations, 7 events, 5 artifacts, and 1 syndrome, which include Mr. Colin Powell, Charles, Prince of Wales, An accident of a Russian nuclear-powerd submarine, Concorde, "Harry Potter", and Windows XP.
The four experts who shared the preparation work acted as a WoZ in the simulated QA systems, and each expert participated in dialogues on the topic for which she/he wrote the summary and abstract, and tried to answer questions from users using the summary, a full text search system, and her/his memory.
Six subjects participated in the experiment and 10 topics were assigned to each subject. That is, each topic was handled by three subjects. The subjects behaved as users of simulated QA systems. Presented with the topic and abstract, the subjects were directed to think about questions beforehand assuming that they had to write a report on that topic, and then they participated in an information access dialogue with the "QA system." The suggested number of questions for each topic was around 10.
The dialogues were conducted through keyboards and character displays. The subjects were told that the system could answer only simple factoid questions, and the WoZs were instructed not to answer complicated questions such as asking for reasons and opinions. No restrictions on the usage of language expressions were imposed but were left to the discretion of the WoZs, though canned phrases 2 Those lengths of Japanese texts roughly correspond to 300 to 600 words and 40 words of English text, respectively. 3 We prepared 101 topics to meet the additional needs of other experiments. It is absolutely not the case that only 20 out of 101 were acceptable for our experiments.  such as "Please wait a moment" and "Sorry, the answer could not be found" were prepared in advance. The WoZs were also instructed that they could clarify users' questions when they were ambiguous or vague, and that their answers should be simple but cooperative and helpful responses were not forbidden. An example of the dialogues collected is shown in Figure 2. In the figure, SYS stands for utterances of the QA system simulated by a WoZ and USR represents that of the user, namely a subject. In the rest of the paper, these are referred to as system's utterances and user's utterances, respectively.

Coding and Results
Excluding meta-utterances for dialogue control such as "Please wait a moment" and "That's all," 620 pairs of utterances were collected, of which 22 system utterances were for clarification. Among the remaining 598 cases, the system gave some answers in 502 cases, and the other 94 utterances were negative responses: 86 utterances said that the answer could not found; 10 utterances said that the question was too complicated or that they could not answer such type of question.

Characteristics of questions and answers
The syntactic classification of user utterances and its distribution is shown in Table 1. The numbers in   (1) parentheses are numbers of occurrences. In spite of the direction of using wh-type questions, more than 10% of utterances are yes-no questions and imperatives for requesting information. Most of the user responses to clarification questions from the system are rephrasing of the question concerned; only one response has a declarative form. Examples of rephrasing will be shown in section 4.3. The classification of user questions and requests according to the subject asked or requested is shown in Table 2; the classification of system answers according to their syntactic and semantic categorization is shown in Table 3. In Table 2, the classification of yes-no questions was estimated based on the information provided in the helpful responses to those. The classification in Table 3 was conducted based on the syntactic and semantic form of the exact part of the answer itself rather than on whole utterances of the system. For example, the categorization of the system utterance "He was born on April 5, 1935," which is the answer to "When was Mr. Colin Powell born?" is not a sentence but a date expression.

Pragmatic phenomena
Japanese has four major types of anaphoric devices: pronouns, zero pronouns, definite noun phrases,  and ellipses. Zero pronouns are very common in Japanese, in which pronouns are not apparent on the surface. As Japanese also has a completely different determiner system from English, the difference between definite and indefinite is not apparent on the surface, and definite noun phrases usually have the same form as generic noun phrases. Table 4 shows a summary of such pragmatic phenomena observed. The total number is more than 620 as some utterances contain more than one anaphoric expression. "How many crew members were in the submarine when the accident happened?" is an example of such a question with multiple anaphoric expressions. Among 203 questions with no reference expression, 60 questions (30%) are the first one of a series of utterances on the same topic. The others are divided into two cases. In the first and major case, the current foci appear literally rather than in pronouns or definite noun phrases. The second case, which is relatively minor, is the beginning of and the resume from a subdialogue. For example, when a user himself resumed talking about Charles, Prince of Wales after a few questions about his children, the user used a literal expression like "Who is the long-term partner of Charles, Prince of Wales?"; after talking about the details of the accident, a user asked "What is the major characteristic of Concorde?" Out of 437 reference expressions excluding ellipses in Table 4, 94 expressions (22%) refer to items other than the global topic. Moreover, 76 expressions of those (81%) are a sole reference expression in the utterance. The existence of questions without referring to the global topic, accompanied with the existence of some questions with no reference expression, means that the focus shifts in those dialogues, and then the local focus can differ from the global topic.

Clarifications
As mentioned above, only 22 clarification utterances were observed in the experiment. They are categorized into those asking about an ambiguous referent (13 utterances) and those asking about a vague question subject (9 utterances

Cooperative and helpful responses
Rather than simple and literal answers to the users' questions and requests, cooperative and helpful responses, in which, for example, information not requested directly by a user was additionally provided (Kaplan 1983), were observed frequently. The results of analyzing such cooperative and helpful behavior in the system responses are shown in Table  5. Questions asking reasons, procedures, situations, definitions, descriptions or explanations, which are categorized into the last three categories except others in Table 2, were excluded from this analysis, since for those questions it is difficult to judge objec- tively whether some information is additional or not and, in addition, most of those are out of the scope of QACIAD, which is our main interest. Table 5 shows the number of occurrences and its percentage among positive responses. Sometimes, more than one behavior was observed in one utterance. 148 utterances out of 334 positive responses (44%) contained some helpful behavior. The definitions and manually constructed examples of cooperative and helpful behavior listed in Table 5 are shown below.

Providing additional information
Information not requested directly from a user is additionally provided. Elaboration of subject A relatively vague subject of a question is elaborated and made concrete. In the following example, a question with a vague expression, "how well" is answered by a value as a concrete statistic.
USR: How well did the movie do?
SYS: In the US, box-office sales reached 188 million dollars in the first 10 days after release.
Providing alternative information Rather than exact information a user requested, alternative related information is provided. An alternative may be proposed by relaxing the condition imposed by the user. In the following example, attendance figures were altered to box-office sales.
USR: How many people went to the movie? SYS: In the US, box-office sales reached 188 million dollars in the first 10 days after release.
Exemplification Instead of a comprehensive list or abstracted general description, some major instances are listed.
USR: What kinds of character goods are on sale?
SYS: Stuffed owls, uniforms for schools of witchcraft and wizardry, and so on.
Providing speculation Rather than fact, speculations and opinions are provided, which can be considered a special case of providing alternative information. Although there are few cases of such behavior in Table 5, there were many such answers in response to questions asking for reasons and situations.
SYS: It is surmised that torpedoes in the shed at the fore exploded.
Detecting and correcting erroneous user assumptions is a famous helpful behavior discussed in the literature (Pollack 1989) (Kaplan 1983). Only two occurrences of such behavior were observed, one of which is shown below. USR: How long did it take from the explosion until the shipwreck? SYS: The explosion happened while the submarine was going down, and ...

Discussion
The analysis of dialogue collected by the WoZ simulation showed very similar results to those obtained in a previous study, in which sequences of questions were written down by subjects without knowing the answers to questions. That is, as shown in Table 2, when users asked questions to get information for a report, the number of why-questions was relatively small. Moreover, there were fewer questions requesting an explanation or definition than expected, probably because definition questions such as "Who is Mr. Colin Powell?" were decomposed into relatively concrete questions such as those asking for his birthday and birthplace. The remainder (65%) could be answered in values and names. Table 3 indicates that 62% of the questions in our experiments were answered by values or names. If compound nouns describing events or situations, which are usually distinguished from names, are considered to be in the range of answers, the percentage of answerable questions reaches 68%. From these results, the setting of QACIAD looks realistic where users write reports interacting with a QA system handling factoid questions that have values and names as answers.
A wide range of reference expressions is observed in information access dialogues for writing reports. Moreover, our study confirmed that those sequences of questions were sometimes very complicated and included subdialogues and focus shifts. It is expected that using an interactive QA system that can manage those pragmatic phenomena will enable fluent information access dialogue for writing reports. In this sense, the objective of QACIAD is appropriate.
It could be concluded from these results that the reality and appropriateness of QACIAD was reconfirmed in a more realistic situation. And yet suspicion remains that even in our WoZ simulation, the subjects were not motivated appropriately, as suggested by the lack of dynamic dialogue development in the example shown in Figure 2. Especially, the users often gave up too easily when they did not obtain answers to prepared questions. 4 The truth, however, may be that in the environment of gathering information for writing reports, dynamic dialogue development is limited compared to the case when trained analysts use QA systems for problem solving. If so, research on this type of QA systems represents a proper milestone toward interactive QA systems in a broad sense.
Another finding of our experiment is the importance of cooperative and helpful responses. Nearly half of WoZ utterances were not simple literal responses but included some cooperative and helpful behavior. This situation contrasts with a relatively small number of clarification dialogues. The importance of this behavior, which was emphasized in research on dialogues systems in the 80s and 90s, was reconfirmed in the latest research, although question-answering technologies were redefined in the late 90s. Some behavior such as providing alternative information could be viewed as a second-best strategy of resource-bounded human WoZs. Even so, it is impossible to eliminate completely the need for such a strategy by improving core QA technologies. In addition, intrinsic cooperative and helpful behavior such as providing additional information was also often observed. These facts, accompanied by the fact that such dialogues are perceived as fluent and felicitous, suggest that the capability to behave cooperatively and helpfully is essential for interactive QA technologies.

Conclusion
Through WoZ simulation, the capabilities and functions needed for interactive QA systems used as a participant in information access dialogues for writing reports were examined. The results are compatible with those of previous research, and reconfirmed the reality and appropriateness of QACIAD. A new finding of our experiment is the importance of cooperative and helpful behavior of QA systems, which was frequently observed in utterances of the WoZs who simulated interactive QA systems. Designing such cooperative functions is indispensable. While this fact is well known in the context of past research on dialogue systems, it has been reconfirmed in the context of the latest interactive QA technologies.


A Dictionary Model for Unifying Machine Readable Dictionaries and Computational Concept Lexicons

The Language Grid, recently proposed by one of the authors, is a language infrastructure available on the Internet. It aims to resolve the problems of accessibility and usability inherent in the currently available language services. The infrastructure will accommodate an operational environment in which a user and/or a software agent can develop a language service that is tailored to specific requirements derived from the various situations of intercultural communication. In order to effectively operate the infrastructure, each atomic language service has to be discovered by the planner of a composite service and incorporated into the composite service scenario. Meta-description of an atomic service is crucial to accomplish the planning process. This paper focuses on dictionary access services and proposes an abstract dictionary model that is vital for the accurate meta-description of such a service. In principle, the proposed model is based on the organization compatible with Princeton WordNet. Computational lexicons, including the EDR dictionary, as well as a range of human monolingual/bilingual dictionaries are uniformly organized into a WordNet-like lexical concept system. A modeling example with a few dictionary instances demonstrates the fundamental validity of the model.

Introduction
Several language services are being made available on the Internet. Some of the representative types of language services include text translation and dictionary access. To help reduce language barriers that prevent smooth and effective communication, it is only natural to adopt these services in various situations of intercultural collaboration. The reality, however, proves to be different; it is substantially difficult for a user to find a language service that precisely meets his/her requirements that emerge from communicative situations. Furthermore, it is usually impossible for a user to newly define or create such a language service. There exist problems of accessibility and usability (Ishida, 2006).
The Language Grid recently proposed by Ishida (2006) is essentially a language infrastructure available on the Internet. It aims to resolve the problems by accommodating an operational environment in which a user, as well as a software agent, can develop a language service that is tailored to specific requirements by developing appropriate atomic language services and coordinating them properly.
In order to achieve this goal, we have to solve a variety of problems, ranging from a service protocol that was optimized for efficient language service execution to higher level management functions that deal with intellectual property rights and/or pricing policies. However, one of the most essential issues among them is the development of a planning mechanism that will enable a user/agent to define a composite language service effectively. With the planning mechanism, a user/agent will be able to create a plan or scenario that specifies the execution of appropriate atomic services in a proper arrangement, given a situation in which each atomic service is adequately described. This description, known as metadata, should be provided based on an ontology that ensures a common understanding between users and agents (Buietlaar, 2003). This paper concentrates on dictionary access services, and proposes a unified abstract dictionary model that can represent a range of machine-readable human dictionaries and computational concept lexicons 1 . The model will provide us with a strong foundation on which we can accurately meta-describe dictionary/lexicon language resources that are the essential components of any dictionary service. In addition, semantic wrappers for dictionary services could be efficiently generated by referring to model-based meta-descriptions.
The remainder of this paper is organized as follows. Section 2 outlines the language grid that motivates the reported work, and discusses the fact that dictionary services are in high demand in several situations of intercultural collaboration. Section 3 describes in detail the types and instances of the language resources that are being considered in the language grid. Section 4 proposes an abstract dictionary model and presents a modeling example. Section 5 discusses several research issues while referring to related works. Finally, concluding remarks are presented in section 6.

Overview of the Language Grid
Figure 1 exemplifies an imaginary organization of the language grid in terms of its architecture (Ishida, 2006). As shown in the figure, the language grid has two dimensions: "horizontal" and "vertical." The horizontal dimension is associated with repertoires of languages, whereas the vertical dimension represents its application fields/purposes. Ishida (2006) designates the former as "standard languages" and the latter as "community languages." Figure 1: Language Grid Architecture (Ishida, 2006) As implied in Figure 1, the key to the success of the language grid scenario is the extent to which we can effectively define a composite component. An example of a composite service shown in Figure 1 is "Japanese WordNet"; a dictionary service with which users can access a Japanese concept lexicon (EDR, 2003) like a Japanese equivalent of the English WordNet (Fellbaum, 1998). It is possible to achieve this by coordinating an EDR dictionary access service with a WordNet consultation service, probably with the help of a Japaneseto-English bilingual dictionary service. Ishida (2006) describes some pilot studies that involve a few NPO-based communities that are planned such that requirements can be derived from the communities to the language grid. The application fields of the studies range from medical interpretation, children's communication, and text-based communication in more than ten languages. While machine translation is the most required language service, dictionary access services could be more in demand. Off-the-shelf Machine Translation systems are still limited to popular language pairs, and often the MT output is insufficient, in particular, for rigorous communications such as those observed in medical interactions. In short, access to bilingual dictionaries is essential in the language grid. In addition, access to concept and/or monolingual dictionaries will be of great help to users to consult the meaning and usage of linguistic expressions. An appropriate combination of these dictionaries could be highly useful for the language grid users facing language barriers.

Metadata for a Dictionary Service
Figure 2 schematizes a general structure of dictionary services in the language grid. The user can access atomic dictionary services that were offered by the service providers. He/she can also consult a composite dictionary service that is made available by the language grid.
The metadata attached to an atomic service plays a central role in this configuration; the metadata is retrieved and utilized whenever a composite service is to be defined. It should not only describe the service grounding information (The OWL Service Coalition, 2003) but also disseminate semantic features of the associated language resources. The dictionary model proposed in this paper provides a strong foundation with which the semantic features can be properly encoded. In addition, this configuration may lead to the possibility of highly effective service deployment; the Web service wrapper of a dictionary service could be efficiently generated by a computational process that examines the metadata.

Dictionary/Lexicon Resources
As mentioned in 2.2, it will be effective for language grid users to be able to combine dictionaries primarily compiled for human use along with computational dictionaries, each classifying the concepts in a language.

Machine-Readable Dictionaries
Currently, there are numerous access services to the machine-readable version of a printed dictionary (MRD; Machine-Readable Dictionary) are available on the Web.
The following examples are taken from the "goo dictionary service" 2 that is based on Sanseido 3 dictionaries.  Figure 3 introduces an entry for the English word form "bank" as a noun in an English-to-Japanese bilingual dictionary 4 . It shows that there are five senses of the word, and each sense is separated by a semicolon. The word sense "financial institution" is listed in the first item. shows an entry for the same word form in an English dictionary service 5 . In this dictionary, there are five sense groups (one is marked as obsolete) or nine finegrained senses 6 . As typically shown in these examples, the information structure in an MRD entry is usually organized based on word senses, with more or less variations in the sense discrimination criteria that are dictionary dependent.

Computational Concept Dictionary
Most of the concept dictionaries have been compiled to be used by computer programs; hence, they could be termed as CCL (Computational Concept Lexicons). We focus on Princeton WordNet and EDR electronic dictionaries as representative and useful CCL resources.

WordNet
WordNet is a well-known and the most utilized lexical concept system for English. A lexical concept, represented as a node in the system, is defined by a set of word forms termed synset. The existence of a word in a synset implies that one of the word senses of the word form is associated with the lexical concept. Synsets are linked by various conceptual relations, such as hyponymy-hypernymy, meronymy-holonymy, and antonymy. A lexical node is annotated by a natural language description called gloss that substantially helps a user to understand the concept.

The EDR Electronic Dictionary
The EDR electronic dictionary is a dictionary system developed for NLP systems. The entire dictionary system consists of the following five large-scale dictionaries (or dictionary groups): Word (monolingual), Bilingual, Concept, Co-occurrence, and Technical Terminology dictionaries. The dictionaries are in Japanese and English. One of the most prominent features of the dictionary system is that every entry is associated with a unique concept identifier (CID), assuming that there is a unique concept system that covers both Japanese and English well. The Concept Classification dictionary, that is main component of the Concept dictionary, organizes the entire concept system into a taxonomy in which a node represents a concept, and a link connects the concepts that have a super-sub relation.
A concept node, if it can be defined, is labeled headconcept. Every entry in any monolingual and bilingual dictionaries in the EDR system is indexed by a headword and has a CID that links the headword to a concept node in the concept system. This enables us to form a pseudo-synset for a concept node. The headconcept together with the headwords in the EDR dictionaries can constitute a set of synonyms 7 .   Figure 5 depicts the logical structure of the EDR dictionary system. In Figure 5, there are two entries that share an identical CID: One entry is from the Japanese monolingual dictionary that has "j1" as its headword, and the other is from the English-to-Japanese bilingual dictionary that has "e1" as the headword. The concept node with this CID has an English headconcept "hc-e" as well as a Japanese headconcept "hc-j." These headwords and headconcepts form a pseudosynset "{hc-e, e1, hc-j, j1}" that represent the concept identified by the CID. This suggests that the logical structure of the EDR dictionary is almost compatible with the WordNet basic structure, implying that our dictionary model can be and should be based on the WordNet organization. It should be noted that the pseudo-synset is a language mixture of Japanese and English.

The Dictionary Model
This section presents the basic ideas of our dictionary model that represents the dictionary/lexicon instances covered by the language grid interests.

Overview of the Model
A similar lexicon model was recently proposed is the LMF (Lexical Markup Framework) (Francopoulo, 2006;ISO 24613, 2005). Our model has the three fundamental principles of the LMF: simplicity/clarity, universal expressiveness, and scalability. However, the LMF is described as "an abstract metamodel that provides a common, standardized framework for computational lexicons." This is in contrast with our model; our primary concern is to represent semantic/conceptual information that is useful for users of MRDs as well as for computational lexicons. Further, we would also like to represent the derived relations that are a result of computational processes that attempt to relate dictionary entries across different dictionaries. These derived relations can be accumulated within the language grid environment for future use. Therefore, the model should be able to encode these relations. Figure 6 introduces an example of dictionary modeling and also suitably provides an overview of our dictionary model. Figure 6 presents entries from four dictionaries/lexicons, which are in some way related to the English word "bank" in the form of a graph structure. The entire model space is divided into individual dictionary spaces. Each space represents an instance from a dictionary/lexicon and is summarized by a dictionary meta-description (as shown in gray boxes). The metadescription has not been provided in detail in this paper; however, it should include information such as dictionary ID (probably given in a URI (Uniform Resource Identifier)), type (monolingual, bilingual, concept, etc.), application domain, language(s), character encoding scheme, and inventory of lexical/semantic/conceptual relations. In addition, administrative information about the resource should also be included here.

Nodes
Nodes in a dictionary space are classified as a "lemma node," "sense node," or "concept node." Lemma node (the blue node in Figure 6): A lemma node is usually associated with the headword of a dictionary entry. It is identified by a canonical written form and part of speech, if defined. In addition, words in Japanese (or any other language similar to Japanese) are further defined by "katakana reading": reading of the written canonical form in katakana. This is necessary for a Japanese written form that has more than one pronunciation and associated meaning. In Figure 5, a lemma node is marked by a label with the form of "/canonicalform/part-of-speech/katakana-reading." A lemma node has one or more links to sense nodes since an entry in a dictionary can have several sub-entries, with each representing a distinct word sense. Sense node (the green node in Figure 6): A sense node stores most of the content described in the MRD. In other words, if it is from a bilingual dictionary, it stores gloss, usage examples, collocations, and translations. For a CCL like WordNet or EDR, a sense node is just an intermediate node that simply connects a lemma node to a concept node. Concept node (the orange node in Figure 6): The information associated with a lexical concept is encapsulated in a concept node. It stores gloss, usage examples, and semantic/conceptual relations, as described in the lexicon. The synset for a concept node is represented by the set of incoming links from the sense nodes.
In Figure 6, a sense/concept node is labeled by a synset and a gloss. The former is represented by "{ }," and the latter by "[ ]"; within the parentheses, the English and Japanese parts are separated by semicolons.
At present, we concentrate on semantic/conceptual information that may be useful in crosslanguage/intercultural communications. However, the following are the types of information that might further facilitate communications: information on etymology, phonology, morphology, syntax, and syntax-semantics linking. For instance, etymological information might be useful in explaining a highly culturally dependent concept that foreigners find difficult to understand. Further, phonological information, such as pronunciations, could be provided by recorded/synthesized voices in order to directly assist non-native users to speak. Information on syntax-semantics linking may provide users with finegrained knowledge to compose a fluent phrase.

Links
The fundamental relations between nodes in an initial dictionary model will be lemma-to-sense for most of the MRDs and sense-to-concept and concept-to-concept for the CCLs. These relations are identified by dictionary entry parsing or simple reformatting of the lexicon source data. Sometimes relations like antonyms or synonyms are explicitly described in a dictionary by using special symbols (e.g., ) that link two sense nodes.
As mentioned previously, some relations that cross dictionary spaces are identified as a result of a composite language service execution and can be attached to the entire dictionary space. These derived relations can be accumulated in the language grid environment and may be used in the future. In Figure 6, these relations are indicated by the dotted arrows. The following are the types of derived links: Lemma-to-lemma link: Equivalent relations of this type are monolingual and are identified by a string level matching process. Grammatical derivational relations can also be encoded with this type of link. Sense-to-sense link: Equivalent or near-equivalent relations of this type can either be monolingual or cross-lingual. In order to provide a composite language service like "Japanese-to-Arabic dictionary" by cascading a Japanese-to-English dictionary and an English-to-Arabic dictionary, we need to identify the optimal sense-to-sense relation between these dictionary entries and represent it with this type of link. Sense/concept-to-concept link: This type of relation is also monolingual or cross-lingual. However, crosslingual relations are more important in our context. Let us assume that we have to provide a composite language service like "Japanese WordNet" that looks for the most similar concept in Princeton WordNet when provided with a Japanese word. It is likely that we will first search for possible English senses in Japanese-to-English and/or English dictionaries and then align them with candidate concept nodes in the WordNet space. The discovered relations should be represented by this type of link.
Since most of the derived relations are identified by computational processes rather than by experts, we require a description for the derived link that indicates the manner in which the relation is reliable. This can be done by assigning weight values that reflect confidence and/or quality assessment of the process to the derived relational links. Another important issue is the inventory of the derived relations that will be defined probably by consulting the mapping relations in the EuroWordNet (Vossen, 2004).

Discussions
Several activities associated with the standardization of computational lexicons, such as MILE (Multilingual ISLE Lexical Entry) (Calzolari, 2002) and OLIF (Open Lexicon Interchange Format) (McCormick, 2005) have been reported. Among them, the LMF (Francopoulo, 2006;ISO 24613, 2005) is the most related work that is currently being pursued in ISO TC 37/SC 4. It adopts a two-layered approach; a "form" node provides access to information associated with a word form, whereas a "sense" node encodes its semantic/conceptual information. On the other hand, our model adopts a three-layered approach. A "lemma" node functions in almost the same manner as that of the "form node" in the LMF. In our model, a "sense" node is introduced to represent an MRD entry that is given according to the word senses, while a "concept" is employed to encode a lexical concept node in the CCLs. However, this difference is not innate; thus, a sense node in our model can be diverted into a concept node because any sense-to-concept relations are based on a one-to-one relation.
One of the problematic issues in dictionary modeling, particularly with cross-linguality, may be the problem of the "lexical gap" (Janssen, 2004). For example, the fourth sense of "bank" in the English-to-Japanese dictionary shown in Figure 6 has no direct translations in Japanese.
The translation provided in the entry is somewhat explanatory, roughly implying the "money of a gambling dealer." Thus, the sense node in the English-to-Japanese dictionary may not be able to find its corresponding node in any Japanese dictionary spaces. This sense is defined in WordNet (Ver.2.1) as the eighth sense of "bank," and explained as "the funds held by a gambling house or the dealer in some gambling games." However, given the scope of the language grid, this might not be a serious problem. The language grid is intended for use in intercultural communications. The explanatory translation may make complete sense to a Japanese user whenever he/she is on the comprehension side of the communication. In contrast, when he/she is on the production side, he/she may not necessarily choose the word "bank" to describe the sense of the "funds held by a gambling dealer" sense. Exact words such as "money of a gambling dealer" would be sufficient, even though it may not be very felicitous. Nevertheless, the lexical gap is certainly an important and interesting linguistic issue that emerges while detailing the dictionary model. We will eventually have to develop a way to deal with multi-word expressions that are used in explanatory translations.

Concluding Remarks
This paper proposed an abstract dictionary model that can represent machine-readable human dictionaries, such as monolingual and bilingual dictionaries, as well as computational concept dictionaries, such as Princeton WordNet or the EDR electronic dictionary. In principle, the model is based on the organization that is compatible with WordNet, insisting that the EDR dictionaries can also be reorganized into a WordNet-like lexical concept system. A modeling example with four dictionary instances was provided to demonstrate the fundamental validity of the model.
However, the proposed model is still in its early stage, and only a rough sketch of the model has been introduced in this paper. We will have to extend it to cover a wide range of dictionary/lexicon instances. We may have to refine it linguistically, particularly to deal with the lexical gaps. In the course of our study, we should be aware and should possibly cooperate with the ongoing standardization activities such as the LMF.
At the same time, we also have to accomplish several tasks to achieve the goals of the language grid. First, we should formalize the model and implement actual dictionary services by using the frameworks developed in the scope of the Semantic Web service. The work reported to represent WordNet with RDF/S and OWL (WordNet Task Force, 2004) will be helpful in achieving this goal. Second, we should apply computational processes to link lexical information in different dictionaries based mainly on word sense/lexical concepts. Studies that have achieved this task include Utiyama (1997), Chen (2002) and others. Further, to facilitate the deployment of dictionary access services in the language grid, we should provide a set of tools for efficiently constructing Web service wrappers. In an attempt to solve this problem, we may be able to adopt the ideas of "programming by demonstration" (Bauer, 2000) and "scheme-guided wrapper generation." (Meng, 2002)


Interaction between Lexical Base and Ontology with Formal Concept Analysis

An ontology describes conceptual knowledge in a specific domain. A lexical base collects a repository of words and gives independent definition of concepts. In this paper, we propose to use FCA as a tool to help constructing an ontology through an existing lexical base. We mainly address two issues. The first issue is how to select attributes to visualize the relations between lexical terms. The second issue is how to revise lexical definitions through analysing the relations in the ontology. Thus the focus is on the effect of interaction between a lexical base and an ontology for the purpose of good ontology construction. Finally, experiments have been conducted to verify our ideas.

Introduction
According to Gruber [1995]'s definition, an ontology can be seen as a catalog of the types of things that are assumed to exist in a domain of interest from the perspective of a person who uses a language for the purpose of talking about the domain. How to construct an ontology is a non-trivial task. An ontology is usually constructed either manually or semi-automatically. It is ideal if we can automatically construct an ontology according to the available data resources compiled by experts. A lexical base which contains lexical terms and explanatory notes can serve as such a resource. The lexical base collects a repository of words and can be seen as a machine-readable dictionary, which provides an index into human knowledge. However, a dictionary often gives independent definition of concepts without explicitly indicating their relationships with other concepts. Priss[2004] has pointed out that the construction of detailed lexica requires precise ontological information, and vice versa. Formal Concept Analysis (FCA) is a mathematical approach to data analysis based on the lattice theory which can provide a natural representation of hierarchies and classifications [Stumme 2002]. FCA can be used to model a lexical knowledge base and construct it as an ontology with clear structures. FCA has been chosen especially for the automatic construction of ontologies [Cimiano 2004]. Through the use of FCA, a lexical base can also be revised through analyzing the relations in the ontology. The improved lexical base can in turn further help the construction of ontology. In this paper, we will present the interaction between a lexical base and a domain ontology using FCA technique. The key to this project is that with the proper tool, not only lexical base can help domain experts to build an ontology, the tool with its visualization capability can also help to revise and fine tune the lexical base. The rest of this paper is organized as follows. Section 2 introduces the basic concepts. Section 3 describes the framework for the interaction between ontology construction and the improvement of a related lexical base using FCA. Section 4 describes how attributes are selected in FCA construction, and section 5 discusses how relationships among concepts are built. Section 6 explains the experiments and presents the evaluation results. Section 7 gives concluding remarks and future directions.

Ontology Definition
In this work, we define ontology as follows. Definition 1: An ontology, denoted by O, is defined by a quadruplet, O = (L, D, C, R), where L is a specific language, D is a specific domain, C is the set of concepts and R is the set of relations between concepts. Normally, in ontology construction, both L and D are already known because any construction method would be applied to a specific language, L, in a specific domain, D. Ontology construction methods aim at how to obtain the set of concept C and how to build the set of relationships R among concepts. The ontology in this paper refers to a formal ontology as described in [Sowa 2000], which is specified by a collection of names for formal concepts and relation types organized in partial ordering.

FCA Overview
FCA takes two sets of data, one is called the object set and the other is called the attribute set 1 , as well as a binary relationship between the data of the two sets, to form a formal context, according to which a so-called formal concept lattice is further constructed with a concept inclusion ordering. The definitions of formal context and formal concept in FCA are given in [Ganter 1999]. In FCA, a formal concept, as a node, has more attributes describing it than its super class concept. The more attributes a formal concept has, the fewer objects it owns. Thus, a formal concept in the lattice having more attributes and less objects than a super class concept. The whole formal concept lattice satisfies the partial ordering relationship. It is easy to see that the FCA model can be used to represent an ontology where the formal concepts in FCA correspond to the concept set C for a specific language L and a specific domain D. However, the issue is what should be the set of attributes used to describe these concepts and we also need to know how to acquire the mapping between the partial ordering relationship in FCA and R.

Lexical Base
A lexical base provides a set of terms with detailed explanation, which is formalized as follows: where t i is a term and e i is the corresponding verbal explanation or definition which describes the characteristics of t i . To construct the formal context of FCA, all the t i can serve as formal objects, and attributes can be extracted from e i . For the Chinese language, we adopt the HowNet [Dong 2000] Lexicon as the seed to construct our lexical base in which terms are described formally by several sememes (the smallest semantic unit), which can serve as attributes in FCA. For example, "解码 (decode)" is a term 2 defined by a set of sememes "computer|电脑", "translate|翻译" and "software|软件". Figure 1 shows the interaction framework of ontology construction and the lexical base HowNet lexicon. We take HowNet as the starting point to construct an ontology step by step. First, we use information gain as the means to choose the sememes with discriminative power, as the set of attributes. We then construct a concept context using the FCA model to obtain a draft ontology. Through the analysis of the relations obtained from this draft ontology, we can analyze HowNet in terms of the appropriateness and the granularity of the sememes used. The hypothesis in HowNet is that a term only has one meaning in a specific domain. Hereafter, a term is used to represent a concept which is an object in FCA. A concept is different from a formal concept as a formal concept is only a node in FCA which can contain several terms and their associated attributes. In other words, a formal concept in FCA can represents several terms(and thus concepts) having the equivalent relationship.. The Java API of an open source software called ConExp 3 is used to generate the concept oriented views with FCA technique. ConExp is a visualization and operating tool of FCA [Serhiy 2000]. It provides convenient function to edit attributes and objects, which is the basis for automatic display of a concept lattice. It also provides attribute reduction function to remove the reducible attributes which do not change the structure of the concept lattice. With this tool, we can ignore the concrete algorithm of FCA and focus on the selection of attributes and objects to construct an ontology and improvement of the lexical base.

Attribute Selection & Ontology Construction
For experimental purpose, we choose Information Technology as our domain for ontology construction with a given manually selected set of IT terms as objects in FCA. Then it is our task to explore the selection of attributes for ontology construction. HowNet has built a set of descriptive sememes, which are used to define terms and thus can serve as possible attributes from which we must pick the appropriate ones. These selected sememes should have discriminative power to differentiate concepts represented by these terms. The discriminating power is calculated through Information Gain (IG) for each sememe s i according to the following formula:

IG(s i ) = E(S-{s i })-E(S)
(1) where E(S) is the entropy of all terms according to the sememe set S of HowNet. E(S-{s i }) is the entropy after s i is deleted from S. P j is the probability of each class of terms which are split by the sememe set S using FCA. All the sememes in HowNet whose information gain is less than a threshold T, is filled out. The remaining sememes forms the set of attributes. The threshold T is a parameter determined experimentally.  Then the relationship between a term t i and a sememe s j is represented by a binary membership value. If t i is defined by s j , the membership value μ(t i ,s j ) is 1, 0 otherwise.
Here is an example of the formal context for 9 selected IT terms as listed in Figure 2a. Then the corresponding concept lattice is produced, as shown in Figure 2b. A term with fewer descriptive sememes always serves as a super class concept. Thus, the concept lattice visually displays the subsumption relationships between terms. The relations between different terms are represented in the form of a triple <R k , t i , t j >, where t i , t j are two terms and R k indicates the relation between t i and t j . Here we only define two kinds of relations: equivalent or isa. In figure 2, we get the results such as <电脑(computer), 计 算机(computer), >, <硬件(hardware), 电脑 (computer), > and so on.

Relation Analysis & Lexicon Improvement
The relations reflect the understanding of concepts by domain experts. In compiling a lexicon manually, it is important to provide domain experts with the appropriate tools and timely feedback for fine-tuning the definitions of terms through a visualized interface. In this section, we manually analyze the relations, mainly the inappropriate ones, and project them to the context lattice so that adjustments to terms and their definitions can be easily done. The following analysis and lexical tuning have been conducted. 1) Merging of equivalent terms: Nodes in the concept lattice should represent different concepts. For example, "computer" and "workstation" have the same definition in the lexicon, which means that they are equivalent, and thus, they should be merged as one node. However, if they need to be conceptually differentiated, revision to the definitions or attributes should be done. 2) Modification of inappropriate links: For isa relations, we also mainly analyze the inappropriate ones. Two relevant terms of one relation are mapped to one node and its superclass node respectively. For example, term "database" is defined by sememes "software, control, store" and forms an isa relation with term "operation system" defined by sememes "software, control". The isa relation is inappropriate and can be modified by defining terms more accurately, e.g. "operation system" is redefined by "software, control, manage".
3) Filling of terms: For nodes in the lattice which do not have associated terms, it implies that there is a concept, yet association is appropriate and terms are missing. Thus, according to the information that the sememes bear, domain experts can fill in some concrete term if possible, the combination of the sememes as its definition. For the first two analyses above, with the help of the lattice, it is relatively easy to modify the ineligible relations, comprehensively considering its relations with other terms at the same time. The main operation is to revise the terms with appropriate sememes, including changing, adding or deleting some descriptive sememes. The third analysis means adding new concepts according to existing concepts and its operation includes discovering new terms and defining them. The whole analysis process aims at tuning the sememe set, redefining terms with new sememes, discovering new terms, according to which the lexical base can be improved. Then we can reuse FCA technique to generate relations between terms. The whole process is depicted as in

Materials
To verify our idea, we have conducted a small-scale experiment due to the manpower limit. Firstly, we used HowNet version 2000, from which 57 IT domain terms with their definitions are chosen as seeds. By calculating information gain using formula (1) with threshold value equal to zero, 38 sememes are selected as formal attributes. Secondly, from a Chinese thesaurus [Wang 1993], we picked out about another 40 IT terms, and define them with the format of HowNet Lexicon according to their liberal explanations. HowNet lexicon is a general resource and there are only a small number of sememes specific for IT domain. In order to define and differentiate concepts in IT domain, domain experts have added twenty five new sememes so that the total number of sememes 63 for the 97 IT terms used in this experiment. Some of the attributes can be written as a combination of other attributes, and has no influence on the structure of the concept lattice, referred to as reducible attributes [Ganter 1999]. The attributes will be eliminated before producing the concept lattice. For example, in these 97 IT terms, whatever term has the sememe "Place" it always has "ProperName". Thus, "ProperName" can be seen having no discriminative power and is thus removed. It is noted that the attributes are reduced in producing a concept lattice for a specific set of terms although they may have discriminative power for a larger set of terms. After attribute reduction, there are 52 sememes left. Figure 3a shows the hierarchical relations of these 97 IT terms using ConExp before lexicon improvement, Figure  3b shows the hierarchical relations of these IT terms after lexicon improvement. In these two figures, the circles represent formal concepts. The larger a circle is, the more terms it owns. The texts in the rectangles are the terms and the rectangles with shadow are attributes. A node with only a point means that the formal concept does not own any terms but only owns some attributes. Because there are too many nodes and edges in these two figures, it is difficult to see much difference by a first glance. In fact, Figure 3b has fewer terms included in each node, and thus Figure 3b can distinguish better between terms. The following evaluation result for produced relations will prove this. From Figure 3a, we found 109 equivalent relations and 147 isa relations. During lexicon improvement, we have analyzed the results and conducted operations on sememes and terms. We have adjusted the sememe set, revised the inappropriate definitions, and filled some new terms, just as the operations mentioned in Section 5. For example, to differentiate between terms " 计 算 机 computer" and " 服 务 器 server", a new sememe "network" is adopted. Note that the new terms are mainly added to the nodes having only attributes. For example, in Figure 3a the node circled by the dashed line has only an attribute "action" with no terms. Through human analysis, a new term "操作(operation)" is added. Then in Figure 3b, a term " 操 作 (operation)" with attribute "action" is represented by the node also circled by the dashed line. Now there are 105 terms and 53 descriptive sememes, from which we can acquire 71 equivalent relations and 154 isa relations.

Evaluation
Most researchers evaluate their ontologies in two parts: the lexical part and the taxonomic part [Cimiano 2003, Jiang 2003]. Here our premise is that the domain-specific terms have been correctly recognized. Then our evaluation work mainly focuses on measuring the automatically generated taxonomic relationship between terms. According to the link in each concept lattice, we pick out the equivalent and hierarchical relations in the form of triples . Five evaluators evaluated the eligibility of these triples. The evaluators all come from the IT fields and are familiar with those terms. For each relation represented by a triple, the evaluators answer [YES]  In Table 1, the evaluation results show that experiment before lexicon improvement gets about 43.2% of answers as "YES" on average. After revising the lexical base, the definitions become more reasonable. For the improved lexical base, the result is that we can get 84.4% of answer as "YES" for the equivalent relations and 59.2% of answer as "YES" for the isa relations respectively. And the average ratio of answer "YES" is 76.4%.

Discussion
It is a win-win situation to automatically identify the relations between domain-specific concepts by using existing resources and provide the visualized tool for improving the lexical base. Our method has received such effect. However, there are still some problems in the method as stated below.
In principle, each attribute in the attribute set of an ontology should be independent. However, in reality, the selection of independent attributes is very difficult. For example, the sememes "computer" and "software", "action" and "break" are related attributes. We try to avoid selecting the dependent attributes to describe the objects. Sometimes dependent attributes cannot be avoid such as in the case that one attributes is the subtype of another attribute(called its parent attribute). Without the subtype attribute, two different concepts cannot be distinguished. In this case, when a concept is associated with the subtype attribute, it should be made explicit in the concept lattice that the term also owns the parent attribute. This will help to maintain the explicit subsumption relationship for consistency. From the evaluation, we can see that more correct relations have been identified after lexicon improvement than before improvement. At the same time, after lexicon improvement, the definitions in the lexical base are more detailed and precise. For example, before lexicon improvement, "server (服务器)" has the same definition as "computer(计算机)" which in turn affect their relations. Consequently, they are identified wrongly as having the equivalent relation. After lexicon improvement, "server" is redefined and is represented as a kind of "computer(计 算机)", and thus the equivalent relationship no longer hold. There are 71 formal concepts before lexicon improvement and 80 formal concepts after the improvement, respectively. That is, redundant concepts are removed and the terms are better differentiated. At the same time, more attributes are adopted. With more attributes, it is easier to define each term separately. However, some sparse attributes may be introduced as a result. We can try to confine the work to use only the predefined sememe set and avoid adding new attributes. Sometimes, after lexicon improvement with existing sememes, there are still some inappropriate definitions, which cause the inappropriate relations in the ontology. Thus to make concepts distinguishable, we have to expand our sememe set. For example, the sememe "network" is added in this work. In addition, FCA has provided a visualized interface, which makes it convenient to improve the lexical base. However, the relationship between concepts still needs a lot of manual work to verify and adjust the term definitions. For the inappropriate relations, experts redefine each term according to their own knowledge. Such definition is somewhat subjective, which may be inconsistent with knowledge of another expert. That is why in our evaluation, that the average evaluation is only 76.4% correct.

Conclusions
In this paper, we have proposed how to use formal concept analysis as an interactive for the construction of an ontology using a lexical knowledge base. Firstly, the focus is how to select attributes to visualize the relations between lexical items. Then, lexical definitions can be revised through analyzing the relations in the ontology. However, this analysis is still quite labor intensive. We can only select a small number of terms for experiments. In future work, the sememe set needs to be further tuned to increase the scale of our experiment. Methods of automatic or semi-automatic inspection and evaluation of lexical base will also be investigated.


Study of Some Distance Measures for Language and Encoding Identification

To determine how close two language models (e.g., n-grams models) are, we can use several distance measures. If we can represent the models as distributions, then the similarity is basically the similarity of distributions. And a number of measures are based on information theoretic approach. In this paper we present some experiments on using such similarity measures for an old Natural Language Processing (NLP) problem. One of the measures considered is perhaps a novel one, which we have called mutual cross entropy. Other measures are either well known or based on well known measures, but the results obtained with them vis-avis one-another might help in gaining an insight into how similarity measures work in practice.

The first step in processing a text is to identify the language and encoding of its contents. This is a practical problem since for many languages, there are no universally followed text encoding standards. The method we have used in this paper for language and encoding identification uses pruned character n-grams, alone as well augmented with word n-grams. This method seems to give results comparable to other methods.

Introduction
Many kinds of models in NLP can be seen as distributions of a variable. For various NLP problems, we need to calculate the similarity of such models or distributions. One common example of this is the n-grams model. We might have several reference data sets and then we may want to find out which of those matches most closely with a test data set. The problem of language and encoding identification can be represented in these terms. One of the most important questions then is which similarity measure to use. We can expect that the performance obtained with the similarity measure will vary with the specific problem and the kind of model used or some other problem specific details. Still, it will be useful to explore how these measures relate to each other.
The measures we are going to focus on in this paper are all very simple ones and they all try to find the similarity of two models or distributions in a (more or less) information theoretic way, except the out of rank measure proposed by Cavnar and Trenkle (Cavnar and Trenkle, 1994).
This work had started simply as an effort to build a language and encoding identification tool specifically for South Asian languages. During the course of this work, we experimented with various similarity measures and some of the results we obtained were at least a bit surprising. One of the measures we used was something we have called mutual cross entropy and its performance for the current problem was better than other measures.
Before the content of a Web page or of any kind of text can be processed for computation, its language and encoding has to be known. In many cases this language-encoding is not known beforehand and has to be determined automatically. For languages like Hindi, there is no standard encoding followed by everyone. There are many well known web sites using their own proprietary encoding. This is one of the biggest problems in actually using the Web as a multilingual corpus and for enabling a crawler to search the text in lan-guages like Hindi. This means that the content in these languages, limited as it is, is invisible not just to people (which could be just due to lack of display support or unavailability of fonts for a particular encoding) but even to crawlers.
The problem of language identification is similar to some other problems in different fields and the techniques used for one such problem have been found to be effective for other problems too. Some of these problems are text categorization (Cavnar and Trenkle, 1994), cryptanalysis (Beesley, 1988) and even species identification (Dunning, 1994) from genetic sequences. This means that if something works for one of these problems, it is likely to work for these other problems.
It should be noted here that the identification problem here is that of identifying both language and encoding. This is because (especially for South Asian languages) the same encoding can be used for more than one languages (ISCII for all Indian languages which use Brahmi-origin scripts) and one language can have many encodings (ISCII, Unicode, ISFOC, typewriter, phonetic, and many other proprietary encodings for Hindi).
In this paper we describe a method based mainly on character n-grams for identifying the language-encoding pair of a text. The method requires some training text for each languageencoding, but this text need not have the same content. A few pages (2500-10000 words) of text in a particular language-encoding is enough. A pruned character based n-grams model is created for each language-encoding. A similar model is created for the test data too and is compared to the training models. The best match is found using a similarity measure. A few (5-15) words of test data seems to be enough for identification in most cases.
The method has been evaluated using various similarity measures and for different test sizes. We also consider two cases, one in which the pruned character n-grams model is used alone, and the other in which it is augmented with a word n-gram model.

Previous Work
Language identification was one of the first natural language processing (NLP) problems for which a statistical approach was used.
Ingle (Ingle, 1976) used a list of short words in various languages and matched the words in the test data with this list. Such methods based on lists of words or letters (unique strings) were meant for human translators and couldn't be used directly for automatic language identification. They ignored the text encoding, since they assumed printed text. Even if adapted for automatic identification, they were not very effective or scalable.
However, the earliest approaches used for automatic language identification were based on the above idea and could be called 'translator approaches'. Newman (Newman, 1987), among others, used lists of letters, especially accented letters for various languages and identification was done by matching the letters in the test data to these lists.
Beesley's (Beesley, 1988) automatic language identifier for online texts was based on mathematical language models developed for breaking ciphers. These models basically had characteristic letter sequences and frequencies ('orthographical features') for each language, making them similar to n-grams models. The insights on which they are based, as Beesley points out, have been known at least since the time of Ibn ad-Duraihim who lived in the 14th century. Beesley's method needed 6-64 K of training data and 10-12 words of test data. It treats language and encoding pair as one entity.
Adams and Resnik (Adams and Resnik, 1997) describe a client-server system using Dunning's n-grams based algorithm (Dunning, 1994) for a variety of tradeoffs available to NLP applications like between the labelling accuracy and the size and completeness of language models. Their system dynamically adds language models. The system uses other tools to identify the text encoding. They use 5-grams with add-k smoothing. Training size was 1-50 K and test size above 50 characters. Some pruning is done, like for frequencies up to 3.
Some methods for language identification use techniques similar to n-gram based text categorization (Cavnar and Trenkle, 1994) which calculates and compares profiles of n-gram frequencies. This is the approach nearest to ours. Such methods differ in the way they calculate the likelihood that the test data matches with one of the profiles. Beesley's method simply uses word-wise probabilities of 'digram' sequences by multiplying the probabilities of sequences in the test string. Others use some distance measure between training and test profiles to find the best match.
Cavnar also mentions that top 300 or so n-grams are almost always highly correlated with the language, while the lower ranked n-grams give more specific indication about the text, namely the topic. The distance measure used by Cavnar is called 'out-of-rank' measure and it sums up the differences in rankings of the n-grams found in the test data as compared to the training data. This is among the measures we have tested.
The language model used by Combrinck and Botha (Combrinck and Botha, 1994) is also based on bigram or trigram frequencies (they call them 'transition vectors'). They select the most distinctive transition vectors by using as measure the ratio of the maximum percentage of occurrences to the total percentage of occurrences of a transition vector. These distinctive vectors then form the model.
Dunning (Dunning, 1994) also used an n-grams based method where the model selected is the one which is most likely to have generated the test string. Giguet (Giguet, 1995b;Giguet, 1995a) relied upon grammatically correct words instead of the most common words. He also used the knowledge about the alphabet and the word morphology via syllabation. Giguet tried this method for tagging sentences in a document with the language name, i.e., dealing with multilingual documents.
Another method (Stephen, 1993) was based on 'common words' which are characteristic of each language. This methods assumes unique words for each language. One major problem with this method was that the test string might not contain any unique words.
Cavnar's method, combined with some heuristics, was used by Kikui (Kikui, 1996) to identify languages as well as encodings for a multilingual text. He relied on known mappings between languages and encodings and treated East Asian languages differently from West European languages.
Kranig (Muthusamy et al., 1994) and (Simon, 2005) have reviewed and evaluated some of the well known language identification methods. Martins and Silva (Martins and Silva, 2005) describe a method similar to Cavnar's but which uses a different similarity measure proposed by Jiang and Conrath (Jiang and Conrath, 1997). Some heuristics are also employed.
Poutsma's (Poutsma, 2001) method is based on Monte Carlo sampling of n-grams from the beginning of the document instead of building a com-plete model of the whole document. Sibun and Reynar (Sibun and Reynar, 1996) use mutual information statistics or relative entropy, also called Kullback-Leibler distance for language identification. Souter et al. (Souter et al., 1994) compared unique character string, common word and 'trigraph' based approaches and found the last to be the best.
Compression based approaches have also been used for language identification. One example of such an approach is called Prediction by Partial Matching (PPM) proposed by Teahan (Teahan and Harper, 2001). This approach uses cross entropy of the test data with a language model and predicts a character given the context.

Pruned Character N-grams
Like in Cavnar's method, we used pruned n-grams models of the reference or training as well as test data. For each language-encoding pair, some training data is provided. A character based ngram model is prepared from this data. N-grams of all orders are combined and ranked according to frequency. A certain number of them (say 1000) with highest frequencies are retained and the rest are dropped. This gives us the pruned character n-grams model, which is used for languageencoding identification.
As an attempt to increase the performance, we also tried to augment the pruned character n-grams model with a word n-gram model.

Distance Measures
Some of the measures we have experimented with have already been mentioned in the section on previous work. The measures considered in this work range from something as simple as log probability difference to the one based on Jiang and Conrath (Jiang and Conrath, 1997) measure.
Assuming that we have two models or distributions P and Q over a variable X, the measures (sim) are defined as below (p and q being probabilities and r and s being ranks in models P and Q: 1. Log probability difference: 2. Absolute log probability difference: 3. Cross entropy: 4. RE measure (based on relative entropy or Kullback-Leibler distance -see note below): 5. JC measure (based on Jiang and Conrath's measure) (Jiang and Conrath, 1997): where, (6) and, 6. Out of rank measure (Cavnar and Trenkle, 1994): 7. MRE measure (based on mutual or symmetric relative entropy, the original definition of KL-distance given by Kullback and Leibler): 8. Mutual (or symmetric) cross entropy: As can be noticed, all these measures, in a way, seem to be information theoretic in nature. However, our focus in this work is more on the presenting empirical evidence rather than discussing mathematical foundation of these measures. The latter will of course be interesting to look into. NOTE: We had initiallly experimented with relative entropy or KL-distance as defined below (instead of the RE measure mentioned above): Another measure we tried was DL measure (based on Dekang Lin's measure, on which the JC measure is based): where A and B are as given above.
The results for the latter measure were not very good (below 50% in all cases) and the RE measure defined above performed better than relative entropy. These results have not been reported in this paper.

Mutual Cross Entropy
Cross entropy is a well known distance measure used for various problems. Mutual cross entropy can be seen as bidirectional or symmetric cross entropy. It is defined simply as the sum of the cross entropies of two distributions with each other.
Our motivation for using 'mutual' cross entropy was that many similarity measures like cross entropy and relative entropy measure how similar one distribution is to the other. This will not necessary mean the same thing as measuring how similar two distributions are to each other. Mutual information measures this bidirectional similarity, but it needs joint probabilities, which means that it can only be applied to measure similarity of terms within one distribution. Relative entropy or Kullback-Leibler measure is applicable, but as the results show, it doesn't work as well as expected.
Note that some authors treat relative entropy and mutual information interchangeably. They are very similar in nature except that one is applicable for one variable in two distributions and the other for two variables in one distribution.
Our guess was that symmetric measures may give better results as both the models give some information about each other. This seems to be supported by the results for cross entropy, but (asymmetric) cross entropy and RE measures also gave good results.

The Algorithm
The foundation of the algorithm for identifying the language and encoding of a text or string has already been explained earlier. Here we give a summary of the algorithm we have used. The parameters for the algorithm and their values used in our experiments reported here have also been listed. These parameters allow the algorithm to be tuned  (1), Assamese (1), Bengali (2), Bulgarian (1), Catalan (1) Czech (1) (1)  or customized for best performance. Perhaps they can even be learned by using some approach as the EM algorithm.
1. Train the system by preparing character based and word based (optional) n-grams from the training data.

Combine n-grams of all orders (O c for characters and O w for words).
3. Sort them by rank.
4. Prune by selecting only the top N c character n-grams and N w word n-grams for each language-encoding pair.
5. For the given test data or string, calculate the character n-gram based score sim c with every model for which the system has been trained.
6. Select the t most likely language-encoding pairs (training models) based on this character based n-gram score.
7. For each of the t best training models, calculate the score with the test model. The score is calculated as: where c and w represent character based and word based n-grams, respectively. And a is the weight given to the word based n-grams. In our experiment, this weight was 1 for the case when word n-grams were considered and 0 when they were not.
8. Select the most likely language-encoding pair out of the t ambiguous pairs, based on the combined score obtained from word and character based models. To summarize, the parameters in the above method are: 1. Character based n-gram models P c and Q c 2. Word based n-gram models P w and Q w 3. Orders O c and O w of n-grams models 4. Number of retained top n-grams N c and N w (pruning ranks for character based and word based n-grams, respectively) 5. Number t of character based models to be disambiguated by word based models 6. Weight a of word based models Parameters 3 to 6 can be used to tune the performace of the identification system. The results reported in this paper used the following values of these parameters: There is, of course, the type of similarity score, which can also be used to tune the performance. Since MCE gave the best overall performance in our experiments, we have selected it as the default score type.

Implementation
The language and encoding tool has been implemented as a small API in Java. This API uses another API to prepare pruned character and word n-grams which was developed as part of another project. A graphical user interface (GUI) has also been implemented for identifying the languages and encodings of texts, files, or batches of files. The GUI also allows a user to easily train the tool for a new language-encoding pair. The tool will be modified to work in client-server mode for documents from the Internet.
From implementation point of view, there are some issues which can significantly affect the performance of the system: 1. Whether the data should be read as text or as a binary file.
2. The assumed encoding used for reading the text, both for training and testing. For example, if we read UTF8 data as ISO-8859-1, there will be errors.
3. Whether the tranining models should be read every time they are needed or be kept in memory.
4. If training models are stored (even if they are only read at the beginning and then kept in memory), as will have to be done for practical applications, how should they be stored: as text or in binary files?
To take care of these issues, we adopted the following policy: 1. For preparing character based models, we read the data as binary files and the characters are read as bytes and stored as numbers.
For word based models, the data is read as text and the encoding is assumed to be UTF8. This can cause errors, but it seems to be the best (easy) option as we don't know the actual encoding. A slightly more difficult option to implement would be to use character based models to guess the encoding and then build word based models using that as the assumed encoding. The problem with this method will be that no programming environment supports all possible encodings. Note that since we are reading the text as bytes rather than characters for preparing 'character based n-grams', technically we should say that we are using byte based n-grams models, but since we have not tested on multi-byte encodings, a byte in our experiments was almost always a character, except when the encoding was UTF8 and the byte represented some meta-data like the script code. So, for practical purposes, we can say that we are using character based n-grams.
2. Since after pruning, the size of the models (character as well as word) is of the order of 50K, we can afford to keep the training models in memory rather than reading them every time we have to identify the language and encoding of some data. This option is naturally faster. However, for some applications where language and encoding identification is to be done rarely or where there is a memory constraint, the other option can be used.
3. It seems to be better to store the training models in binary format since we don't know the actual encoding and the assumed encoding for storing may be wrong. We tried both options and the results were worse when we stored the models as text.
Our identification tool provides customizability with respect to all the parameters mentioned in this and the previous section.

Evaluation
Evaluation was performed for all the measures listed earlier. These are repeated here with a code for easy reference in table-3.  acters, namely 100, 200, 500, 1000, 2000, and all the available test data (which was not equal for various language-encoding pairs). The number of language-encoding pairs was 53 and the minimum number of test data sets was 840 when we used all available test data. In other cases, the number was naturally larger as the test files were split in fragments (see table-2).
The languages considered ranged from Esperanto and Modern Greek to Hindi and Telugu. For Indian languages, especially Hindi, several encodings were tested. Some of the pairs had UTF8 as the encoding, but the information from UTF8 byte format was not explicitly used for identification. The number of languages tested was 39 and number encodings was 19. Total number of language-encoding pairs was 53 (see table-1).
The test and training data for about half of the pairs was collected from web pages (such as Gutenberg). For Indian languages, most (but not all) data was from what is known as the CIIL corpus.
We didn't test on various training data sizes. The size of the training data ranged from 2495 to 102377 words, with more on the lower side than on the higher.
Note that we have considered the case where both the language and the encoding are unknown, not where one of them is known. In the latter case, the performance can only improve. Another point worth mentioning is that the training data was not very clean, i.e., it had noise (such as words or sentences from other languages). Error details have been given in table-4.

Results
The results are presented in table-3. As can be seen almost the measures gave at least moderately good results. The best results on the whole were obtained with mutual cross entropy. The JC measure gave almost equally good results. Even a simple measure like log probability difference gave surprisingly good results. It can also be observed from table-3 that the size of the test data is an important factor in performance. More test data gives better results. But this does not always happen, which too is surprising. It means some other factors also come into play. One of these factors seem to whether the training data for different models is of equal size or not. Another factor seems to be noise in the data. This seems to affect some measures more than the others. For example, LPD gave the worst performance when all the available test data was used. For smaller data sets, noise is likely to get isolated in some data sets, and therefore is less likely to affect the results.
Using word n-grams to augment character ngrams improved the performance in most of the cases, but for measures like JC, RE, MRE and MCE, there wasn't much scope for improvement. In fact, for smaller sizes (100 and 200 characters), word models actually reduced the performance for these better measures. This means either that word models are not very good for better measures, or we have not used them in the best possible way, even though intuitively they seem to offer scope for improvement when character based models don't perform perfectly.

Issues and Enhancements
Although the method works very well even on little test and training data, there are still some issues and possible enhancements. One major issue is that Web pages quite often contain text in more than one language-encoding. An ideal languageencoding identification tool should be able to mark which parts of the page are in which languageencoding.
Another possible enhancement is that in the case of Web pages, we can also take into account the language and encoding specified in the Web page (HTML). Although it may not be correct for non-standard encodings, it might still be useful for differentiating between very close encodings like ASCII and ISO-8859-1 which might seem identical to our tool.
If the text happens to be in Unicode, then it might be possible to identify at least the encoding (the same encoding might be used for more than one languages, e.g., Devanagari for Hindi, Sanskrit and Marathi) without using a statistical method. This might be used for validating the result from the statistical method.
Since every method, even the best one, has some limitations, it is obvious that for practical applications we will have to combine several approaches in such a way that as much of the available information is used as possible and the various approaches complement each other. What is left out by one approach should be taken care of by some other approach. There will be some issues in combining various approaches like the order in which they have to used, their respective priorities and their interaction (one doesn't nullify the gains from another).
It will be interesting to apply the same method or its variations on text categorization or topic identification and other related problems. The distance measures can also be tried for other problems.

Conclusion
We have presented the results about some distance measures which can be applied to NLP problems. We also described a method for automatically identifying the language and encoding of a text using several measures including one called 'mutual cross entropy'. All these measures are applied on character based pruned n-grams models created from the training and the test data. There is one such model for each of the known languageencoding pairs. The character based models may be augmented with word based models, which increases the performance for not so good measures, but doesn't seem to have much effect for better measures. Our method gives good performance on a few words of test data and a few pages of training data for each language-encoding pair. Out of the measures considered, mutual cross entropy gave the best results, but RE, MRE and JC measures also performed almost equally well.

Acknowledgement
The author wishes to thank Preeti Pradhan, Nandini Upasani and Anita Chaturvedi of Language Technologies Research Centre, International Institute of Information Technology, Hyderabad, India for helping in preparing the data for some of the language-encoding pairs. The comments of reviewers also helped in improving the paper.


Regionalization Method for Nonlinear Differential Equation Systems In a Cartesian Plan

We propose a regionalization technique for analyzing nonlinear differential equation systems where coefficients are standard and nonzero. The present work starts with the study of a natural object which was the magic squares providing us with a new way to partition the plan in regions.

INTRODUCTION
In the present work we study the effects of delinearity of box type in orbital geometry and in orbital dynamics. We start this work with a first natural object around which we organize our plan , namely the magic square (MS) giving the partition of the plan 2 ℜ into 25 external sets depicted in the following heuristic diagram . 15 22 9  16  3  2  14  21  8  20  19  1  13  25  7  6  18  5  12  24  23  10  17  4  11 Also, it plays an essential role in the nonclassic partition (regionalization) as following ( Here are some of the questions that can be asked The apparition of the magic square The behaviour of the orbits in the regions of the MS The transition of the orbits of a region have the other The nature of the singular place The strut with the linear case. The objects: We are interested by non-standard systems of nonlinear differential equations in 2 ℜ provided with cartesian coordinates ( X 1 , X 2 ).   (1) where the reals a 11 , a 12 , a 21 , a 22 , b 1, b 2 (resp α 1 > 0 ,α 2 >0) are standard and nonzero (resp infinitely great ) and for i= 1,2 we proceed to a sharp delinearization " of box type delinearization " of differential system with constant coefficients With conserving the linear equations. Then the problem is to evaluat the effects.
We can also see a problem of transient to the limit ( ) +∞ → +∞ → 2 1 , α α In some families which are linear when . 1 2 1 = = α α The differential system (1) is divided into three families :F 1 , F 2 , F 3 F 1 : (a 21, a 22, b 2 ) = m(a 11, a 12, b 1 ) F 2 : (a 21, a 22, b 2 ) = m (a 11, a 12, b 1 ) + (0,0,d) ; d ≠ 0 The technique: we use the technique of regionalization to get some predictions relative to the macroscopic behaviour of orbits and the dynamics along the orbits. Some predictions i. The magic square (MS) in the first analysis the plan 2 ℜ is partitioned in 25 external regions where we denote by (15) (resp (3)) the region defined by the conditions 1 X pp -1 and 2 X ff 1 (resp 1 X ff 1 and 2 X ff 1) (22) (resp (16)) the region defined by the conditions 1 X ≈ -1 and 2 X ff 1 (resp 1 X ≈ 1 and 2 X ff 1) ' is a first integral. The non-singular orbits are rectiligne and with the same slope m, the singular position is given by the equation a differential system of the family F1 induce a family with one real parameter C (C specify the level straight) of differential the form of singular place of F 1 implique some number of bifurcations in the equations D c when C follow ℜ .

The family F 2
The singular place is empty If d was null we obtain a system of 1 F with a singular emptiness in the case to add 0 ≠ d hunts the singular place, but it stay a witness that create a river phenomena.

The family F 3 :
we distinguish three cases j. the vectors ( ) ( ) ( )  (1)) is infinitely near to the rectiligne field vectors Proof of proposition 1: By the lemma of short shadows, the orbits of (1) have in the region (13) the same halo as the system orbits In the regions (19) and (7) (resp (9) and (17) are infinitely small .

Proof of proposition 2:
The proposition 2 is an immediate consequence of the lemma of the short shadows as long as we have lemma 2.  , the curves C 1 = (X' 1 = 0) and C 2 =(X' 2 =0) don't intersect.