In difficult classification problems of the z-dimensional points into two groups giving 0-1 responses due to the messy data structure, we try to find the denser regions for the favorable customers of response 1, instead of finding the boundaries to separate the two groups. Such regions are called the bumps, and finding the boundaries of the bumps is called the bump hunting. The main objective of this paper is to find the largest region of the bumps under a specified ratio of the number of the points of response 1 to the total. Then, we may obtain a trade-off curve between the number of points of response 1 and the specified ratio. The decision tree method with the Gini's index will provide the simple-shaped boundaries for the bumps if the marginal density for response 1 shows a rather simple or monotonic shape. Since the computing time searching for the optimal trees will cost much because of the NP-hardness of the problem, some random search methods, e.g., the genetic algorithm adapted to the tree, are useful. Due to the existence of many local maxima unlike the ordinary genetic algorithm search results, the extreme-value statistics will be useful to estimate the global optimum number of captured points; this also guarantees the accuracy of the semi-optimal solution with the simple descriptive rules. This combined method of genetic algorithm search and extreme-value statistics use is new. We apply this method to some artificial messy data case which mimics the real customer database, showing a successful result. The reliability of the solution is discussed.

We consider the problem of dynamically apportioning resources among a set of options in a worst-case online framework. The model we investigate is a generalization of the well studied online learning model. In particular, we allow the learner to see as additional information how high the risk of each option is. This assumption is natural in many applications like horse-race betting, where gamblers know odds for all options before placing bets. We apply Vovk's Aggregating Algorithm to this problem and give a tight performance bound. The results support our intuition that it is safe to bet more on low-risk options. Surprisingly, the loss bound of the algorithm does not depend on the values of relatively small risks.

Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this problem in such a way that points are inserted one by one with uniformity preserved at every instance. Our criterion for uniformity is to minimize the gap ratio (which is the maximum gap over the minimum gap) at every point insertion. We present a linear time algorithm for finding an optimal n-point sequence with the maximum gap ratio bounded by in the 1-dimensional case. We describe how hard the same problem is for a point set in the plane and propose a local search heuristics for finding a good solution.

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.

We consider the problem of triangulating an x-monotone polygon with a small number of different edge lengths using Steiner points. Given a parameter α, where 0<α<1, we shall present an algorithm for finding an almost uniform triangular mesh with 3π/8α²+o(1/α²) different edge lengths such that every edge length is between l and (2+α)l. Experiments demonstrate the effectiveness of this algorithm.

In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.

An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.

It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c!n)^O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.

The behavior of Bard-type pivoting algorithms for the linear complementarity problem with a P-matrix is represented by an orientation of a hypercube. We call it a PLCP-cube. In 1978, Stickney and Watson conjectured that such an orientation has no facet on which all even outdegree vertices appear. We prove that this conjecture is true for acyclic PLCP-cubes in dimension five.

Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069 where is the average degree of the given graph. In this paper we improve (ii). Namely we give a new VC-PM algorithm which greatly outperforms the above one and its approximation factor is roughly . Our algorithm also works for graphs with "large" matchings, although its approximation factor is degenerated.

3D virtual environment provides a limited amount of information, mainly focusing on visual information. This is the main cause of users losing the sense of direction in the environment. Many researches for developing a navigation tools that address this problem have been carried out. In this study, a navigation tool is designed by applying topic map, one of the technologies for semantic web construction, to a 3D virtual environment. Topic map constructs a semantic link map by defining the connection relation between topics. According to an experiment done to evaluate the proposed navigation tool, the tool was more helpful in finding detailed object than highly represented objects. Also, it could be seen that providing the surrounding knowledge is effective for object selection by users when that target for searching is not defined.

Visual criteria for diagnosing liver diseases, such as cirrhosis, from ultrasound images can be assisted by computerized texture classification. This paper proposes a system applying a PNN (Pyramid Neural Network) for classifying the hepatic parenchymal diseases in ultrasonic B-scan texture. In this study, we propose a multifractal-dimensions method to select the patterns for the training set and the validation sets. A modified box-counting algorithm is used to calculate the dimensions of the B-scan images. FDWT (Fast Discrete Wavelet Transform) is applied for feature extraction during the preprocessing. The structure of the proposed neural network is testified by training and validation sets by cross-validation method. The performance of the proposed system and a system based on the conventional multilayer network architecture is compared. The results show that, compared with the conventional 3-layer neural network, the performance of the proposed pyramid neural network is improved by efficiently utilizing the lower layer of the neural network.

