The overflow probability is one of criteria that evaluate the performance of fixed-to-variable length (FV) codes. In the single source coding problem, there were many researches on the overflow probability. Recently, the source coding problem for correlated sources, such as Slepian-Wolf coding problem or source coding problem with side information, is one of main topics in information theory. In this paper, we consider the source coding problem with side information. In particular, we consider the FV code in the case that the encoder and the decoder can see side information. In this case, several codes were proposed and their mean code lengths were analyzed. However, there was no research about the overflow probability. We shall show two lemmas about the overflow probability. Then we obtain the condition that there exists a FV code under the condition that the overflow probability is smaller than or equal to some constant.

Measuring the relational similarity between word pairs is important in numerous natural language processing tasks such as solving word analogy questions, classifying noun-modifier relations and disambiguating word senses. We propose a supervised classification method to measure the similarity between semantic relations that exist between words in two word pairs. First, each pair of words is represented by a vector of automatically extracted lexical patterns. Then a binary Support Vector Machine is trained to recognize word pairs with similar semantic relations to a given word pair. To train and evaluate the proposed method, we use a benchmark dataset that contains 374 SAT multiple-choice word-analogy questions. To represent the relations that exist between two word pairs, we experiment with 11 different feature functions, including both symmetric and asymmetric feature functions. Our experimental results show that the proposed method outperforms several previously proposed relational similarity measures on this benchmark dataset, achieving an SAT score of 46.9.

Source coding theorem reveals the minimum achievable code length under the condition that the error probability is smaller than or equal to some small constant. In the single user communication system, the source coding theorem was proved for general sources. The class of general source is quite large and it is important result since the result can be applied for a wide class of sources. On the other hand there are several studies to evaluate the achievable code length more precisely for the restricted class of sources by using the restriction. In the multi-user communication system, although the source coding theorem was proved for general correlated sources, there is no study to evaluate the achievable code length more precisely. In this study, we consider the stationary memoryless correlated sources and show the coding theorem for Slepian-Wolf type problem more precisely than the previous result.

Providing seamless QoS guarantees for multimedia services is one of the most critical requirements in the mobile Internet. However, the effects of host mobility make it difficult to provide such services. The next steps in signaling (NSIS) was proposed by the IETF as a new signaling protocol, but it fails to address some mobility issues. This paper proposes a new QoS NSIS signaling layer protocol (QoS NSLP) using a cross-layer design that supports mobility. Our approach is based on the advance discovery of a crossover node (CRN) located at the crossing point between a current and a new signaling path. The CRN then proactively reserves network resources along the new path that will be used after handoff. This proactive reservation significantly reduces the session reestablishment delay and resolves the related mobility issues in NSIS. Only a few amendments to the current NSIS protocol are needed to realize our approach. The experimental results and simulation study demonstrate that our approach considerably enhances the current NSIS in terms of QoS performance factors and network resource usage.

In this paper, we briefly review kernel methods for analysis of chemical compounds with focusing on the authors' works. We begin with a brief review of existing kernel functions that are used for classification of chemical compounds and prediction of their activities. Then, we focus on the pre-image problem for chemical compounds, which is to infer a chemical structure that is mapped to a given feature vector, and has a potential application to design of novel chemical compounds. In particular, we consider the pre-image problem for feature vectors consisting of frequencies of labeled paths of length at most K. We present several time complexity results that include: NP-hardness result for a general case, polynomial time algorithm for tree structured compounds with fixed K, and polynomial time algorithm for K=1 based on graph detachment. Then we review practical algorithms for the pre-image problem, which are based on enumeration of chemical structures satisfying given constraints. We also briefly review related results which include efficient enumeration of stereoisomers of tree-like chemical compounds and efficient enumeration of outerplanar graphs.

Previous studies of pattern recognition have shown that classifiers ensemble approaches can lead to better recognition results. In this paper, we apply the voting technique for the CoNLL-2010 shared task on detecting hedge cues and their scope in biomedical texts. Six machine learning-based systems are combined through three different voting schemes. We demonstrate the effectiveness of classifiers ensemble approaches and compare the performance of three different voting schemes for hedge cue and their scope detection. Experiments on the CoNLL-2010 evaluation data show that our best system achieves an F-score of 87.49% on hedge detection task and 60.87% on scope finding task respectively, which are significantly better than those of the previous systems.

