The recursive and hierarchical structure of full rooted trees is applicable to statistical models in various fields, such as data compression, image processing, and machine learning. In most of these cases, the full rooted tree is not a random variable; as such, model selection to avoid overfitting is problematic. One method to solve this problem is to assume a prior distribution on the full rooted trees. This enables the optimal model selection based on Bayes decision theory. For example, by assigning a low prior probability to a complex model, the maximum a posteriori estimator prevents the selection of the complex one. Furthermore, we can average all the models weighted by their posteriors. In this paper, we propose a probability distribution on a set of full rooted trees. Its parametric representation is suitable for calculating the properties of our distribution using recursive functions, such as the mode, expectation, and posterior distribution. Although such distributions have been proposed in previous studies, they are only applicable to specific applications. Therefore, we extract their mathematically essential components and derive new generalized methods to calculate the expectation, posterior distribution, etc.

<title>Abstract</title>Prediction based on a single linear regression model is one of the most common way in various field of studies. It enables us to understand the structure of data, but might not be suitable to express the data whose structure is complex. To express the structure of data more accurately, we make assumption that the data can be divided in clusters, and has a linear regression model in each cluster. In this case, we can assume that each explanatory variable has their own role; explaining the assignment to the clusters, explaining the regression to the target variable, or being both of them. Introducing probabilistic structure to the data generating process, we derive the optimal prediction under Bayes criterion and the algorithm which calculates it sub-optimally with variational inference method. One of the advantages of our algorithm is that it automatically weights the probabilities of being each number of clusters in the process of the algorithm, therefore it solves the concern about selection of the number of clusters. Some experiments are performed on both synthetic and real data to demonstrate the above advantages and to discover some behaviors and tendencies of the algorithm.

Suppose that we have two training sequences generated by parametrized distributions P_{\\theta} and P_{\\varepsilon^{* } }, where \\theta ∗ and \\xi^{*} are unknown true parameters. Given training sequences, we study the problem of classifying whether a test sequence was generated according to P_{\\theta} ∗ or P_{\\xi^{* } }. This problem can be thought of as a hypothesis testing problem and our aim is to analyze the weighted sum of type-I and type-II error probabilities. Utilizing the analysis of the codeword lengths of the Bayes code, our previous study derived more refined bounds on the error probability than known previously. However, our previous study had the following deficiencies: i) the prior distributions of \\theta and \\xi are the same
ii) the prior distributions of two hypotheses are uniform
iii) no numerical calculation at finite blocklength. This study solves these problems. We remove the restrictions i) and ii) and derive more general results than obtained previously. To deal with problem iii), we perform a numerical calculation for a concrete model.

This paper deals with a prediction problem of a new targeting variable corresponding to a new explanatory variable given a training dataset. To predict the targeting variable, we consider a model tree, which is used to represent a conditional probabilistic structure of a targeting variable given an explanatory variable, and discuss statistical optimality for prediction based on the Bayes decision theory. The optimal prediction based on the Bayes decision theory is given by weighting all the model trees in the model tree candidate set, where the model tree candidate set is a set of model trees in which the true model tree is assumed to be included. Because the number of all the model trees in the model tree candidate set increases exponentially according to the maximum depth of model trees, the computational complexity of weighting them increases exponentially according to the maximum depth of model trees. To solve this issue, we introduce a notion of meta-tree and propose an algorithm called MTRF (Meta-Tree Random Forest) by using multiple meta-trees. Theoretical and experimental analyses of the MTRF show the superiority of the MTRF to previous decision tree-based algorithms.

We propose two new criteria to understand the advantage of deepening neural networks. It is important to know the expressivity of functions computable by deep neural networks in order to understand the advantage of deepening neural networks. Unless deep neural networks have enough expressivity, they cannot have good performance even though learning is successful. In this situation, the proposed criteria contribute to understanding the advantage of deepening neural networks since they can evaluate the expressivity independently from the efficiency of learning. The first criterion shows the approximation accuracy of deep neural networks to the target function. This criterion has the background that the goal of deep learning is approximating the target function by deep neural networks. The second criterion shows the property of linear regions of functions computable by deep neural networks. This criterion has the background that deep neural networks whose activation functions are piecewise linear are also piecewise linear. Furthermore, by the two criteria, we show that to increase layers is more effective than to increase units at each layer on improving the expressivity of deep neural networks.

A spatially "Mt. Fuji"coupled (SFC) low-density paritycheck (LDPC) ensemble is a modified version of the spatially coupled (SC) LDPC ensemble. Its decoding error probability in the waterfall region has been studied only in an experimental manner. In this paper, we theoretically analyze it over the binary erasure channel by modifying the expected graph evolution (EGE) and covariance evolution (CE) that have been used to analyze the original SC-LDPC ensemble. In particular, we derive the initial condition modified for the SFC-LDPC ensemble. Then, unlike the SC-LDPC ensemble, the SFC-LDPC ensemble has a local minimum on the solution of the EGE and CE. Considering the property of it, we theoretically expect the waterfall curve of the SFC-LDPC ensemble is steeper than that of the SC-LDPC ensemble. In addition, we also confirm it by numerical experiments.

Change-point detection is the problem of finding points of time when a probability distribution of samples changed. There are various related problems, such as estimating the number of the changepoints and estimating magnitude of the change. Though various statistical models have been assumed in the field of change-point detection, we particularly deal with i.p.i.d. (independent-piecewise-identically-distributed) sources. In this paper, we formulate the related problems in a general manner based on statistical decision theory. Then we derive optimal estimators for the problems under the Bayes risk principle. We also propose e_cient algorithms for the change-point detection-related problems in the i.p.i.d. sources, while in general, the optimal estimations requires huge amount of calculation in Bayesian setting. Comparison of the proposed algorithm and previous methods are made through numerical examples.

This paper clarifies the relationship between two information quantities related to two distortion balls in variable-length lossy source coding. To show various fundamental limits in variable-length lossy source coding, the notion of distortion ball has been known to be useful. In the previous study by Kostina et al., it was shown that the fundamental limit of the minimum average codewordlengths under an excess distortion constraint is characterized by the information quantity related to the distortion ball centered at a source symbol. On the other hand, in our previous study, it was shown that the same fundamental limit is characterized by the information quantity related to thedistortion ball centered at a reproduction symbol. Then, what is the relationship between these twoinformation quantities? This paper gives an answer to this question.

In this paper, we propose an autoregressive stochastic generative model for images. This modelshould be one of the most basic models for the new type of lossless image compression which explicitly assume the stochastic generative model. We can easily expand it and theoretically interpret theimplicitly assumed stochastic generative models in the various previous predictive coding methods as the expanded versions of our model. Moreover, we can utilize the achievements in the related fields where the linear regression analysis and its expansion are studied to construct the Bayes codes for these generative models. As an example, we expand our generative model from the one with normalnoise to the one with the t-distributed noise. Then, we construct the sub-optimal Bayes codes for this generative model by utilizing the variational Bayesian method.

We focus on smooth locally decodable codes (SLDC) and Private Information Retrieval (PIR). Recently, a relationship between SLDC and PIR are studied using information theoretical notations. In this paper, we clarify a relationship between SLDCs and PIR using set theoretical notations mainly.

We focus on smooth locally decodable codes (SLDC) and Private Information Retrieval (PIR). Recently, a relationship between SLDC and PIR are studied using information theoretical notations. In this paper, we clarify a relationship between SLDCs and PIR using set theoretical notations mainly.

Suppose that we have two training sequences generated by parametrized distributions P θ 1∗ and P θ 2∗, where θ 1∗{\\ast} and θ 2∗{\\ast} are unknown. Given training sequences, we study the problem of classifying whether a test sequence was generated according to P θ 1∗ or P θ 2∗. This problem can be thought of as a hypothesis testing problem and the weighted sum of type-I and type-II error probabilities is analyzed. To prove the results, we utilize the analysis of the codeword lengths of the Bayes code. It is shown that upper and lower bounds of the probability of error are characterized by the terms containing the Chernoff information, the dimension of a parameter space, and the ratio of the length between the training sequences and the test sequence. Further, we generalize the part of the preceding results to multiple hypotheses setup.

In this paper, we deal with the problem of database statistics publishing with privacy and utility guarantees. While various privacy and utility metrics have been proposed, purposes of using the statistics for a user and an adversary and their background knowledge about the database have not been specified. We model the user and the adversary from two perspectives. First, we model their background knowledge: knowledge of statistics of the database and knowledge of distribution for the database. Then we model the purposes of them as decision functions in statistical decision theory. Privacy and utility metrics are defined based on risk functions. Comparison of the statistical decision-theoretic framework we propose and differential privacy framework is made through a numerical example.

We focus on smooth locally decodable codes (SLDC) and Private Information Retrieval (PIR). Recently, a relationship between SLDC and PIR are studied using information theoretical notations. In this paper, we clarify a relationship between SLDCs and PIR using set theoretical notations mainly.

F.P. Preparata et al. have proposed a fault diagnosis model to find all faulty units in the multicomputer system by using outcomes which each unit tests some other units. In this paper, for probabilistic diagnosis models, we show an efficient diagnosis algorithm to obtain a posteriori probability that each of units is faulty given the test outcomes. Furthermore, we propose a method to analyze the diagnostic error probability of this algorithm.

A locally recoverable code (LRC code) is a code such that each codeword symbol can be recovered from other codeword symbols. In this research, we propose one possible generalization of previous LRC codes and we derive a bound on the rate of the proposed code.

A new type of spatially coupled low density parity check (SCLDPC) code is proposed. This code has two benefits. (1) This code requires less number of iterations to correct the erasures occurring through the binary erasure channel in the waterfall region than that of the usual SCLDPC code. (2) This code has lower error floor than that of the usual SCLDPC code. Proposed code is constructed as a coupled chain of the underlying LDPC codes whose code lengths exponentially increase as the position where the codes exist is close to the middle of the chain. We call our code spatially "Mt. Fuji" coupled LDPC (SFCLDPC) code because the shape of the graph representing the code lengths of underlying LDPC codes at each position looks like Mt. Fuji. By this structure, when the proposed SFCLDPC code and the original SCLDPC code are constructed with the same code rate and the same code length, L (the number of the underlying LDPC codes) of the proposed SFCLDPC code becomes smaller and M (the code lengths of the underlying LDPC codes) of the proposed SFCLDPC code becomes larger than those of the SCLDPC code. These properties of L and M enables the above reduction of the number of iterations and the bit error rate in the error floor region, which are confirmed by the density evolution and computer simulations.

This letter treats the problem of lossless fixed-to-variable length source coding in moderate deviation regime. We investigate the behavior of the overflow probability of the Bayes code. Our result clarifies that the behavior of the overflow probability of the Bayes code is similar to that of the optimal non-universal code for i.i.d. sources.

