With the increase of the number of elderly people living alone around the world, there is a growing demand for sensor-based detection of anomalous behaviors. Although smart homes with ambient sensors could be useful for detecting such anomalies, there is a problem of lack of sufficient real data for developing detection algorithms. For coping with this problem, several sensor data simulators have been proposed, but they have not been able to model appropriately the long-term transitions and correlations between anomalies that exist in reality. In this article, therefore, we propose a novel sensor data simulator that can model these factors in generation of sensor data. Anomalies considered in this study were classified into three types of state anomalies, activity anomalies, and moving anomalies. The simulator produces ten years data in 100 min, including six anomalies, two for each type. Numerical evaluations based on edit distance between activity series show that this simulator is superior to the past simulators in the sense that it simulates well day-to-day variations of real data.

Multi-task learning (MTL) improves generalization by sharing information among related tasks. Structured sparsity-inducing regularization has been widely used in MTL to learn interpretable and compact models, especially in high-dimensional settings. These methods have achieved much success in practice, however, there are still some key limitations, such as limited generalization ability due to specific sparse constraints on parameters, usually restricted in matrix form that ignores high-order feature interactions among tasks, and formulated in various forms with different optimization algorithms. Inspired by Generalized Lasso, we propose the Generalized Group Lasso (GenGL) to overcome these limitations. In GenGL, a linear operator is introduced to make it adaptable to diverse sparsity settings, and helps it to handle hierarchical sparsity and multi-component decomposition in general tensor form, leading to enhanced flexibility and expressivity. Based on GenGL, we propose a novel framework for Structured Sparse MTL (SSMTL), that unifies a number of existing MTL methods, and implement its two new variants in shallow and deep architectures, respectively. An efficient optimization algorithm is developed to solve the unified problem, and its effectiveness is validated by synthetic and real-world experiments.

In multi-task learning (MTL), multiple prediction tasks are learned jointly, such that generalization performance is improved by transferring information across the tasks. However, not all tasks are related, and training unrelated tasks together can worsen the prediction performance because of the phenomenon of negative transfer. To overcome this problem, we propose a novel MTL method that can robustly group correlated tasks into clusters and allow useful information to be transferred only within clusters. The proposed method is based on the assumption that the task clusters lie in the low-rank subspaces of the parameter space, and the number of them and their dimensions are both unknown. By applying subspace clustering to task parameters, parameter learning and task grouping can be done in a unified framework. To relieve the error induced by the basic linear learner and robustify the model, the effect of hidden tasks is exploited. Moreover, the framework is extended to a multi-layer architecture so as to progressively extract hierarchical subspace structures of tasks, which helps to further improve generalization. The optimization algorithm is proposed, and its effectiveness is validated by experimental results on both synthetic and real-world datasets.

Multi-Label Classification (MLC), which aims to assign multiple labels to each sample simultaneously, has achieved great success in a wide range of applications. MLC saves global label correlation by building a single model shared by all samples but ignores sample-specific local structures, while Personalized Learning (PL) is able to preserve sample-specific information by learning local models but ignores the global structure. Integrating PL with MLC is a straightforward way to overcome the limitations, but it still faces three key challenges. 1) capture both local and global structures in a unified model; 2) efficiently preserve high-order interactions among labels, features and samples; 3) learn a concise and interpretable model where only a fraction of interactions are associated with multiple labels. In this paper, we propose a novel Multi-Label Personalized Classification (MLPC) method to handle these challenges. For 1), it integrates local and global components to preserve sample-specific information and global structure shared across samples, respectively. For 2), a multilinear model is developed to capture high-order interactions, and over-parameterization is avoided by tensor factorization. For 3), exclusive sparsity regularization penalizes factorization by promoting intra-group competition, thereby eliminating irrelevant and redundant interactions during Exclusive Sparse Tensor Factorization (ESTF). Moreover, theoretical analysis reveals the equivalence between MLPC with a family of jointly regularized counterparts. We develop an alternating algorithm to solve the optimization problem, and extensive experiments on various datasets demonstrate its effectiveness.