In this paper, we propose an SNMP-aware web cache design that has two main objectives: (1) to avoid overload of network devices by SNMP requests, and (2) guaranteeing the monitoring time granularity of SNMP Object Identifiers (OID) for a large scale network such as the Internet. To meet these objectives, a cache is built into an RESTful active proxy, called Tambourine, which is the gateway for accessing management information through the Internet. Tambourine changes the landscape of traditional SNMP monitoring by allowing the Internet users to monitor closed-domain network devices through translating requests in HTTP into SNMP. However, the typical web cache algorithm can not be used in Tambourine due to two main reasons: (1) SNMP is not a cache-aware protocol and therefore can not provide Tambourine with the caching rules that need to be applied, and (2) the cache in Tambourine needs to accommodate two SNMP monitoring patterns: periodic and on-demand polling. In order for efficient periodic polling, SNMP traffic is reduced by a multi-TTL cache and user (or Manager)-side aggregation. For efficient on-demand polling, four-state transition is used to categorize OIDs into dynamic and static objects, each of which is allocated an optimum TTL. To provide users with a proper time stamp, the cache time stamp is included in the response to the users' request. Our experiments show that our cache design gives the staleness of 0 and a bounded number of SNMP requests even when the number of users' requests goes to infinity.

We propose online prediction algorithms for data streams whose characteristics might change over time. Our algorithms are applications of online learning with experts. In particular, our algorithms combine base predictors over sliding windows with different length as experts. As a result, our algorithms are guaranteed to be competitive with the base predictor with the best fixed-length sliding window in hindsight.

The contribution of this paper is two-fold. Firstly, we conduct a large-scale real-world evaluation of the effectiveness of integrating an automatic transliteration system with a machine translation system. A human evaluation is usually preferable to an automatic evaluation, and in the case of this evaluation especially so, since the common machine translation evaluation methods are affected by the length of the translations they are evaluating, often being biassed towards translations in terms of their length rather than the information they convey. We evaluate our transliteration system on data collected in field experiments conducted all over Japan. Our results conclusively show that using a transliteration system can improve machine translation quality when translating unknown words. Our second contribution is to propose a novel Bayesian model for unsupervised bilingual character sequence segmentation of corpora for transliteration. The system is based on a Dirichlet process model trained using Bayesian inference through blocked Gibbs sampling implemented using an efficient forward filtering/backward sampling dynamic programming algorithm. The Bayesian approach is able to overcome the overfitting problem inherent in maximum likelihood training. We demonstrate the effectiveness of our Bayesian segmentation by using it to build a translation model for a phrase-based statistical machine translation (SMT) system trained to perform transliteration by monotonic transduction from character sequence to character sequence. The Bayesian segmentation was used to construct a phrase-table and we compared the quality of this phrase-table to one generated in the usual manner by the state-of-the-art GIZA++ word alignment process used in combination with phrase extraction heuristics from the MOSES statistical machine translation system, by using both to perform transliteration generation within an identical framework. In our experiments on English-Japanese data from the NEWS2010 transliteration generation shared task, we used our technique to bilingually co-segment the training corpus. We then derived a phrase-table from the segmentation from the sample at the final iteration of the training procedure, and the resulting phrase-table was used to directly substitute for the phrase-table extracted by using GIZA++/MOSES. The phrase-table resulting from our Bayesian segmentation model was approximately 30% smaller than that produced by the SMT system's training procedure, and gave an increase in transliteration quality measured in terms of both word accuracy and F-score.

The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Mi and a target marking Mt, construct a marking that is closest to Mt among those which can be reached from Mi by firing transitions.” MCP includes the well-known marking reachability problem of Petri nets. MCP is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (MAX LFS) or (ii) using an algorithm for MAX LFS. Moreover, this paper proposes four pseudo-polynomial time algorithms: MCG and MCA for (i), and MCHFk and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHFk). Their performance is evaluated through results of computing experiment.

The brain-machine interface (BMI) is a new method for man-machine interface, which enables us to control machines and to communicate with others, without input devices but directly using brain signals. Previously, we successfully developed a real time control system for operating a robot arm using brain-machine interfaces based on the brain surface electrodes, with the purpose of restoring motor and communication functions in severely disabled people such as amyotrophic lateral sclerosis patients. A fully-implantable wireless system is indispensable for the clinical application of invasive BMI in order to reduce the risk of infection. This system includes many new technologies such as two 64-channel integrated analog amplifier chips, a Bluetooth wireless data transfer circuit, a wirelessly rechargeable battery, 3 dimensional tissue-fitting high density electrodes, a titanium head casing, and a fluorine polymer body casing. This paper describes key features of the first prototype of the BMI system for clinical application.