This paper investigates the problem of variable-length lossy source coding. We deal with the case where both the excess distortion probability and the overflow probability of codeword length are less than or equal to positive constants. The infimum of the thresholds on the overflow probability is characterized by a smooth max entropy-based quantity. Both non-asymptotic and asymptotic cases are analyzed. To show the achievability results, we do not utilize the random coding argument but give an explicit code construction.

<p>In this research we apply Markov decision processes to asset management with sensor network. We propose a new asset management method which minimizes total cost with reference to a Bayes criterion.</p>

<p>In this research we apply Markov decision processes to recommender system with transitions of user classes. We propose a new recommender method which maximizes total reward with reference to a Bayes criterion.</p>

We treat lossless fixed-to-variable length source coding under general sources for finite block length setting. We evaluate the threshold of the overflow probability for prefix and non-prefix codes in terms of the smooth max-entropy. We clarify the difference of the thresholds between prefix and non-prefix codes for finite block length. Further, we discuss our results under the asymptotic block length setting.

This letter deals with the Slepian-Wolf coding problem for general sources. The second-order achievable rate region is derived using quantity which is related to the smooth max-entropy and the conditional smooth max-entropy. Moreover, we show the relationship of the functions which characterize the second-order achievable rate region in our study and previous study.

In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance d(fp) of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to. inverted left perpendiculard(fp)/2inverted right perpendicular - 1 errors.

We treat lossless fixed-to-variable length source coding under general sources for finite block length setting. We evaluate the threshold of the overflow probability for prefix and non-prefix codes in terms of the smooth max-entropy. We clarify the difference of the thresholds between prefix and non-prefix codes for finite block length. Further, we discuss our results under the asymptotic block length setting.

Copyright © 2016 The Institute of Electronics, Information and Communication Engineers.This letter deals with the Slepian-Wolf coding problem for general sources. The second-order achievable rate region is derived using quantity which is related to the smooth max-entropy and the conditional smooth max-entropy. Moreover, we show the relationship of the functions which characterize the second-order achievable rate region in our study and previous study.

Copyright © 2016 The Institute of Electronics, Information and Communication Engineers.In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance df p of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to df p =2 - 1 errors.

In this paper, we develop a new decoding algorithm of binary linear codes for symbol-pair read channel. The Symbol-pair read channel has recently been introduced by Cassuto and Blaum to model channel whose write resolution is higher than read resolution. The proposed decoding algorithm is based on the linear programming (LP). It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance d(fp) of the code which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to [d(fp)/2] - 1 errors.

There are many research on hybrid selective-repeat ARQ method. In many previous research purposes have been to maximize a throughput on the number of messages delivered to the user. Important theoretical limits were studied under the condition that a decoding error was very small and neglected.
In this research we propose the optimal type-I hybrid selective-repeat ARQ with finite receiver buffer. The proposed method maximizes an expected total reward regarding the number of messages delivered to the user correctly based on statistical decision theory.

A new theory known as compressed sensing considers the problem to acquire and recover a sparse signal from its linear measurements. In this paper, we propose a new support recovery algorithm from noisy measurements based on the linear programming (LP). LP is widely used to estimate sparse signals, however, we focus on the problem to recover the support of sparse signals rather than the problem to estimate sparse signals themselves. First, we derive an integer linear programming (ILP) formulation for the support recovery problem. Then we obtain the LP based support recovery algorithm by relaxing the ILP. The proposed LP based recovery algorithm has an attracting property that the output of the algorithm is guaranteed to be the maximum a posteiori (MAP) estimate when it is integer valued. We compare the performance of the proposed algorithm to a state-of-the-art algorithm named sparse matching pursuit (SMP) via numerical simulations.

Recently, studies of linear network coding have attracted attention. This paper considers a probabilistic error model for the deterministic linear network coding. In the previous studies of error-correcting codes, Kaneko et al. proposed a decoding algorithms for probabilistic error model. This is a maximum likelihood decoding algorithm that uses the optimization method called branch and bound method. This paper constructs a new model of deterministic linear network coding and proposes a maximum likelihood decoding algorithm that uses the branch and bound method.

Cooperative regenerating codes are a class of codes that enable a data collector to reconstruct the original data by connecting to a subset of storage nodes, and also can repair multiple failed nodes by downloading data from the surviving nodes and exchanging data among the new nodes. In cooperative regenerating codes, there exists a tradeoff between the storage size of each node and repair-bandwidth. In this study, we propose new classes of cooperative regenerating codes based on correlation of information stored on nodes. We also consider relationships between each class of cooperative regenerating codes and storage size and repair-bandwidth.

Linear Unequal Error Protection (UEP) codes were proposed by Masnick et al. and largely developed by Dunning et al. and Gils. On the other hand, random linear network coding is recently studied by many researchers. Kotter et al. proposed a new coding technique named subspace codes and applied it to random linear network coding. Moreover. Silva et al. proposed constructions of subspace codes using rank metric codes. In this paper, we propose subspace UEP codes and apply them to the random linear network coding. Then, we propose rank metric UEP codes and constructions of the subspace UEP codes using the rank metric UEP codes.

As a distributed storage system with regenerating function of failed nodes, regenerating codes have been studied recently. In a [n, k, d]-regenerating codes framework, a message can be reconstructed from any subsets of k nodes out of n nodes and any failed nodes can be repaired from any subsets of d nodes out of (n -1) nodes. The conditions of the reconstruction and regeneration can be generalized. In this paper, we propose the regenerating codes with generalized conditions and derive their optimal constructing algorithm under the multiple assignment map construction framework. The optimal codes of the framework are obtained by solving integer programming problems in a similar way of generalized secret sharing scheme's construction based on a multiple assignment map.

This paper considers universal lossless variable-length source coding problem and investigates the Bayes code from viewpoints of the distribution of its codeword lengths. First, we show that the codeword lengths of the Bayes code satisfy the asymptotic normality. This study can be seen as the investigation on the asymptotic shape of the distribution of codeword lengths. Second, we show that the codeword lengths of the Bayes code satisfy the law of the iterated logarithm. This study can be seen as the investigation on the asymptotic end points of the distribution of codeword lengths. Moreover, the overflow probability, which represents the bottom of the distribution of codeword lengths, is studied for the Bayes code. We derive upper and lower bounds of the infimum of a threshold on the overflow probability under the condition that the overflow probability does not exceed epsilon is an element of(0, 1). We also analyze the necessary and sufficient condition on a threshold for the overflow probability of the Bayes code to approach zero asymptotically.

This paper considers universal lossless variablelength source coding problem and deals with one of the fundamental limits and pointwise asymptotics of the Bayes code for stationary ergodic finite order Markov sources. As investigation of the fundamental limits, we show upper and lower bounds of the minimum rate such that the probability which exceeds it is less than epsilon is an element of (0, 1). Furthermore, we prove that the codeword length of the Bayes code satisfies the asymptotic normality (pointwise root n asymptotics) and the law of the iterated logarithm (pointwise root n log log n asymptotics), where n represents length of a source sequence and "log" is the natural logarithm.

This paper considers universal lossless variable-length source coding problem and investigates the Bayes code from viewpoints of the distribution of its codeword lengths. First, we show that the codeword lengths of the Bayes code satisfy the asymptotic normality. This study can be seen as the investigation on the asymptotic shape of the distribution of codeword lengths. Second, we show that the codeword lengths of the Bayes code satisfy the law of the iterated logarithm. This study can be seen as the investigation on the asymptotic end points of the distribution of codeword lengths. Moreover, the overflow probability, which represents the bottom of the distribution of codeword lengths, is studied for the Bayes code. We derive upper and lower bounds of the infimum of a threshold on the overflow probability under the condition that the overflow probability does not exceed ε∈(0,1). We also analyze the necessary and sufficient condition on a threshold for the overflow probability of the Bayes code to approach zero asymptotically.

In this paper, sequential prediction is studied. The typical assumptions about the probabilistic model in sequential prediction are following two cases. One is the case that a certain probabilistic model is given and the parameters are unknown. The other is the case that not a certain probabilistic model but a class of probabilistic models is given and the parameters are unknown. If there exist some parameters and some models such that the distributions that are identified by them equal the source distribution, an assumed model or a class of models can represent the source distribution. This case is called that specifiable condition is satisfied. In this study, the decision based on the Bayesian principle is made for a class of probabilistic models (not for a certain probabilistic model). The case that specifiable condition is not satisfied is studied. Then, the asymptotic behaviors of the cumulative logarithmic loss for individual sequence in the sense of almost sure convergence and the expected loss, i.e. redundancy are analyzed and the constant terms of the asymptotic equations are identified.

AdaBoost はパターン認識において用いられるアルゴリズムで，逐次的に学習データに対する誤差が最小になるようにモデルを構成する．しかしながら，新たなデータに対する予測を考えるとき，学習データに対する誤差が最小であるモデルが適切とは限らない．それに対し，特に線形回帰の分野では様々な正則化法や変数選択法が研究されている．変数選択法のうちの変数増加法の 1 つとして Stagewise がある．Stagewise は各反復において変数を １ つ選択する．このとき，それに対応するパラメータを誤差関数が最小になるように増加させるのではなく，わずかにパラメータが増加するよう更新を行うアルゴリズムで，予測誤り率を改善することが知られている．AdaBoost のモデルを線形回帰のモデルと比較して考えると AdaBoost は変数増加法とみなすことができる．本研究では，AdaBoost において Stagewise の考え方を適用することで，新たなデータに対する予測誤り率の改善について検討する．AdaBoost is an algorithm used for pattern recognition. This algorithm successively makes the model which minimizes an error for sample data. However, to consider prediction, there is no guarantee that such model is optimum. Regarding this issue, there are many studies about regularization method and variable selection method. Forward selection method is one of the methods of variable selection method and Stagewise is one of the methods of forward selection method. Each iteration, Stagewise selects one variable. Stagewise updates parameters slightly increase and not minimizes an error for sample data. It is known that Stagewise improves the rate of a prediction error. In this research, we apply the idea of Stagewise for AdaBoost and consider improvement the rate of a prediction error.

In this paper, we consider a completion problem of multiple related matrices. Matrix completion problem is the problem to estimate unobserved elements of the matrix from observed elements. It has many applications such as collaborative filtering, computer vision, biology, and so on. In cases where we can obtain some related matrices, we can expect that their simultaneous completion has better performance than completing each matrix independently. Collective matrix factorization is a powerful approach to jointly factorize multiple matrices. However, existing completion algorithms for the collective matrix factorization have some drawbacks. One is that most existing algorithms are based on non-convex formulations of the problem. Another is that only a few existing algorithms consider the strength of the relation among matrices and it results in worse performance when some matrices are actually not related. In this paper, we formulate the multiple matrix completion problem as the convex optimization problem. Moreover, it considers the strength of the relation among matrices. We also develop an optimization algorithm which solves the proposed problem efficiently based on the alternating direction method of multipliers (ADMM). We verify the effectiveness of our approach through numerical experiments on both synthetic data and real data set: MovieLens.

