This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t4(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t2(n))-time deterministic hyperbolic CA. We also show that nr+-time (non)deterministic hyperbolic CAs are strictly more powerful than nr-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: Ph= NPh = PSPACEh EXPTIMEh= NEXPTIMEh = EXPSPACEh , where Ch is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NPh APh unless PSPACE = NEXPTIME, and (ii) APh EXPTIME h.

Rectangle search is a well-known packet classification scheme which is based on multiple hash accesses for different filter length. It shows good scalability with respect to the number of filters; however, the performance is not fast enough to fulfill the high-speed requirement of packet classification. In this paper, we propose a lookahead caching which can significantly improve the performance of hash-based algorithm. The basic idea is to filter out the un-matched probing case by using dual-hash architecture. The experimental results indicate that the proposed scheme can improve the performance by the factor of two for the 2-dimension (source prefix, destination prefix) filter database.

Although many researchers have verified the superiority of Support Vector Machine (SVM) on text categorization tasks, some recent papers have reported much lower performance of SVM based text categorization methods when focusing on all types of parts of speech (POS) as input words and treating large numbers of training documents. This was caused by the overfitting problem that SVM sometimes selected unsuitable support vectors for each category in the training set. To avoid the overfitting problem, we propose a two step text categorization method with a variable cascaded feature selection (VCFS) using SVM. VCFS method selects a pair of the best number of words and the best POS combination for each category at each step of the cascade. We made use of the difference of words with the highest mutual information for each category on each POS combination. Through the experiments, we confirmed the validation of VCFS method compared with other SVM based text categorization methods, since our results showed that the macro-averaged F1 measure (64.8%) of VCFS method was significantly better than any reported F1 measures, though the micro-averaged F1 measure (85.4%) of VCFS method was similar to them.

In face recognition, simple classifiers are frequently used. For a robust system, it is common to construct a multi-class classifier by combining the outputs of several binary classifiers; this is called output coding method. The two basic output coding methods for this purpose are known as OnePerClass (OPC) and PairWise Coupling (PWC). The performance of output coding methods depends on accuracy of base dichotomizers. Support Vector Machine (SVM) is suitable for this purpose. In this paper, we review output coding methods and introduce a new sequential fusion method using SVM as a base classifier based on OPC and PWC according to their properties. In the experiments, we compare our proposed method with others. The experimental results show that our proposed method can improve the performance significantly on the real dataset.

This paper presents the performance modeling application of SIP-T (Session Initiation Protocol for Telephones) signaling system based on two-class priority queueing process in carrier class VoIP (Voice over IP) network. The SIP-T signaling system defined in IETF (Internet Engineering Task Force) is a mechanism that uses SIP (Session Initiation Protocol) to facilitate the interconnection of existing PSTN (Public Switched Telephone Network) with carrier class VoIP network. One of the greatest challenges in the migration from PSTN toward NGN (Next Generation Networks) is to build a carrier class VoIP network that preserves the ubiquity, quality, and reliability of PSTN services while allowing the greatest flexibility for use of new VoIP technology. Based on IETF, the SIP-T signaling system not only promises scalability, flexibility, and interoperability with PSTN but also provides call control function of MGC (Media Gateway Controller) to set up, tear down, and manage VoIP calls in carrier class VoIP network. This paper presents the two class priority queueing model, performance analysis, and simulation of SIP-T signaling system in carrier class VoIP network focused on toll by-pass or tandem by-pass of PSTN. In this paper, we analyze the average queueing length, the mean of queueing delay, and the variance of queueing delay of SIP-T signaling system that are the major performance evaluation parameters for improving QoS (Quality of Service) and system performance of MGC in carrier class VoIP network. A mathematical model of the M/G/1 queue with two-class non-preemptive priority assignment is proposed to represent SIP-T signaling system. Then, the formulae of average queueing length, queueing delay, and delay variation for the non-preemptive priority queue are expressed respectively. Several significant numerical examples of average queueing length, queueing delay, and delay variation are presented as well. Finally, the two-class priority queueing model and performance analysis of SIP-T signaling system are shown the accuracy and robustness after the comparison between theoretical estimates and simulation results.