The number of elderly people living alone has been increasing worldwide. The Internet of Things (IoT) technology has a high potential in protecting them from risks such as falls. This can be achieved by continuously monitoring the behavior of the residents in a smart home. To develop anomaly detection algorithms in such smart homes, we need a simulator to produce realistic sensor data over a long period of time. Unfortunately, however, existing simulators lack a high degree of reproducibility.In this study, we developed a novel behavioral simulator centered on wandering behavior. Users can easily and intuitively embed their knowledge in the simulator, keeping the exact definitions of target anomalies. Sensor data can be obtained from several types of sensors attached to the simulated home. We focus on simulating wandering behavior as an important anomaly, considering the degree of progress of dementia as a latent variable. We show that the proposed simulator is more usable than previous simulators from the view point of reproducibility.

We had previously proposed a supervised Laplacian eigenmap for visualization (SLE-ML) that can handle multi-label data. In addition, SLE-ML can control the trade-off between the class separability and local structure by a single trade-off parameter. However, SLE-ML cannot transform new data, that is, it has the “out-of-sample” problem. In this paper, we show that this problem is solvable, that is, it is possible to simulate the same transformation perfectly using a set of linear sums of reproducing kernels (KSLE-ML) with a nonsingular Gram matrix. We experimentally showed that the difference between training and testing is not large; thus, a high separability of classes in a low-dimensional space is realizable with KSLE-ML by assigning an appropriate value to the trade-off parameter. This offers the possibility of separability-guided feature extraction for classification. In addition, to optimize the performance of KSLE-ML, we conducted both kernel selection and parameter selection. As a result, it is shown that parameter selection is more important than kernel selection. We experimentally demonstrated the advantage of using KSLE-ML for visualization and for feature extraction compared with a few typical algorithms.

Approximate nearest neighbor search (ANNS) is a fundamental problem that has a wide range of applications in information retrieval and data mining. Among state-of-the-art in-memory ANNS methods, graph-based methods have attracted particular interest owing to their superior efficiency and query accuracy. Most of these methods focus on the selection of edges to shorten the search path, but do not pay much attention to the computational cost at each hop. To reduce the cost, we propose a novel graph structure called HVS. HVS has a hierarchical structure of multiple layers that corresponds to a series of subspace divisions in a coarse-to-fine manner. In addition, we utilize a virtual Voronoi diagram in each layer to accelerate the search. By traversing Voronoi cells, HVS can reach the nearest neighbors of a given query efficiently, resulting in a reduction in the total search cost. Experiments confirm that HVS is superior to other state-of-the-art graph-based methods.

We propose a method of converting a real-weighted voting classifier to a compact integer-weighted voting classifier. Real-weighted voting classifiers like those trained using boosting are very popular and widely used due to their high prediction performance. Real numbers, however, are space-consuming and its floating-point arithmetic is slow compared to integer arithmetic, so compact integer weights are preferable for implementation on devices with small computational resources. Our conversion makes use of given feature vectors and solves an integer linear programming problem that minimizes the sum of integer weights under the constraint of keeping the classification result for the vectors unchanged. According to our experimental results using datasets of UCI Machine Learning Repository, the bit representation sizes are reduced to $5.2$-$33.4$% within $3.7$% test accuracy degrade in 7 of 8 datasets for the weighted voting classifiers of decision stumps learned using AdaBoost-SAMME.

Locality sensitive hashing (LSH) is a widely practiced c-approximate nearest neighbor (c-ANN) search algorithm because of its appealing theoretical guarantee and empirical performance. However, available LSH-based solutions do not achieve a good balance between cost and quality because of certain limitations in their index structures. In this paper, we propose a novel and easy-to-implement disk- based method named R2LSH to answer ANN queries in high-dimensional spaces. In the indexing phase, R2LSH maps data objects into multiple two-dimensional projected spaces. In each space, a group of B+-trees is constructed to characterize the corresponding data distribution. In the query phase, by setting a query-centric ball in each projected space and using a dynamic counting technique, R2LSH efficiently determines candidates and returns query results with the required quality. Rigorous theoretical analysis reveals that the proposed algorithm supports c-ANN search for arbitrarily small c ≥ 1 with probability guarantee. Extensive experiments on real datasets verify the superiority of R2LSH over state-of-the-art methods.