Modern microprocessors employ caches to bridge the great speed variance between a main memory and a central processing unit, but these caches consume a larger and larger proportion of the total power consumption. In fact, many values in a processor rarely need the full-bit dynamic range supported by a cache. The narrow-width value occupies a large portion of the cache access and storage. In view of these observations, this paper proposes an Adaptive Various-width Data Cache (AVDC) to reduce the power consumption in a cache, which exploits the popularity of narrow-width value stored in the cache. In AVDC, the data storage unit consists of three sub-arrays to store data of different widths. When high sub-arrays are not used, they are closed to save its dynamic and static power consumption through the modified high-bit SRAM cell. The main advantages of AVDC are: 1) Both the dynamic and static power consumption can be reduced. 2) Low power consumption is achieved by the modification of the data storage unit with less hardware modification. 3) We exploit the redundancy of narrow-width values instead of compressed values, thus cache access latency does not increase. Experimental results using SPEC 2000 benchmarks show that our proposed AVDC can reduce the power consumption, by 34.83% for dynamic power saving and by 42.87% for static power saving on average, compared with a cache without AVDC.

Data caching is widely known as an effective power-saving technique, in which mobile devices use local caches instead of original data placed on a server, in order to reduce the power consumption necessary for network accesses. In such data caching, a cache invalidation mechanism is important in preventing these devices from unintentionally accessing invalid data. In this paper, we propose a broadcast-based protocol for cache invalidation in a location-aware system. The proposed protocol is designed to reduce the access time required for obtaining necessary invalidation reports through broadcast media and to avoid client-side sleep fragmentation while retrieving the reports. In the proposed protocol, a Bloom filter is used as the data structure of an invalidation report, in order to probabilistically check the invalidation of caches. Furthermore, we propose three broadcast scheduling methods that are intended to achieve flexible broadcasting structured by the Bloom filter: fragmentation avoidance scheduling method (FASM), metrics balancing scheduling method (MBSM), and minimizing access time scheduling method (MASM). The broadcast schedule is arranged for consecutive accesses to geographically neighboring invalidation reports. In addition, the effectiveness of the proposed methods is evaluated by simulation. The results indicate that the MBSM and MASM achieve a high rate of performance scheduling. Compared to the FASM, the MBSM reduces the access time by 34%, while the fragmentations on the resultant schedule increase by 40%, and the MASM reduces the access time by 40%, along with an 85% increase in the number of fragmentations.

Since retina blood vessels (RBV) are a major factor in ophthalmological diagnosis, it is essential to detect RBV from a fundus image. In this letter, we proposed the detection method of RBV using a morphological analysis and support vector machine classification. The proposed RBV detection method consists of three strategies: pre-processing, features extraction and classification. In pre-processing, noises were reduced and RBV were enhanced by anisotropic diffusion filtering and illumination equalization. Features were extracted by using the image intensity and morphology of RBV. And a support vector machine (SVM) classification algorithm was used to detect RBV. The proposed RBV detection method was simulated and validated by using the DRIVE database. The averages of accuracy and TPR are 0.94 and 0.78, respectively. Moreover, by comparison, we confirmed that the proposed RBV detection method detected RBV better than the recent RBV detections methods.

Power consumption has become an increasing concern in high performance microprocessor design. Especially, Instruction Cache (I-Cache) contributes a large portion of the total power consumption in a microprocessor, since it is a complex unit and is accessed very frequently. Several studies on low-power design have been presented for the power-efficient cache design. However, these techniques usually suffer from the restrictions in the traditional Instruction Fetch Unit (IFU) architectures where the fetch address needs to be sent to I-Cache once it is available. Therefore, work to reduce the power consumption is limited after the address generation and before starting an access. In this paper, we present a new power-aware IFU architecture, named Analysis Before Starting an Access (ABSA), which aims at maximizing the power efficiency of the low-power designs by eliminating the restrictions on those low-power designs of the traditional IFU. To achieve this goal, ABSA reorganizes the IFU pipeline and carefully assigns tasks for each stages so that sufficient time and information can be provided for the low-power techniques to maximize the power efficiency before starting an access. The proposed design is fully scalable and its cost is low. Compared to a conventional IFU design, simulation results show that ABSA saves about 30.3% fetch power consumption, on average. I-Cache employed by ABSA reduces both static and dynamic power consumptions about 85.63% and 66.92%, respectively. Meanwhile the performance degradation is only about 0.97%.