We discuss a new design methodology of polynomial neural networks (PNN) in the framework of genetic algorithm (GA). The PNN is based on the ideas of group method of data handling (GMDH). Each node in the network is very flexible and can carry out polynomial type mapping between input and output variables. But the performances of PNN depend strongly on the number of input variables available to the model, the number of input variables, and the type (order) of the polynomials to each node. In this paper, GA is implemented to better use the optimal inputs and the order of polynomial in each node of PNN. The appropriate inputs and order are evolved accordingly and are tuned gradually throughout the GA iterations. We employ a binary coding for encoding key factors of the PNN into the chromosomes. The chromosomes are made of three sub-chromosomes which represent the order, number of inputs, and input candidates for modeling. To construct model by using significant approximation and generalization, we introduce the fitness function with a weighting factor. Comparisons with other modeling methods and conventional PNN show that the proposed design method offers encouraging advantages and better performance.

Solving the error correcting code is an important goal with regard to communication theory. To reveal the error correcting code characteristics, several researchers have applied a statistical-mechanical approach to this problem. In our research, we have treated the error correcting code as a Bayes inference framework. Carrying out the inference in practice, we have applied the NMF (naive mean field) approximation to the MPM (maximizer of the posterior marginals) inference, which is a kind of Bayes inference. In the field of artificial neural networks, this approximation is used to reduce computational cost through the substitution of stochastic binary units with the deterministic continuous value units. However, few reports have quantitatively described the performance of this approximation. Therefore, we have analyzed the approximation performance from a theoretical viewpoint, and have compared our results with the computer simulation.

The audio delay is becoming an important factor in audio streaming over short-range wireless network. In this study, we propose an efficient two-level delay control method, called frame sequence adaptation and audio sampling frequency compensation, for achieving stable audio delay with a small variation. To prove the effectiveness of our scheme, we implemented and evaluated the scheme on a Bluetooth network. Experimental results show that our scheme can control audio delay robustly and remove phase shift problem in multi-channel stereophonic audio broadcasting as well.

The security vulnerabilities of a number of provable secure proxy signature schemes are examined with the assumption that users can register their public keys without having corresponding private keys. This assumption is different from that of a standard proxy signature in which the public keys of users are authentic. Under this assumption, both the Triple Schnorr scheme and Kang et al's scheme are shown to be vulnerable to a rogue public key registration attack. This attack gives an adversary the ability to generate a proxy signature without the valid agreement of the original signer. Moreover, it is shown that an adversary can manipulate the description of a delegated signing right at will. This work can be considered as an awakening to the importance of Proof of Possession (PoP) in the PKI environment, as in many cases certificate authorities do not require the PoP protocol, as has been stated [1].

This letter describes a robust speech recognition system for recognizing fast speech by stretching the length of the utterance in the cepstrum domain. The degree of stretching for an utterance is determined by its rate of speech (ROS), which is based on a maximum likelihood (ML) criterion. The proposed method was evaluated on 10-digits mobile phone numbers. The results of the simulation show that the overall error rate was reduced by 17.8% when the proposed method was employed.

Based on the theory of block projection onto convex sets (BPOCS), a novel de-blocking algorithm is proposed. A new smoothness constraint set (SCS) is used to remove the unnecessary high frequencies. In addition, an adaptive quantization constraint set (AQCS) is employed to suppress error in the smoothing process. The proposed size and position of new SCS are different from traditional ones. Extensive experimental results are provided to demonstrate that the proposed method can achieve better image quality with fewer iterations.

Automated information extraction systems from biomedical text have been reported. Some systems are based on manually developed rules or pattern matching. Manually developed rules are specific for analysis, however, new rules must be developed for each new domain. Although the corpus must be developed by human effort, a machine-learning approach automatically learns the rules from the corpus. In this article, we present a system for automatically extracting protein-protein interaction information from biomedical text with support vector machines (SVMs). We describe the performance of our system and compare its ability to extract protein-protein interaction information with that of other systems.