We consider the problem of efficient learning of probabilistic concepts (p-concepts) and more generally stochastic rules in the sense defined by Kearns and Schapire and by Yamanishi. Their models extend the PAC-learning model of Valiant to the learning scenario in which the target concept or function is stochastic rather than deterministic as in Valiant's original model. In this paper, we consider the learnability of stochastic rules with respect to the classic 'Kullback-Leibler divergence' (KL divergence) as well as the quadratic distance as the distance measure between the rules. First, we show that the notion of polynomial time learnability of p-concepts and stochastic rules with fixed range size using the KL divergence is in fact equivalent to the same notion using the quadratic distance, and hence any of the distances considered in [6] and [18]: the quadratic, variation, and Hellinger distances. As a corollary, it follows that a wide range of classes of p-concepts which were shown to be polynomially learnable with respect to the quadratic distance in [6] are also learnable with respect to the KL divergence. The sample and time complexity of algorithms that would be obtained by the above general equivalence, however, are far from optimal. We present a polynomial learning algorithm with reasonable sample and time complexity for the important class of convex linear combinations of stochastic rules. We also develop a simple and versatile technique for obtaining sample complexity bounds for learning classes of stochastic rules with respect to the KL-divergence and quadratic distance, and apply them to produce bounds for the classes of probabilistic finite state acceptors (automata), probabilistic decision lists, and convex linear combinations.

This paper describes a unique motion estimation and compensation (ME/MC) hardware architecture for a scene-adaptive algorithm. By statistically analyzing the characteristics of the scene being encoded and controlling the encoding parameters according to the scene, the quality of the decoded image can be enhanced. The most significant feature of the architecture is that the two modules for ME/MC can work independently. Since a time interval can be inserted between the operations of the two modules, a scene-adaptive algorithm can be implemented in the architecture. The ME/MC architecture is loaded on a single-chip MPEG-2 video encoder.

The hardware-software codesign of distributed embedded systems is a more challenging task, because each phase of codesign, such as copartitioning, cosynthesis, cosimulation, and coverification must consider the physical restrictions imposed by the distributed characteristics of such systems. Distributed systems often contain several similar parts for which design reuse techniques can be applied. Object-oriented (OO) codesign approach, which allows physical restriction and object design reuse, is adopted in our newly proposed Distributed Embedded System Codesign (DESC) methodology. DESC methodology uses three types of models: Object Modeling Technique (OMT) models for system description and input, Linear Hybrid Automata (LHA) models for internal modeling and verification, and SES/workbench simulation models for performance evaluation. A two-level partitioning algorithm is proposed specifically for distributed systems. Software is synthesized by task scheduling and hardware is synthesized by system-level and object-oriented techniques. Design alternatives for synthesized hardware-software systems are then checked for design feasibility through rapid prototyping using hardware-software emulators. Through a case study on a Vehicle Parking Management System (VPMS), we depict each design phase of the DESC methodology to show benefits of OO codesign and the necessity of a two-level partitioning algorithm.

With the advancement of technologies in wireless communication and computer down-sizing, it becomes possible to access a global network using handy terminals which are equipped with wireless communication facilities. In such a mobile computing environment, data management is one of the primary objectives of effective computer uses. However, since conventional distributed data management technologies assume that servers and clients are fixed at certain locations in a network, they do not provide any tools to construct advanced applications which make full use of dynamically changing information in such an environment. In this paper, in order to incorporate data distributed over mobile computing environment, we propose a dynamic data integration mechanism called MobiView which is an enhanced view mechanism of a conventional database system. In MobiView, we introduce four methods for database indication without using conventional host name or its local name: host-specified, cell-specified, location-dependent, and MobiView-oriented, through which we discuss how to handle both mobile database servers and mobile database clients.

