TR99-0001 (April)

Title: Translingual Information Management by Natural Language Processing
Author(s): Akitoshi Okumura
Contact person: Akitoshi Okumura (okumura@cs.titech.ac.jp)
Abstract: Translingual information management that can choose appropriate information and obtain useful knowledge from the flood of global information is being increasingly demanded. This research is aimed at developing a practical system for managing translingual information. Translingual information management has a fundamental cycle of information needs and information search. In order to enhance the search quality and to accelerate the cycle, this research focuses on three core technologies: coordinate structure analysis, cross-language information retrieval, and information navigation.
First, we propose a model for analyzing coordinate structure. This model provides top-down scope information on the correct syntactic structure by taking advantage of the symmetric patterns of parallelism. The analysis of coordinate structure creates a bottleneck when dealing with documents because most long sentences contain a coordinate structure. The model ensured about 70% accuracy when analyzing 3,215 sentences from the Wall Street Journal. The model results in a high-quality search because it enables accurate analysis.
Second, we propose the GDMAX method, which is a method for translating query terms for use in cross-language information retrieval (CLIR). GDMAX was tested in an experiment using half a million English documents and 15 Japanese queries. GDMAX queries were 6% more accurate than machine translation queries and 12% more accurate than bilingual dictionary-based queries. This method produces highquality search results by choosing appropriate translation terms for CLIR.
Finally, in order to make translingual information management efficient, we propose a method for information navigation that classifies documents and enables a user to navigate by using 5W1H (who, when, where, what, why, how, and predicate) information. This method was implemented on an information navigation system and provides three functions: episodic retrieval, multidimensional classification, and bird's-eye classification. The system was used to access 6,400 newspaper articles and 1,500 sales reports. The three functions proved to be effective for office documentation work; that is, the extraction precision was approximately 82%.

TR99-0002 (June)

Title: Abstracted Instruction Cache of TITAC2 - As a Benchmark Circuit for Timed Asynchronous Circuit Verification
Author(s): Tomohiro Yoneda
Contact person: Tomohiro Yoneda (yoneda@cs.titech.ac.jp)
Abstract: As a benchmark circuit for timed asynchronous circuit verification, we have developed an abstracted version of TITAC 2 instruction cache sub-system and its formal specification. This document shows all the figures of the gate level sub-circuits which compose the abstracted instruction cache. A time Petri net model for the formal specification is also shown with the detailed explanation. The text files describing those circuits and Petri nets can be obtained from http://yoneda-www.cs.titech.ac.jp/~yoneda/pub.html.

TR99-0003 (August)

Title: On some asymptotic properties of learning automaton networks
Author(s): Taisuke Sato
Contact person: Taisuke Sato (sato@cs.titech.ac.jp)
Abstract: In this report, we analyze the collective behavior of learning automata which are used in a programming language under development that combines reinforcement learning and symbolic programming \cite{Ka96,Sa99}. Learning automata can automatically improve their behavior by using a response from a random stationary environment, but when connected with each other, their behavior becomes much complex and hard to analyze. We analyzed a class of learning automaton networks and proved that they eventually take the most rewarding action with probability one when they use an appropriately decaying learning rate.

TR99-0004 (September)

Title: Training data selection for optimal generalization with noise variance reduction in neural networks
Author(s): Sethu Vijayakumar, Masashi Sugiyama and Hidemitsu Ogawa
Contact person: Masashi Sugiyama
Abstract: In this paper, we discuss the problem of active training data selection in the presence of noise. We formalize the learning problem in neural networks as an inverse problem using a functional analytic framework and use the Averaged Projection criterion as our optimization criterion for learning. Based on the above framework, we look at training data selection from two objectives, namely, improving the generalization ability and secondly, reducing the noise variance in order to achieve better learning results. The final result uses the apriori correlation information on noise characteristics and the original function ensemble to devise an efficient sampling scheme, which can be used in conjunction with the incremental learning schemes devised in our earlier work to achieve optimal generalization.

TR99-0005 (September)

Title: Exact incremental projection learning in neural networks
Author(s): Masashi Sugiyama and Hidemitsu Ogawa
Contact person: Masashi Sugiyama
Abstract: We propose an incremental learning method in neural networks under the projection learning criterion. The method provides exactly the same generalization capability as that obtained by batch projection learning. Thus, the optimal generalization capability is acheived. Moreover, the proposed incremental learning method is more efficient in computation than the batch learning method. Finally, an incremental learning algorithm which further reduces the computational complexity and memory usage under certain conditions is given, and the effectiveness of the algorithm is demonstrated through computer simulations.

TR99-0006 (September)

