Shu-Ling SHIEH I-En LIAO Kuo-Feng HWANG Heng-Yu CHEN
This paper proposes an efficient self-organizing map algorithm based on reference point and filters. A strategy called Reference Point SOM (RPSOM) is proposed to improve SOM execution time by means of filtering with two thresholds T1 and T2. We use one threshold, T1, to define the search boundary parameter used to search for the Best-Matching Unit (BMU) with respect to input vectors. The other threshold, T2, is used as the search boundary within which the BMU finds its neighbors. The proposed algorithm reduces the time complexity from O(n2) to O(n) in finding the initial neurons as compared to the algorithm proposed by Su et al. [16] . The RPSOM dramatically reduces the time complexity, especially in the computation of large data set. From the experimental results, we find that it is better to construct a good initial map and then to use the unsupervised learning to make small subsequent adjustments.
In this paper, we propose an improved SO-PMI (Semantic Orientation Using Pointwise Mutual Information) algorithm, for use in Japanese Weblog Opinion Mining. SO-PMI is an unsupervised approach proposed by Turney that has been shown to work well for English. When this algorithm was translated into Japanese naively, most phrases, whether positive or negative in meaning, received a negative SO. For dealing with this slanting phenomenon, we propose three improvements: to expand the reference words to sets of words, to introduce a balancing factor and to detect neutral expressions. In our experiments, the proposed improvements obtained a well-balanced result: both positive and negative accuracy exceeded 62%, when evaluated on 1,200 opinion sentences sampled from three different domains (reviews of Electronic Products, Cars and Travels from Kakaku.com). In a comparative experiment on the same corpus, a supervised approach (SA-Demo) achieved a very similar accuracy to our method. This shows that our proposed approach effectively adapted SO-PMI for Japanese, and it also shows the generality of SO-PMI.
Yasushi HIDAKA Masashi SUGIYAMA
In order to obtain better generalization performance in supervised learning, model parameters should be determined appropriately, i.e., they should be determined so that the generalization error is minimized. However, since the generalization error is inaccessible in practice, the model parameters are usually determined so that an estimator of the generalization error is minimized. The regularized subspace information criterion (RSIC) is such a generalization error estimator for model selection. RSIC includes an additional regularization parameter and it should be determined appropriately for better model selection. A meta-criterion for determining the regularization parameter has also been proposed and shown to be useful in practice. In this paper, we show that there are several drawbacks in the existing meta-criterion and give an alternative meta-criterion that can solve the problems. Through simulations, we show that the use of the new meta-criterion further improves the model selection performance.
Shun GOKITA Masashi SUGIYAMA Keisuke SAKURAI
In order to obtain better learning results in supervised learning, it is important to choose model parameters appropriately. Model selection is usually carried out by preparing a finite set of model candidates, estimating a generalization error for each candidate, and choosing the best one from the candidates. If the number of candidates is increased in this procedure, the optimization quality may be improved. However, this in turn increases the computational cost. In this paper, we focus on a generalization error estimator called the regularized subspace information criterion and derive an analytic form of the optimal model parameter over a set of infinitely many model candidates. This allows us to maximize the optimization quality while the computational cost is kept moderate.
Estimating the generalization error is one of the key ingredients of supervised learning since a good generalization error estimator can be used for model selection. An unbiased generalization error estimator called the subspace information criterion (SIC) is shown to be useful for model selection, but its range of application is limited to linear learning methods. In this paper, we extend SIC to be applicable to non-linear learning.
Masashi SUGIYAMA Keisuke SAKURAI
For obtaining a higher level of generalization capability in supervised learning, model parameters should be optimized, i.e., they should be determined in such a way that the generalization error is minimized. However, since the generalization error is inaccessible in practice, model parameters are usually determined in such a way that an estimate of the generalization error is minimized. A standard procedure for model parameter optimization is to first prepare a finite set of candidates of model parameter values, estimate the generalization error for each candidate, and then choose the best one from the candidates. If the number of candidates is increased in this procedure, the optimization quality may be improved. However, this in turn increases the computational cost. In this paper, we give methods for analytically finding the optimal model parameter value from a set of infinitely many candidates. This maximally enhances the optimization quality while the computational cost is kept reasonable.
Masashi SUGIYAMA Hidemitsu OGAWA
Kernel-based learning algorithms have been successfully applied in various problem domains, given appropriate kernel functions. In this paper, we discuss the problem of designing kernel functions for binary regression and show that using a bell-shaped cosine function as a kernel function is optimal in some sense. The rationale of this result is based on the Karhunen-Loeve expansion, i.e., the optimal approximation to a set of functions is given by the principal component of the correlation operator of the functions.
Hiroyuki KAJI Yasutsugu MORIMOTO
An unsupervised method for word-sense disambiguation using bilingual comparable corpora was developed. First, it extracts word associations, i.e., statistically significant pairs of associated words, from the corpus of each language. Then, it aligns word associations by consulting a bilingual dictionary and calculates correlation between senses of a target polysemous word and its associated words, which can be regarded as clues for identifying the sense of the target word. To overcome the problem of disparity of topical coverage between corpora of the two languages as well as the problem of ambiguity in word-association alignment, an algorithm for iteratively calculating a sense-vs.-clue correlation matrix for each target word was devised. Word-sense disambiguation for each instance of the target word is done by selecting the sense that maximizes the score, i.e., a weighted sum of the correlations between each sense and clues appearing in the context of the instance. An experiment using Wall Street Journal and Nihon Keizai Shimbun corpora together with the EDR bilingual dictionary showed that the new method has promising performance; namely, the F-measure of its sense selection was 74.6% compared to a baseline of 62.8%. The developed method will possibly be extended into a fully unsupervised method that features automatic division and definition of word senses.
Kenichi YOSHIDA Fuminori ADACHI Takashi WASHIO Hiroshi MOTODA Teruaki HOMMA Akihiro NAKASHIMA Hiromitsu FUJIKAWA Katsuyuki YAMAZAKI
The volume of mass unsolicited electronic mail, often known as spam, has recently increased enormously and has become a serious threat not only to the Internet but also to society. This paper proposes a new spam detection method which uses document space density information. Although the proposed method requires extensive e-mail traffic to acquire the necessary information, it can achieve perfect detection (i.e., both recall and precision is 100%) under practical conditions. A direct-mapped cache method contributes to the handling of over 13,000 e-mail messages per second. Experimental results, which were conducted using over 50 million actual e-mail messages, are also reported in this paper.
Hiroki SASAMURA Toshimichi SAITO Ryuji OHTA
This paper presents a simple learning algorithm for network formation. The algorithm is based on self-organizing maps with growing cell structures and can adapt input data which correspond to nodes of the network. In basic numerical experiments, as a parameter is selected suitably, our algorithm can generate network having small-world-like structure. Such network structure appears in some natural networks and has advantages in practical systems.
This work explores generative models of handwritten digit images using natural elastic nets. The analysis aims to extract global features as well as distributed local features of handwritten digits. These features are expected to form a basis that is significant for discriminant analysis of handwritten digits and related analysis of character images or natural images.
Yasuyuki SUGAYA Kenichi KANATANI
Many techniques have been proposed for segmenting feature point trajectories tracked through a video sequence into independent motions, but objects in the scene are usually assumed to undergo general 3-D motions. As a result, the segmentation accuracy considerably deteriorates in realistic video sequences in which object motions are nearly degenerate. In this paper, we propose a multi-stage unsupervised learning scheme first assuming degenerate motions and then assuming general 3-D motions and show by simulated and real video experiments that the segmentation accuracy significantly improves without compromising the accuracy for general 3-D motions.
Masashi SUGIYAMA Hidemitsu OGAWA
In supervised learning, the selection of sample points and models is crucial for acquiring a higher level of the generalization capability. So far, the problems of active learning and model selection have been independently studied. If sample points and models are simultaneously optimized, then a higher level of the generalization capability is expected. We call this problem active learning with model selection. However, active learning with model selection can not be generally solved by simply combining existing active learning and model selection techniques because of the active learning/model selection dilemma: the model should be fixed for selecting sample points and conversely the sample points should be fixed for selecting models. In this paper, we show that the dilemma can be dissolved if there is a set of sample points that is optimal for all models in consideration. Based on this idea, we give a practical procedure for active learning with model selection in trigonometric polynomial models. The effectiveness of the proposed procedure is demonstrated through computer simulations.
Masanori SHIMADA Toshimichi SAITO
This paper presents a flexible learning algorithm for the binary neural network that can realize a desired Boolean function. The algorithm determines hidden layer parameters using a genetic algorithm. It can reduce the number of hidden neurons and can suppress parameters dispersion. These advantages are verified by basic numerical experiments.
Shouji SAKAMOTO Youichi KOBUCHI
To elucidate the mechanism of topographic organization, we propose a simple topographic mapping formation model from generalized cell layer to generalized cell layer. Here generalized cell layer means that we consider arbitrary cell neighborhood relations. In our previous work we investigated a topographic mapping formation model between one dimensional cell layers. In this paper we extend the cell layer structure to any dimension. In our model, each cell takes a binary state value and we consider a class of learning principles which are extensions of Hebb's rule and Anti-Hebb's rule. We pay special attention to correlation type learning rules where a synaptic weight value is increased if pre and post synaptic cell states have the same value. We first show that a mapping is stable with respect to the correlational learning if and only if it is semi-embedding. Second, we introduce a special class of weight matrices called band type and show that the set of band type weight matrices is strongly closed and such a weight matrix can not yield a topographic mapping. Third, we show by computer simulations that a mapping, if it is defined by a non band type weight matrix, converges to a topographic mapping under the correlational learning rules.
Masashi SUGIYAMA Hidemitsu OGAWA
In this paper, we consider the problem of active learning, and give a necessary and sufficient condition of sample points for the optimal generalization capability. By utilizing the properties of pseudo orthogonal bases, we clarify the mechanism of achieving the optimal generalization capability. We also show that the condition does not only provide the optimal generalization capability but also reduces the computational complexity and memory required to calculate learning result functions. Based on the optimality condition, we give design methods of optimal sample points for trigonometric polynomial models. Finally, the effectiveness of the proposed active learning method is demonstrated through computer simulations.
To enhance safety and traffic efficiency, a driver assistance system and an autonomous vehicle system are being developed. A preceding vehicle recognition method is important to develop such systems. In this paper, a vision-based preceding vehicle recognition method, based on supervised learning from sample images is proposed. The improvement for Modified Quadratic Discriminant Function (MQDF) classifier that is used in the proposed method is also shown. And in the case of road environment recognition including the preceding vehicle recognition, many researches have been reported. However in those researches, a quantitative evaluation with large number of images has rarely been done. Whereas, in this paper, over 1,000 sample images for passenger vehicles, which are recorded on a highway during daytime, are used for an evaluation. The evaluation result shows that the performance in a low order case is improved from the ordinary MQDF. Accordingly, the calculation time is reduced more than 20% by using the proposed method. And the feasibility of the proposed method is also proved, due to the result that the proposed method indicates over 98% as classification rate.
Akira HIRABAYASHI Hidemitsu OGAWA Akiko NAKASHIMA
In supervised learning, one of the major learning methods is memorization learning (ML). Since it reduces only the training error, ML does not guarantee good generalization capability in general. When ML is used, however, acquiring good generalization capability is expected. This usage of ML was interpreted by one of the present authors, H. Ogawa, as a means of realizing 'true objective learning' which directly takes generalization capability into account, and introduced the concept of admissibility. If a learning method can provide the same generalization capability as a true objective learning, it is said that the objective learning admits the learning method. Hence, if admissibility does not hold, making it hold becomes important. In this paper, we introduce the concept of realization of admissibility, and devise a realization method of admissibility of ML with respect to projection learning which directly takes generalization capability into account.
This paper surveys recent progress in the investigation of the underlying discrete proximity structures of geometric clustering with respect to the divergence in information geometry. Geometric clustering with respect to the divergence provides powerful unsupervised learning algorithms, and can be applied to classifying and obtaining generalizations of complex objects represented in the feature space. The proximity relation, defined by the Voronoi diagram by the divergence, plays an important role in the design and analysis of such algorithms.
Kei EGUCHI Takahiro INOUE Akio TSUNEDA
In this paper, a new digital chaos circuit which can generate multiple-scroll strange attractors is proposed. Being based on the piecewise-linear function which is determined by on-chip supervised learning, the proposed digital chaos circuit can generate multiple-scroll strange attractors. Hence, the proposed circuit can exhibit various bifurcation phenomena. By numerical simulations, the learning dynamics and the quasi-chaos generation of the proposed digital chaos circuit are analyzed in detail. Furthermore, as a design example of the integrated digital chaos circuit, the proposed circuit realizing the nonlinear function with five breakpoints is implemented onto the FPGA (Field Programmable Gate Array). The synthesized FPGA circuit which can generate n-scroll strange attractors (n=1, 2, 4) showed that the proposed circuit is implementable onto a single FPGA except for the SRAM.