Locality sensitive hashing (LSH) is a widely practiced c -approximate nearest neighbor( c -ANN) search algorithm in high dimensional spaces. The state-of-the-art LSH based algorithm searches an unbounded and irregular space to identify candidates, which jeopardizes the efficiency. To address this issue, we introduce the concept of virtual hypersphere partitioning. The core idea is to impose a virtual hypersphere, centered at the query, in the original feature space and only examine points inside the hypersphere. The search space of a hypersphere is isotropic and bounded, and thus more efficient than the existing one. In practice, we use multiple physical hyperspheres with different radii in corresponding projection subspaces to emulate the single virtual hypersphere. We also developed a principled method to compute the hypersphere radii for given success probability. Based on virtual hypersphere partitioning, we propose a novel disk-based indexing and searching scheme VHP to answer c -ANN queries. In the indexing phase, VHP stores LSH projections with independent B + -trees. To process a query, VHP keeps increasing the radii of physical hyperspheres co-ordinately, which in effect amounts to enlarging the virtual hypersphere, to accommodate more candidates until the success probability is met. Rigorous theoretical analysis shows that the proposed algorithm supports c -ANN search for arbitrarily small c ≥ 1 with probability guarantee. Extensive experiments on a variety of datasets, including the billion-scale ones, demonstrate that VHP could achieve different tradeoffs between efficiency and accuracy, and achieves up to 2x speedup in running time over the state-of-the-art methods.

Multi-label classification aims to assign multiple labels to a single test instance. Recently, more and more multi-label classification applications arise as large-scale problems, where the numbers of instances, features and labels are either or all large. To tackle such problems, in this paper we develop a clustering-based local multi-label classification method, attempting to reduce the problem size in instances, features and labels. Our method consists of low-dimensional data clustering and local model learning. Specifically, the original dataset is firstly decomposed into several regular-scale parts by applying clustering analysis on the feature subspace, which is induced by a supervised multi-label dimension reduction technique; then, an efficient local multi-label model, meta-label classifier chains, is trained on each data cluster. Given a test instance, only the local model belonging to the nearest cluster to it is activated to make the prediction. Extensive experiments performed on eighteen benchmark datasets demonstrated the efficiency of the proposed method compared with the state-of-the-art algorithms.

Multi-label classification (MLC), allowing instances to have multiple labels, has been received a surge of interests in recent years due to its wide range of applications such as image annotation and document tagging. One of simplest ways to solve MLC problems is label-power set method (LP) that regards all possible label subsets as classes. LP validates traditional multi-classification classifiers such as multi-class SVM but it suffers from the increased number of classes. Therefore, several improvements have been made for LP to be scaled for large problems with many labels. Random k labELsets (RAkEL) proposed by Tsoumakas et al. solves this problem by randomly sampling a small number of labels and taking ensemble of them. However, RAkEL needs all instances for constructing each model and thus suffers from high computational complexity. In this paper, we propose a new fast algorithm for RAkEL. First, we assign each training instance to a small number of models. Then LP is applied for each model with only the assigned instances. Experiments on twelve benchmark datasets demonstrated that the proposed algorithm works faster than the conventional methods while keeping accuracy. In the best case, it was 100 times faster than baseline method (LP) and 30 times faster than the original RAkEL.

Visualization helps us to understand single-label and multi-label classification problems. In this paper, we show several standard techniques for simultaneous visualization of samples, features and multi-classes on the basis of linear regression and matrix factorization. The experiment with two real-life multi-label datasets showed that such techniques are effective to know how labels are correlated to each other and how features are related to labels in a given multi-label classification problem.

Lately, multi-label classification (MLC) problems have drawn a lot of attention in a wide range of fields including medical, web, and entertainment. The scale and the diversity of MLC problems is much larger than single-label classification problems. Especially we have to face all possible combinations of labels. To solve MLC problems more efficiently, we focus on three kinds of locality hidden in a given MLC problem. In this paper, first we show how large degree of locality exists in nine datasets, then examine how closely they are related to labels, and last propose a method of reducing the problem size using one kind of locality.