Title: Pseudo orthogonal bases give the optimal solution to active learning in neural networks
Author(s): Masashi Sugiyama and Hidemitsu Ogawa
Contact person: Masashi Sugiyama
Abstract: Pseudo orthogonal bases are a certain type of frames proposed in the engineering field, whose concept is equivalent to a normalized tight frame in the frame terminology. This paper shows that pseudo orthogonal bases play an essential role in neural network learning. One of the most important issues in neural network learning is "what training data provides the optimal generalization capability?", which is referred to as active learning in the neural network community. We derive a necessary and sufficient condition of training data to provide the optimal generalization capability in the trigonometric polynomial space, where the concept of pseudo orthogonal bases is essential. By utilizing useful properties of pseudo orthogonal bases, we clarify the mechanism of achieving the optimal generalization.

TR99-0007 (September)

Title: Incremental projection learning for optimal generalization
Author(s): Masashi Sugiyama and Hidemitsu Ogawa
Contact person: Masashi Sugiyama
Abstract: In many practical situations in neural network learning, it is often expected to further improve the generalization capability after the learning process has been completed. One of the common approaches is to add training data to the neural network. In view of the learning methods of human beings, it seems natural to build posterior learning results upon prior results, which is generally referred to as incremental learning. Many incremental learning methods have been devised so far. However, they provide poor generalization capability compared with batch learning methods. In this paper, a method of incremental projection learning in the presence of noise is presented, which provides exactly the same learning result as that obtained by batch projection learning. The effectiveness of the presented method is demonstrated through computer simulations.

TR99-0008 (September)

Title: Properties of incremental projection learning
Author(s): Masashi Sugiyama and Hidemitsu Ogawa
Contact person: Masashi Sugiyama
Abstract: We proposed a method of incremental projection learning which provides exactly the same generalization capability as that obtained by batch projection learning in the previous paper. However, properties of the method have not yet been investigated. In this paper, we analyze its properties from the following aspects: First, it is shown that some of the training data which is regarded as redundant in most incremental learning methods have potential effectiveness, i.e., they will contribute to better generalization capability in the future learning process. Based on this fact, an improved criterion for redundancy of additional training data is derived. Second, the relationship between prior and posterior learning results is investigated where effective training data is classified into two categories from the viewpoint of improving generalization capability. Finally, a simpler form of incremental projection learning under certain conditions is given. The size of memory required for storing prior results in the representation is fixed and independent of the total number of training data.

TR99-0009 (September)

Title: Subspace information criterion for model selection
Author(s): Masashi Sugiyama and Hidemitsu Ogawa
Contact person: Masashi Sugiyama
Abstract: The problem of model selection is considerably important for acquiring higherlevels of generalization capability in supervised learning. In this paper, we propose a new criterion for model selection called the subspace information criterion (SIC). Computer simulations show that SIC works well even when the number of training examples is small.

TR99-0010 (October)

Title: Incremental active learning for optimal generalization
Author(s): Masashi Sugiyama and Hidemitsu Ogawa
Contact person: Masashi Sugiyama
Abstract: The problem of designing input signals for optimal generalization is called active learning. In this paper, we propose two active learning methods. One is the multi-point-search method applicable to arbitrary models. The effectiveness of this method is shown through computer simulations. The other is the optimal sampling method in trigonometric polynomial models. This method precisely specifies the optimal sampling locations.

TR99-0011 (November)

Title: Simultaneous evaluation of syntax and semantics of general L-attributed LR(k) grammars based on bottom-up parsing
Author(s): Kouji Yamamoto, Yoshimasa Kimura and Takehiro Tokuda
Contact person: Kouji Yamamoto
Abstract: The class of L-attributed grammar are a useful subclass of attribute grammar. There exist a number of methods for simultaneous attribute evaluation of L-attributed grammars. However, these methods can deal with restricted classes of L-attributed grammars or these methods are not rigorously simultaneous. This paper shows a method to simultaneously evaluate attribute values of general L-attributed LR(k) grammars based on bottom-up parsing of a given input string.

TR99-0012 (November)

Title: Parsing with truncated counter vectors of terminal symbols
Author(s): Kouji Yamamoto and Takehiro Tokuda
Contact person: Kouji Yamamoto
Abstract: In ordinary parsing methods, an input is an ordered sequence of terminal symbols. Those methods are not suitable to parse a diagram represented by a sequence of terminal symbols which is generated by a parameterized context-free grammar. Because the sequence is not necessarily in the same order as derived. We show two methods to parse such a sequence of a diagram. Our two methods use counter vectors of truncated number of occurrences of terminal symbols of inputs. Our bottom-up method requires the unique shift action based on counter vectors. Our top-down method can handle some type of left-recursive productions.

TR99-0013 (November)