The control of class DE amplifier is an important problem since its switching operations do not satisfy class E switching conditions when the load resistance varies from the initial designed values. Therefore, several of control schemes of class DE amplifier were proposed. However, the changes of the output voltage and the power conversion efficiency by using these controls can be measured only experimentally and thus, they cannot be found theoretically. In this paper, an exact analysis of class DE amplifier with FM and PWM control schemes is presented. From the analysis, we can theoretically derive the output voltage, the power conversion efficiency and so on. Moreover, the frequency and the duty ratio to keep the constant output voltage can be found when the load resistance or the input voltage varies. We indicate that the theoretical predictions are similar to the experimental results quantitatively. The measured efficiency is over 94% with 1.0 MHz and 1.8 W output.

The case postpositions usually have more than one semantic role in Korean. The adverbial postpositions among various postpositions especially make the development of Korean-based machine translation system difficult, because they have more semantic roles than others. In this paper, we describe a new method for resolving semantic ambiguities of adverbial postpositions using decision tree induction. The lack of training examples in decision tree induction is overcome by clustering words into classes using a kind of greedy algorithm. The cross validation results show that the presented method achieves 76.5% of accuracy on the average, which is 20.3% improvement over the baseline method.

The applications of biometrics in the real world include various types of large-scale "one-to-many" identification, which require high performance classification technology. This paper presents a system with a classification algorithm that integrates multiple features observed in a set of fingerprints and uses them, to pre-select candidates, for more efficient personal identification from a very large fingerprint enrollment database. The algorithm determines a fingerprint's pattern type by using both ridge structure analysis and direction-based neural networks. It measures such additional feature characteristics as core-delta distance and ridge counts in parallel, along with confidence indexes associated with each feature. The pre-selector then integrates the set of obtained features from multiple fingers, after weighting them according to each feature's inherent ability to contribute to the selection process and the expected errors in observations of that feature. The system calculates the similarity between pairs of sets on the basis of feature differences, statistically evaluates the conditional probability of each pair being a correct match, and selects most similar collection of candidates for detailed matching. Experimental results confirm that it achieves an effective pre-selecting capability of 0.2% average selection (false acceptance or penetration) rate with 2% selection error (false rejection) rate.

A set of systematic experiments on intelligent email categorization has been conducted with different machine learning algorithms applied to different parts of data in order to achieve the most correct classification. The categorization is based on not only the body but also the header of an email message. The metadata (e.g. sender name, sender organization, etc.) provide additional information that can be exploited to improve the categorization capability. Results of experiments on real email data demonstrate the feasibility of our approach to find the best learning algorithm and the metadata to be used, which is a very significant contribution in email classification. It is also shown that categorization based only on the header information is comparable or superior to that based on all the information in a message for all the learning algorithms considered.

We consider the classification problem as a problem of approximation of a given training set. This approximation is constructed in a multiresolution framework, and organized in a tree-structure. It allows efficient training and query, both in constant time per training point. The proposed method is efficient for low-dimensional classification and regression estimation problems with large data sets.

Immune system protects living body from an extraordinarily large variety of bacteria, viruses, and other pathogenic organisms. Based on immunological principles, new computational techniques are being developed, aiming not only at a better understanding of the system, but also at solving engineering problems. Our overall goal for this paper is twofold: to understand the real immune system from the information processing perspective, and to use idea generated from the immune system to construct new engineering application. As one example of the latter, we propose an artificial immune system architecture inspired by the human immune system and apply it to pattern recognition. We test the proposed architecture by the simulations on arbitrary sequences of analog input pattern classification and binary input pattern recognition. The simulation results illustrate that the proposed architecture is effective at clustering arbitrary sequences of analog input patterns into stable categories and it can produce stronger noise immunity than the binary network .