The objective of this research is to evaluate the epsilon-minimum overflow threshold of the Bayes codes for a Markov source. In the lossless variable-length source coding problem, typical criteria are the mean codeword length and the overflow probability. The overflow probability is the probability with which a codeword length per source symbol exceeds a threshold and the epsilon-minimum overflow threshold is defined. In the non-universal setting, the Shannon code is optimal under the mean codeword length and the epsilon-minimum overflow threshold for the Shannon code is derived for an i.i.d. source. On the other hand, in the universal setting, the Bayes code is one of universal codes which minimize the mean codeword length under the Bayes criterion. However, few studies have been done on the overflow probability for the Bayes codes. In this paper, we assume a stationary ergodic finite order Markov source and derive the upper and lower bounds of the epsilon-minimum overflow threshold of the Bayes codes.

本稿ではプライバシー保護を目的とした回帰分析について扱う．これは複数のユーザがそれぞれ異なるデータを保持したもとで，それぞれの保持するデータを互いに公開，共有することなく，協力して全てのデータを用いた場合と同等の回帰分析を行うというものである．本稿ではまず，ユーザが2人の場合を想定し，2者が異なる属性に関するデータを保持しているもとで最小二乗推定量を分散計算する場合を考える．そのもとで，新たな分散計算プロトコルを提案し，プライバシーについてプロトコルの安全性を評価する．また，提案するプロトコルは繰り返し計算を行うため，数値実験によりプロトコルの繰り返し数についての評価を行う．さらに，収束回数を削減する修正プロトコルを提案し，多者間での分散計算への拡張も行う．

近年,遊び手である人間の負荷を軽減することを目的に,遊び手が操作するキャラクタであるプレイヤキャラクタ(PC)以外にコンピュータが操作するキャラクタであるノンプレイヤキャラクタ(NPC)が導入されたロールプレイングゲーム(RPG)が増えてきた.従来からマルコフ決定過程(MDP)を用いたRPGのモデル化が行われているが,NPCを伴うRPGのMDPを用いたモデル化はまだ行われていない.そこで,本研究では,MDPを用いてNPCを伴うRPGのモデル化を行う.更に,MDPの真のパラメータ未知の場合に相当するNPCを伴うRPGについて,報酬の期待値をベイズ基準のもとで最大にする攻略法を算出するアルゴリズムを提案する.

従来からマルコフ決定過程(MDP)を用いたロールプレイングゲーム(RPG)のモデル化が行われている.しかし,RPGの攻略法を能動的に学習する研究は行われていない.そこで,本研究では,真のパラメータが未知のMDPで表現されたRPGにおける期待総利得をベイズ基準のもとで最大にする攻略法を求める能動的な学習方法を提案する.シミュレーションをとおして,提案方法の有効性を確認する.

In this paper, we develop an iterative multiuser joint decoding of code-division multiple-access (CDMA) signals based on a distributed optimization algorithm. For the joint decoding problem, decoding algorithm based on the turbo principle is widely used. The algorithm consists of soft-input soft-output (SISO) channel decoder and SISO multiuser detector and it can be derived as an application of the sum-product algorithm. On the other hand, in the research area of error correcting codes, the decoding algorithm based on convex optimization has been attracting a great deal of attention. Decoding algorithm based on linear programming (LP) has decoding error rate which is comparable with sum-product algorithm with stronger theoretical guarantees. We formulate the joint decoding problem of CDMA signals as an convex optimization problem and we present a relax form of the problem. Moreover, we propose a distributed algorithm which efficiently solves the relaxed optimization problem. The proposed algorithm is based on alternating direction method of multipliers (ADMM). We also see the performance of the proposed decoder through numerical simulations. © 2013 IEEE.

ユーザ入力をもとにシステムが予測し候補を提示する文書作成支援技術が普及している．この応用を想定したNグラムモデルを用いた単語の予測法を検討する．Nグラムモデルは学習データをもとに構築されるが，単語列を構成する単語の組合せが膨大なため次数が増加するにつれ疎となる．モデル構築においては，高次のモデルの推定に対し，低次のモデルの推定結果をもとにいかに補間するかが課題である．従来は混合分布の仮定や，ごく少数にしか出現しない単語列を考慮した割引係数をもとに，各次数のモデルを重みづけ足し合わせることが行われていたが，予測に対する理論的な保証はない．本稿では，これに対し真の次数が未知の統計問題ととらえ，ベイズ決定理論に基づいて，単語の予測誤りの損失に対しベイズ基準のもとで最小となることが保証された予測法を導出する．さらに，日本語文書データでの単語予測の実験を行い，提案法が実用的にも有効であることを示す．

Experiments usually aim to study how changes in various factors affect the response variable of interest. Since the response model used most often at present in experimental design is expressed through the effect of each factor, it is straightforward to ascertain how each factor affects the response variable. However, since the response model contains redundant parameters, in the analysis of variance we must calculate the degrees of freedom defined by the number of independent parameters. In this letter, we propose the idea of calculating the degrees of freedom over the model based on an orthonormal system for the first time. In this way, we can easily obtain the number of independent parameters associated with any component, which reduces the risk of mistakes in the calculation of the number of independent parameters and facilitates the implementation of estimation procedures. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

従来のランプ型鍵事前配布方式は結託したユーザ数の増加に従って攻撃対象である鍵の情報が段階的に得られる安全性を有しているが,センターの結託数に対してはそのような性質を有していない.そこで本論文では,従来のランプ型鍵事前配布方式を一般化したモデルを新たに定義し,そのモデルに対してセンター及びユーザの記憶容量の下界をそれぞれ導出し,それぞれの下界を達成するランプ型鍵事前配布方式の最適な構成法を提案する.

The document classification problem has been investigated by various techniques, such as a vector space model, a support vector machine, a random forest, and so on. On the other hand, J.Ziv et al. have proposed a document classification method using Ziv-Lempel algorithm to compress the data. Furthermore, the Context-Tree Weighting (CTW) algorithm has been proposed as an outstanding data compression, and for the document classification using the CTW algorithm experimental results have been reported. In this paper, we assume that each document with same category arises from Markov model with same parameters for the document classification. Then we propose an analysis method to estimate a classification error probability for the document with the finite length.

We propose new algorithms for fault diagnosis problem based on the dual decomposition method and the augmented Lagrangian method. Our algorithms are convergent and those outputs are same as that of Linear Programming (LP) based fault diagnosis algorithm. The proposed algorithms have smaller computational complexity than ordinary LP solver. Experimental results show the practical potentials of the proposed algorithms.

Lossless variable-length source coding with unequal cost function is considered for general sources. In this problem, the codeword cost instead of codeword length is important. The infimum of average codeword cost has already been determined for general sources. We consider the overflow probability of codeword cost and determine the infimum of achievable overflow threshold. Our analysis is on the basis of information-spectrum methods and hence valid through the general source.

We analyze the asymptotic properties of the cumulative logarithmic loss in the decision problem based on the Bayesian principle and explicitly identify the constant terms of the asymptotic equations as in the case of previous studies by Clarke and Barron and Gotoh et al. We assume that the set of models is given that identify a class of parameterized distributions, it has a nested structure and the source distribution is not contained in all the families of parameterized distributions that are identified by each model. The cumulative logarithmic loss is the sum of the logarithmic loss functions for each time decision-, e. g., the redundancy in the universal noiseless source coding.

A stream cipher is an important class of encryption algorithms. Its safety depends on the structure of the pseudo-random number generator used. There are various types of pseudo-random number generators in existence, and attack algorithms used on them have been studied individually. In this paper, we express the problem of attacks on a general stream cipher as a probabilistic inference problem, and formulate the optimal key estimation. We also propose a unified framework of attack algorithms that can be applied to a wide variety of stream ciphers. The optimal key estimation, however, has computational complexity. To reduce the complexity, an approximation algorithm based on a probabilistic inference is proposed. We also describe some attack algorithms used on practical pseudo-random number generators. Finally, the proposed algorithm is evaluated by through a computer simulation.

推薦問題を扱うためのより一般化されたマルコフ決定過程モデルに対して，ベイズ基準のもとで最適な推薦ルールを履歴データから求める方法を提案する．推薦問題に関する研究において，これまで，ある商品を推薦した結果どの商品が買われたのか（推薦結果）や，さらには，一定期間内に行った複数の推薦結果が考慮されることはほとんどなかった．これに対して，マルコフ決定過程モデルを用いることで上記2点を初めて考慮した手法が提案されている．提案法は，その従来研究のモデルを一般化した点に新規性がある．また，もう1つの新規性として，推薦ルールを求めるためのプロセスを統計的決定問題として厳密に定式化した点がある．従来のモデルを一般化することで，マルコフ決定過程モデルを用いた推薦手法の適用領域が拡大され，かつ，推薦する目的に対して最適な推薦が行えるようになった．人工データを用いた評価実験により，提案する推薦手法の有効性を確認した．

It has recently been shown that the model in experimental design can be expressed in terms of an orthonormal system. In this case, the model is expressed by using Fourier coefficients instead of the effect of each factor. As there is an abundance of software for calculating the Fourier transform, such a system allows for a straightforward implementation of the procedures for estimating the Fourier coefficients by using Fourier transform. However, Fourier coefficients themselves do not provide a direct representation of the effect of each factor, and the relation between the Fourier coefficients and the effect of each factor has not yet been clarified. In this paper, we present theorems of the relation between the Fourier coefficients and the effect of each factor. By using these theorems, the effect of each factor can be easily obtained from the computed Fourier coefficients. Therefore, with the aid of an orthonormal system, it is possible to easily implement the estimation procedures as well as to understand how each factor affects the response variable in the model.

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.

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.

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

Allocation methods for Cartesian product files on multiple disks using linear error-correcting codes are discussed. In this paper, we propose an allocation method using unequal error protection (UEP) codes. Codewords of an UEP code have some special bits which are protected against a greater number of errors than the other bits. We firstly assume a model that "*", which means "don't care", appears with different probability in each attribute of queries. In this case, the average access time can be calculated using the split distance distribution. Finally, we illustrate the average access time of the methods using UEP codes.

F.P.Preparata et al. have proposed a fault diagnosis model to find all faulty units in the multicomputer system by using outcomes which each unit tests some other units. In this paper, for probabilistic diagnosis models, we show an efficient diagnosis algorithm to obtain a posteriori probability that each of units is faulty given the test outcomes. Furthermore, we propose a method to analyze the diagnostic error probability of this algorithm.

Experiments usually aim to study how changes in various factors affect the response variable of interest. Since the response model used most often at present in experimental design is expressed through the effect of each factor, it is straightforward to ascertain how each factor affects the response variable. However, since the response model contains redundant parameters, we must calculate the degrees of freedom defined by the number of independent parameters in the analysis of variance. In this paper, we show that through a description of experimental design based on an orthonormal system, the response model can be expressed using only independent parameters. Hence, we do not have to calculate the degrees of freedom defined by the number of independent parameters.