Multi-label classification has attracted many attentions in various fields, such as text categorization and semantic image annotation. Aiming to classify an instance into multiple labels, various multi-label classification methods have been proposed. However, the existing methods typically build models in the identical feature (sub)space for all labels, possibly inconsistent with real-world problems. In this paper, we develop a novel method based on the assumption that meta-labels with specific features exist in the scenario of multi-label classification. The proposed method consists of meta-label learning and specific feature selection. Experiments on twelve benchmark multi-label datasets show the efficiency of the proposed method compared with several state-of-the-art methods.

Recording of the activity of people working in an office or in a living room is important for several goals: to design an evacuation route, to measure the degree of ADL (Activity of Daily Living) of single-living elderly persons, and to analyze the working contents of people, and so on. Camera systems are available for these goals, but they are weak for the light condition change (not available at dark in general) and invasive for the users' privacy. Therefore, we use an infrared ceiling sensor network for localizing moving people and use some extra pieces of evidence for identifying them. Such ID evidence is taken from a finger-vein authentication system at the entrance/exit and from the staying duration at their personal desks. The kind of activity of individuals is determined by the locations and the staying duration related to those activities, e.g., spending two minutes or more at kitchen means “cooking.” A challenging task is to find how to recover missing IDs and related their activities. This sometimes happens when two or more persons cross or meet at a place or someone sits at a desk silently, because a motion sensor reacts only when something with human temperature “moves” in the focus of view. This system succeeded in recording of the activity of three persons for three hours at 87.4% and six persons for seven hours at 15.0%.

Nonnegative Tensor Factorization (NTF) has become a popular tool for extracting informative patterns from tensor data. However, NTF has high computational cost both in space and in time, mostly in iterative calculation of the gradient. In this paper, we consider variable selection to reduce the cost, assuming sparsity of the factor matrices. In fact, it is known that the factor matrices are often very sparse in many applications such as network analysis, text analysis and image analysis. We update only a small subset of important variables in each iterative step. We show the effectiveness of the algorithm analytically and experimentally in comparison with conventional NTF algorithms. The algorithm was five times faster than the naive algorithm in the best case and required one to five hundred times less memory while keeping the approximation accuracy as the same.

Low-cost sensor networks for multitarget tracking are increasingly becoming important equipment in many applications. A major problem is that these sensors usually provide only a binary response in each epoch, if a target is present or absent. Efficient approaches for realizing the location and tracking of multiple targets are needed. In this paper, we develop a soft tracking system using an infrared ceiling sensor network and propose a novel algorithm for tracking multiple people. In this system, 43 infrared sensors were attached to the ceiling of an office room (15.0 m × 8.5 m). Some pieces of weak evidence such as locations of personal desks, and the moving directions of people, were used for soft tracking. Through experiments, the ability of tracking in different situations was evaluated. The tracking accuracy during a 3 h period was investigated. The results showed that this system was able to track up to eight people simultaneously for hours in an office room. The tracking accuracy was above 90% most of the time, although some identity ambiguities occurred.

In some dynamic environments, the degree of importance of features for classification varies over time. For example, if we want to identify the kinds of birds in a forest, different groups of birds might sing in different time periods. Then we have to change the features to identify the kinds of a bird, e.g., frequency, depending on time of observation. This study deals with such a sequence of feature subsets changing their importance over time. We assume that such a change happens gradually, that is, the case of population drift. To track drifting distributions, we use volume prototypes with a forgetting factor and on the basis of volume prototypes at each time period we extract feature subsets useful for that time.

A weighted naïve Bayes (WNB) classifier using Rényi entropy is discussed with its tree augmented extension. A WNB classifier is one solution for gaining efficiency against large-scale classification problems with an enormous amount of data and a lot of features. Such a WNB classifier has been studied so far, aiming at improving the prediction performance or at reducing the number of features. Among those studies, weighting with Shannon entropy has succeeded in reducing the number of features while keeping the classification performance. However, it has not been fully revealed how different weighting methods affect the performance of classification and feature selection. In this paper, it is analyzed by changing the weights using a parametric α-Rényi entropy. As the first clue, the relationship between Rényi entropy and the marginal Bayes error is analyzed in detail. It was revealed that the WNB classifiers becomes the regular (without weight) naïve Bayes classifier in one end (α = 0.0) and naïve Bayes classifier weighted by the marginal Bayes error in the other end (α = ∞). In addition, an extension of WNB classifiers to incorporate tree-structured correlation between features is discussed.