This paper describes an efficient face recognition method using a combination of the Radon transform and the KL expansion. In this paper, each facial image is transformed into many sets of line integrals resulting from the Radon transform in 2D space. Based on this transformation, a new face-recognition method is proposed by using many subspaces generated from the vector spaces of the Radon transform. The efficiencies of the proposed method are proved by the classification rate of 100% in the experimental results, and the reduction to O(n4) instead of O(n6) of the operation complexity in KL(Karhunen-Loeve) expansion, where n is the size of sample images.

A second-generation CMOS current conveyor (CCII) consisting of a rail-to-rail complementary N- and P-channel differential input stage for the voltage input, a class AB push-pull stage for the current input, and current mirrors for the current outputs is developed. The CCII was implemented using a double-poly triple-metal 0.6 µm n-well CMOS process, to confirm its operation experimentally. A prototype chip achieves a rail-to-rail swing 2.4 V under 2.5 V power supplies and shows the exact voltage and current following performances up to 100 MHz. These performances make the CCII proposed herein quite useful for a building block of current-mode circuits. The prototype CCII is applied to current-mode filters to demonstrate the wideband signal processing capabilities.

A novel postprocessing algorithm for concealing spatial block errors in block-based coded images is proposed using block classification with a variable operating region (VOR). In the proposed algorithm, a missing block is classified as flat, edge, or complex based on local information from the surrounding blocks which is extracted using a Sobel operation in a VOR. In this case, the VOR is determined adaptively according to the number of edge directions in the missing block. Using the classification, the flat blocks are then concealed by the linear interpolation (LI) method, the edge blocks are concealed by the boundary multi-directional interpolation (BMDI) method, and the complex blocks are concealed by a combined linear interpolation and boundary matching (CLIBM) method. Experimental results demonstrated that the proposed algorithm improved the PSNR and visual quality of the concealment for both original images and JPEG compressed images, and produced better results than conventional algorithms.

This paper presents a dynamic node decaying method (DNDM) for layered artificial neural networks that is suitable for classification problems. Our purpose is not to minimize the total output error but to obtain high generalization ability with minimal structure. Users of the conventional back propagation (BP) learning algorithm can convert their program to the DNDM by simply inserting a few lines. This method is an extension of a previously proposed method to more general classification problems, and its validity is tested with recent standard benchmark problems. In addition, we analyzed the training process and the effects of various parameters. In the method, nodes in a layer compete for survival in an automatic process that uses a criterion. Relatively less important nodes are decayed gradually during BP learning while more important ones play larger roles until the best performance under given conditions is achieved. The criterion evaluates each node by its total influence on progress toward the upper layer, and it is used as the index for dynamic competitive decaying. Two additional criteria are used: Generalization Loss to measure over-fitting and Learning Progress to stop training. Determination of these criteria requires a few human interventions. We have applied this algorithm to several standard benchmark problems such as cancer, diabetes, heart disease, glass, and iris problems. The results show the effectiveness of the method. The classification error and size of the generated networks are comparable to those obtained by other methods that generally require larger modification, or complete rewriting, of the program from the conventional BP algorithm.

A novel postprocessing algorithm for reducing the blocking artifacts in block-based coded images is proposed using block classification and adaptive multi-layer perceptron (MLP). This algorithm is exploited the nonlinearity property of the neural network learning algorithm to reduce the blocking artifacts more accurately. In this algorithm, each block is classified into four classes; smooth, horizontal edge, vertical edge, and complex blocks, based on the characteristic of their discrete cosine transform (DCT) coefficients. Thereafter, according to the class information of the neighborhood block, adaptive neural network filters (NNF) are then applied to the horizontal and vertical block boundaries. That is, for each class a different two-layer NNF is used to remove the blocking artifacts. Experimental results show that the proposed algorithm produced better results than conventional algorithms both subjectively and objectively.

Music style is one of the features that people used to classify music. Discovery of music style is helpful for the design of content-based music retrieval systems. In this paper we investigated the mining and classification of music style by melody from a collection of MIDI music. We extracted the chord from the melody and investigated the representation of extracted features and corresponding mining techniques for music classification. Experimental results show that the classification achieved 64% to 84% accuracy for two-way classification.