We discuss disk allocation methods for Cartesian product files by introducing error correcting codes, and have clarified the performance of the methods by system evaluation models developed by using rate distortion theory. Let us assume q(n) Cartesian product files with n attributes and q actual values in each attribute, and store q(n) files into G(&lt;= q(n)) disks. For a partial match access request, we represent new disk allocation methods which able to access the disks in parallel as much as possible, where the partial match access request includes an indefinite case (don't care: "*") in some attributes and the * requires to access the files with corresponding to the attribute for the all actual attribute values. In this paper, we propose to apply unequal error protection codes to the case where the probabilities of occurrence of the * in the attributes for a partial match access request are not the same. We show the disk allocation methods have desirable properties as n becomes large.

In this chapter, we propose that the model of experimental design be expressed as an orthonormal system, and show that the model contains no redundant parameters. Then, the model is expressed by using Fourier coefficients instead of the effect of each factor. As there is an abundance of software for calculating the Fourier transform, such a system allows for a straightforward implementation of the procedures for estimating the Fourier coefficients by using Fourier transform. In addition, the effect of each factor can be easily obtained from the Fourier coefficients. Therefore, it is possible to implement easily the estimation procedures as well as to understand how each factor affects the response variable in a model based on an orthonormal system. Moreover, the analysis of variance can also be performed in a model based on an orthonormal system. Hence, it is clear that two main procedures in the experimental design, that is, the estimation of the effects and the analysis of variance can be executed in a description of experimental design on the basis of an orthonormal system.

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a nonlinear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm. Copyright © 2011 The Institute of Electronics, Information and Communication Engineers.

Document classification is one of important topics in the field of NLP (Natural Language Processing). In the previous research a document classification method has been proposed which minimizes an error rate with reference to a Bayes criterion. But when the number of documents in training data is small, the accuracy of the previous method is low. So in this research we use estimating data in order to estimate prior distributions. When the training data is small the accuracy using estimating data is higher than the accuracy of the previous method. But when the training data is big the accuracy using estimating data is lower than the accuracy of the previous method. So in this research we also propose another technique whose accuracy is higher than the accuracy of the previous method when the training data is small, and is almost the same as the accuracy of the previous method when the training data is big.

Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP) Since it is an NP hard problem in general there are many researches about the algorithms to approximately solve the problem One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al LP decoding is based on the LP relaxation which Is a method to approximately solve the ILP corresponding to the ML decoding problem Advanced algorithms for solving ILP (approximately or exactly) include cutting plane method and branch and bound method As applications of these methods adaptive LP decoding and branch and bound decoding have been proposed by Taghavi et al and Yang et al respectively Another method for solving ILP is the branch and cut method which is a hybrid of cutting plane and branch and bound methods The branch and cut method is widely used to solve ILP however it is unobvious that the method works well for the ML decoding problem In this paper we show that the branch and cut method is certainly effective for the ML decoding problem Furthermore the branch and cut method consists of some technical components and the performance of the algorithm depends on the selection of these components It is important to consider how to select the technical components in the branch and cut method We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations

We propose that the model in experimental design be ex pressed in terms of an orthonormal system Then we can easily estimate the effects using Fourier transforms We also provide the theorems with respect to the sum of squares needed in analysis of variance Using these theorems It is clear that we can execute the analysis of variance in this model

本研究では,メッセージブロックに誤りを生じるブロック誤り率が既知で,動作時間と受信バッファ容量が有限の選択再送ARQを研究対象とする.マルコフ決定過程を用いて定式化し,スループットの期待値を最大化する方法を導出し,その理論的限界を計算する.

In digital signal processing, the sampling theorem states that any real valued function f can be reconstructed from a sequence of values of f that are discretely sampled with a frequency at least twice as high as the maximum frequency of the spectrum of f. This theorem can also be applied to functions over finite domain. Then, the range of frequencies of f can be expressed in more detail by using a bounded set instead of the maximum frequency. A function whose range of frequencies is confined to a bounded set is referred to as bandlimited function. And a sampling theorem for bandlimited functions over Boolean domain has been obtained. Here, it is important to obtain a sampling theorem for bandlimited functions not only over Boolean domain (GF(2)(n) domain) but also over GF(q)(n) domain, where q is a prime power and GF(q) is Galois field of order q. For example, in experimental designs, although the model can be expressed as a linear combination of the Fourier basis functions and the levels of each factor can be represented by GF(q), the number of levels often take a value greater than two. However, the sampling theorem for bandlimited functions over GF(q)(n) domain has not been obtained. On the other hand, the sampling points are closely related to the codewords of a linear code. However, the relation between the parity check matrix of a linear code and any distinct error vectors has not been obtained, although it is necessary for understanding the meaning of the sampling theorem for bandlimited functions. En this paper, we generalize the sampling theorem for bandlimited functions over Boolean domain to a sampling theorem for bandlimited functions over GF(q)(n) domain. We also present a theorem for the relation between the parity check matrix of a linear code and any distinct error vectors. Lastly, we clarify the relation between the sampling theorem for functions over GF(q)(n) domain and linear codes.

本論文では,複数の鍵配送センターを設置したランプ型鍵事前配布方式(KPS:Key Predistribution System)を提案する.この方式は,n_P人のユーザとn_D個の鍵配送センターからなるネットワークにおいて,任意のm人以下のユーザとd個以下の鍵配送センターが結託しても,結託したユーザが属していないグループの秘密鍵に関する情報は全く得られず,結託ユーザ数がm+1人からm+c人の場合には,結託ユーザ数が大きくなるにつれて,その情報が段階的に得られる方式である.本論文では,このようなランプ型鍵事前配布方式モデルにおいて,各ユーザが秘密鍵を生成するために必要な記憶容量の下界の導出と,その下界を達成するプロトコルを提案する.

In this paper, we consider density evolution analyses of low-density parity-check (LDPC) codes for a finite-state Markov channel (FSMC). Since operations in the subgraph corresponding to the estimation process do not satisfy symmetry conditions, all densities involved in each value of the channel state should be kept track. In [6], to avoid the complexity to compute plural pdfs, only one pdf involved in the channel state is computed exploiting marginalization operations. We suppose that this approach is not accurate enough to track the estimation process of the joint estimation-decoding. In this paper, we present a procedure of the density evolution analysis of LDPC codes for an FSMC of which all densities involved in each value of the channel state are kept track. © 2010 Taylor &amp
Francis Group, LLC.

In coding theory, it is important to calculate an upper bound for the size of codes given the length and minimum distance. The Linear Programming (LP) bound is known as a good upper bound for the size of codes. On the other hand, Unequal Error Protection (UEP) codes have been studied in coding theory. In UEP codes, a codeword has special bits which are protected against a greater number of errors than other bits. In this paper, we propose a LP bound for UEP codes. Firstly, we generalize the distance distribution (or weight distribution) of codes. Under the generalization, we lead to the LP bound for UEP codes. And we show a numerical example of the LP bound for UEP codes. Lastly, we compare the proposed bound with a modified Hamming bound.

We consider the source coding problem with side information. Especially, we consider the FV code in the case that the encoder and the decoder can see side information. 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.

Lossless fixed-to-variable(FV) length codes are considered. The overflow probability is one of criteria that evaluate the performance of FV code. 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. Especially, 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.

In digital signal processing, the sampling theorem states that any real valued function f can be reconstructed from a sequence of values of f that are discretely sampled with a frequency at least twice as high as the maximum frequency of the spectrum of f . This theorem can also be applied to functions over finite domain. Then, the range of frequencies of f can be expressed in more detail by using a bounded set instead of the maximum frequency. A function whose range of frequencies is confined to a bounded set is referred to as bandlimited function. And a sampling theorem for bandlimited functions over Boolean domain has been obtained. Here, it is important to obtain a sampling theorem for bandlimited functions not only over Boolean domain (GF(2) n domain) but also over GF(q)n domain, where q is a prime power and GF(q) is Galois field of order q. For example, in experimental designs, although the model can be expressed as a linear combination of the Fourier basis functions and the levels of each factor can be represented by GF(q), the number of levels often take a value greater than two. However, the sampling theorem for bandlimited functions over GF(q)n domain has not been obtained. On the other hand, the sampling points are closely related to the codewords of a linear code. However, the relation between the parity check matrix of a linear code and any distinct error vectors has not been obtained, although it is necessary for understanding the meaning of the sampling theorem for bandlimited functions. In this paper, we generalize the sampling theorem for bandlimited functions over Boolean domain to a sampling theorem for bandlimited functions over GF(q)n domain. We also present a theorem for the relation between the parity check matrix of a linear code and any distinct error vectors. Lastly, we clarify the relation between the sampling theorem for functions over GF(q)n domain and linear codes. © 2010 The Institute of Electronics, Information and Communication Engineers.

In the field of experimental design, it is important to construct orthogonal designs. In this paper, we propose a new algorithm to construct orthogonal design. This algorithm uses Ukita’s algorithm, which is essentially based on projective geometries, and uses orthogonal designs constructed by error-correcting codes. We show some numerical examples of the proposed algorithm, and show that the proposed algorithm can construct good orthogonal designs with low complexity even if there are high order effects. © 2010 Taylor &amp
Francis Group, LLC.

The universal lossless source coding problem is one of the most important problem in communication systems. The aim of source coding is to compress data to reduce costs in digital communication. Traditional universal source coding schemes are usually designed for stationary sources. Recently, some universal codes for nonstationary sources have been proposed. Independent piecewise identically distributed (i.p.i.d.) sources are simple nonstationary sources that parameter changes discontinuously. In this paper, we assume new i.p.i.d. sources class, and we prove that Bayes codes minimize the mean redundancy when parameter transition pattern is known and parameter is unknown. © 2010 Taylor &amp
Francis Group, LLC.

The joint source-channel coding problem is considered. The joint source-channel coding theorem reveals the existence of a code for the pair of the source and the channel under the condition that the error probability is smaller than or equal to epsilon asymptotically. The separation theorem guarantees that we can achieve the optimal coding performance by using the two-stage coding. In the case that epsilon = 0, Han showed the joint source-channel coding theorem and the separation theorem for general sources and channels. Furthermore the epsilon-coding theorem (0 &lt;= epsilon &lt; 1) in the similar setting was studied. However, the separation theorem was not revealed since it is difficult in general. So we consider the separation theorem in this setting.

This paper describes an extension of XEX* mode, which is a method to convert a block cipher into a tagged tweakable block cipher, a notion introduced by Rogaway in 2004 as an extension of the tweakable block cipher by Liskov et al. Our extension attaches an additional encryption function to the original XEX*, which has some limitation but is slightly faster than the encryption implemented by XEX*. We prove our scheme's security in a general form, where the offset function, a key component of our construction, is not restricted to the one used by XEX*. We also provide some applications of our result, in particular to OCB 2.0, an authenticated encryption based on XEX*.