Since the traffic of NetNews is increasing, keeping all articles becomes serious problem from a viewpoint of waste of network bandwidth and the amount of disk usage. In addition, users read not all incoming articles. We have proposed several caching algorithms to overcome this problem and shown that a selective prefetch scheme gives the best system performance among the proposed ones. However, since the selective prefetch scheme employed a simple selecting policy, the scheme gave low hit ratio in some cases. Therefore, this paper intends to improve the selective prefetch scheme from a viewpoint of the amount of disk usage as well as hit ratio. In this paper, we divide the scheme into three factors: reference span, criterion, and threshold in criterion. Through simulation experiments using actual NetNews logs, we investigate the influence of the factors of the reference span and the threshold to system performance. As a result, it is shown that the reference span is more significant factor than the threshold, the selective prefetch scheme with a value around the seven days reference span keeps high hit ratio and reduces the amount of disk usage.

A multimedia content is usually read-only and composed of multimedia objects with their spatial and temporal specifications. These specifications given by its author can enforce the display of objects to be well organized for its context. When multimedia contents are serviced in network environment by an on-demand basis, the temporal relationship among the objects can be used to improve the performance of the service. This paper models the temporal relationship as a scenario that represents the presentation order of the objects in a scenario and proposes several scheduling methods that make it possible to rearrange the transmission order of objects in a scenario. As a result, system resources such as computing power and network bandwidth can be highly utilized. Since the temporal relationship of a scenario is static, it is possible to reduce the scheduling overhead of a server by pre-scheduling currently servicing scenarios. In addition, several simulation results are presented in order to compare and analyze the characteristics of the proposed methods.

We have proposed a new string-based haptic interface device in this paper. It is a kind of device that allows a user to use both hands and multi-fingers to direct manipulate the virtual objects in the computer simulated virtual environment. One of the advantages of the device is to allow the user to use both hands to perform the cooperative works of hands, such as holding a large object that cannot be grasped or held by single hand. In addition, the haptic feedback sensation provided by the device at the fingertips makes possible for the user to perform dexterous manipulation, such as manipulating small size of objects. We have discussed about the design of the proposed device and have elaborated the methods of fingertip positions measurement and force feedback generation. The experiments had been carried out to verify the capabilities of the proposed device.

This paper describes experimental results on whole word HMM-based speech recognition of connected digits in Japanese with special focus on the training data size and the "sheep and goats" problem. The training data comprises 757000 digits uttered by 2000 speakers, while the testing data comprises 399000 digits uttered by 1700 speakers. The best word error rate for unknown length strings was 1.64% obtained using context dependent HMMs. The word error rate was measured for various subsets of the training data reduced both in the number of speakers (s) and the number of utterances per speakers (u). As a result, an empirical formula of s[{min(0.62s^0.75, u)}^0.74 + {max(0, u-0.62s^0.75)}^0.27] = D(E_w) was developed, where E_w and D(E_w) designate word error rate and effective data size, respectively. Analyses were conducted on several aspects of the low performance speakers accounting for the major part of recognition errors. Attempts were also made to improve their recognition performance. It was found that 33% of the low performance speakers are improved to the normal level by speaker clustering centered around each low performance speaker.

Most scheduling applications have been classified into NP-complete problems. This fact implies that an optimal solution for a large scheduling problem is extremely time-consuming. A number of schemes are introduced to solve NP-complete scheduling applications, such as linear programming, neural network, and fuzzy logic. In this paper, we demonstrate a new approach, fuzzy Hopfield neural network, to solve the scheduling problems. This fuzzy Hopfield neural network approach integrates fuzzy c-means clustering strategies into a Hopfield neural network. In this investigation, we utilizes this new approach to demonstrate the feasibility of resolving a multiprocessor scheduling problem with no process migration, limited resources and constrained times (execution time and deadline). In the approach, the process and processor of the scheduling problem can be regarded as a data sample and a cluster, respectively. Then, an appropriate Lyapunov energy function is derived correspondingly. The scheduling results can be obtained using a fuzzy Hopfield neural network clustering technique by iteratively updating fuzzy state until the energy function gets minimized. To validate our approach, three scheduling cases for different initial neuron states as well as fuzzification parameters are taken as testbed. Simulation results reveal that imposing the fuzzy Hopfield neural network on the proposed energy function provides a sound approach in solving this class of scheduling problems.