Title: An incremental and hierarchical constraint solver with the lazy planning phase for user interface construction
Author(s): Tetsuya Suzuki and Takehiro Tokuda
Contact person: Tetsuya Suzuki
Abstract: Many graphical user interface development systems have their integrated constraint solvers. The constraint solvers make application programmers free from building procedures to maintain relations among displayed objects and application data. This paper presents an overview of a constraint solver called Twister. It is an extension of an incremental constraint solver DeltaBlue and has a hierarchical module mechanism. Thanks to the module mechanism, Twister can treat a group of constraints as a single constraint and perform lazy and hierarchical constraint solving. Our experiments show that Twister works much faster than DeltaBlue for large constraint problems with an appropriate module decomposition.

TR99-0014 (November)

Title: A repeated-update problem in the DeltaBlue algorithm
Author(s): Tetsuya Suzuki and Takehiro Tokuda
Contact person: Tetsuya Suzuki
Abstract: We observe a repeated-update problem in the process of updating walkabout strengths of the DeltaBlue algorithm, which is known as a fast constraint solving method based on local propagation. According to the basic references on the DeltaBlue algorithm, the time complexity of the planning phase is described as O(MN) for a constraint problem such that the number of constraints is N and the maximum number of methods a constraint has is M. We, however, point out that the time complexity is not O(MN) using a very simple example. In this example, the time complexity is exponential order for N. Then we present a corrected DeltaBlue algorithm whose time complexity is O(EN²) for a constraint problem such that the number of constraints is N and the maximum number of variables a constraint has is E. Finally we measure the performance of the corrected DeltaBlue algorithm using two benchmarks.

TR99-0015 (December)

Title: Hardware acceleration for BDD manipulations
Author(s): Tomohiro Yoneda and Takeshi Ishigaki
Contact person: Tomohiro Yoneda
Abstract: In this paper, in order to accelerate BDD based algorithms, we propose implementing BDD operations by hardware. We have designed a RTL model of the proposed hardware, and expressed it by C language so that we can count the number of clocks needed for each BDD operation. We have examined its performance improvement with respect to the original software library by using several benchmark circuits.

TR99-0016 (December)

Title

A study on PGLR parser for speech recognition

Author(s)

Hiroki Imai

Contact person

Hiroki Imai (imai@ael.fujitsu.co.jp)

Abstract

Recent speech recognition systems are based on a method of translating speech into word sequences using probabilistic language models such as N-gram models. Thus obtained word sequences do not include syntactic information sufficiently.

The HMM-LR method is known as the speech recognition method by combining HMM and GLR parsing. The HMM-LR has the following advantages. First, accurate recognition is achieved by predicting plausible hypotheses using lookaheads of GLR parsing algorithm. Second, a HMM-LR system outputs not only word sequences but also parse trees as recognition results.

In this research, we propose a new language model named PGLR+ for HMM-LR systems. PGLR+ is the PGLR language model extended by GLR parsing algorithm with multi-level connection constraints (GLR+). The PGLR model is known as the most sophisticated GLR-based probabilistic model from a theoretical and empirical point of view. GLR+ enables to incorporate not only allophone-level connection constraints but also morphological-category-level ones into an LR table simultaneously. PGLR+ has an advantage that it is more precise language model than N-gram language models because of syntactic and multi-level connection constraints.

There are two problems in constructing the PGLR+ language model. The first is that the traditional GLR parsing algorithm cannot treat multi-level connection constraints because a lookahead is a terminal symbol. We incorporate shift-reduce parsing algorithm for context-sensitive grammar into the GLR parsing algorithm. This modification enables to treat an arbitrary symbol as a lookahead and check connection constraints between two nonterminal symbols. The second is how to assign probabilities to a modified LR table for GLR+. We showed that a GLR+ parser could decide a lookahead which belongs to nonterminal symbols by the previously executed action. We also showed that utilization of this knowledge could assign probabilities to an LR table of GLR+.

Experiments using Japanese dialog corpus showed that PGLR+ was more effective than the trigram model in terms of test-set perplexity, which is the average number of hypotheses at a decision point. Finally, we compared our experiment with past researches using the same corpus. Although our experiments used the larger number of test-set sentences and lexical rules than past researches, PGLR+ obtained the best results.

TR99-0017 (December)

Title: Reactive Logic Programming by Reinforcement Learning
Author(s): Taisuke Sato and Satoshi Funada
Contact person: Taisuke Sato
Abstract: This paper describes an attempt to combine logic programming with reinforcement learning to provide a framework for reactive programming in which programs learn better behaviors reactively in response to the reward and penalty returned from an environment for the computed answer. We embedded learning automatons in logic programs as primitive reinforcement learning devices so that programs can learn to make the most rewarding decisions after an enough number of computation trials. We applied our framework to a variant of TSP problem and the problem of Turing machine synthesis.