Document classification is one of important topics in the field of NLP(Natural Language Processing). In our previous research we've proposed a document classification method which minimizes an error rate with reference to a Bayes criterion. But when the number of documents in training data is small, the accuracy of the previous method is low. So in this research we propose a document classification method whose accuracy is higher than the previous method when the number of documents in training data is small. © 2009 SICE.

Code construction for digital fingerprinting, which is a copyright protection technique for multimedia, is considered. Digital fingerprinting should deter collusion attacks, where several fingerprinted copies of the same content are mixed to disturb their fingerprints. In this paper, we consider the averaging attack, which is known to be effective for multimedia fingerprinting with the spread spectrum technique. We propose new methods tor constructing fingerprinting codes to increase the coding rate of conventional fingerprinting codes, while they guarantee to identify the same number of colluders. Due to the new fingerprinting codes, the system can deal with a larger number of users to supply digital contents.

The context tree models are widely used in a lot of research fields. Patricia[7] like trees are applied to the context trees that are expanded according to the increase of the length of a source sequence in the previous researches of non-predictive source coding and model selection. The space complexity of the Patricia like context trees are O(t) where t is the length of a source sequence. On the other hand, the predictive Bayes source coding algorithm cannot use a Patricia like context tree, because it is difficult to hold and update the posterior probability parameters on a Patricia like tree. So the space complexity of the expanded trees in the predictive Bayes coding algorithm is O(t(2)). In this paper, we propose an efficient predictive Bayes coding algorithm using a new representation of the posterior probability parameters and the compact context tree holding the parameters whose space complexity is O(t).

The context tree models are widely used in a lot of research fields. Patricia[7] like trees are applied to the context trees that are expanded according to the increase of the length of a source sequence in the previous researches of non-predictive source coding and model selection. The space complexity of the Patricia like context trees are O(t) where t is the length of a source sequence. On the other hand, the predictive Bayes source coding algorithm cannot use a Patricia like context tree, because it is difficult to hold and update the posterior probability parameters on a Patricia like tree. So the space complexity of the expanded trees in the predictive Bayes coding algorithm is O(t(2)). In this paper, we propose an efficient predictive Bayes coding algorithm using a new representation of the posterior probability parameters and the compact context tree holding the parameters whose space complexity is O(t).

In this paper, we generalize the sampling theorem for bandlimited functions over the Boolean domain to a sampling theorem for bandlimited functions over a GF(q)(n) domain. We also present a theorem for the relation between the parity check matrix of a linear code and any distinct error vectors. Lastly, we clarify the relation between the sampling theorem for functions over a GF(q)(n) domain and linear codes.

In this paper. we analyze the robustness for low-density parity-check (LDPC) codes over the Gilbert-Elliott (GE) channel. For this purpose we propose a density evolution method for the case where LDPC decoder uses the mismatched parameters for the GE channel. Using this method, we derive the region of tuples of true parameters and mismatched decoding parameters for the GE channel. where the decoding error probability approaches asymptotically to zero.

A new ensemble of low-density parity-check (LDPC) codes for correcting a solid burst erasure is proposed. This ensemble is an instance of a combined matrix ensemble obtained by concatenating some LDPC matrices. We derive a new bound on the critical minimum span ratio of stopping sets for the proposed code ensemble by modifying the bound for ordinary code ensemble. By calculating this bound, we show that the critical minimum span ratio of stopping sets for the proposed code ensemble is better than that of the conventional one with keeping the same critical exponent of stopping ratio for both ensemble. Furthermore from experimental results, we show that the average minimum span of stopping sets for a solid burst erasure of the proposed codes is larger than that of the conventional ones.

This paper introduces two channel models of correlated parallel channels. Then we analyze structure of error correcting codes over these correlated parallel channels. We derive necessary and sufficient conditions for these codes and some code construction is presented. We also show some upper and lower bounds on the coding rate of the error correcting codes for correlated parallel channels. The introduced channel models are related to burst error channels and the codes analyzed in this paper can be used as asymmetric interleaving codes for burst error channels.

In this paper, we investigate the design of low-density parity-check (LDPC) codes for the Gilbert-Elliott (GE) channel. Recently, Eckford et al. proposed a design method of irregular LDPC codes using approximate density-evolution (DE) for Markov channels [7]. In the design method proposed by Eckford et al., the probability density function (PDF) of the messages from variable nodes to check nodes is approximated by the Gaussian distribution. In this paper, we first show the method to obtain the accurate PDF of the messages from variable nodes to check nodes by utilizing two DE steps for the Gaussian distribution. We call this method the iterative density approximation (IDA). Using this method, we can design the good LDPC codes. Next, we propose an efficient design method of irregular LDPC codes by using Beta approximation to the PDF of the channel state probability for the GE channel. Consequently, we show that the complexity to calculate PDFs of the channel messages is considerably reduced though the rates of LDPC codes obtained by using the proposed approximation are almost the same as that of the IDA method.

In this paper, we consider a, ramp scheme for Key Pre-distribution System (KPS). In the ramp scheme, it can be regarded ass one kind of generalization of KPS, and the required resources can be reduced at the cost of a security degradation which depends on the size of users. We define a ramp scheme for KPS, show lower bound on the amount of user's information needed to generate a common key, and design a protocol that realize a ramp scheme for KPS.

In this study, we consider a joint source-channel coding problem. The joint source-channel coding theorem reveals the existence of a code for the pair of the source V and the channel W under the condition that the probability of error is smaller than or equal to E asymptotically. We show the separation theorem for general sources and general channels.

統計解析を行う際，得られたデータの中に外れ値が含まれることが多々ある．外れ値は少量であっても解析結果に大きく影響を与えることがあるため，従来から外れ値を含むデータに対する統計解析手法が数多く研究されている．従来，Boxらにより線形回帰モデルに対し混合分布を用いて外れ値の発生をモデル化する研究が行われている．同様のモデルに対し様々な研究が行われているが，いずれも外れ値の検出やパラメータの推定を目的としている．そこで本研究では，外れ値データの発生を含む回帰モデルに対する予測法について扱う．まず，このモデルに対しベイズ基準のもとで最適な予測法を示す．しかし，この方法はデータ数に対し指数的に計算量が増大してしまう．そこで，EMアルゴリズムを用いて計算量を削減した近似アルゴリズムを提案し，シミュレーションにより有効性を検証する．Outliers are often included in statistical data. A statistical analysis result is influenced from outliers. Therefore, there are many researches for a statistical analysis of data with outliers. Box modeled outliers using mixture distribution. There are many researches that aim parameter estimation or outlier detection about this model. In this paper, we treat prediction problem about this model. First, we present an optimal prediction method with reference to the Bayes criterion in this model. The computational complexity of this method grows exponentially with data size. Next, we propose an approximation algorithm reducing the computational complexity using EM algorithm, and evaluate this algorithm through some simulations.

This paper presents MACs that combine a block cipher and its component such as a reduced-round version. Our MACs are faster than the standard MAC modes such as CBC-MAC, and provably secure if the block cipher is pseudorandom and its component is a permutation with a small differential probability. Such a MAC scheme was recently proposed by one of authors, and we provide improvements about security and treading-off between speed and amount of preprocessing.

Reliability-based hybrid ARQ (RB-HARQ) is a kind of incremental-redundancy ARQ recently introduced. In the RB-HARQ, the receiver returns both NAK signal and set of unreliable bit indices if the received sequence is not accepted. Since each unreliable bit index is determined by the bitwise posterior probability, better approximation of that probability becomes crucial as the number of retransmissions increases. Assuming the systematic code for the initial transmission, the proposed RB-HARQ scheme has the following two features: (a) the sender retransmits newly encoded and interleaved parity bits corresponding to the unreliable information bits; (b) the retransmitted parity bits as well as the initial received sequence are put all together to perform the message passing decoding i.e. the suboptimal MAP decoding. Finally, simulation results are shown to evaluate the above two features.

Digital fingerprinting , a copyright protection tech-nique of multimedia data , is considered. For digital finger-printing , measures against collusion attacks , where several fingerprinted copies of the same content are mixed to disturb their fingerprints , should be taken. In this paper , we propose a shortening method of collusion-secure fingerprinting codes based on finite geometries , which reduces the code length with keeping the number of codewords and the codes' resilience. We also propose a concatenated coding method which combines a conventional collusion-secure fingerprinting code and an error correcting code for increasing the coding rate , ue to the new fingerprinting codes , the system can deal with a larger number of users to distribute a digital content.

We provide new security proofs for PMAC, TMAC, and XCBC message authentication modes. The previous security bounds for these modes were σ2/2n, where n is the block size in bits and σ is the total number of queried message blocks. Our new bounds are lq 2/2n for PMAC and lq2/2n + l 4q2/22n for TMAC and XCBC, where q is the number of queries and l is the maximum message length in n-bit blocks. This improves the previous results under most practical cases, e.g., when no message is exceptionally long compared to other messages. © International Association for Cryptologic Research 2007.

Digital fingerprinting, a copyright protection technique for digital contents, is considered. Digital fingerprinting should deter collusion attacks, where several fingerprinted copies of the same content are mixed to disturb their fingerprints. In this paper, we consider the averaging attack, which has effect for multimedia fingerprinting. We propose new collusion-secure fingerprinting codes based on finite geometries (FGs) which increase the rate of conventional collusion-secure codes, while they guarantee to identify the same number of colluders. Due to the new FG-based fingerprinting codes, the system can deal with a larger number of users to distribute a digital content.

Word segmentation is the most fundamental and important process for Japanese or Chinese language processing. Because there is no separation between words in these languages, we firstly have to separate the sequence into words. On this problem, it is known that the approach by probabilistic language model is highly efficient, and this is shown practically. On the other hand, recently, a word-valued source has been proposed as a new class of source model for the source coding problem. This model can be supposed to reflect more of the probability structure of natural languages. We may regard Japanese sentence or Chinese sentence as the sequence emitting from a non-prefix-free WVS. In this paper as the first phase of applying WVS to natural language processing, we formulate a word segmentation problem for the sequence from non-prefix-free WVS. Then, we examine the performance of word segmentation for the models by numerical computations.

Morphological analysis is one of important topics in the field of NLP(Natural Language Processing). In many previous research a HMM(Hidden Markov Model) with unknown parameters has been used as a language model. In this research we also use the HMM as the language model. And we assume that sate transitions in the HMM are dominated by a second order Markov chain. At first we propose two types of morphological analysis methods which minimize the error rate with reference to a Bayes criterion. But the computational complexity of the proposed Bayes optimal morphological analysis methods are exponential order. So we also propose approximate methods.

We study a tweakable blockcipher for arbitrarily long message (also called a tweakable enciphering scheme) that consists of a universal hash function and an expansion, a keyed function with short input and long output. Such schemes, called HCTR and HCH, have been recently proposed. They used (a variant of) the counter mode of a blockcipher for the expansion. We provide a security proof of a structure that underlies HCTR and HCH. We prove that the expansion can be instantiated with any function secure against Known-plaintext attacks (KPAs), which is called a weak pseudorandom function (WPRF). As an application of our proof, we provide efficient blockcipher-based schemes comparable to HCH and HCTR. For the double-block-length case, our result is an interesting extension of previous attempts to build a double-block-length cryptographic permutation using WPRF.