The characteristics of whispered speech are not well known. The most remarkable difference from ordinal speech is the pitch (the height of speech), since whispered speech has no fundamental frequency. In this study, we have tried to reveal the mechanism of producing pitch in whispered speech through an experiment in which a male and a female subjects uttered Japanese whispered vowels in a way so as to tune their pitch to the guidance tone with different five to nine frequencies. We applied multivariate analysis such as the principal component analysis to the data in order to make clear which part of frequency contributes much to the change of pitch. We have succeeded in endorsing the previous observations, i.e. shift of formants is dominant, with more detailed numerical evidence. In addition, we obtained some implications to approach the pitch mechanism of whispered speech. The main result obtained is that two or three formants of less than 5 kHz are shifted upward and the energy is increased in high frequency region over 5 kHz.

Recently we face classification problems with many categorical features, as seen in genetic data and text data. In this paper, we discuss some ways to give weights on features in the framework of naïve Bayes classifier, that is, under independent assumption of features. Because no order exists in a categorical feature, we consider a histogram over possible values (bins) in the feature. Taking into the difference of number of samples falling in each bin, we propose two kinds of weights: 1) one is derived from the probability that the majority class takes the majority even in samples, and 2) another reflects the expected conditional entropy. With the latter entropy weight, it will be shown that more discriminative features gain higher weights and non-discriminative feature diminishes as the number of samples goes infinity. We reveal the properties of these two kinds of weights through artificial data and some real-life data.

Automatic speech recognition of conversational speech has not reached the level of practical use yet. Possible reasons are 1) multiple speakers speak in turn or sometimes at the same time, and 2) they speak very casually. One of key features to characterize conversational speech is the speaking speed. By knowing the speaking speed it becomes possible to adapt a recognition system to speech at that speed. Therefore, in this paper, we aim to estimate the speech rate in real time in order to choose a recognition model suitable for the speech rate. This paper introduces a probabilistic method for estimating the speech rate as well as the changing points of speech rates. We use a martingale framework in two stages to this goal. For examining the effectiveness of our method, two experiments are conducted. First, phoneme-level speech rate change detection is tried in both of reading and conversational speech. Second, the detection of the changing points of word-level speech rates is tried.

One of central topics of kernel machines in the field of machine learning is a model selection, especially a selection of a kernel or its parameters. In our previous work, we discussed a class of kernels forming a class of nested reproducing kernel Hilbert spaces with an invariant metric; and proved that the kernel corresponding to the smallest reproducing kernel Hilbert space, including an unknown true function, gives the optimal model. In this paper, we consider a class of kernels forming a class of nested reproducing kernel Hilbert spaces whose metrics are not always invariant and show that a similar result to the invariant case is not obtained by providing a counter example using a class of Gaussian kernels.

The usage of convex hulls for classification is discussed with a practical algorithm, in which a sample is classified according to the distances to convex hulls. Sometimes convex hulls of classes are too close to keep a large margin. In this paper, we discuss a way to keep a margin larger than a specified value. To do this, we introduce a concept of "expanded convex hull" and confirm its effectiveness.

A relationship between generalization error and training samples in kernel regressors is discussed in this paper. The generalization error can be decomposed into two components. One is a distance between an unknown true function and an adopted model space. The other is a distance between an estimated function and the orthogonal projection of the unknown true function onto the model space. In our previous work, we gave a framework to evaluate the first component. In this paper, we theoretically analyze the second one and show that a larger set of training samples usually causes a larger generalization error.

We study the problem of enumerating concepts in a Sperner family concept class using subconcept queries, which is a general problem including maximal frequent itemset mining as its instance. Though even the theoretically best known algorithm needs quasi-polynomial time to solve this problem in the worst case, there exist practically fast algorithms for this problem. This is because many instances of this problem in real world have low complexity in some measures. In this paper, we characterize the complexity of Sperner family concept class by the VC dimension of its intersection closure and its characteristic dimension, and analyze the worst case time complexity on the enumeration problem of its concepts in terms of the VC dimension. We also showed that the VC dimension of real data used in data mining is actually small by calculating the VC dimension of some real datasets using a new algorithm closely related to the introduced two measures, which does not only solve the problem but also let us know the VC dimension of the intersection closure of the target concept class.

