Full Publication List with Abstracts

This study focuses on an implementation of a feature structure abstract machine, a framework for handling feature structures efficiently, whose basic notion was proposed by Carpenter et al. The feature structures, which are usually represented as directed graphs or terms in logic programming language, are compiled into an instruction sequence of the abstract machine. High-efficiency is accomplished since an interpretative process of feature structures can be omitted. In addition to the implementation, this study pursues several extensions of the instruction set and the compilation method in the original framework. Comparison with other systems is also shown.

This paper describes LiLFeS, an integrated unification-based programming system for linguistic formalisms based on typed feature structures, such as HPSG. The core engine of LiLFeS is an abstract machine developed for efficient handling of typed feature structures. Its basic design and optimization techniques are described. Performance comparisons between LiLFeS and other systems for typed feature structures show that LiLFeS is more than 50 times faster than ALE, and competitive to ProFIT.

This paper describes an extension of a feature structure abstract machine for supporting partial unification, which is used in an efficient parsing algorithm for HPSG proposed by Torisawa et al. An abstract machine for attribute-value logics, a framework for processing typed feature structures proposed by Carpenter and Qu, is not only efficient but also easily extendable. We extended the abstract machine for partial unification by only adding a set of instructions to the machine. By combining this technique with the pre-computation of possible feature structures, efficiency of HPSG parsing is improved. We also show the feasibility of our implementation by a series of experiments.

This paper presents the LiLFeS system, an efficient feature-structure description language for HPSG. The core engine of LiLFeS is an Abstract Machine for Attribute-Value Logics, proposed by Carpenter and Qu. Basic design policies, the current status, and performance evaluation of the LiLFeS system are described. The paper discusses two implementations of the LiLFeS. The first one is based on an emulator of the abstract machine, while the second one uses a native-code compiler and therefore is much more efficient than the first one.

This study discusses design and implementation of a native-code compiler for LiLFeS, a unification-based programming language with typed feature structures (TFSs). Although LiLFeS has been designed as a platform for natural language processing of TFS-based formalisms based on an Abstract Machine for Attribute-Value Logics (AMAVL) proposed by Carpenter et al., people require more efficiency in order to implement advanced natural language processing applications, such as for statistical learning from large corpora. A large number of studies have been made on efficient implementations of Prolog, such as for the native-code compiler Aquarius Prolog, and those studies are partially applicable to the LiLFeS implementation. However, in order to increase efficiency of TFS unification, optimization using type information is necessary and the compiler should directly generate unification code, including type manipulation. A simple extension of current Prolog or AMAVL implementations cannot achieve that. This thesis describes a design for a LiLFeS compiler, which is an extension of the Berkeley Abstract Machine, the implementation framework of Aquarius Prolog. The thesis focuses on an implementation of TFS unification on an abstract machine, including (1) construction and analysis of unification algorithm for direct generation of TFS unification code, (2) design of abstract machine instructions for expressing the algorithm described in (1), and (3) static analysis techniques for type hierarchies and definite clause programs for providing context information used in code optimization. Performance comparisons of the LiLFeS compiler to other LiLFeS and Prolog systems show the high efficiency of the implementation detailed in this thesis.

This article evaluates the efficiency of the LiLFeS abstract machine by performing parsing tasks with the LinGO English resource grammar. The instruction set of the abstract machine is optimized for efficient processing of definite clause programs and typed feature structures. LiLFeS also supports various tools required for efficient parsing (e.g. efficient copying, a built-in CFG parser) and the constructions of standard Prolog (e.g. cut, assertions, negation as failure). Several parsers and large-scale grammars, including the LinGO grammar, have been implemented in or ported to LiLFeS. Precise empirical results with the LinGO grammar are provided to allow comparison with other systems. The experimental results demonstrate the efficiency of the LiLFeS abstract machine.

This paper explores a mechanism of memory in human brain from a viewpoint of sentence understanding. We pointed out the following: (1) Some complexity must be incorporated into memory coding in order to be capable of representing binding in a meaning of a sentence. (2) When temporal coding is used to achieve the complexity, some mechanism is required to arbitrate phases (temporal slots) among memorized items. (3) Considering its implementation, the mechanism is likely to be global, which resembles a sort of structured memory, such as a push-down stack. (4) Episodic memory, which is thought to be formed through mammal hippocampus, can be regarded as a phase arbitration mechanism and is possibly related in depth to sentence understanding.

Various language processing algorithms have been studied to find the algorithm used in the human language understanding, but no algorithm has proven its existence by physiological evidences. In such a situation, we should consider an approach to pursue implementational constraints and preferences from a computational theory of the language understanding process.

In this paper, we study the model of a short-term memory mechanism of the human brain suitable for language understanding. Specifically, the following three topics are pursued.

(1) The exploration of the element necessary for building a short-term memory mechanism suitable for language understanding in the framework of neural network

(2) The techniques for an efficient simulation of general pulse neural networks in a continuous time.

(3) Construction of a primitive simulation of language understanding based on (1) and (2).

In (1), we clarify the following on the language-understanding neural networks. i) A binding problem has to be solved in order to represent a result of language understanding, and the most promising way is to utilize behavior in the time domain of a neural network. ii) Requirement of phase arbitration causes us to build a structural time-series memory on a neural network. iii) Application of grammatical rules can be implemented in the same way as a prediction of a time series.

In (2), we studied the event-driven pulse neural network simulator. In order to research complex operations in a time domain, such as phase mediation, the network simulation with high time precision is demanded, while conventional discrete-time systems is limited in simulation speed. On the other hand, discrete-event systems have difficulty in handling delayed firing for general neuron models. In this study, we show that our new technique with the second-order incremental partitioning method enables us to build an event-driven pulse network simulator in general neuron models by numerical calculation of delayed firing times. We also describe technique for more efficient handling of delayed firing by filtering redundant predictions.