The CTW(Context Tree Weighting) algorithm is an efficient universal coding algorithm on context tree models. The CTW algorithm has been interpreted as the non-predictive Bayes coding algorithm assuming a special prior distribution over context tree models. An efficient recursive calculation method using a gathering context tree in the CTW algorithm is well known. Although there exist efficient recursive algorithms for the Bayes codes assuming a special class of prior distributions, the basic property of the prior distribution class has been scarcely investigated. In this paper we show the exact definition of a prior distribution class on context tree models that has the similar property to the class of conjugate priors. We show the posterior distribution is also included in the same distribution class as the prior distribution class. So we can also construct an efficient algorithm of predictive Bayes codes on context tree models by using the prior distribution class. Lastly the asymptotic mean code length of the codes is investigated.

In this paper, transmission schemes with noiseless and high capacity feedback channel is considered. We propose two types of transmission schemes using LDPC codes and clarify the density evolution analysis method for these proposed schemes. We investigate the performance of the proposed schemes by the density evolution analysis and computer simulations. The result shows some interesting characteristics for schemes with high capacity feedback channel.

In this paper, transmission schemes with noiseless and high capacity feedback channel is considered. We propose two types of transmission schemes using LDPC codes and clarify the density evolution analysis method for these proposed schemes. We investigate the performance of the proposed schemes by the density evolution analysis and computer simulations. The result shows some interesting characteristics for schemes with high capacity feedback channel.

In this paper, we present an iterative algorithm for computing the secrecy capacity of broadcast channel with confidential message (BCC) in the situation that the main channel is less noisy than the eavesdropper's channel. The global convergence of the algorithm is proved, and an expression for its convergence rate is derived.

In this paper, we generalize the achievability of variable-length coding from two viewpoints. One is the definition of an overflow probability, and the other is the definition of an achievability. We define the overflow probability as the probability of codeword length, not per symbol, is larger than eta(n) and we introduce the epsilon-achievability of variable-length codes that implies an existence of a code for the source under the condition that the overflow probability is smaller than or equal to epsilon.
Then we show that the epsilon-achievabitity of variable-length codes is essentially equivalent to the epsilon-achievability of fixed-length codes for general sources. Moreover we show the condition of epsilon-achievability for some restricted sources given epsilon.

In this letter, we generalize the achievability of variable-length coding from two viewpoints. One is the definition of an overflow probability, and the other is the definition of an achievability. We define the overflow probability as the probability of codeword length, not per symbol, is larger than ηn and we introduce the e-achievability of variable-length codes that implies an existence of a code for the source under the condition that the overflow probability is smaller than or equal to ∈. Then we show that the e-achievability of variable-length codes is essentially equivalent to the e-achievability of fixed-length codes for general sources. Moreover by using above results, we show the condition of e-achievability for some restricted sources given ∈. Copyright © 2007 The Institute of Electronics, Information and Communication Engineers.

Recently, a word-valued source has been proposed as a new class of information source models. A word-valued source is regarded as a source with a probability distribution over a word set. Although a word-valued source is a nonstationary source in general, it has been proved that an entropy rate of the source exists and the Asymptotic Equipartition Property (AEP) holds when the word set of the source is prefix-free. However, when the word set is not prefix-free (non-prefix-free), only an upper bound on the entropy density rate for an i.i.d. word-valued source has been derived so far. In this paper, we newly derive a lower bound on the entropy density rate for an i.i.d. word-valued source with a finite non-prefix-free word set. Then some numerical examples are given in order to investigate the behavior of the bounds.

We propose a new fixed-rate error correction system with a feedback channel. In our system, the receiver transmits a list of positions of unreliable information bits based on the log a-posteriori probability ratios by outputs of a soft-output decoder to the transmitter. This method is just like that of the reliability-based hybrid ARQ scheme. To dynamically select an appropriate interleaving function with feedback information is a key feature of our system. By computer simulations, we show that the performance of a system with a feedback channel is improved by dynamically selecting an appropriate interleaving function.

Reliability Based Hybrid ARQ (RB-HARQ) is an ARQ scheme using the modified feedback. In the RB-HARQ, the receiver returns both NAK signal and unreliable bit indices if the received sequence is not acknowledged. Since the unreliable bit index is determined by the bitwise posterior probability, better approximation of that probability is crucial. Assuming the systematic codes, the proposed RB-HARQ scheme has two features for this approximation: (1) The sender retransmits newly encoded parity bits corresponding to the unreliable information bits; (2) The retransmitted parity bits as well as the initial received sequence are put all together to perform the message passing decoding.

Orthogonal Arrays (OAs) have been playing important roles in the field of experimental design. It has been known that OAs are closely related to error-correcting codes. Therefore, many OAs can be constructed from error-correcting codes. But these OAs are suitable for only cases that equal interaction effects can be assumed, for example, all two-factor interaction effects. Since these cases are rare in experimental design, we cannot say that OAs from error-correcting codes are practical. In this paper. we define OAs with unequal strength. In terms of our terminology. OAs from error-correcting codes are OAs with equal strength. We show that OAs with unequal strength are closer to practical OAs than OAs with equal strength. And we clarify the relation between OAs with unequal strength and unequal error-correcting codes. Finally, we propose some construction methods of OAs with unequal strength from unequal error-correcting codes.

We propose transformation of a parity-check matrix of any low-density parity-check code. A code with transformed parity-check matrix is an equivalent of a code with the original parity-check matrix. For the binary erasure channel, performance of a message-passing algorithm with a transformed parity-check matrix is better than that with the original matrix.

If we can use a high capacity feedback channel, the receiver may transmit the indices of unreliable bits in a received sequence instead of ACK/NAK signals. We consider the error correction schemes using the indices of unreliable bits. The suitable parity symbols are incrementally transmitted using the feedback information. The bitwise reliability can be calculated by message passing algorithms on the variable graph constructed by adding the new nodes and arcs corresponding to the received parity bits to a former graph at each stage.

1993年,C. Berrouらは加法的白色ガウス雑音(AWGN)通信路に村し1情報記号当りの信号対雑音比(E_b/N_o)に対するシャノン限界に近いビット誤り確率(BER)を達成するターボ符号を提案した.その後S. Benedettoら及びJ. Hagenauerらにより,構成符号にブロック符号を用いるブロックターボ符号が提案されている.本論文ではS. Benedettoらにより提案されたPCBC (Parallel Concatenated Block Codes)型ブロックターボ符号を一次元の符号とみなしたときの性能の解析を行い,大きな最小距離をもつインタリーバの構成法を提案する.まずとり得るインタリーバに制約を加えることにより,各情報記号のハミング重み(情報量み)に村応する符号語のハミング重み(符号語重み)の下界を導出する.更に情報量みが1及び2のときの符号語重みに対する下界を大きくするインタリーバの構成手法を示し,最小距離を大きくすることが可能な要素符号を探索により求めるアルゴリズムを提案する.結果的に得られる要素符号及びインタリーバを用いることにより,従来より大きな最小距離を保証するブロックターボ符号を設計することが可能となる.

The reliability-based heuristic search methods for maximum likelihood decoding (MLD) generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Test error patterns are stored in lists and its space complexity is crucially large for MLD of long block codes. Based on the decoding algorithms both of Battail and Fang and of its generalized version suggested by Valembois and Fossorier, we propose a new method for reducing the space complexity of the heuristic search methods for MLD including the well-known decoding algorithm of Han et al. If the heuristic function satisfies a certain condition, the proposed method guarantees to reduce the space complexity of both the Battail-Fang and Han et al. decoding algorithms. Simulation results show the high efficiency of the proposed method.

Reliability Based Hybrid ARQ (RBH-ARQ)は, Hybrid ARQ手法の一種であり, 復号器はACK/NAK信号だけで無く, 最大事後確率復号法の出力から決定される信頼度の低いビットのインデックスをフィードバック情報として用いる.送信器はフィードバック情報を元に符号化を行い, その符号語を再送する.本研究では, 再帰的組織畳み込み符号に対しRBH-ARQを用いた新たな誤り訂正手法をいくつか提案する.これらはそれぞれ, 復号器において再送された受信値の用い方に明確な差異のあるものとなっている.これらの性能の比較を行うことで, RBH-ARQ手法における再送された受信値の用い方や符号器の構成法等について検討を行う.

マトリックスクラスタリングとは与えられた疎行列に対し，指定された面積以上で，指定された密度（部分行列における1の要素の比率）以上の密な部分行列を抽出することと定義される．この手法はCRM向けのデータマイニング手法として提案されたものであり，より関連の深い商品と顧客をクラスタリングすることを可能としている．本稿ではアプリオリアルゴリズムを拡張し，ある特定の条件を満たす部分行列全てを抽出するマトリックスクラスタリングアルゴリズムを提案する．これにより，顧客の購買情報をきめ細かく分析することが可能となる．

The problem of universal codes with side information is investigated from Bayes criterion. We propose side information context tree models which are an extension of context tree models to sources with side information. Assuming a special class of the prior distributions for side information context tree models, we propose an efficient algorithm of Bayes code for the models. The asymptotic code length of the Bayes codes with side information is also investigated.

The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it.

Yamamoto, Itohの判定帰還(ARQ)方式[1]で用いられていた判定基準LR[3]は, 判定基準の計算に必要な労力が少ないことから, ビタビアルゴリズム(VA)との整合性に優れていることが知られている. また, Forneyは, ブロック符号に対して, 最ゆう復号を可変サイズのリスト復号(VLD)に拡張した符号化定理を導いている. 本論文では, 畳込み符号をVAで復号する場合に, LRを用いた可変サイズのリスト復号(VLD)へ拡張するアルゴリズムを提案し, その誤り指数の下界を離散的無記憶通信路を仮定して導出する.

The probabilistic reasoning given distribution evidence, virtual evidence, indirect evidence or likelihood have been investigated in previous research.In this paper, we classify the reasoning into two types and define each type of the reasoning by mathematical formulas. We clarify the difference between two types by the definition. From the definition, we show that the first type of reasoning is solved by the minimization of Kullback-Leibler(K-L) information under marginal constraints and the second type is calculated by the ordinary probabilistic reasoning methods such as Belief Propagation(BP). We also show that the Iterative Scaling Procedure(ISP) is applied to the first type reasoning. Moreover, we propose an efficient propagation algorithm, which are based on ISP, for the reasoning on Junction trees. Both the space and the time complexities of the proposed algorithm are lower than that of the previous research