This paper provides conceptual and experimental analysis of a new approach in the study of kanji, our “Learner's Visualization (LV) Approach”. In a previous study we found that the LV Approach assists beginning learners in significantly updating their personal kanji deconstruction visualization. Additionally, in another study our findings provided evidence that beginning learners also receive a significant impact in the ability to acquire vocabulary. In this study, our research problem examines how beginning and intermediate students use visualization to cognitively deconstruct (divide) kanji in different ways, and how this affects their learning progress. We analyze the cognitive differences in how kanji learners explore and deconstruct novel kanji while using the LV Approach and how these differences affect their learning process while using the LV Approach. During the learning experience, our LILES System (Learner's Introspective Latent Envisionment System), based on the LV Approach, guides learners to choose from a set of possible “kanji deconstruction layouts” (layouts showing different ways in which a given kanji can be divided). The system then assists learners in updating their “kanji deconstruction level” (the average number of parts they visualize within kanji according to their current abilities). Statistical analysis based on achieved performance was conducted. The analysis of our results proves that there are cognitive differences: beginners deconstruct kanji into more parts (“blocks”) than intermediate learners do, and while both improve their kanji deconstruction scores, there is a more significant change in “kanji deconstruction level” in beginners. However, it was also found that intermediate learners benefit more in “kanji retention score” compared with beginners. Suggestions for further research are provided.

We propose a polarization-multiplexing QPSK modulator for synthesis of a 16 QAM signal. The generation mechanism of 16 QAM is based on an electro-optic vector digital-to-analog converter, which can generate optical multilevel signals from binary electric data sequences. A quad-parallel Mach-Zehnder modulator (QPMZM) used in our previous research requires precise control of electric signals or fabrication of a variable optical attenuator, which significantly raises the degree of difficulty to control electric signals or device fabrication. To overcome this difficulty, we developed the polarization-multiplexing QPSK modulator, which improved the method of superposition of QPSK signals. In the polarization-multiplexing QPSK modulator, two QPSK signals are output with orthogonal polarization and superposed through a polarizer. The amplitude ratio between the two QPSK signals can be precisely controlled by rotating the polarizer to arrange the 16 symbols equally. Generation of 16 QAM with 40 Gb/s and a bit error rate of 5.6910-5 was successfully demonstrated using the polarization-multiplexing QPSK modulator. This modulator has simpler configuration than the previous one, utilized a dual-polarization MZM, alleviating complicated control of electric signals.

Lattice decoding in statistical machine translation (SMT) is useful in speech translation and in the translation of German because it can handle input ambiguities such as speech recognition ambiguities and German word segmentation ambiguities. In this paper, we show that lattice decoding is also useful for handling input variations. “Input variations” refers to the differences in input texts with the same meaning. Given an input sentence, we build a lattice which represents paraphrases of the input sentence. We call this a paraphrase lattice. Then, we give the paraphrase lattice as an input to a lattice decoder. The lattice decoder searches for the best path of the paraphrase lattice and outputs the best translation. Experimental results using the IWSLT dataset and the Europarl dataset show that our proposed method obtains significant gains in BLEU scores.

The Krivine-style evaluation mechanism is well-known in the implementation of higher-order functions, allowing to avoid some useless closure building. There have been a few type systems that can verify the safety of the mechanism. The incorporation of the proposed ideas into an existing compiler, however, would require significant changes in the type system of the compiler due to the use of some dedicated form of types and typing rules in the proposals. This limitation motivates us to propose an alternative light-weight Krivine typing mechanism that does not need to extend any existing type system significantly. This paper shows how GADTs (Generalized algebraic data types) can be used for typing a ZINC machine following the Krivine-style evaluation mechanism. This idea is new as far as we know. Some existing typed compilers like GHC (Glasgow Haskell compiler) already support GADTs; they can benefit from the Krivine-style evaluation mechanism in the operational semantics with no particular extension in their type systems for the safety. We show the GHC type checker allows to prove mechanically that ZINC instructions are well-typed, which highlights the effectiveness of GADTs.

In this letter, a new terrain type classifier is proposed for polarimetric Synthetic Aperture Radar (Pol-SAR) images. This classifier uses the binary tree structure. The homogenous and inhomogeneous areas are first classified by the support vector machine (SVM) classifier based on the texture features extracted from the span image. Then the homogenous and inhomogeneous areas are, respectively, classified by the traditional Wishart classifier and the SVM classifier based on the texture features. Using a NASA/JPL AIRSAR image, the authors achieve the classification accuracy of up to 98%, demonstrating the effectiveness of the proposed method.