It has been promising to provide personalized services for improving our living environment in support of information technologies. Sitting is one of the natural actions in our daily life. We focus on sitting behavior as a cue for providing such services. We used a pressure sensor seat on a chair for identifying sitting postures. In the experiments, we classified nine postures, including leaning forward / backward / right / left and legs crossed. We obtained classification rates of 98.9% when the sitting person was known and 93.9% when the person was not known.

A set of convex bodies including samples of a single class only is used for classification. The convex body is defined by some facets (hyper-planes) that separate the class from the other classes. This paper describes an algorithm to find a set of such convex bodies efficiently and examine the performance of a classifier using them. The relationship to the support vector machines is also discussed.

Associative classifiers that utilize association rules have been widely studied. It has been shown that associative classifiers often outperform traditional classifiers. Associative classifiers usually find only rules with high support values, because reducing the minimum support to be satisfied increases computational cost. However, rules with low support but high confidence may contribute to classification. We have proposed an approach to build a classifier composed of almost all consistent (100% confident) rules. The proposed classifier was extended by introducing item reduction and bagging in order to relax the constraint of consistency, which resulted in slightly increased performance for 26 datasets from the UCI machine learning repository.

An information table or a training/designing sample set is all that can be obtained to infer the underlying generation mechanism (distribution) of tuples or samples. However, how an information table is available in representation, in treatment, and in interpretation, can still be discussed. In this paper, these matters are discussed on the basis of “granularity.” First, an explanation is given to identify the reasons why different goals/treatments of information tables exist in some different research fields. In this stage, it will be emphasized that “granularity concept” plays an important role. Next, a framework of information tables is reformulated in terms of attribute sets and tuple sets. Here, a “Galois connection” helps to understand their relationship. Then, the use of “closed subsets” is proposed instead of given tuples, for efficiency and for interpretability. With a special type of closed subsets, the traditional logical DNF expression framework can be naturally extended to those with multivalues and continuous values. Last, several concepts on rough sets are reformulated using “variable granularity” connected to closed subsets. This paper determines how and in what points granularity can give flexibility in dealing with several problems. Through several concepts defined in this paper, some intuitions toward development of data exploration and data mining are given.

We introduce a stricter Web community definition to overcome boundary ambiguity of a Web community defined by Flake, Lawrence and Giles [2], and consider the problem of finding communities that satisfy our definition. We discuss how to find such communities and hardness of this problem.We also propose Web page partitioning by equivalence relation defined using the class of communities of our definition. Though the problem of efficiently finding all communities of our definition is NP-complete, we propose an efficient method of finding a subclass of communities among the sets partitioned by each of n-1 cuts represented by a Gomory-Hu tree [10], and partitioning a Web graph by equivalence relation defined using the subclass.According to our preliminary experiments, partitioning by our method divided the pages retrieved by keyword search into several different categories to some extent.

In this paper, firstly, processes of classical inference are reviewed as granular reasoning from a point of view of reconstructing Kripke-style models with granularity. The essential point of the reconstruction is that some possible worlds are amalgamated to generate granules of worlds and vice versa. It is also called zoom reasoning systems. Then, the idea is applied for fuzzy reasoning processes by considering fuzzily granularized possible worlds. There linguistic truth values with linguistic hedges can be naturally introduced.

The subclass method is a classifier based on approximation of class regions. It assumes that all classes are separable (but not necessarily linear separable). We extend the method so as to meet cases in which class-conditional probability density functions (PDFs) overlap each other. In this extension, the method becomes a histogram approach for approximating PDFs, but the method allows overlapping of bins unlike usual histogram approaches. It is shown that this method is consistent in the sense that the error rate approaches the Bayes error rate as the number of samples tends to infinity. It is also shown that the convergence rate is faster than that using a previous MDL-based histogram approach in the range of practical number of samples.