一般化ビタビアルゴリズム（GVA）は，木符号に対する簡略的復号アルゴリズムであり，固定されたリストサイズ（fixed sizelist decoder）のリスト復号器を用いる．そして，その復号拘束長を大きくしたときの漸近的な有効性を示す符号化定理が与えられている．本論文では，固定されたリストサイズではなく，リストサイズが確率変数であるリスト復号器（variable size list decoder）を適用したときの新しい簡略的復号法を提案し，その性質を考察する．

Nishiara and Morita defined an i.i.d. word-valued source which is defined as a pair of an i.i.d. source with a countable alphabet and a function which transforms each symbol into a word over finite alphabet. They showed the asymptotic equipartition property (AEP) of the i.i.d. word-valued source and discussed the relation with source coding algorithm based on a string parsing approach. However, their model is restricted in the i.i.d. case and any universal code for a class of word-valued sources isn't discussed. In this paper, we generalize the i.i.d. word-valued source to the ergodic word-valued source which is defined by an ergodic source with a countable alphabet and a function from each symbol to a word. We show existence of entropy rate of the ergodic word-valued source and its formula. Moreover, we show the recurrence time theorem for the ergodic word-valued source with a finite alphabet. This result clarifies that Ziv-Lempel code (ZL77 code) is universal for the ergodic word-valued source.

In this paper, we discuss the difference in code lengths between the code based on the minimum description length (MDL) principle (the MDL code) and the Bayes code under the condition that the same prior distribution is assumed for both codes. It is proved that the code length of the Bayes code is smaller than that of the MDL code by o(1) or O(1) for the discrete model class and by O(1) for the parametric model class. Because we can assume the same prior for the Bayes code as for the code based on the MDL principle, it is possible to construct the Bayes code with equal or smaller code length than the code based on the MDL principle. From the viewpoint of mean code length per symbol unit (compression rate), the Bayes code is asymptotically indistinguishable from the MDL two-stage codes.

Ill many practical transmission systems, transmission error rate of the channel is time-varying. In previous works for controlling the rime-varying channel, the state of the channel is estimated and is uniquely determined. Then, the optimum value is chosen as a control parameter for the determined state. However, there is a discrepancy between the actual channel state and estimated state. The optimum control parameter determined for the estimated state does not necessarily provide the best performance presented by some object function in error control such as throughput efficiency. In th is study, the expected value of throughput is calculated by using the posterior probability for each state and an algorithm in which the control parameter is selected to maximize the expected performance is proposed. From the viewpoint of the statistical decision theory, it is shown that this selection is the optimum in maximizing the throughput under the Bayes criterion. Using simulation, the proposed method is evaluated and its effectiveness is shown. (C) 2001 Scripta Technica

In this paper, the generalized proof are shown for the coding theorem of [1]. Consequently, the further discussion is obtained.

In this paper, we show maximal rates in the case that random number generators generate a random sequence with an arbitrary prescribed distribution from a random sequence with an arbitrary given distribution.

In this paper, we show the probability of length overflow of several codes by using the variance and the asymptotic normality of the codelength.

We analyse the extended stochastic complexity (ESC) which has been proposed by K. Yamanishi. The ESC can be applied to learning algorithms for on-line prediction and batch-learning settings. Yamanishi derived the upper bound of ESC satisfying uniformly for all data sequences and that of the asymptotic expectation of ESC. However, Yamanishi concentrates mainly on the worst case performance and the lower bound has not been derived. In this paper, we show some interesting properties of ESC which are similar to Bayesian statistics: the Bayes rule and the asymptotic normality. We then derive the asymptotic formula of ESC in the meaning of almost sure and mean convergence within an error of o(1) using these properties.

For the two-dimensional BCH code, several decoding methods exceeding the BCH bound and correcting the errors that cannot be corrected by the conventional limited distance decoding method have been proposed. This article proposes an algorithm that allows reduction of the computational volume in a decoding method exceeding the BCH bound by solving the equation for unknown variables beforehand and limiting the range of the error location. Further, this decoding method exceeding the BCH bound is applied to soft-decision decoding methods that use limited-distance decoding multiple times, and especially to Chase decoding, the decoding of Tanaka et al., and that of Kaneko et al. It is shown that the amount of computation and the decoding error rate are improved.

We shall generalize B.S. Clarke and A.R. Barron's analysis of the Bayes method for the FSMX sources. The FSMX source considered here is specified by the set of all states and its parameter value. At first, we show the asymptotic codelengths of individual sequences of the Bayes codes for the FSMX sources. Secondly, we show the asymptotic expected codelengths. The Bayesian posterior density and the maximum likelihood estimator satisfy asymptotic normality for the finite ergodic Markov source, and this is the key of our analysis.

We shall generalize B.S. Clarke and A.R. Barron's analysis of the Bayes method for the FSMX sources. The FSMX source considered here is specified by the set of all states and its parameter value. At first, we show the asymptotic codelengths of individual sequences of the Bayes codes for the FSMX sources. Secondly, we show the asymptotic expected codelengths. The Bayesian posterior density and the maximum likelihood estimator satisfy asymptotic normality for the finite ergodic Markov source, and this is the key of our analysis.

This paper presents a new architecture for multiple-input signature analyzers. The proposed signature analyzer with H delta inputs is designed by parallelizing a GLFSR(delta, m), where delta is the number of input signals and m is the number of stages in the feedback shift register. The GLFSR, developed by Pradhan and Gupta, is a general framework for representing LFSR-based signature analyzers. The parallelization technique described in this paper can be applied to any kind of GLFSR signature analyzer, e.g., SISRs, MISRs, multiple MISRs and MLFSRs. It is shown that a proposed signature analyzer with H delta inputs requires less complex hardware than either single GLFSR(H delta, m)s or a parallel construction of the H original GLFSR(delta, m)s. It is also shown that the proposed signature analyzer, while requiring simpler hardware, has comparable aliasing probability with analyzers using conventional GLFSRs for some CUT error models of the same test response length and test lime. The proposed technique would be practical for testing CUTs with a large number of output sequences, since the test circuit occupies a smaller area on the LSI chip than the conventional multiple-input signature analyzers of comparable aliasing probability.

In this paper, we shall derive the upper bounds on error rates of the statistical model selection using the information criteria, P(e)*. The similar bounds were derived by J.Suzuki [2]. We shall generalize the results for the general model class.

In this paper, we shall derive the upper bounds on error rates of the statistical model selection using the information criteria, P(e)*. The similar bounds were derived by J.Suzuki [2]. We shall generalize the results for the general model class.

本研究では，遷移確率行列が未知であるようなマルコフ決定過程によってモデル化されている，学習期間と制御期間に分割された強化学習問題における，最適アルゴリズムの提案を行っている．従来研究では，真の遷移確率行列を同定できれば制御期間の収益を最大化できるため，学習期間の目的を単に未知の遷移確率行列の推定としているが，有限の学習期間のもとでは推定誤差があるため，収益最大化の厳密な保証はない．そこで本研究では，有限の学習期間と有限の制御期間の強化学習問題において，制御期間の収益をベイズ基準のもとで最大化する基本最適アルゴリズムを提案する．しかし，基本最適アルゴリズムの計算量が指数オーダーのため，さらにその改良を行い，改良最適アルゴリズムを提案する．改良最適アルゴリズムは基本最適アルゴリズム同様に収益をベイズ基準のもとで最大化することができ，かつその計算量は多項式オーダーに軽減されている．In this paper,new algorithms are proposed based on statistical decision theory in the field of Markov decision processes under the condition that a transition probability matrix is unknown.In previous researches on RL(reinforcement learning),learning is based on only the estimation of an unknown transition probability matrix and the maximum reward is not received in a finite period,though their purpose is to maximize a reward.In our algorithms it is possible to maximize the reward within a finite period with respect to Bayes criterion.Moreover, we propose some techniques to reduce the computational complexity of our algorithm from exponential order to polynomial order

本研究では，遷移確率行列が未知であるようなマルコフ決定過程によってモデル化されている，学習期間と制御期間に分割された強化学習問題における，最適アルゴリズムの提案を行っている．従来研究では，真の遷移確率行列を同定できれば制御期間の収益を最大化できるため，学習期間の目的を単に未知の遷移確率行列の推定としているが，有限の学習期間のもとでは推定誤差があるため，収益最大化の厳密な保証はない．そこで本研究では，有限の学習期間と有限の制御期間の強化学習問題において，制御期間の収益をベイズ基準のもとで最大化する基本最適アルゴリズムを提案する．しかし，基本最適アルゴリズムの計算量が指数オーダーのため，さらにその改良を行い，改良最適アルゴリズムを提案する．改良最適アルゴリズムは基本最適アルゴリズム同様に収益をベイズ基準のもとで最大化することができ，かつその計算量は多項式オーダーに軽減されている．In this paper,new algorithms are proposed based on statistical decision theory in the field of Markov decision processes under the condition that a transition probability matrix is unknown.In previous researches on RL(reinforcement learning),learning is based on only the estimation of an unknown transition probability matrix and the maximum reward is not received in a finite period,though their purpose is to maximize a reward.In our algorithms it is possible to maximize the reward within a finite period with respect to Bayes criterion.Moreover, we propose some techniques to reduce the computational complexity of our algorithm from exponential order to polynomial order

2元BCH符号に対し, 通常の限界距離復号法では訂正不可能な誤りを訂正する復号法としてBCH限界を超える復号法が種々提案されている.本論文ではBCH限界を超える復号法において, あらかじめ未知となる変数の方程式を解き誤り位置の範囲を限定することにより, 計算量を低減することが可能なアルゴリズムを提案する.更にこのBCH限界を超える復号法を限界距離復号を複数回用いる軟判定復号法, 特にChase復号法, Tanakaらの復号法, Kanekoらの復号法に応用する.その結果, 計算量および復号誤り確率が改善されることを示す.

This paper presents a new architecture for multiple-input signature analyzers. The proposed signature analyzer with Hδ inputs is designed by parallelizing a GLFSR(δ, m), where δ is the number of input signals and m is the number of stages in the feedback shift register. The GLFSR, developed by Pradhan and Gupta, is a general framework for representing LFSR-based signature analyzers. The parallelization technique described in this paper can be applied to any kind of GLFSR signature analyzer, e.g., SISRs, MISRs, multiple MISRs and MLFSRs. It is shown that a proposed signature analyzer with Hδ inputs requires less complex hardware than either single GLFSR(Hδ, m)s or parallel construction H original GLFSR(δ, m)s. It is also shown that the proposed parallelization technique can be applied to a test pattern generator in BIST, since the GLFSR is also used to generate patterns for a CUT. The proposed technique would be practical for testing CUTs with a large number of input and output sequences, since the test circuit occupies a smaller area on the LSI chip than conventional test circuits.

Bayesian theory is effective in statistics, lossless, source coding, machine learning, etc. It is often, however, computationally expensive since the calculation of posterior probabilities and of mixture distributions is not tractable. In this paper, we propose a new method for approximately calculating mixture distributions in a discrete hypothesis class.