An electrophysiological experiment showed that spike timing was precise to less than one millisecond. This result indicates the possibility in the precise time codings. For a high accurate time coding, reconsideration of a neural mechanism which decides firing time is required. From such viewpoint, we quantitatively examined change in firing time with interference between two synaptic inputs through Hodgkin-Huxley (HH) and integrate-and-fire (IF) model neurons. The precise firing times in the HH model neuron were extremely different from those in the IF model neuron. In this paper, the relations of input intensity to firing time are investigated in the other more two pulse generation models: Morris-Lecar (ML) and FitzHugh-Nagumo (FN) model. The result of the ML model in a certain parameter set (type-I) exhibited monotone decreasing like that of the IF model while the result of the ML model in the otter parameter set (type-II) exhibited non-monotone decreasing like that of the HH model. The result of the FN model exhibited non-monotone decreasing like the HH model despite its qualitativeness. Next the firing patterns in the four model neurons on a model of V1 (primary visual area) and LGN (lateral geniculate nucleus) with circular and mutual excitatory connections are investigated to show how dependent on model neurons the firing patterns are. The spikes in the HH, the ML type-II, and the FN model neurons elicited synchronous oscillations while the spikes in the IF and the ML type-I model neurons did not; the firing patterns dramatically changed with the dependence on the model neurons.

This paper describes a method for classification of hematoxylin and eosin (HE)-stained breast tumor images into benign or malignant using the adaptive searching ability of artificial organisms. Each artificial organism has some attributes, such as, age, internal energy and coordinates. In addition, the artificial organism has a differentiation function for evaluating "malignant" or "benign" tumors and the adaptive behaviors of each artificial organism are evaluated using five kinds of texture features. The texture feature of nuclei regions in normal mammary glands and that of carcinoma regions in malignant tumors are treated as "self" and "non-self," respectively. This model consists of two stages of operations for detecting tumor regions, the learning and searching stages. At the learning stage, the nuclei regions are roughly detected and classified into benign or malignant tumors. At the searching stage, the similarity of each organism's environment is investigated before and after the movement for detecting breast tumor regions precisely. The method developed was applied to 21 cases of test images and the distinction between malignant and benign tumors by the artificial organisms was successful in all cases. The proposed method has the following advantages: the texture feature values for the evaluation of tumor regions at the searching stage are decided automatically during the learning stage in every input image. Evaluation of the environment, whether the target pixel is a malignant tumor or not, is performed based on the angular difference in each texture feature. Therefore, this model can successfully detect tumor regions and classify the type of tumors correctly without affecting a wide variety of breast tumor images, which depends on the tissue condition and the degree of malignancy in each breast tumor case.

We consider syntactic congruences of some codes. As a main result, for an infix code L, it is proved that the following (i) and (ii) are equivalent and that (iii) implies (i), where P_L is the syntactic congruence of L. (i) L is a P_L²-class. (ii) L^m is a P_L^k-class, for given two integers m and k with 1 m k. (iii)L^* is a P_L*-class. Next we show that every (i), (ii) and (iii) holds for a strongly infix code L. Moreover we consider properties of syntactic conguences of a residue W(L) for a strongly outfix code L.

If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph can be used to identify critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In general, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. For instance, Chang et al. presented an O(n+m) time algorithm for finding all hinge vertices of a strongly chordal graph. Ho et al. presented a linear time algorithm for all hinge vertices of a permutation graph. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of an interval graph.

Conventional spatial transform based motion estimation algorithms are not practical because of their heavy computational loads. In this paper, we proposed motion estimation method with variable grid size, which is more efficient than conventional spatial transform based methods and gives better PSNR performance than conventional BMA.

The performance of conventional error concealment (EC) is significantly affected by the method of selecting candidate motion vectors (MVs). In order to obtain more robust EC results, this letter proposes a new and efficient way to choose candidate MVs. The proposed approach systematically utilizes available neighboring MVs by exploiting a well-known spatiotemporal correlation of block MVs. Through extensive simulations with H.263, this letter demonstrates that the proposed candidate MVs provide superior concealed video quality in comparison to the best results of other existing techniques.