Obtaining 3D geometric and texture information of urban scenes has received a great deal of attention in many fields such as civil engineering, traffic systems, car navigation systems, entertainment etc. It is, however, difficult to obtain a 3D description of an outdoor static scene because a camera is easily influenced by the environment such as lighting and background. In addition, it is expensive to obtain the description, especially in data input by human hand. To resolve these problems, we need an efficient and automatic framework for 3D modeling of city scenes. We propose an efficient method with epipolar-plane image analysis to model a 3D city scene along a road from an image sequence recorded by a camera boarded on a vehicle. With the method presented, we detect vertical edges and track the edges in a spatiotemporal solid of images. The locus of the edges gives us the distances from the path of the camera to the objects including the edges, such as buildings as well as their heights. The side of an object will be estimated as a rectangle, of which both sides are two different estimated edges with the same height. Our method is able to obtain both the distance and the height of the objects simultaneously. Therefore, the constructed model is expected to be stable and precise.

In computer vision, estimation of the motion of objects has a wide range of applications, such as machine vision and on-board camera systems. The motion in 2D or 3D is observed as a 2D vector, called an optical flow. An optical flow is extracted under a linear constraint between flow vectors and time-space derivations of an image. This constraint (optical flow constraint, OFC) requires the assumption of a linear change of the intensity. On the other hand, the motion is most notably visible as a movement of the edge, but the intensity around the edge cannot be approximated linearly. Therefore, such a simple optical flow is not reliable in the edge which reflects the motion noticeably. We therefore used the OFC of edges proposed by M. Muikaichi and N. Hamada (1999) to extract more precisely the flow of edges and to estimate the motion of the object using these flows.

Numerous image coding techniques have been proposed over the last decade, among which a discrete cosine transform (DCT) is a key technique adapted in JPEG as a standard. Although DCT shows a good coding performance, the problem of block distortion or blur of details is often observed in the case of a low bit rate. It is therefore difficult to obtain a high-quality image with only a few bits. By using multi-channel coding, however, an image can be divided into spatial components and each of the components is encoded according to its property, which enables the resolution of eyesore noise such as block distortion. However, its performance is not as good as that of JPEG's. Y. Yanagihara (1997) proposed a two-channel coding technique using spline interpolation. In this technique, a low-frequency component is represented by a smooth spline surface and a high-frequency component is represented as the difference between the original image and the low-frequency image. Yanagihara showed that this method is superior to JPEG for compressing images while maintaining a high quality. We discuss ways of sampling points for the spline surface in order to improve the performance in Yanagihara's technique.

Over the past few decades, numerous attempts have been made to solve combinatorial optimization problems that are NP-complete or NP-hard in a heuristic approach. A Hopfield-type neural network is a method that is often used to solve problems such as the traveling salesman problem. However, it is difficult to find an optimal solution because it is based on gradient descent and its energy function has many local minima. Therefore, many attempts have been made to find ways of escaping from local minima and to find better solutions. T. Tanaka et al. (1996) succeeded in improving the solutions by controlling the coefficient of the energy function. However, their results were not completely satisfying in terms of the quality of the solutions and the computation time. In order to find better solutions in a short time, we introduced a method called tabu search into a Hopfield-type neural network. Tabu search is a simple and flexible method for obtaining good solutions quickly and has been applied to NP-complete problems. Through computer simulations, better solutions were obtained than those obtained by using an ordinary model. Moreover, the computation time was reduced.

One of the popular recognition methods is the k-nearest neighbor (follows k-NN) method. In this method, however, when the number of training samples is large, the computation cost increases in proportion to the size of the samples. Therefore, we propose a method for reducing the computation cost of searching k-NNs on the basis of the branch-and-bound algorithm (K. Fukunaga and P.M. Narendra, 1975). The aim of the study was to reduce the computation time required for recognition while not considering the computation time required for pre-processing. In our method, we add some conditions for terminating the procedure when the true k-NNs are found. We show the effectiveness of these conditions using real data.

We propose a novel method for determining the number of components in mixture-based classifiers. Each class-conditional probabilistic density function can be approximated well by the mixture of Gaussian components. However, the performance of this classifier depends on the number of components. In our proposed method, determination of the number of components is based on both probabilistic likelihood and class separability. The results of experiments confirmed the effectiveness and the property.