Finally, in (3), we build a neural network simulation model, which understands the simple sentence of 3 to 4 words, in order to demonstrate the studies of language understandings in (1) and (2). We discuss our language-understanding system in various aspects and future directions of research for better understanding of a sentence.

This paper describes an indexing substrate for typed feature structures (ISTFS), which is an efficient retrieval engine for typed feature structures. Given a set of typed feature structures, the ISTFS efficiently retrieves its subset whose elements are unifiable or in a subsumption relation with a query feature structure. The efficiency of the ISTFS is achieved by calculating a unifiability checking table prior to retrieval and finding the best index paths dynamically.

Efficient simulation techniques for a discrete-event pulsed neural network simulator were developed. In a discrete-event simulation framework, simulation of complex neural behaviors, such as phase precession and phase arbitration, demands prediction of delayed firing times. The new technique, the incremental partitioning method, uses linear envelopes of the state variable of a neuron to partition the simulated time so that the delayed-firing time is reliably calculated by applying the bisection-combined Newton-Raphson method to every partition. The quick filtering technique is also proposed for reducing calculation cost of linear envelopes. The developed simulator, Punnets, has achieved efficiency and precision but still is capable of simulating a complex behavior of large-scale neural network models.

We propose a computational theory of internal-state estimation for others, which is the basis of information processing in human communication. To estimate internal states of the other equivalent to the self, we have to deal with two substantial difficulties, restriction of the estimator's parameter dimension and conversion between objective and subjective information. The proposed computational theory that solves both difficulties is based on self-observation principle. Learning the dynamics of the self provides prior knowledge of the dynamics of the other, which reduces the restriction of the parameter dimension; learning the association between the subjective state for the self and the objective observation of the self provides a mechanism for conversion between objective observation of the other and subjective information to the other. In this paper, we formalize communication in a framework of dynamics-estimation problems, and describe the two difficulties and our proposal on the framework. We also discuss relations of our proposal to evolutional psychology and neuroscience.

In the target article, LR3 (Parity), one of the possible criteria for language readiness, is defined with a simple description: “What counts for the speaker (or producer) must count for the listener (or receiver).” Based on a self-observation principle, we would like to suggest that this ability plays a much more crucial role in communication than can be inferred from the statement, namely, the role of “understanding others.”

We have developed a general framework to configure a spiking neuronal network so that it can precisely generate a desired spatio-temporal pattern of spikes. The unit of spiking neuronal networks employed here is a leaky integrate-and-fire model with a connection delay. We have shown that the required network configuration, and its existence, can be characterized by a set of linear inequalities constructed from the given pattern. The stability of the configured spiking neuronal network is discussed, which lead us to applying some routine methods in linear-programming to solve the set of inequalities, and yields the desirable spiking neural network configuration. To demonstrate the application of our approach, numerical examples with randomly generated patterns were explored and included.

We have developed a new series of multi-agent reinforcement learning algorithms that choose a policy based on beliefs about co-players¡Çpolicies. The algorithms are applicable to situations where a state is fully observable by the agents, but there is no limit on the number of players. Some of the algorithms employ embedded beliefs to handle the cases that co-players are also choosing a policy based on their beliefs of others¡Ç policies. Simulation experiments on Iterated Prisoners¡Ç Dilemma games show that the algorithms using on policy-based belief converge to highly mutually-cooperative behavior, unlike the existing algorithms based on action-based belief.

We briefly describe mentalizing, or understanding others' mental states, in an active research area of cognitive science. To overcome inaccessiblity of others' mental states, theoretical studies assume some mentalizing mechanism in the brain, including simulating others' behavior within knowledge of behavior of the self. We also present our computer-simulation study that tackles the role of mentalizing in a social environment, which examines behavior of agents based on reinforcement learning in Iterated Prisoners' Dilemma games. The results show that agents that choose actions using the estimated policy (corresponding to the mental state) of the co-player, achieve higher cooperation rates than control agents do, which choose actions using only the expected action of the co-player, or only the recent history of game plays.

I suggest that layer 4 of the shared circuits model (SCM) should monitor the failure of performing an action, instead of output inhibition, to obtain actual/possible and self/other distinction. The target article's assumption of selective inhibition leaves some questions unansweres, such asa the criteria for the selection. Monitoing failure can answer these questions because failure does not require selection. It also provices a basis for more likely explanation for the phylogenetic and ontogenetic origin of both monitoring and output inhibition.

We briefly describe mentalizing, or understanding others' mental states, in an active research area of cognitive science. To overcome inaccessiblity of others' mental states, theoretical studies assume some mentalizing mechanism in the brain, including simulating others' behavior within knowledge of behavior of the self. We also present our computer-simulation study that tackles the role of mentalizing in a social environment, which examines behavior of agents based on reinforcement learning in Iterated Prisoners' Dilemma games. The results show that agents that choose actions using the estimated policy (corresponding to the mental state) of the co-player, achieve higher cooperation rates than control agents do, which choose actions using only the expected action of the co-player, or only the recent history of game plays.

We present an algorithm for on-line, incremental discovery of temporal-difference (TD) networks. The key contribution is the establishment of three criteria to expand a node in TD network: a node is expanded when the node is well-known, independent, and has a prediction error that requires further explanation. Since none of these criteria requires centralized calculation operations, they are easily computed in a parallel and distributed manner, and scalable for bigger problems compared to other discovery methods of predictive state representations. Through computer experiments, we demonstrate the empirical effectiveness of our algorithm.