- Title
- On the Rigidity of a Vandermonde Matrix
- Author(s)
- Tatsuie Tsukiji
- Contact person
- Tatsuie Tsukiji (tsukiji@cs.titech.ac.jp)
- Abstract
-
- Title
- Analysis of a Japanese compound noun using collocatinal
information
- Author(s)
- Kobayasi Yosiyuki
- Contact person
- Tokunaga Takenobu (take@cs.titech.ac.jp)
- Abstract
- This paper proposes a method to analyze the structure of compound
nouns by using collocational information which are extracted from text
and ordinary dictionaries. The method has two parts: the part for
analysis of the dependecy structure and the part for analysis of the
syntactic relation.
- Title
- Integrating connection constraints into a GLR parser and its
applications in a continuous speech recognition system
- Author(s)
- Hui Li
- Contact person
- Hozumi Tanaka tanaka@cs.titech.ac.jp
- Abstract
- This paper proposes a method to analyze the structure of compound
nouns by using collocational information which are extracted from text
and ordinary dictionaries. The method has two parts: the part for
analysis of the dependecy structure and the part for analysis of the
syntactic relation.
In this thesis, I propose a new method for integrating connection
constraints into the GLR parsing algorithm. I propose an algorithm
for generating an LR table that combines both a grobal constraint and
a local constraint.
- Title
- Optimal two-level unequal error control codes for computer
systems
- Author(s)
- Tepparit Ritthongpitak, Masato Kitakami and Eiji Fujiwara
- Contact person
- Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
- Abstract
- This paper proposes a method to analyze the structure of compound
nouns by using collocational information which are extracted
from text and ordinary dictionaries. The method has two parts: the
part for analysis of the dependecy structure and the part for analysis
of the syntactic relation. In this thesis, I propose a new method for
integrating connection constraints into the GLR parsing algorithm. I
propose an algorithm for generating an LR table that combines both a
grobal constraint and a local constraint. Error control codes are now
successfully applied to computer systems, especially to memory
systems. This paper proposes an extended class of unequal error
control codes which protects the fixed-byte strongly in computer words
from multiple errors. The fixed-byte stores valuable information such
as control and address information in computer/communication messages
or pointer information in database words. Here, fixed-byte means the
clustered information digits in the word whose position is determined
in advance. As a simple and practical class of the codes, this paper
proposes an extended type of two-level unequal error control codes
which has two error control levels in the codeword; one with strong
error control function for the fixed-byte, and the other with weak
function for the other part of the codeword. The proposed optimal
codes are single-bit error correction, double-bit error detection and
fixed b-bit byte error correction code, called SEC-DED-FbEC code, and
single-bit plus fixed b-bit byte error correction code, called
(S+Fb)EC code, which corrects single-bit errors and fixed-byte errors
occurring simultaneously. For both types of codes, this paper
clarifies necessary and sufficient conditions and bounds on code
length, and demonstrates code construction method of the optimal codes
and evaluation of these codes from the perspectives of error
correction/detection capability and decoder hardware complexity.
- Title
- Admissibility of memorization learning with respect to
projection learning in the presence of noise
- Author(s)
- Akira Hirabayashi and Hidemitsu Ogawa
- Contact person
- Akira Hirabayashi (hira@cs.titech.ac.jp)
- Abstract
- This paper proposes a method to analyze the structure of compound
nouns by using collocational information which are extracted
from text and ordinary dictionaries. The method has two parts: the
part for analysis of the dependecy structure and the part for analysis
of the syntactic relation. In this thesis, I propose a new method for
integrating connection constraints into the GLR parsing algorithm. I
propose an algorithm for generating an LR table that combines both a
grobal constraint and a local constraint. Error control codes are now
successfully applied to computer systems, especially to memory
systems. This paper proposes an extended class of unequal error
control codes which protects the fixed-byte strongly in computer words
from multiple errors. The fixed-byte stores valuable information such
as control and address information in computer/communication messages
or pointer information in database words. Here, fixed-byte means the
clustered information digits in the word whose position is determined
in advance. As a simple and practical class of the codes, this paper
proposes an extended type of two-level unequal error control codes
which has two error control levels in the codeword; one with strong
error control function for the fixed-byte, and the other with weak
function for the other part of the codeword. The proposed optimal
codes are single-bit error correction, double-bit error detection and
fixed b-bit byte error correction code, called SEC-DED-FbEC code, and
single-bit plus fixed b-bit byte error correction code, called
(S+Fb)EC code, which corrects single-bit errors and fixed-byte errors
occurring simultaneously. For both types of codes, this paper
clarifies necessary and sufficient conditions and bounds on code
length, and demonstrates code construction method of the optimal codes
and evaluation of these codes from the perspectives of error
correction/detection capability and decoder hardware complexity. In
the training of multilayered feedforward neural networks using the
error-backpropagation(BP) algorithm, it has been observed that
the error over non-training set may increase, even though the error
over training set decreases. This phenomenon is referred to as
over-learning. In the previous works we showed how over-learning can
be viewed as being the result of using the BP criterion as a
substitute for some true criterion. There, the concept of
admissibility, which is defined using the relationship between the two
criteria, was introduced. In this paper we consider the case where
the true criterion is the projection learning criterion, and give the
necessary and sufficient conditions for the projection learning to
admit memorization learning in the presence of noise. Based on these
conditions, we devise a method of choosing the training sets so that
the admissibility conditions are satisfied.
- Title
- A functional analytic approach to incremental learning in optimally generalizing neural networks
- Author(s)
- Sethu Vijayakumar and Hidemitsu Ogawa
- Contact person
- Sethu Vijayakumar (sethu@cs.titech.ac.jp)
- Abstract
- For a given set of training data, a method of learning for optimally
generalizing neural networks using functional analytic approach already
exists. Here, we consider the case when additional training
data is made available at a later stage. We devise a method of
carrying out optimal learning with respect to the entire set of
training data (including the newly added one) using the results
of the previously learned stage. This ensures that the learning
operator and the learned function can both be computed incrementally,
leading to a reduced computational cost. Finally, we also provide a
simplified relationship between the newly learned function and the
previous function, opening avenues for work into selection of optimal
training set.
- Title
- An improvement of the digital cash protocol of Okamoto and Ohta
- Author(s)
- Osamu Watanabe and Osamu Yamashita
- Contact person
- Osamu Watanabe (watanabe@cs.titech.ac.jp)
- Abstract
- Okamoto and Ohta proposed a digital cash protocol
and showed that it satisfies some useful properties for digital
cash as well as basic requirements such as security. One of its
features is ``divisibility''; i.e., a property that enable us to
subdivide a piece of given digital cash into several pieces of smaller
value. This feature is made possible in Okamoto-Ohta protocol by
using ``hierarchical structure table'', which is, intuitively, a
collection of small coins. That is, in Okamoto-Ohta protocol, one
piece of digital cash is a collection of small coins, and a user can
select some of them for his/her payment. Then naturally, the amount
of data transfer per payment may increase depending on the amount of
the payment and how the coins have been used. Here we propose a new
protocol in which one digital cash can be regarded as a check book.
That is, for each payment, a user can write a figure (within the
limit) on one page of his/her digital check book, and pass it to a
merchant. Thus, in this protocol, we can fix the amount of data
transfer per payment, which is much smaller than the average amount
necessary in Okamoto-Ohta protocol. For Okamoto-Ohta protocol, some
cryptographic tools have been used, and for justifying them, we need
some assumptions from computational complexity theory and
computational cryptography such as the existence of public-key
cryptosystems. Our new protocol, which uses essentially the same
cryptographic tools, is also based on such assumptions.
- Title
- NP-completeness results for NONOGRAM via parsimonious
reductions
- Author(s)
- Nobuhisa Ueda and Tadaaki Nagao
- Contact person
- Nobuhisa Ueda (ueda@cs.titech.ac.jp)
- Abstract
- We introduce a new class of NP problems called ANOTHER SOLUTION
PROBLEMs. For a given NP problem X, ANOTHER SOLUTION PROBLEM
for X (ASP for X) is to ask, for a given
instance I for X and its solution, whether
there is another solution for I. The difficulty of
ASP for X may not be immediate from the difficulty of
X. For example, for some NP-complete problems such as
3SAT or 3DM,
it is easy to show that their ASPs are NP-complete; on the other hand,
ASP for, e.g., VERTEX COLORING is trivially in P. In this paper, we
propose one approach for showing the NP-completeness of ASP for a
given NP problem X. That is, for some NP problem
Y for which it
is provable that ASP is NP-complete, we show a parsimonious reduction
from Y to X that has the following additional
property: given a
solution for an instance for Y, a solution for the
corresponding
instance for X is computable in polynomial time. Then the
NP-completeness of ASP for Y clearly implies that of ASP for
X.
As an example of this approach, we demostrate the NP-completeness of
ASP for one interesting puzzle ``NONOGRAM''.
- Title
- Partial Occam's razor and its applications
- Author(s)
- Carlos Domingo, Tatsuike Tsukiji and Osamu Watanabe
- Contact person
- Osamu Watanabe (watanabe@cs.titech.ac.jp)
- Abstract
- We introduce the notion of ``partial Occam algorithm''.
A partial Occam algorithm produces a succinct hypothesis that
is partially consistent with given examples, where the proportion of
consistent examples is a bit more than half. By using this new
notion, we propose one approach for obtaining a PAC learning
algorithm. First, as shown in this paper, a partial Occam algorithm
is equivalent to a weak PAC learning algorithm. Then by using
boosting techniques of Schapire or Freund, we can obtain an ordinary
PAC learning algorithm from this weak PAC learning algorithm. We
demonstrate some examples that some improvement is possible by this
approach. First we obtain a new (non-proper) PAC learning algorithm
for k-DNF, which has similar sample complexity as Littlestone's
Winnow, but produces hypothesis of size polynomial in
d and logk
for a k-DNF target with n variables and
d terms (Cf. The hypothesis size of Winnow is
O(nk). Next we show that
1-decision lists of length d with n variables
are (non-proper) PAC learnable by using
O(1/epsilon (log 1/delta + 16d log n (d + log
log n)2))
examples within polynomial time w.r.t. n,
2d, 1/epsilon, and
log 1/delta. Thus, for example, a class of decision lists of
length O(log n) is polynomial time PAC learnable.
- Title
- The application of machine learning to student modeling: A
survey and comparative analysis
- Author(s)
- Raymund Sison and Masamichi Shimura
- Contact person
- Raymund Sison (sison@cs.titech.ac.jp)
- Abstract
- We first review and analyze using a common framework the various
ways in which machine learning techniques have been used in student
modeling, from LMS (Sleeman, 1982) to SMS1 (Sison and Reyes, 1995).
The major limitations of these works are the brute force style of
inductive approaches to learning malrules and the relatively
unintelligible malrules learned using the deductive application of
perturbation rules. We then outline how two machine learning methods
-- theory revision and conceptual clustering -- can be used to
overcome these limitations.
- Title
- Incremental clustering of relational descriptions
- Author(s)
- Raymund Sison and Masamichi Shimura
- Contact person
- Raymund Sison (sison@cs.titech.ac.jp)
- Abstract
- We present an algorithm for the incremental clustering of relational
descriptions. Major clustering algorithms in the literature can so
far handle only attribute-value representations, though a few can
handle ground relations. Preliminary results of applying the
algorithm to the problem of bug interpretation in student modeling
are presented and discussed.
- Title
- OSL language specification ver.2.0 (in Japanese)
- Author(s)
- Yasuhiro Iida
- Contact person
- Yasuhiro Iida (iida@cs.titech.ac.jp)
- Abstract
- This article defines the specification of OSL (ver.2.0).
OSL is the description language of OOAG, which is
a computational model based on attribute grammars
extended with object-oriented features.
The goal of OOAG is to describe and generate
language-based software databases.
The rest part of the article is written in Japanese.
New features from ver.1.0 are as follows:
static type system, structured data types,
objects as data, revised remote object reference,
external class (interface to C++),
attribution for attribute values,
some restriction of message passing for efficiency,
built-in infix operators.
- Title
- Constructing the campus network of Tokyo Institute of
Technology
- Author(s)
- Yutaka Kikuchi
- Contact person
- Yutaka Kikuchi kikuchi@cs.titech.ac.jp
- Abstract
- The author turns out difficulties of volunteer based LAN management
and provides some hints on proceeding it to business based management.
First, the paper points out that a LAN would be faced with a
fatal situation when it is managed by volunteers because of
hidden difficulties.
Second, the paper shows an experience in constructing a LAN of
Tokyo Institute of Technology in early 1994.
The example provides some hints on proceeding to business based
LAN management that is a solution of volunteer based one.
The paper is a handout of the invited talk at JUS UNIX
Symposium in August 1994.
- Title
- #P-completeness of counting graph edge colorings
- Author(s)
- Tadaaki Nagao
- Contact person
- Tadaaki Nagao (nagao@cs.titech.ac.jp)
- Abstract
- The problem of counting the number of edge-colorings of a graph
is called #EDGE-COLORING. While the associated decision problem was
proved to be NP-complete, deciding whether a given graph is uniquely
edge-colorable is known to be computable in polynomial time. And it
is known that if #EDGE-COLORING is reducible from #SAT via a
reduction that preserves the number of solutions, then P = NP. This
aspect of #EDGE-COLORING is somewhat significant beside hundreds of
known NP-complete problems. In this paper, we prove that
#EDGE-COLORING, however, still remains #P-complete.
- Title
- Simple yet effective algorithms for constraint satisfaction
and related problems (doctoral thesis)
- Author(s)
- Hoong Chuin Lau
- Contact person
- Hoong Chuin Lau (hclau@cs.titech.ac.jp)
- Abstract
- In this thesis, we are mainly concerned with the design and
analysis of simple yet provably effective algorithms to tackle various
Constraint Satisfaction (CSP) and related problems. The main topics
of discussion are as follows. We will study the computational
complexity of and exact algorithms for restricted forms of the
standard CSP. We will consider random CSP instances and study the
behavior of several types of local search algorithms. We show
conditions under which local search performs well with high
probability, both theoretically and experimentally. We next consider
CSP optimization problems, namely, finding an assignment which
maximizes certain linear objective functions. For this, we will first
propose and analyse the worst-case behavior of local search algorithms
in finding approximate solutions. Next, we will propose and analyse a
new approach based on the randomized rounding of mathematical
programs. Our theoretical results improve several known results in
approximation of NP-hard problems. In the final part of this thesis,
we will present efficient algorithms to solve a special case of the
CSP, the manpower scheduling problem, which has direct real-world
applications.
- Title
- On data integration in software development environments
based on object-oriented attribute grammars: OOAG
(In Japanese)
- Author(s)
- Katsuhiko Gondow and Takuya Katayama
- Contact person
- Katsuhiko Gondow (gondow @cs.titech.ac.jp)
- Abstract
- We show the advantages and disadvantages of Object-Oriented Attribute
Grammars (OOAG) when applying it to data modelling in software
development environments (SDEs). Attribute grammar approach for SDEs
has many positive characteristics such as high readable and high
maintainable description, high integration and fine granurarity due to
abstract syntax tree, automatic generation of incremental attribute
evaluator as change propagation engine. But attribute grammars lack
many object management issues like concurrency control, transactions,
interactiveness. OOAG has been introduced to solve these drawbacks of
attribute grammars. This paper shows the OOAG power of: (1) multiple
subtree replacement by calculation, (2) remote object reference, as
well as some problems that OOAG have not solved yet. The rest part of
this report is written in Japanese.
- Title
- Algorithms for learning finite automata from queries: a
unified view
- Author(s)
- Jose José L. Balcázar, Josep Díaz,
Ricard Gavald\`{a} and Osamu Watanabe
- Contact person
- Osamu Watanabe (watanabe@cs.titech.ac.jp)
- Abstract
- In this survey we compare several known variants of the
algorithm for learning deterministic finite automata via
membership and equivalence queries. We believe that our
presentation makes it easier to understand what is going
on and what the differences between the various algorithms
mean. We also include the comparative analysis of the
algorithms, review some known lower bounds, prove a new one,
and discuss the question of parallelizing this sort of
algorithms.
- Title
- Coding complexity: the computational complexity of succinct
descriptions
- Author(s)
- José L. Balcázar, Ricard Gavaldà and Osamu
Watanabe
- Contact person
- Osamu Watanabe (watanabe@cs.titech.ac.jp)
- Abstract
- For a given set of strings,
the problem of obtaining a succinct description
becomes an important subject of research,
related to several areas of theoretical computer science.
In structural complexity theory,
researchers have developed
a reasonable framework for studying the complexity of these problems.
In this paper,
we survey how such investigation has proceeded,
and explain the current status of our knowledge.
- Title
- A computational approach to the orientation selectivity
problem I: a mathematical framework and some experimental
results
- Author(s)
- Tadashi Yamazaki and Osamu Watanabe
- Contact person
- Osamu Watanabe (watanabe@cs.titech.ac.jp)
- Abstract
- Neurobiologists have found, in the primary visual cortex (area 17) of
cat and monkey, some group of neurons that show ``orientation
selectivity'', or ``orientation preference''. That is, each of such
neurons reacts strongly to the presentation of light bars of a certain
orientation. Furthermore, there is some evidence that such
orientation selectivity is obtained in some animals through the
training during the very early stage after the birth. Neuroscientists
have proposed several models explaining this process of developing
orientation selectivity. In fact, some of such models have been
investigated mathematically. Nevertheless, the problem has not been
fully understood, and one can still look into it from different view
points. In this paper, we propose one mathematical framework, or a
mathematical abstraction, on which we compare the behavior of several
models for the selectivity.
- Title
- Reliable logic circuits with byte error control codes -- a
feasibility study
- Author(s)
- Jien-Chung Lo, Masato Kitakami and Eiji Fujiwara
- Contact person
- Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
- Abstract
- This paper addresses the relations between logic circuit synthesis,
error model and error control codes so that the efficient
reliable logic circuits can be obtained. We propose that single fault
masking capability of a random logic circuit can be obtained by
encoding its outputs in a byte error correcting code; this is
equivalent to that of the triple modulo redundancy (TMR)
technique. Similarly, byte error detecting code can be used to provide
an equivalence of duplication. In this paper, we address the problems
and issues related to the realization of byte-organized configuration
where the byte error control codes can be applied. Some MCNC benchmark
circuits are used as examples to demonstrate the feasibility of the
proposed concept.
- Title
- Metrics of error locating codes
- Author(s)
- Masato Kitakami, Shuxin Jiang and Eiji Fujiwara
- Contact person
- Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
- Abstract
- Error locating codes were first presented by J. K. Wolf and B. Elspas
in 1963. Recently, the error locating codes suitable for
byte-organized semiconductor memory systems have been proposed. It is
apparent that code conditions of error correcting/detecting codes are
expressed by Hamming distance, but, on the other hand, those of error
locating codes cannot always be expressed by only Hamming
distance. That is, algebraic structure of the error locating codes has
not yet been clarified. This paper deduces the necessary and
sufficient conditions of the error locating codes by using a newly
defined metric and the function which represents the number of the
bytes where Hamming distance between corresponding bytes of two
codewords has a certain integer region. These conditions clarify the
relation between the error locating codes and the error
correcting/detecting codes. That is, the error locating code which can
locate any byte errors is an error correcting code and if the byte
length is equal to code length, an error locating code is an error
detecting code.
- Title
- Concept formation in noisy domains
- Author(s)
- Xiaolong Zhang and Masayuki Numao
- Contact person
- Xiaolong Zhang (zxl@cs.titech.ac.jp)
- Abstract
- In inductive logic programming, concept formation in noisy domains
can be considered as learning from noisy data. This paper
describes an approach to learning from noisy examples with an
approximate theory. Although this kind of learning is more close to
practical application, there are few systems can deal with such
problems. The proposed learning approach includes a theory preference
criterion and an overfitting avoidance technique. The theory
preference criterion is a coding scheme which extends the minimum
description length (MDL) principle principle by unifying model
complexity and exception cost. Model complexity is the encoding cost
for an algorithm to obtain a logic program; exception cost is encoding
length of the training examples misclassified by a theory. By means
of overfitting avoidance technique, the system learns more accurate
clauses from the remainder of the training set after a revision
session. Accounting for the above cases, our approach performs more
accurately and efficiently compared with existing approaches.
- Title
- Probability to achieve TSC goal
- Author(s)
- Jien-Chung Lo and Eiji Fujiwara
- Contact person
- Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
- Abstract
- In this paper we propose a probabilistic measure for self-checking (SC)
circuits that is analogous to reliability of fault-tolerant
systems. This measure is defined as the probability to achieve
totally self-checking (TSC) goal at the t-th cycle: TSCG(t). TSCG
provides insight to the worst case dynamic behavior of SC circuits
with respect to the application environment and component failure
rates. TSCG surpasses the TSC definitions in determining the
applicability of a circuit in a given application environment. An SC
circuit achieves TSC goal when no erroneous information or data is
propagated beyond the boundary of this circuit. TSCG is therefore the
probability that this fault confinement mechanism is intact. The SC
properties are obtained through adding hardware redundancy to the
original design. Which means that an SC circuit has a higher failure
rate than the original circuit. Further, there are tradeoffs between
the level of hardware redundancy, the reliability, and the TSCG. We
give several examples in this paper to clearly demonstrate these
tradeoffs for different design environments. The proposed probability
measure allows designers to choose from cost-effective SC designs that
are suitable for their specifications. We emphasize that the TSCG is
intended to provide a mean of dynamic error handling performance
evaluation of SC designs. The TSC definitions and alike are still
intact, since a cost-effective SC circuit must begin with a TSC
circuit. The TSCG gives confidence in the use of cost-effective error
control codes and/or reduction in error handling capability. Analogous
to reliability, the TSCG can be used in product specifications. This
is a crucial step toward the practical applications of TSC or CED
circuits.