A classifier based on a mixture model is proposed. The expectation maximisation algorithm for construction of a mixture density is sensitive to the initial densities. It is also difficult to determine the optimal number of component densities. In this study, we construct a mixture density on the basis of a hyper-rectangles found in the subclass method, in which the number of components is determined automatically. Experimental results show the effectiveness of this approach.

A method for visualizing the structure of classes using a graph is proposed. Unlike the previous approaches of mapping data points onto a plane, this method represents a few sets of data points as nodes of the graph. From the sizes of the nodes and the widths of the links connecting the nodes, one can know how complex the structure is and to what degree the classes are separable. The experimental results show that the approach is effective for revealing a hidden structure of classes in a high-dimensional space.

Some initial component densities are compared in a mixture model for pattern recognition. The EM algorithm is widely adopted in construction of a mixture density for approximating a class-conditional density. However, the algorithm is very sensitive to the number of component densities and the initial component densities themselves. The initial component densities are obtained by a clustering method. We report the results of comparison between clustering methods yielding non-overlapping clusters and methods yielding overlapping clusters.

We show a positive result for learnability of all arbitrary disjunctive normal form (DNF) formula. We propose a learning algorithm that requires a polynomial number of examples in the size of an unknown formula under probably approximately correct (PAC) learning with a subset query, while it is not polynomial time. Our algorithm is based on Valiant's (1984) approach with respect to monotone-DNF.

A technique to find sure and ambiguous regions in a class is proposed. These regions are defined by lower approximations in rough set theory. Outputs of many classifiers are combined in order to make such lower approximations and to give class labels to them. As an application of this technique, a classifier with a few misclassifications is proposed.

The MDL (minimum description length) criterion is used to select the best classifier among several types of classifiers on a given pattern recognition problem. Unlike previous studies, our technique can compare a wide variety of classifiers if we know a combinational property, viz., the Vapnick-Chervonenkis (VC) dimension. Three classifiers are compared using this criterion. Experimental results show the effectiveness of the method.

The signals that direct the excision of introns from mammalian pre-mRNA are not yet well understood. However, at least three kinds of signals--5'-splice site signals, 3'-splice site signals and branch point signals--play important roles in the excision of introns. In the present paper we treat only the 5'-splice sites. In addition to a consensus sequence for 5'-splice signals, several methods have been proposed, based on a statistical model, and used to analyze relative importance of each nucleotide at each position. In our approach a nucleotide sequence is regarded as a string with symbols of 'A', 'T', 'G' and 'C'; important substrings of 5'-splice site sequences, called pattern sequences, are extracted. A pattern sequence expresses which nucleotide is needed at a limited number of positions around the 5'-splice site. It is observed that a particular pattern sequence matches predominantly 5'-splice site sequences nearest to the 5'-end of a gene and another pattern sequence matches predominantly the second nearest ones. Moreover, it is confirmed that the pattern sequences accurately predict authentic 5'-splice sites for unknown genes and explain some mutation examples.

The authors present an efficient algorithm for finding optimal subclasses of a class whose members are represented by several dichotomous features with 0 or 1. Each subclass is expressed by a logical formula with common features among its members. It is shown that some typical subclasses, which contain a large number of samples from a class, consist of a few features. Thus one can select these features as a small subset of all features in problems of feature selection. The selection of best subclasses, when subclasses found by the algorithm is a moderate size, is discussed.>

The signals which direct the excision of introns from eukaryotic pre-mRNA are not yet well understood. In order to define the signals for 5'-splice sites of mRNA splicing, nucleotide sequences including 5'-splice junctions of mammalian pre-mRNAs are analysed by means of syntactic pattern analysis. Taking this approach, we infer the grammatical rules which specify 5'-splice sites and construct a finite automaton which is the recognizer of the nucleotide sequences at 5'-splice sites. By scanning the automaton along nucleotide sequences, we can identify the positions of 5'-splice junctions with a degree of discrimination of up to 94-97% in the known genes, while the degree of prediction is in the range 50-55% in new genes.