Bayesian theory is effective in statistics, lossless source coding, machine learning, etc. It is often, however, computationally expensive since the calculation of posterior probabilities and of mixture distributions is not tractable. In this paper, we propose a new method for approximately calculating mixture distributions in a discrete hypothesis class.

In this paper, we consider the problem to predict the class of an unknown sample after learning from queries, We propose to evaluate a learning algorithm by a loss function for the prediction under a constraint, In this paper, the error probability for the prediction and the number of queries is defined as the loss function and the constraint, respectively, Then our objective is to minimize the error probability, the error probability is determined by what presentation order for instances to query and how to predict, Since the optimal prediction has been shown in previous researches, we only have to select the optimal presentation order for instances to query, We propose a lower bound used in the branch-and-bound algorithm to select the optimal presentation order for instances, Lastly, we show the efficiency of the algorithm using the derived lower bound by numerical computation.

In this paper, we obtain an accurate asymptotic formula of the Bayes optimal codelength in the case that the sources are not always i.i.d. sources by deriving the asymptotic codelength of sufficient statistic codes. © 1997 IEEE.

計算論的学習理論のパラダイムの1つであるOn-line 学習モデルでは, 重みを用いた学習アルゴリズムについて多くの研究がなされてきた。WINNOWはその代表的なアルゴリズムの1つであり, プール関数のクラスにおいてリテラルや節などに対応する重みを用いて学習を行なう。一方Wighted Majority Algorithm (WMA)は重みを個々の概念に対応させて学習するアルゴリズムである。これらのアルゴリズムの長所として, 概念クラスから任意の1つの仮説を選択して予測するアルゴリズムよりも優れた性能を持っことが, ヒューリスティックな方法で示されている。この性質はベイズ統計学の枠組を用いることにより, 厳密に証明することができる。D.Hausslerらは計算論的学習理論の立場からベイズ的学習モデルを研究し, ベイズアルゴリズムのsample complexityについての解析を行なっている。また情報理論の考え方を取り入れた解析結果も明らかにしている。このベイズアルゴリズムはベイズ統計学に立脚した最適性を保証するという優れた性能を持っているが, 問題の領域が大きくなると事後確率の更新や平均損失を最小にする決定を探索する計算量が膨大になるという問題点もある。計算量の問題は, もう1つの学習パラダイムであるProbably Approximately Correct (PAC)学習モデルでは, 多くのクラスについての学習可能性が明らかにされているが, On-line学習モデルの予測可能性についての議論は不十分である。またPAC学習モデルにおいても, 従来の学習可能性の議論のみではネガティブな結果しか得られず, 現実問題との乖離が大きい。本稿はこれらの点を考慮し, ベイズアルゴリズムを考える場合にsample complexityだけでなくtime complexityも考えた学習モデルの枠組を提案する。このモデルではベイズ統計学と計算量理論の両方の視点からモデル化を行ない, PAC学習モデルだけでなくOn-line学習モデルについても同様に扱うモデルであることを明らかにする。さらにベイズ予測可能性という新しい概念を提案し, 典型的な概念クラスについて予測可能性を明らかにし, その性質についても述べる。なお, 本文ではブール関数を対象とするが, q元, q>2, の事例空間, 概念表現空間のクラスへの拡張は可能である。

キーワードを用いた文献検索では個々の文献をキーワードの集合によって特性づける。簡単なモデルではフォーマット化を行い個々の文献jに長さNの二次情報ベクトルx^^→_jを対応させる。個々のビット位置はキーワードの有無に対応じ, 1のあるビット位置のキーワードは文献に含まれるが, 0のビット位置のキーワードは文献に含まれないことを意味する。質問(query)x^^→としていくつかのキーワードを与えて, これらのキーワードをすべて含む文献の二次情報レコードx^^→_jを求める。これをx^^→⊆x^^→_jにより表す。次にこの二次情報レコードに対応する一次情報を二次記憶内から探し出すのが通常の文献検索である。上の簡単なモデルでは, 二次情報の大きさは文献数n_0と二次情報レコードの長さNの積になるがこれが主記憶(RAM)容量よりもかなり大きい場合には二次情報を縮小してRAMに格納せねばならない。これはRAMに格納する1レコードあたりの情報がキーワードの総数Nよりも小さいことを意味する。この場合にx^^→⊆x^^→_jを満足するx^^→_jをすべて求めようとすると, 必然的に不必要なx^^→ (x^^→⊆x^^→_jを満たさない)の一部分も含まれてしまう。この結果, 必要な文献の一次情報ばかりでなく不必要な文献の一次情報も二次記憶装置からRAMにロードすることになる。これは二次記憶装置へのアクセス回数が増大することを意味している。したがって, 不必要なx^^→の総数(extratransmission, 余剰伝送数と呼ぶ)をできるだけ低減することが重要である。余剰転送数を低減するためにRAMの情報を利用する考えは参考文献[1]で報告されている。参考文献[2]ではベクトルx^^→とのハミング距離がしきい値T以内にあるレコードx^^→_jを求めることを目的とする場合に, 余剰転送数の上界の評価が情報理論の視点から行われた。

近年、知識工学の分野において、さまざまなエキスパートシステムが活発に開発されている。数多くのエキスパートシステムの中に、不確実な知識を確信度という概念を用いて記述したものが存在する・しかし、従来の確信度を用いた推論方武では推論結果の信頼性について言及されていない。このため、その確信度を用いたエキスパートシステムによって推論された結果下される判断は、どの程度妥当なのか、どのくらいの信頼性があるのかということについては、明確にされていない。そこで本研究は・システムの信頼性を保特しながら・確信度を持つ推論を行う方法について考察を行っている。すなわち、確率世界論理における確信度の推定に統計学の区間推定の理論を用い、確信度の上限と下限を明示する推論方式を提案する。その結果、導出された推論結果の信頼性を確率1一α（αは適当に小さい定数）で保証することができる。また、この幅を特つ確信痩を用いて帰納・演繹の推論がー連の推論として考察可能となる。本研究は、エキスパートシステムなどの推論緒果の信頼性を保証するという見地から有効な手段である。

We show that the received sequences, which are rejected and not discarded on ARQ schemes, make the next decision with repeat request powerful by a random coding arguments. We first give the ordinary ARQ of the basic algorithm with some criterion, and define the ARQ with cumulating the rejected sequences, which naturally extended from the ordinary one. Then we study the error exponent of decoding the second received sequences under the condition that the first is rejected. We assume the block coded ARQ with noiseless feedback. © 1994 IEEE.

The context tree weighting (CTW) algorithm [Willems et al., 1993] has high compressibility for universal coding with respect to FSMX sources. The present authors propose an algorithm by reinterpreting the CTW algorithm from the viewpoint of Bayes coding. This algorithm can be applied to a wide class of prior distribution for finite alphabet FSMX sources. The algorithm is regarded as both a generalized version of the CTW procedure and a practical algorithm using a context tree of the adaptive Bayes coding which has been studied in Mataushima et al. (1991). Moreover, the proposed algorithm is free from underflow which frequently occurs in the CTW procedure. © 1994 IEEE.

Considering inductive inference and deductive inference as not individual processes but a serial process of information processing, the serial inference procedure is studied from two purposes: one is the compression of observed facts, and the other is the prediction of new wffs. A new scheme of the serial inference process is proposed by using the correspondence to source coding and prediction problem. The optimal inference procedures for the two purposes are shown in the proposed scheme.

The problem of distortionless encoding when the parameters of the probabilistic model of a source are unknown is considered from a statistical decision theory point of view. A class of predictive and nonpredictive codes is proposed that are optimal within this framework. Specifically, it is shown that the codeword length of the proposed predictive code coincides with that of the proposed nonpredictive code for any source sequence. A bound for the redundancy for universal coding is given in terms of the supremum of the Bayes risk. If this supremum exists, then there exists a minimax code whose mean code length approaches it in the proposed class of codes, and the minimax code is given by the Bayes solution relative to the prior distribution of the source parameters that maximizes the Bayes risk.

In designing systems with a human‐computer interface with a minimum number of interactions, there are two issues to consider: the determination of a proper sequence of questions by the user, and proper termination by the computer system, based on previous instructions. In short, these issues are those of feature selection ordering and a stopping rule for pattern recognition processes. Conventional treatments of these problems have been investigated from the viewpoint of an average error rate. When the number of patterns is large, however, and the number of instructions to be terminated is large, from the point of view of user interface efficiency, and the average error rate is not an effective indicator at the intermediate stage. In this paper, a new method is proposed for determining feature selection ordering and a stopping rule which focuses on the remaining patterns at each stage, and which maximizes the value of mutual information between the user's responses and the required pattern. Important properties associated with this scheme have been demonstrated while evaluating its performance via computer simulation. One is that the average information gain at each stage decreases monotonically, and another is that this scheme produces the minimum error rate. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company

質問応答回数最小をねらいとするインタフェース設計の問題は，過去のユーザの応答履歴から次にどの質問を与えて，いつまで質問を続けるかの基準を設定する．パターン認識における特徴選択順序と打切り規則の問題として帰着できる．従来のこの問題への対処は，いずれも平均誤り率を基準に検討されてきた．しかしながら，ここで扱うインタフェースの効率化の問題では，想定するパターン数が多く，アクセプトまでのステージ数が大きいため，途中段階での平均誤り率が指標としての意味をもたなくなる．そこで本論文ではこのために，相互情報量最大を基準にすることによってステージごとに残留するパターンを最小に絞り込む，新しいクラスの質問選択と打切りについて提案している．その結果，シミュレーションによって有効性を評価するだけでなく，各ステージで得られる平均の情報量が単調に減少する点，大局的に平均誤り率の最小化を図っている点などの，従来手法にはない重要な性質が導かれている．

判定帰還方式(ARQ方式)の研究の中で,ランダム符号化によって符号化定理を導き,あるクラスの符号に対して誤り指数の下界を求める研究がある.最近,Hashimotoは,判定基準LR+Thを用いた判定帰還方式がForneyのブロック符号の帰還誤り指数(feedback exponent)を達成することを示した.本論文では,ブロック符号を用いたLR+Thを用いた判定帰還方式の誤り指数導出において,文献において行われた解析の手法を一部適用する.その結果,Forneyのブロック符号の帰還誤り指数の下界よりも,更に大きな値の帰還誤り指数の下界が導出できる通信路の例があることを明らかにする.

Most information retrieval systems are denoted as a set of Horn clauses representing the average user's concept in order to gain solutions which satisfy some predicates about conditions demanded by the user. In this paper, the system prepares the default rules considering general user's requirements in advance. Each user inputs rules representing individual demands sequentially. Both of the rules are matched with each other, and the solution which has the highest value of the certainty factor is derived. The strategy on how we can gain the solution with the minimum number of the questions and answers is investigated based on the certainty factor computed by the minimax rule. The game theoretical framework is established and the optimal question strategy is shown in a minimax criterion. Our scheme has a large merit of applying not only to individual systems but also to general information retrieval systems.