In this paper, we describe an adaptive integration method for an audio-visual speech recognition system that uses not only the speaker's audio speech signal but visual speech signals like lip images. Human beings communicate with each other by integrating multiple types of sensory information such as hearing and vision. Such integration can be applied to automatic speech recognition, too. In the integration of audio and visual speech features for speech recognition, there are two important issues, i.e., (1) a model that represents the synchronous and asynchronous characteristics between audio and visual features, and makes the best use of a whole database that includes uni-modal, audio only, or visual only data as well as audio-visual data, and (2) the adaptive estimation of reliability weights for the audio and visual information. This paper mainly investigates two issues and proposes a novel method to effectively integrate audio and visual information in an audio-visual Automatic Speech Recognition (ASR) system. First, as the model that integrates audio-visual speech information, we apply a product of hidden Markov models (product HMM), the product of an audio HMM and a visual HMM. We newly propose a method that re-estimates the product HMM using audio-visual synchronous speech data so as to train the synchronicity of the audio-visual information, while the original product HMM assumes independence from audio-visual features. Second, for the optimal audio-visual information reliability weight estimation, we propose a Gaussian mixture model (GMM) based-MCE-GPD (minimum classification error and generalized probabilistic descent) algorithm, which enables reductions in the amount of adaptation data and amount of computations required for the GMM estimation. Evaluation experiments show that the proposed audio-visual speech recognition system improves the recognition accuracy over conventional ones even if the audio signals are clean.

On research to determine reliable acoustic indicators for the type of stress present in speech, the majority of systems have concentrated on the statistics extracted from pitch contour, energy contour, wavelet based subband features and Teager-Energy-Operator (TEO) based feature parameters. These systems work mostly on pair-wise distinction between stress and neutral speech. Their performance decreases substantially when tested in multi-style detection among many stress categories. In this paper, a novel system is proposed using linear short time Log Frequency Power Coefficients (LFPC) and TEO based nonlinear LFPC features in both time and frequency domain. Five-state Hidden Markov Model (HMM) with continuous Gaussian mixture distribution is used. The stress classification ability of the system is tested using data from the SUSAS (Speech Under Simulated and Actual Stress) database to categorize five stress conditions individually. It is found that the performance of linear acoustic features LFPC is better than that of nonlinear TEO based LFPC feature parameters. Results show that with linear acoustic feature LFPC, average accuracy of 84% and the best accuracy of 95% can be achieved in the classification of the five categories. Results of test of the system under different signal-to-noise conditions show that the performance of the system does not degrade drastically with increase in noise. It is also observed that classification using nonlinear frequency domain LFPC features gives relatively higher accuracy than that using nonlinear time domain LFPC features.

In this paper, we propose a Distributed Request based CDMA Reservation ALOHA protocol to support multi-class services, such as voice, data, and videophone services, efficiently in multi-rate transmission cellular systems. The proposed protocol introduces a frame structure composed of an access slot and an transmission slot and an adaptive access permission probability based on the estimated number of contending users for each service, in order to control MAI by limiting the access to slots. It can provide voice service without the voice packet dropping probability through the proposed code assignment scheme, unlike other CDMA/PRMA protocols. The code reservation is allowed for voice and videophone services. The low-rate data service basically uses the remaining codes among the codes reserved for the voice service, but it can also use the codes already assigned to voice calls during the their silent periods to utilize codes efficiently. On the other hand, the high-rate data service uses the codes reserved for itself and the remaining codes among the codes reserved for the videophone service. Using the analytic method based on the Markov-chain subsystem model for each service including the handoff calls in uplink cellular systems, we show that the proposed protocol can guarantee the constant GoS for the handoff calls even with a large number of contending users through the proposed code assignment scheme and the access permission probability. Also, we show that the data services are integrated efficiently on the multi-rate transmission environment.