本研究の目的は，言語学習を統一的な枠組みで捉え，相手（学習者）を感じて助言を行う人工教師を搭載した自学自習システムを開発し，その評価を行うことである．「相手を感じる」とは，学習者の学習状況をシステム側が把握することを指す．本研究では，自学自習システムの開発に必要な学習者のつまずきを検出するための方法や学習状態を推定する方法とシステムの開発を行った．またそれらを用いて英語およびプログラミング言語の学習の実証実験を行った．さらに，英語教育とプログラミング言語教育の関連性や教育方法の援用についての調査・検討を行った．さらに，本研究成果の普及に向けての脳波以外の計測器での代用可能性の研究を行った．

本研究ではプログラミング初学者を対象として，実際の授業用のWEBを用いたe-learningプログラミング教育システムを構築し，さらにそこから得られたビッグデータに対してラーニングアナリティクスを用いて分析を行なう手法を検討した．具体的にはまず学習者のプログラミングの各種ログを取得し，機械学習手法を用いたプログラムの自動採点により，教員の労度を大幅に削減しつつ精度の高い採点を行うことが可能であることを明らかにした．さらに課題の採点結果を用いて，同じ採点結果の傾向を示す学習者及び課題を自動的に抽出する手法の提案並びに評価を行い，提案したモデル並びに分析法の有効性を示した．

多様なコンテキストを収集できるeラーニングシステムを構築し，これを授業で用いた実証実験から，学習者のどのような行動パターンがつまずき，興味関心の低下などを示すサインとなっているかを明らかにした．とくに，資料の閲覧順序，プログラミングにおけるエラーパターンなど，コンテキストの特徴的な出現パターンを明らかにすることにより，学習者の行動モデルを構築した．このモデルを用いて，学習者の状態を把握するための学生指導に必要な情報を教員へフィードバックできる機能を実現した．

本研究では，大規模かつ多様なビジネスデータの分析技術（ビジネスアナリティクス）の体系化と深化を研究の目的とし，様々なビジネスデータに対応した分析モデルの提案と評価を行った．具体的には，１）ECサイトのデータベース情報を対象とした情報分析技術の開発，２）テキストデータとして蓄積されるマーケティング情報の分析技術の開発，３）情報推薦のための統計モデルの開発，４）情報検索や推薦の技術を活用したWebマーケティングモデルの理論解析，５）高次元かつ疎な大規模データを対象とした分析手法の開発，６）プライバシー保護データ解析の方法論の開発，などの個別研究課題を軸として研究を推進した．

本研究を通して，大規模データに対する統計的手法並びに凸最適化に基づく自動分類法を応用することにより，広範な諸問題に対して精度の高い解を効果的に求めることが可能であることを示した．
具体的にはデータに秘匿性を持たせて学習を行うプライバシー保護分散処理問題，ECサイトにおける潜在クラスの解析問題，動的再構成回路の設計問題，L1最適化による文書分類問題，CARTを用いた無ひずみデータ圧縮，授業への出欠情報を用いた隠れ属性モデル解析問題，ランダムマルコフフィールドを用いた大規模故障診断問題，大規模プログラミング編集履歴取得・可視化，等々に対するアルゴリズム並びに解析手法を提案し，それらの有効性を示した．

本研究では、コミュニケーション・マネジメント、学習ストラテジ―、チーム・ワーク、クリティカル・シンキング、分析・統合能力、問題解決能力、企画力と達成能力、多様性対応能力の養成を満たす3段階方式で少人数教育によるコースを開発した。電子化教材を端末に依存しない配信し、コンピュータ適応型の成果測定テストを作成、インタラクティブウィジェット機能を追加し、英文読解過程のログの可視化を行った。異文化交流実践講座と多地点のテレビ会議では、音声品質、伝送速度を測定し、著名研究者のオンデマンド講義を25コース開講した。

本研究では，平成23年度より3年間，クラウドコンピューティング環境による次世代ｅラーニングスタイルに関する研究開発に関する研究開発を行った．学習スタイルとしては，平成23年度には学習者が仮想化デスクトップを経由してeラーニングを行う場合を，24年度には学習者が電子書籍を使用しながらeラーニングを行う場合を，また25年度にはクラウドコンピューティング環境側で学習者の学習履歴を取得可能なシステムの試作を行い，それぞれについて実証実験を行い評価を行うことで一定の有効性を確認することができた．得られた研究成果は関連する学会において発表を行った．

本研究では, センサネットワークを含むネットワーク分散処理の問題に対して, 多端子情報理論と統計的決定理論に基づいた基礎モデルを構築し, 構築したモデル上での最適解の導出及び最適解またはその近似解を実現するアルゴリズムを設計した.

近年,誤り訂正符号の分野で提案されたTurbo符号,Turbo復号法はその誤り訂正能力の高さから21世紀の高信頼度情報通信,蓄積技術の重要な技術として注目を集めている.このTurbo復号を合む反復復号アルゴリズムは,知識情報処理の分野で不確実推論アルゴリズムとして用いられている確信度伝搬(BP: Belief Propagation)アルゴリズムの応用例として解釈されることが明らかとなっており,Turbo復号はBPアルゴリズムと同等な方法で,事後確率計算を近似的に効率よく行っていると解釈される.平成12-14年度科学研究費補助金の助成による「不確実推論を用いた高信頼度反復復号アルゴリズムの設計と解析」の研究成果として得られた拡張ジャンクショングラフ(EJG)と並列反復事後確率計算アルゴリズムは,従来の確率伝播アルゴリズムと比べー般的な確率モデル(符号)を扱えると共にループのあるグラフ(ほとんどの実用的符号はループがある)においても性能の劣化が少ないことが確認された.
本研究では以下のように様々な応用を試み、その性能を実験的及び解析的に検討を行った.
(1)ARQ方式などの帰還通信路を持つ通信路モデルにおける確率伝播アルゴリズムの応用と性能評価を行った.
(2)EJGと並列反復事後確率計算アルゴリズムをスモールループを含むLDPC符号に適用した際のアルゴリズムの効率化および性能解析を行った.
(3)他の分野への応用として,ストリーム暗号の解読アルゴリズムへの適用および性能解析を行った.

1.既に提案したベイジアンネットやグラフィカルモデルを含む一般的確率モデルに対する推論アルゴリズムをもとに,有効な符号のクラスを含む一般的確率モデルに対する一般的事後確率計算アルゴリズムを設計し,理論的及び実験的評価を行った.
2.また,このアルゴリズムだけにとらわれず,事後計算アルゴリズムの収束性や計算結果の精度に対し,微分幾何からの考察を発展させ,学習理論や統計学から,より一般的視点を用いて考察した.
3.事後分布を拡張した一般化事後分布を定義し,証拠として,ある事象の分布が与えられたもとでの確率推論を一般化確率推論として定式化し,その推論結果に保証があるアルゴリズムを提案し,その性質を解析した.さらに計算量・メモリ量の効率をより良くしたアルゴリズムと並列アルゴリズムへの改善,及び性能解析を行った.
4.上記のアルゴリズムを,ジャンクショングラフ(JG)を拡張した拡張JGに適用して,効率的伝播アルゴリズムを提案し,その性質について考察した.LDPC符号より拡張JGを構成し,2のアルゴリズムを復号アルゴリズムとして適用し,その性質について理論及び実験の両面から考察した.
5.畳み込み符号やtail-biting畳み込み符号についても拡張JGを用いて符号を表現し,2のアルゴリズムにより復号を行い,その性質について理論及び実験の両面から考察した.
6.前年度で提案した一般的事後確率計算アルゴリズムを考察により明らかとなった収束性が保証される特別なクラスに適用することにより,推論結果にも保証があるもとで計算量・メモリ量の効率をより良くしたアルゴリズムへの改善,及び性能解析
7.前年度の結果を実際の復号アルゴリズムへと発展させ,その性質について理論及び実験の両面からの考察を行った.

今年度目標とした項目に対し,下記の結果を得た.
1.データマイニングとテキストマイニング
新聞記事などのテキストデータについて,その自動分類法と,特に複合語に着目し分類精度を向上させる方式を提案した。また,大規模データベースにおいて属性値が連続値をとる場合に属性間の相関を考慮した離散化の方法を提案し,いずれも信学会・ソサエティ大会で発表した.定型項目と記述項目が混在するアンケートデータからの相関ルールを抽出する新しい方法を提案した.エントロピーを用いて多値属性値の出現頻度から複雑さを評価し,これを最小支持度の修正に反映する.これはテキスト中の単語の出現頻度に対しても合理的に取り扱うことが出来る方法になっており、実データに適用しその有効性を明らかにした.情報理論とその応用シンポジウムで発表した.
2.符号化技術
ブロックターボ符号におけるインタリーバの有効な設計方法を提案した.置換行列に制約条件を加えることにより,構成されたターボ符号の最小距離を増加させることができる.そのときの条件・置換行列の求め方・要素符号を与えたときの最小距離の導出などを具体的に与え評価した.また,リスト復号法を用いた連接符号の復号アルゴリズムの提案・評価,および周期的畳み込み符号の新しい構成法とその性能の導出を行った.いずれも情報理論とその応用シンポジウムで発表した.

本年度は最終年度であるので、当初の研究計画に対する実績を示す。
(1)情報源符号化の中でテキストを対象としたデータ圧縮の問題について(1)MDL基準に基づく符号とベイズ符号の符号長の理論的比較及び、この成果を用いたモデル選択問題への応用を図った。(2)ベイズ符号に対する計算量低減の近似最適アルゴリズムの開発を行った。ベンチマークテスト、実在するファイルなどに適用し良好な結果を得た。音声・画像などを対象とする情報縮約の問題についてトレリス符号を用いた源符号化アルゴリズムの提案、実用に耐える符号表の作成とその評価実験を行った。
(2)通信路符号化の問題では(1)ブロック符号についてBCH限界を超える復合法、その軟判定復号法の開発を行った。計算量の点からも実用に耐える復号法の方式を見出した。(2)たたみ込み符号についてViterbi復合法とシンドローム復合法の関係を明らかにした。また、ARQ方式への適用を図りリスト復合による低符号化比率で優れた性能をもつ方式を明らかにした。(3)誤り訂正符号のLSIのテスト方式への応用として並列演算によるシグネチャ生成法を明らかにした。

情報回線の高機能化及びデ-タベ-スセンタの大容量化に伴い、各分野におけるペ-パレス化が進み、OAによる情報管理システムが急速に進展している。このようなシステムにおける大量の文書の入出力を行うタ-ミナルは、ネットワ-ク加入者が相互に自由にアクセスできるという利便性がある反面、不当な利用者が情報の改ざんや不当な入手を行う危険性が存在する。本研究では、この問題を解決する具体的なアルゴリズムを提案し、論理的な整理を行なった。また、個人の端末で加速度的に発生量を増している文書情報を合理的な手段により個人対応で管理し、組織として共有する具体的なシステムを提案し、実システムによる実験を行なった。
本研究はLAN及びISDN回線で互いに結ばれる複数の独立した利用者が、それぞれの機密に要する文書を共通のデ-タベ-スセンタに預け、正当な利用者のみが預けた文書を取り出すことができる方策を実現することであったが、主に次の問題に対して、ISDN回線とG4ファクシミリの実システムを用いて具体的な機能を実現する見通しを得た。
1.ネットワ-クアクセス及びプロトコルにおける機密保持
2.デ-タベ-スセンタにおけるアクセスの機密保持
3.情報アクセスに鍵が掛けられるマルチメディアタ-ミナルの機能
文書内容を暗号化することで情報内容の機密保護を行う点に関しては従来の方法に委ね、本研究ではアクセス機能に焦点を置いた。

本講演では、Cプログラミングを用いて基本的な情報処理の方法やアルゴリズムの組み立て方を学ぶ「情報処理基礎演習」の授業を対象とし、編集履歴可視化システムの具体的な活用事例について報告する。具体的には、荒本らによって開発された編集履歴可視化システムを活用して、学生のプログラム作成時の編集履歴データを取得すると共に、演習授業中に実施する小テストやレポート、及び試験得点といったこれまでの教学データを統合し、教育支援に役立てる試みについて検討する。これにより、プログラミング系科目におけるLearning Analyticsの具体的な方法論や活用し得る分析モデルについて明らかにする。

ShamaiとSasonは,最尤復号法の復号誤り確率の上界式であるDS2上界式に条件を付加することで,従来知られている様々な上界式が導かれることを指摘した.一方,Hofらは,この手法をForneyの最尤復号法の一般化(GD:Generalized Decoding)に対して適用し,復号誤り確率の上界式を導出した.さらにHofらは,2元入力出力対称通信路および完全重み分布既知の線形符号の仮定を加えることで,GDに対するSulman-Feder上界式(以下,GD-SF上界式)を導出している.ここで,Hofらの上界式はForneyの議論とは異なり,チャーノフ上界の2つのパラメータについて独立に最適化を施した上界式ではない.そこで本論文では,GD-SF上界式を導くために最適となる関数g(y)を導出し,この結果を用いてForneyの解析と同様に2つの独立なパラメタを用いたGD-SF上界式を導出する.そして,この上界式がHofらのGD-SF上界式よりもタイトであることを示す.

本研究では，大学教育用の教科書の作成を通して，マルテメディアコンテンツやインタラクティブコンテンツを含む電子教材の開発方針の検討を行う。

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.

自動分類問題や回帰問題に対して,2001年にL. Breimanにより提案されたランダムフォレストは,CARTによって生成した複数の木を用いることにより,大変良い性能を発揮することが知られている.本稿では単一あるいは複数の回帰木を用いて,2次元データである画像の無歪み圧縮を行う手法について検討する.このとき画像圧縮の特性に着目し,すでに圧縮した箇所を説明変数とし,次に圧縮する色要素を目的変数として扱う.圧縮対象の画像についてCART及びランダムフォレストで学習を行い,学習結果である回帰木をまず符号化する.次にこれらの回帰木を用いて圧縮対象の各画素値の推定を行い,推定値と画素値との差分のみを圧縮する.結果的に,いくつかの画像に適用したときにPNG 形式よりも圧縮可能であることを示す.

推薦問題を扱うためのより一般化されたマルコフ決定過程モデルに対して，ベイズ基準のもとで最適な推薦ルールを履歴データから求める方法を提案する．推薦問題に関する研究において，これまで，ある商品を推薦した結果どの商品が買われたのか（推薦結果）や，さらには，一定期間内に行った複数の推薦結果が考慮されることはほとんどなかった．これに対して，マルコフ決定過程モデルを用いることで上記2点を初めて考慮した手法が提案されている．提案法は，その従来研究のモデルを一般化した点に新規性がある．また，もう1つの新規性として，推薦ルールを求めるためのプロセスを統計的決定問題として厳密に定式化した点がある．従来のモデルを一般化することで，マルコフ決定過程モデルを用いた推薦手法の適用領域が拡大され，かつ，推薦する目的に対して最適な推薦が行えるようになった．人工データを用いた評価実験により，提案する推薦手法の有効性を確認した．In this paper, we propose a general markov decision process model for the recommendation system. Furthermore, by using historical data, we derive the optimal recommendation lists from the proposed model based on bayesian decision theory. In the recommendation research area, there were little studies that considered both the purchased items and the past recommended items within a given period. In these circumstances, markov decision process based recommend method that can take these two things into account has been proposed. Our method also uses both things as with the previous method. Here, the unique thing about this paper is not only that we generalize the existing model, but also that we formulate the process to get the recommendation lists as the statistical decision problem. As a result, we can obtain the most suitable recommendation lists with respect to the purpose of the recommendation for a wide variety of recommendation scene. By using artificial data, we show the experimental results that our method can obtain more rewards than the conventional method gets.

一般化された(u,+v)構成法, g(u,u+v)構成法,に基づいて少数の情報記号数に対する最適2元線形定重み符号のC^<(h_1,h_2…,h_1)>_<(s_1,s_2,…,s_1)>を構成している.本論文ではまず始めに符号長n≦128の範囲でBrouwerとVerhoefのバウンドを満たすという意味で最適な2元線形重み一定符号を情報記号数κ=2およびκ=3に対して構成している.さらに本論文ではn≦128の範囲でk=2,3,4,5,6,に対する最適2元線形重み一定符号を構成している.最後に,本論文で明らかにしている符号について以下のような予想を与えている.・符号C^<(h1)>_<(s1)>(k=3)は任意のh_1に対し符号長n=3h_1,情報記号数k=2,最小距離d=2h_1の最適な線形一定重み符号を与える.・符号C^<(h1)>_<(s1)>(k=3)は任意のh_1に対しn=7h_1,k=3,d=4h_1の最適な線形一定重み符号を与える.・符号C^<(h1,h2…,h1)>_<(s1,s2,…,s1)>は任意のkに対しn=2^k-2,k-1,d =2^<k-1>の符号>を与える.

一般化された(u,+v)構成法, g(u,u+v)構成法,に基づいて少数の情報記号数に対する最適2元線形定重み符号のC^<(h_1,h_2…,h_1)>_<(s_1,s_2,…,s_1)>を構成している.本論文ではまず始めに符号長n≦128の範囲でBrouwerとVerhoefのバウンドを満たすという意味で最適な2元線形重み一定符号を情報記号数κ=2およびκ=3に対して構成している.さらに本論文ではn≦128の範囲でk=2,3,4,5,6,に対する最適2元線形重み一定符号を構成している.最後に,本論文で明らかにしている符号について以下のような予想を与えている.・符号C^<(h1)>_<(s1)>(k=3)は任意のh_1に対し符号長n=3h_1,情報記号数k=2,最小距離d=2h_1の最適な線形一定重み符号を与える.・符号C^<(h1)>_<(s1)>(k=3)は任意のh_1に対しn=7h_1,k=3,d=4h_1の最適な線形一定重み符号を与える.・符号C^<(h1,h2…,h1)>_<(s1,s2,…,s1)>は任意のkに対しn=2^k-2,k-1,d =2^<k-1>の符号>を与える.

本稿では情報数理教育を対象として，インタラクティブなコンテンツに対する電子教材の試作を検討する．具体的にはRSA暗号に対するインタラクティブな教育コンテンツを作成し，評価を行う．このとき，マルチプラットフォーム化を念頭におき，コンテンツはHTML,CSS,JavaScriptのみを使用して構築する．数式の表示はMathJaxにより行う．さらにPhoneGapを用いてマルチプラットフォームに対応可能なアプリ化を検討する．

本研究では、大学教育用の教科書としての電子書籍の試作を行い、電子書籍内のマルチメディアコンテンツが内容理解に与える影響の評価を行なう。具体的には、教科書の内容を補助するような動画や音声を配した電子書籍を試作し、ユーザアンケートによって教育効果を評価する。

本稿ではプライバシー保護を目的とした回帰分析について扱う.まず,2者が異なる属性に関するデータを保持しているもとで,2者間でデータを渡すことなく回帰係数の最小二乗推定量を分散計算する新たな方式を提案し,プライバシーの安全性を評価する.また,提案するプロトコルは繰り返し計算を行うため,数値実験によりプロトコルの繰り返し数についての評価を行う.さらに,多者間での分散計算への拡張も行う.

学習データの特徴を表現した行列の学習を行うメトリックラーニングの一手法として拡張余弦尺度が提案されている.しかしながら,拡張余弦尺度は学習データ全体に対し一つの行列を学習するものであり,カテゴリ毎にその特徴が大きく異なることが想定される文書データに対しては改善の余地がある.そこで,本研究ではカテゴリ単位に計量行列を学習する手法を提案すると共に,新聞記事データを用いたシミュレーションにより提案手法の有効性を示す.

B. M. Kurkoskiらは2元入力離散多値出力通信路に対し,相互情報量を基準とする最適な量子化器の設計法を提案した.またLDPC符号の復号アルゴリズムの設計に応用する手法も提案している.ただしこの手法は通信路の出力が離散に限られ,またより一般の通信システムに直接適用するのは困難である.そこで本研究ではMIMO通信システムを対象とし,相互情報量を基準とした量子化器の設計法について検討を行う.このとき相互情報量の勾配を用いて共役勾配法によりその最大化を行う手法を提案する.

The SQL injection attack causes very serious problem to web applications which have database including personal data. To detect the SQL injection attack, the parsing and the black list based on the existed attack have been widely used. Those approaches, however, have some problems in terms of the size of list or calculation costs as the number of attacks increases. For this point, the authors have previously proposed a simple automatic detection algorithm of SQL injection attack. This algorithm requires to calculate the contained rate of suspicious characters with input sequence. This rate would be compared with a known real-valued threshold. This paper proposes the learning algorithm to choose the real-valued threshold from training data sets. Furthermore, some criteria would be considered and their performances would also be examined.The SQL injection attack causes very serious problem to web applications which have database including personal data. To detect the SQL injection attack, the parsing and the black list based on the existed attack have been widely used. Those approaches, however, have some problems in terms of the size of list or calculation costs as the number of attacks increases. For this point, the authors have previously proposed a simple automatic detection algorithm of SQL injection attack. This algorithm requires to calculate the contained rate of suspicious characters with input sequence. This rate would be compared with a known real-valued threshold. This paper proposes the learning algorithm to choose the real-valued threshold from training data sets. Furthermore, some criteria would be considered and their performances would also be examined.

推薦問題を扱うためのより一般化されたマルコフ決定過程モデルに対して，ベイズ基準のもとで最適な推薦ルールを履歴データから求める方法を提案する．提案法の特徴は，ある商品を推薦した後に何が買われたのかを考慮していること，さらに，一回の推薦結果だけでなく一定期間内に行った複数の推薦結果を評価している点にある．ここで，従来の推薦手法と大きく異なる点は，推薦ルールを求めるためのプロセスを統計的決定問題として厳密に定式化したことにある．その結果，推薦する目的に対して最適な推薦が行えるようになった．人工データを用いた評価実験により，提案する推薦手法の有効性を示す．In this paper, we proposed a general markov decision process model for the recommendation system. Furthermore, based on the bayesian decision theory, we derived the optimal recommendation lists from the proposed model using historical data. Our method takes into account not only the purchased items but also the past recommended items within a given period. Here, the unique thing about this paper is that we formulate the process to get the recommendation lists as the statistical decision problem. As a result, we can obtain the most suitable recommendation lists with respect to the purpose of the recommendation. We show the experimental results by using artificial data that our method can obtain more rewards than the conventional method gets.

F.P. Preparataらは,マルチコンピュータシステムの要素である各ノードを別のいくつかのノードが独立に検査を行い,それらの結果からシステム中の全ての故障ノードを発見する故障診断モデルを提案した.本論文では確率的に検査結果を誤る故障診断モデルを対象として,線形計画法を用いた故障診断法を示す.更に計算機シミュレーションによりその有効性を明らかにする.

サイバー大学IT総合学部の専門必修科目「コンピュータ入門」の学生アンケートを分析した.ここで,アンケートは選択型の質問と記述型の質問が混在している.授業モデルを提案し,PLSIモデルを用いて文書のクラスタリング・分類,および重要文抽出・特徴語抽出を行い,授業改善に結びつくヒントを得た.

本稿では,フルオンデマンド形式の情報系科目で実施された学生アンケートの分析結果について報告する.対象とするのはすべての授業がインターネット上で実施され通学を必要としない4年制大学におけるコンピュータ関連の科目である.従来の通学制とは異なる新しい授業形態であることから,効果的な授業のあり方や授業改善についても新しい取り組みが必要になると考えられる.そこで本研究では,通学制の大学において同内容の授業で実施された学生アンケートとの比較分析により,フルオンデマンド授業の特性について検討を行う.

カテゴリが既知の学習データを用いて,新規データのカテゴリを推定する自動分類問題は,サポートベクターマシンなど数多く研究が行われている.本研究では,カテゴリ中に発生するデータがマルコフモデルに従って発生すると仮定したときに,学習データを用いて分類誤り確率を推定する手法を提案する.

Experiments usually aim to study how changes in various factors affect the response variable of interest. Since the model used most often at present in experimental design is expressed through the effect of each factor, it is easy to understand how each factor affects the response variable. However, since the model contains redundant parameters, a considerable amount of time is often necessary to implement the procedure for estimating the effects. On the other hand, it has recently been shown that the model in experimental design can also be expressed in terms of an orthonormal system. In this case, the model contains no redundant parameters. Moreover, the theorem with respect to the sum of squares for the 2-factor interaction, needed in the analysis of variance (ANOVA) has been obtained. However, 3-factor interaction is often to be considered in real cases, but the theorem with respect to the sum of squares for the 3-factor interaction has not been obtained up to now. In this paper, we present the theorem with respect to the sum of squares for the 3-factor interaction in a model based on an orthonormal system. Furthermore, we can also obtain the theorem for interactions with 4 or more factors by the similar proof. Hence, in any real case, we can execute ANOVA in the model based on an orthonormal system.

In this paper, we present the theorem of the relation between the Fourier coefficients and the 3-factor interaction effects. From this theorem, the 3-factor interaction effects can be easily obtained from the Fourier coefficients. Therefore, it is possible to implement the estimation procedures easily as well as to understand how any interaction affects the response variable in the model based on an orthonormal system.

性能の良いデータ圧縮法として文脈木重みづけ法が知られており,これを用いた文書分類法が提案されている.本研究では各カテゴリの文書は1つの確率モデルから生起することを仮定し,新規テスト文書の文書長が有限の場合の分類誤り確率を評価する.このとき新規テスト文書に対する理想符号長の平均と分散を評価し,中心極限定理を用いることにより各カテゴリの分類誤り確率を近似する手法を提案する.

F.P.Preparataらは,マルチコンピュータシステムの要素である各ノードを別のいくつかのノードが独立に検査を行い,それらの結果からシステム中のすべての故障ノードを発見する故障診断モデルを提案した.本論文では確率的な故障診断システムを対象とし,事後確率を用いて診断を行ったときに診断誤り確率を小さくする検査グラフの構成法を示す.更にPMCモデルに対して事後確率診断を行ったとき,故障やシンドロームの発生確率が未知のもとで正しく診断可能な故障パターンについて解析を行う.

従来,誤り訂正符号を用いて直積ファイルを複数のディスクペ配置する方法が提案されている.本研究では不均一誤り訂正(UEP)符号を用いた直積ファイルのディスク配置法を提案する.UEP符号とは各符号語の位置ごとに誤り訂正能力が異なる符号である.本研究ではまず,部分照合質問の属性の出現に偏りがあるモデルを仮定する.そして,そのときの平均処理時間が符号の分割重み分布と呼ばれる値を用いることにより計算できることを示す.そして,UEP符号を用いた場合の平均処理時間を求め,その効果を検証する.

グラフィカルモデル上の確率推論の問題は,符号理論・画像処理・音声認識などの様々な工学上の問題に現れ重要である.近年,確率推論の応用の1つである誤り訂正符号の複号問題に対して,線形計画法に基づいた復号アルゴリズムに関する研究が盛んに行われている.誤り訂正符号の復号問題をファクターグラフにより表現すると,グラフ中に含まれる関数は,指示関数とそれ以外の関数(非指示関数)に分類される.特に指示関数は複数の変数ノードに接続し,非指示関数は単一の変数ノードのみに接続している.一般的な確率推論の問題をファクターグラフとして表現した場合,複数の変数ノードと接続する非指示関数がファクターグラフに含まれる場合がある.本研究では,このような問題に対して,線形計画法に基づいた推論アルゴリズムを構築することを目的とする.

LDPC符号や線形ブロック符号とLDPC符号を組み合わせて構成される一般化LDPC (GLDPC)符号を符号化する際,生成行列を用いると,符号長の二乗に比例する時間計算量が必要となる.J. Luらは確率的に構成された任意のLDPC符号に対し,タナーグラフを階層的にラベル付けしてパリティビットを再帰的に算出することで,符号長に対し線形オーダーで符号化が可能な方法を提案した.本研究では,GLDPC符号のベース符号に対しDulmage Mendelsohn分解を行い,組み込む線形ブロック符号に対してガウスの消去法と擬似逆行列を用いたパリティビットの算出法を導出した効率的な符号化法を提案する.提案した符号化法の最大計算回数を導出し,有効性を評価する.

ビット反転(BF)復号法は確率伝搬型(BP)復号法より反復閾値など性能は劣るが,簡単な計算ができる.しかし通信路の誤り確率が低い領域において,エラーフロアが発生しやすいことが問題である.そのような問題に対し,S. K. Planjeryらは2元対称通信路において従来のBF復号法で用いるメッセージに信頼度を表すビットを付加した3ビットBF複号法を提案している.3ビットBF復号法はBF復号法よりもエラーフロア領域における性能が向上しているが,更新ルールが複雑なためビットノードの次数が3の正則LDPC符号の場合しか複号法が示されていない.本研究では,非正則LDPC符号のような様々な次数をもつLDPC符号でも実行できる新しい更新ルールに基づく3ビットBF復号法を提案する.計算機シミュレーションによる実験の結果,提案した復号法の有効性を示す.また,従来および提案した3ビットBF復号法に対し密度発展法による性能解析を行い反復閾値が向上することを示す.

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.

近年,電子文書の増加に伴い効率的な知識獲得が重要な課題となっている.その手法のひとつに文書分類手法がある.本稿では,この文書分類手法にProbabilistic Latent Semantic Indexing (PLSI)を用いる.PLSIの特徴として,マルチカテゴリに対応していることと,EMアルゴリズムによる解法であることがあげられる.本稿においては,このEMアルゴリズムを用いて,少量の学習データに対して分類可能な手法を提案する.さらに,本手法をWEBページ分類に適用し,その有効性を明らかにする.

2元線形符号を用いた多元接続通信路における線形計画法に基づいた復号法を提案する.近年,通信路符号化の最尤復号の問題に対して線形計画復号法が注目を浴びている.本研究ではまず,2元線形符号を用いた多元接続通信路における最尤復号の問題がどのようにして線形計画問題として定式化されるかを示す.これは,目的関数である対数尤度関数が,一般的には符号語シンボルに対する線形関数ではないため自明ではない.そこで,本研究では,目的関数がその変数の線形関数になるような補助変数を導入する.これにより,最尤復号の問題が線形計画問題として定式化されるが,この問題を解くには非常に多くの計算量を要し,現実的ではない.本研究では,1対1通信における線形計画復号法と同様に,この問題を緩和した線形計画問題を考える.提案された復号法は,1対1通信の場合と同様,復号結果が整数ならば最尤復号であることが保証されるという望ましい性質を持つ.提案された復号法は,通信路のユーザー数に対して指数オーダーの計算量が必要となるが,ガウス型多元接続通信路においてはその計算量を削減することが出来ることを示す.また,コンピュータシミュレーションにより,Sum-Productアルゴリズムに基づいた復号法との性能比較を行う.

近年,インターネットの普及により膨大なテキストデータからの知識発見を扱うテキストマイニングの技法が注目されている.本研究では,テキストマイニングが取り扱う問題の中でも,特に文書分類の問題を取り上げ,形態素解析後の単語の出現分布としてある確率モデルのクラスを仮定し,文書分類の性能,並びに分類に用いられる距離について漸近的な分析を行う.一般に,文書分類に不必要な単語の混入を完全に排除することは難しく,様々な重要単語の重み付け法などが提案されている.本論文で扱う最初の問題は,このような分類に不必要な単語が混入することが,文書分類に与える性能劣化の程度を把握することである.さらには,単語の出現頻度に基づく文書分類においては,個々の単語の生起頻度は少なく,多くの単語の頻度がゼロとなってしまうというスパースネスの問題がある.すなわち,このベクトル空間上で一つの文書を表す点は,ゼロを多くの要素に持つベクトルで表現される.しかし,「このような状況で,文書同士の距離による分類がある程度の分類性能を示すのは何故か」という疑問については依然として経験的な解釈が与えられているのみである.その理論的根拠を与えるため,本稿では,各要素の出現頻度を有限に保ったまま,次元数を無限大とする新たな漸近論の概念を導入することにより,スパースな文書ベクトル間の距離について解析的な性能を示す.

F.P.Preparataらは,マルチプロセッサシステムの要素である各ノードを別のいくつかのノードが独立に検査を行い,それらの結果からシステム中のすべての故障ノードを発見する故障診断モデルを提案した.本論文では確率的に検査結果を誤る故障診断モデルを対象とし,部分的なシンドロームに対する故障の事後確率を効率的に求める診断アルゴリズムを示す.更にいくつかの仮定のもとでこのアルゴリズムの診断誤り確率を解析する手法を提案し,その有効性を示す.

F.P.Preparataらは,マルチプロセッサシステムの要素である各ノードを別のいくつかのノードが独立に検査を行い,それらの結果からシステム中のすべての故障ノードを発見する故障診断モデルを提案した.本稿では確率的に検査結果を誤る故障診断モデルを対象とし,部分的なシンドロームに対する故障の事後確率を効率的に求める診断アルゴリズムを示す.さらにこのアルゴリズムの診断誤り確率を解析する手法を提案する.

In digital signal processing, the sampling theorem states that any real valued function ƒ can be reconstructed from a sequence of values of ƒ that are discretely sampled with a frequency at least twice as high as the maximum frequency of the spectrum of ƒ. This theorem can also be applied to functions over finite domain. Then, the range of frequencies of ƒ 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(q)ⁿ domain) but also over GF(q)ⁿ 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)ⁿ 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)ⁿ 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)ⁿ domain and linear codes.

一般化された(u,u+v)構成法,g(u,u+v)構成法,に基づいて少数の情報記号数に対する最適2元線形符号の大きなクラスを構成している.そしてこの構成法に基づいて(3(2^m-1,m+1,3・2^m-1)符号,(3(2^m-1),m+1,3・2^m-1)符号,(3(2^m-1),m+1,3・2^m)符号を構成し,これらの符号がBrouwer-Verhoeffのテーブル(BVテーブル)に記載の最小距離にn≦125の範囲で一致し,それ故に最適2元線形符号であること且つn≧126の範囲においても最適2元線形符号であることが予測されることを述べる.さらに情報記号数k=2,符号長n,最小距離dの(n,2,d)線形符号および情報記号数3の(n,3,d)線形符号を与えている.そして(n,2,d)符号がn≦125の任意の符号長に対しBVテーブル記載の最小距離限界に一致すること,即ち理論的限界式を完全に満たすことを示している.同様に(n,3,d)符号もn=8+7μ(μ=1,2,…)を除く任意の符号長において(BVテーブル)理論的限界式を満たすことを示している.これらの符号はn≧126の範囲においても最適性を満たすことが強く予想される.さらに情報記号数k=4,5,6および7に対する最適符号を構成し,具体例を示している.

正則LDPC符号アンサンブルにおいて2次モーメント法を利用して,訂正可能なバースト消失の最大の長さ以下となる確率の下界を導出する.

誤り訂正符号の中でもLow-Density Parity-Check(LDPC)符号は繰り返し復号を行うことで優れた復号性能を示す.線形ブロック符号とLDPC符号を組み合わせて構成される一般化LDPC(GLDPC)符号も通信路容量に迫る性能をもつが,符号化を実行する際の計算量が膨大である.本研究ではGLDPC符号に組織型の部分符号を組み込み,またextended Irregular Repeat Accumulate(eIRA)符号の階段状の構造を利用することで,符号長に対し線形時間で符号化が可能なGLDPC符号の構成法を提案する.その結果,従来のGLDPC符号よりも符号化に要する演算回数が大幅に低減できることを示す.また,シミュレーションによる実験結果から,提案したGLDPC符号は従来のGLDPC符号とほぼ同じ復号性能をもつことも示す.

非正則LDPC符号の検査行列を用いてBP復号法を実行したとき,復号性能は検査行列の構造によって大きく依存され,その構造によっては復号性能が劣化する可能性がある.そこで本研究では,BP復号法において,より効果的な確率伝播を行えるような構造をもつ半確定的な非正則LDPC符号の構成法を提案する.また,同様の考え方を用いてShuffled BP復号法に対しても,効果的な確率伝播を行えるような更新順序の決定法を提案する.計算機シミュレーションによる実験の結果,提案手法によって得られた非正則LDPC符号は従来の非正則LDPC符号よりも復号性能が高いことを示す.

Traffic forecasting from past observed traffic data with small calculation complexity has been one of important problems for planning of servers and networks. Focusing on World Wide Web (WWW) traffic as fundamental investigation, this paper would deal with Bayesian forecasting of network traffic on the time varying Poisson model from a viewpoint from statistical decision theory. Under this model, we would show that the forecasting estimate is obtained by simple arithmetic calculation with a known constant of time varying degree parameter and expresses real WWW traffic well from both theoretical and empirical points of view.Traffic forecasting from past observed traffic data with small calculation complexity has been one of important problems for planning of servers and networks. Focusing on World Wide Web (WWW) traffic as fundamental investigation, this paper would deal with Bayesian forecasting of network traffic on the time varying Poisson model from a viewpoint from statistical decision theory. Under this model, we would show that the forecasting estimate is obtained by simple arithmetic calculation with a known constant of time varying degree parameter and expresses real WWW traffic well from both theoretical and empirical points of view.

バースト消失を訂正するために適した非正則低密度パリティ検査(LDPC)符号の構成方法を2つ提案する.非正則LDPC符号は次数が2の変数のノードによって小さいサイズのストッピングセットが生成されやすく,性能が著しく劣化する原因となる.本研究では,次数2の変数ノードによる影響が少なくなるように構成されたextend irregular repeart accumulate(eIRA)符号の構造を利用し,効果的に列置換を行うことで最小スパンを向上させる.またバースト消失に対する訂正能力が大きいLR-LDPC符号の構造も利用し,バースト消失に対する訂正能力が高い非正則LR-LDPC符号の構成法も提案する.提案する符号は,eIRA符号がもつ符号長に対し線形で符号化が可能な性質を保持する.また生成された符号サンプルに対して最小スパンを計測することで,提案した符号が元の符号より向上することを示す.

本研究では非正則LDPC符号を用いたGroup Shumed BP復号法に対して,符号の次数分布とタナーグラフの構造を考慮することで効果的なグループ分割法を行い,復号遅延を減らし,同時に収束を早くする.提案したグループ分割法は従来の受信ビット順のグループ分割法と比較して優れた誤り訂正能力を持つことを計算機シミュレーションによって示す.

低密度パリティ検査(LDPC)符号とbelief-propagation(BP)復号法の組み合わせは高い復号性能を示すことが知られている.現在LDPC符号は高速無線・有線通信,磁気録音機器等における誤り訂正法として考えられている.従来研究ではバースト消失に対する訂正能力を評価するために,符号アンサンブルに対して解析を行なっている.まずLDPC符号のストッピングセットを用いて最小スパンの解析を行ない,次に訂正可能なバースト消失の比率を表す臨界最小スパン比率の計算を行なう.本研究では最小ストッピングセットを考慮することで,より精密な臨界最小スパン比率を導出する方法を提案し,バースト消失に対して高い訂正能力を持つと言われている,タナーグラフを組み合わせたLRタナーグラフアンサンブルにおいて,最小スパンの漸近的解析を行なう.

統計解析を行う際，得られたデータの中に外れ値が含まれることが多々ある．外れ値は少量であっても解析結果に大きく影響を与えることがあるため，従来から外れ値を含むデータに対する統計解析手法が数多く研究されている．従来，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.

本研究では,要素符号としてLPDC符号を用いる交錯符号についての研究を行う.交錯符号は有限状態マルコフ通信路などのバースト誤り通信路に適した誤り訂正方式として知られており,バースト誤りを個々の要素符号に分散させるために交錯を利用する.これに対し本研究においては,Joint estimation-decodingにおける通信路の状態推定精度を向上させるために交錯を利用する.長いバースト誤りを発生する有限状態マルコフ通信路においては,このように交錯を利用した誤り訂正方式が,単一の誤り訂正符号を用いた方式より高い誤り訂正能力を持つことを計算機実験により示した.また,この交錯符号に対して,通信路の状態を考慮した密度発展法を基にした性能解析手法を提案した.

本論文では,学習を用いた改変画像の検出手法を提案する.提案手法では,元画像と改変画像の特徴量ベクトルの差分は,空間上において元画像に依存せずに元画像を含むその改変画像のクラスとそれ以外の非改変画像のクラスを形成していると仮定する.提案手法では,事前に学習を行うことで,差分値の大きな特徴量を改変に大きな影響を与える要素とみなし選択する.また,類似した情報を表す特徴量を縮約することで,無関係画像が誤検出されることを防ぐ.提案手法は学習をしていない未知画像に対しても有効な手法である.画像データセットを用いた実験により,提案手法の検出精度が向上することを示す.

従来,情報源の確率構造と通信路の誤り確率が既知である一般情報源,一般通信路において誤りなく情報伝送可能な必要十分条件が求められていた.本研究では,そこで得られた結果をユニバーサル情報源・通信路結合符号化に応用する.また,分離定理に関しても考察する.

確率伝搬法を利用したCDMAマルチユーザ検出アルゴリズムを提案する.従来より確率伝搬法を利用したマルチユーザ検出アルゴリズムは提案されているが,これは計算量的困難性のために確率伝搬法をさらに近似したアルゴリズムとなっている.本研究では,ファクターグラフの構造を変えることで,確率伝搬法を定義通りの形でマルチユーザ検出の問題に適用できることを示す.提案するアルゴリズムは,拡散符号によって定まるファクターグラフにループが存在しない場合には,最適なマルチユーザ検出アルゴリズムとなる.

統計解析を行う際，得られたデータの中に外れ値が含まれることが多々ある．外れ値は少量であっても解析結果に大きく影響を与えることがあるため，従来から外れ値の取り扱いについて広く研究が行われている．従来 Ｂｏｘ らにより線形回帰モデルに対し混合分布を用いて外れ値の発生をモデル化する研究が行われている．同様のモデルに対し様々な研究が行われているが，いずれも外れ値の検出やパラメータの推定を目的としている．そこで本研究では，外れ値データの発生を含む回帰モデルに対する予測法について扱う．まず，このモデルに対しベイズ基準のもとで最適な予測法を示す．次に ＥＭ アルゴリズムを用いて計算量を削減した近似アルゴリズムを提案し，シミュレーションにより有効性を検証する．Outliers are often included in statistical data. The statistics analysis result is influenced from outliers. Therefore, there are many researches for handling of 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. Next, we propose an approximation algorithm reducing the computational complexity using EM algorithm , and evaluate this algorithm through some simulations.

本論文ではテクスチャ画像を対象とした類似画像検索において，ビットプレーンの出現確率とオイラーベクトルを特徴量とした手法を提案する．JPEG2000 ではビットプレーンは Wavelet 係数の値を２値展開し"１"の共起を同一ビット毎にまとめたものであり，復号の際に得ることができる．一方，オイラーベクトルは１枚のビットプレーンから生成されるため，JPEG2000 との親和性が高い．そこで本論文では，オイラーベクトルを特徴量として追加した JPEG2000 のビットプレーンを用いたテクスチャ画像の検索手法を提案し，Vis Tex データを用いた実験により検索精度が向上することを示す．We propose an image retrieval method that extracts features using probability and Euler vectors of wavelet coefficient's bit-plane. Each bit-plane is associated with probabilities represents the frequency of "1" occurrence, and bit-plane of wavelet coefficients can be extracted from JPEG2000 coded images. On the other hand, Euler vectors generated from a bit-plane, it has a great affinity for JPEG2000. In this paper,we propose the image retrieval method using bit-planes and the Euler vector of JPEG2000 coded texture image. We show by simulation result with using Vis Tex data set that retrieval precision of the proposed method is better than that of the conventional one.

本論文ではテクスチャ画像を対象とした類似画像検索において,ビットプレーンの出現確率とオイラーベクトルを特徴量とした手法を提案する.JPEG2000ではビットプレーンはWavelet係数の値を2値展開し"1"の共起を同一ビット毎にまとめたものであり,復号の際に得ることができる.一方,オイラーベクトルは1枚のビットプレーンから生成されるため,JPEG2000との親和性が高い.そこで本論文では,オイラーベクトルを特徴量として追加したJPEG2000のビットプレーンを用いたテクスチャ画像の検索手法を提案し,Vis Texデータを用いた実験により検索精度が向上することを示す.

This paper generalizes parallel error correcting codes proposed by Ahlswede et al. over a new type of multiple access channel called parallel error channel. The generalized parallel error correcting codes can handle with more errors compared with the original ones. We show construction methods of independent and non-independent parallel error correcting codes and decoding methods. We derive some bounds about the size of respective parallel error correcting codes. The obtained results imply a single parallel error correcting code can be constructed by two or more kinds of error correcting codes with distinct error correcting capabilities.

本研究ではMerhavらの定義したオーバーフロー確率を一般化した一般化オーバーフロー確率を考える.著者等は従来この一般化オーバーフロー確率に対して,一般化オーバーフロー確率が一定値以下になる条件のもとで達成可能な符号長の最小値をi.i.d.情報源に対して求めた.本研究ではまず,復号情報源に対して,一般化オーバーフロー確率を考えたときの達成可能性を定義する.さらに,達成可能なしきい値の十分条件を検討する.

従来情報源符号化における符号の性能は主に平均符号長で評価されてきた.それに対し,近年Merhavらが符号のオーバフロー確率を評価尺度とすることを提案し,オーバフロー確率に関するいくつかの結果が報告されている.本研究ではMerhavらの定義したオーバフロー確率を一般化した一般化オーバフロー確率を考える.そしてこの一般化オーバフロー確率に対して,まずある符号を用いた際の漸近的なオーバフロー確率を求める.次にオーバフロー確率を最小にする符号を提案する.最後にこの符号を用いたときに,オーバフロー確率が漸近的に0に収束するための条件を導く.

We have developed a public key certificate validation system considering the restrictions peculiar to the mobile environment, such as processing the speed and memory capacity of a cellular-phone terminal, and the network transmission speed. In this paper we derive a theoretical formula showing the performance of a validity check of the public key certificate of the conventional system and of the proposed system, and compare and examine a theoretical value in a mobile environment. Moreover, we evaluate the actual measurement that uses the server and cellular-phone terminal that we developed. We show that our proposed system based on the certificate validation server (CVS) system is better than the conventional system from the viewpoint of processing speed and transmission speed. (c) 2007 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.

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.

In the present paper, we consider the automatic text categorization as a series of information processing and propose a new classification technique called the Frequency Ratio Accumulation Method (FRAM). This is a simple technique that calculates the sum of ratios of word frequency in each category. However, in FRAM, feature terms can be used without limit. Therefore, we propose the use of the character N-gram and the word N-gram as feature terms using the above-described property of FRAM. Next, we evaluate the proposed technique through a number of experiments. In these experiments, we classify newspaper articles from Japanese CD-Mainichi 2002 and English Reuters-21578 using the Naive Bayes method (baseline method) and the proposed method. As a result, we show that the classification accuracy of the proposed method is far better than that of the baseline method. Specifically, the classification accuracy of the proposed method is 87.3% for Japanese CD-Mainichi 2002 and 86.1% for English Reuters-21578. Thus, the proposed method has very high performance. Although the proposed method is a simple technique, it provides a new perspective and has a high potential and is language-independent Thus, the proposed method can be expected to be developed further in the future.

By combining statistical analyses and information retrieval techniques, an efficient way for knowledge discovery from questionnaires is discussed. Since usual questionnaires include questions answered by a fixed format and those by a free format, it is important to introduce the methods by both data mining and text mining. The answers by the fixed format are called "items", and those by the free format, simply "texts". In this paper, using an algorithm for processing answers with both the items and the texts and that for extracting important sentences from texts combined with statistical techniques, a method for analyzing the questionnaires is established. The method is applied to a case of improvements for the quality of education by which the student questionnaire is executed to a class, and we obtain useful knowledge which leads to faculty development.

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 consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.

We study a modification method for constructing low-density parity-check (LDPC) codes for solid burst erasures. Our proposed modification method is based on a column permutation technique for a parity-check matrix of the original LDPC codes. It can change the burst erasure correction capabilities without degradation in the performance over random erasure channels. We show by simulation results that the performance of codes permuted by our method are better than that of the original codes, especially with two or more solid burst erasures.

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.

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.

Orthogonal Arrays (OAs) have been playing important roles in the field of experimental design. It is well known that OAs are closely related to error-correcting codes, and many good OAs are constructed from error-correcting codes. And factorial effects that can be estimated with OAs corresponding to error-correcting codes are clarified. On the other hand, in our past researches, we focused on the relation between OAs and unequal error protection codes (UEP codes). OAs corresponding to UEP codes are called OAs with unequal strength (UOAs), where OAs corresponding to error-correcting codes are called OAs with equal strength. We showed that UOAs are more practical than OAs with equal strength, and proposed some construction methods of UOAs from UEP codes. But, in the researches, we only showed some examples of factorial effects that can be estimated with UOAs, so we had never clarified these factorial effects as well as OAs with equal strength. In this paper, we clarify factorial effects that can be estimated with UOAs.

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.

Tail biting trellis codes and block concatenated codes are discussed from random coding arguments. An error exponent and decoding complexity for tail biting random trellis codes are shown. We then propose a block concatenated code constructed by a tail biting trellis inner code and derive an error exponent and decoding complexity for the proposed code. The results obtained by the proposed code show that we can attain a larger error exponent at all rates except for low rates with the same decoding complexity compared with the original concatenated code. © 2006 Taylor &amp
Francis Group, LLC.

This paper generalizes parallel error correcting codes proposed by Alshwede et al. over a type of multiple access channels called a parallel channel. The generalized parallel error correcting codes can handle with more errors compared with the original ones. We show construction methods of independent and non-independent parallel error correcting code and decoding methods. We derive some bounds about the size of respective parallel error correcting code.

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.

Orthogonal arrays have been used in the field of experimental design. Hedayat and Sloane showed the relation between orthogonal arrays and error-correcting codes[1]. And they proposed some construction methods of both linear and nonlinear orthogonal arrays from error-correcting codes. On the other hand, the paper[5] defined unequal orthogonal arrays as new class. It showed that unequal orthogonal arrays are more applicable to experimental design. Furthermore, it showed the relation between unequal orthogonal arrays and unequal error-correcting codes[3], and proposed the construction method of unequal orthogonal arrays from unequal error-correcting codes. But orthogonal arrays from this construction method are all linear. In this paper, we clarify the relation between nonlinear unequal orthogonal arrays and codes. And we propose one of construction methods of nonlinear unequal orthogonal arrays from error-correcting codes.

大学の授業改善への取り組みがますます重要課題となってきている。本研究では，学生アンケートの分析結果を授業改善に活用する手法の開発を目的とする。まず，学生の特性と満足度，成績などの関係をモデル化する。次に，モデルに基づいてアンケートを設計する。さらに，得られたアンケート結果を統計的手法を用いて解析し，授業改善に有用な情報が得られることを示す。

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. © 2005 IEEE.

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.

Reliability-based maximum likelihood decoding (MLD) algorithms of linear block codes have been widely studied. These algorithms efficiently search the most likely codeword using the generator matrix whose most reliable and linearly independent k (dimension of the code) columns form the identity matrix. In this paper, conditions for omitting unnecessary metrics computation of candidate codewords are derived in reliability-based MLD algorithms. The proposed conditions utilize an order relation of binary vectors. A simple method for testing if the proposed conditions are satisfied is devised. The method for testing proposed conditions requires no real number operations and, consequently, the MLD algorithm employing this method reduces the number of real number operations, compared to known reliability-based MLD algorithms.

本研究では,情報源の分布のクラスのみ仮定し,パラメータについては未知である場合のユニバーサル情報源符号化について扱う.その中でもベイズ符号は,ベイズ基準のもとで冗長度を最小にする符号として知られている.近年,非定常な情報源に対するベイズ符号の研究が数多く行われている.その一つに,一定区間では定常なパラメータを持つが,ある時点でパラメータの値が突然変化する情報源に対する研究がある.この情報源は個々の区間をみれば定常とみなすことができるが,パラメータの変化が複数回おこるため,全体としては非定常な情報源として扱われる.従来,この情報源に対し総変化回数が既知のもとで漸近的な平均冗長度の評価が行われている.しかし,厳密な評価については行われておらずユニバーサル性を持つ符号であるかについて正確な議論はされていない.また,より一般化された問題設定として,総変化回数が未知である場合を扱った研究もある.そのもとで有限時点での冗長度の評価が行われているが,漸近的な評価については行われていない.そのため,この情報源におけるベイズ符号の漸近的な性質についてはいまだ知られていない.そこで,本研究では区間で定常なパラメータを持つ非定常情報源に対し,総変化回数が未知のもとで漸近的な平均冗長度についての評価を行う.そのもとで,ある条件を満たすとベイズ符号がユニバーサル性を持つことを示す.

本稿では,センターが各ユーザーに個別情報を配り,ユーザー間の通信を必要としないしきい値鍵配送方式について考える.従来のしきい値鍵配送方式では,k人以下のユーザーが結託してもネットワーク全体の秘密は完全に守られ,k+1人以上のユーザーが結託してしまうと,ネットワーク全体の秘密が完全に漏れてしまう方式になっている.本研究では,た人以下のユーザーが結託してもネットワーク全体の秘密は完全に守られ,k+1人以上,k+d人未満のユーザーが結託すると,ネットワークの安全性は結託するユーザー数に対して線形に減少していき,た十d人以上のユーザーの結託で,ネットワーク全体の秘密が完全に漏れてしまう鍵配送方式を定義し,このときの各ユーザーが持つべき情報量の評価,構成法の提案を行う.

通信路の確率構造が未知であるユニバーサル通信路符号化の通信路容量を求める問題は従来から研究されている.Csiszarらはユニバーサル離散無記憶通信路符号化問題における通信路容量が入力確率分布と出力確率分布の相互情報量の最大値となることを示した.本稿で考える通信路はパラメトリックな確率構造を仮定し,パラメータ空間は既知であるがパラメータは未知な通信路である.この通信路に対してベイズ基準の下で最適な復号法を提案し,その復号法を用いてユニバーサル通信路容量を求める.

Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most. likely codeword, using the most reliable information set. where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total; compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.

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.

従来,決定木モデルを用いた予測(分類,判別)を行う場合,決定木生成アルゴリズムが用いられてきた.これらは,データが与えられたもとでのモデル選択アルゴリズムとみなすことができる.つまり,従来はデータが与えられたもとでモデルを一つ選択し,選択したモデルを用いて予測を行っているといえる.よって,予測誤り率に対して理論的な評価を行うのは非常に困難であった.そこで本研究では,平均予測誤り率を最小にする予測アルゴリズムを示す.そのためにまず,従来の決定木モデルをパラメトリックな確率モデルとして再定式化する.そのモデルを用いて,ベイズ決定理論にもとづく最適な予測アルゴリズムを示す.更に,モデルクラスを制約することで効率的に予測分布を計算するアルゴリズムについて述べる.

近年,Sequiturアルゴリズムや最頻digram統合法等のデータ系列の文法を用いたデータ圧縮法の研究が盛んに行われている.文法を用いた圧縮法では,データ系列を直接符号化するのではなく,データ系列を生成するような文法を構成し,それを符号化する.中村らによる最頻digram統合法では,データ系列を全て読み込み,連続する2記号であるdigramの出現頻度を求め,最頻digramをルールとする文法生成を行っている.これに対して,神田らは,この文法の符号化に算術符号を適用することを前提とし,算術符号の理想符号長を計算しながら符号長の観点から最適な文法を生成する手法を提案している.本研究では,神田らの手法と同様に算術符号の理想符号長を計算しながら文法生成を行うが,digramだけでなくより長く連続するN記号であるN-gramを考慮して文法生成を行う手法を提案する.またカルガリーデータに対して本手法を適用し,シミュレーションによる評価によって,その有効性を示す.更に系列長nのデータに対し提案手法の計算量及びメモリ量が神田らの手法と同様O(n)であることを示す.

代表的なユニバーサル符号であるZiv-Lempel(LZ)符号は,理論面だけでなく実用面からもより圧縮効果を高める修正アルゴリズムが数多く提案され,ユニバーサル性の証明や冗長度について議論されている.一方近年,実データに近い情報源を表現するモデルとして,言語アルファベット情報源や単語単位情報源が提案され,そのエントロピーレートが解析されている.また,LZ78符号は単語単位の定常エルゴード情報源に対して漸近最良であることがすでに示されている.単語単位の情報源に対するLZ78符号化として,(i)単語単位で増分分解を行う(ii)シンボル単位で増分分解を行うという2通りを考えることができる.これら2通りの方法でLZ78符号化を行う場合にどの程度の差が生じてくるのかという性能解析は興味深いテーマである.そこで,本稿では上記2通りのLZ78符号に基づく符号化法の平均冗長度について,その上界を求め,LZ78符号の有効性について考察を行う.その結果,(i)(ii)の2通りの方法ともその上界がO(1/log n)を達成することを示す.ここでnは入力系列長である.

情報源の確率モデルは既知であるが,そのパラメータは未知である場合の符号化法において,ベイズ符号はベイズ基準のもとで冗長度を最小にする符号である.また,ベイズ符号を構成するアルゴリズムとしてFSMX情報源に対する文脈木を用いたベイズ符号化法が提案されている.このアルゴリズムは文脈木を逐次的に生成することにより,最大深さが任意のFSMX情報源に対してベイズ符号を構成している.しかし,実用化を考えた場合,系列長とともに文脈木を生成することはメモリの点から困難である.本論文ではメモリ容量を低減した近似ベイズ符号化アルゴリズムを提案しその性能を評価する.

Ziv-Lempel (ZL) codes and Bayes codes are typical universal codes. An improved algorithm of the ZL code is widely used in compression software. On the other hand, practical use of Bayes codes is difficult due to the large amount of computation needed. However, a realizable algorithm in terms of computation effort has been constructed for the FSMX model group [9]. In this paper, an information source generating a sequence by word units is assumed as a model that can represent the probabilistic structure of actual data such as text data. The asymptotic compression performance of both codes is analyzed and evaluated for the information source class (information source for the block unit) with a constant (fixed) word length. As a result, it is found that Bayes code cannot directly be universal as a coding algorithm for symbol units. On the other hand, the ZL78 code can be directly universal. Also, a configuration method for the Bayes coding method is given for an information source with a block unit. (C) 2002 Wiley Periodicals, Inc.

In this paper, we consider the Bayesian approach for representation of a set of documents. In the field of representation of a set of documents, many previous models, such as the latent semantic analysis (LSA), the probabilistic latent semantic analysis (PLSA), the Semantic Aggregate Model (SAM), the Bayesian Latent Semantic Analysis (BLSA), and so on, were proposed. In this paper, we formulate the Bayes optimal solutions for estimation of parameters and selection of the dimension of the hidden latent class in these models and analyze it's asymptotic properties.

Based on techniques in information retrieval, we discuss methods for knowledge acquisition from documents composed of both fixed and free for-mats. The documents with the fixed format imply items such as those of selecting one from sentences, words, symbols, or numbers. While the documents with the free format are the usual texts. In this paper, starting with an item-document matrix and a term-document matrix used for the representation of a document set, we propose a new method for knowledge acquisition taking simultaneously into account of both fixed and free formats. A method based on the Probabilistic Latent Semantic Indexing (PLSI) model is used for clustering a set of documents. The proposed method is applied to a document set given by questionnaires of students which is taken for the purpose of faculty development. We show the effectiveness of the proposed method compared to the conventional method.

LDPC符号の代表的復号法であるsum-productアルゴリズムは事後確率(APP)復号に基づいて雑音が混入した受信系列に対して復号を行う。その際,尤度を計算する必要があるため,通信路のパラメータは既知であることを仮定している.しかし,現実の通信路を想定した場合,パラメータが既知であることは稀である.そこで,通信路雑音が隠れマルコフモデルに従うと仮定した上で,パラメータが未知の場合でもパラメータを推定しつつ復号を行う手法を提案する.その結果,パラメータが既知の場合と同程度の復号誤り確率を達成できることを示す.

符号間干渉(ISI)の補償器として著名なものにGodardブラインド等化アルゴリズムがあり,このアルゴリズムを改良する様々な研究がなされている.この等化アルゴリズムは非線形最適解を求めるものであり,等化パラメータが局所的最適解に陥ることが問題となっている.近年,K.DogancayとR.A.KennedyはGodardアルゴリズムを再定式化し,このアルゴリズムを線形最適化問題に帰着させた.その結果,よりロバストなパラメータ推定が可能となっている.本稿では,Dogancyay-Kennedyアルゴリズムについて雑音モデルを仮定し,等化パラメータの推定値の偏りを少なくする等化アルゴリズムを提案する.また,この等化法の効率よいアルゴリズムを提案する.

本稿で扱う分散協調問題は, 相関のある複数の情報を各エージェントがそれぞれ観測し, エージェント間で情報交換を行ったもとで, 各エージェントが個別に意思決定を行うといった問題設定とする.本稿では, 多端子情報理論におけるモデルを, 二人のエージェント間で情報交換する分散協調問題に適用し, ベイズ決定理論に基づいて定式化を行うことで, 対数損失に対してのベイズ最適な決定関数を導出した.また, そのときのベイズリスクが相互情報量の形で表現できることを示した.

本稿では, ベイズ決定理論に基づくモデル選択の漸近的性質について考察する.まず, モデル選択問題をベイズ決定理論に基づいて定式化する.その際, より現実的問題に対応できる形の一般的な損失関数を導入する.さらに, 一般的なモデル族を仮定して, この選択方法の選択誤り確率について, その上界の解析を試みる.

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

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.

キーワードを用いた文献検索システムでは、検索を高速化するために転置ファイルを利用することがある。本論文では転置ファイルの新たな圧縮・復号方式を提案する。提案方式の特徴は二段階で圧縮・復号を行うことと、符号のシンドロームを利用して圧縮することである。転置ファイルを数学的モデルで表現し、圧縮ファイル及び復号木を格納する二次記憶装置のメモリ量と復号の計算量によりシステムを評価した。評価基準を導く際にVG限界式を利用した。数値計算の結果、二つの評価基準はトレード・オフの関係にあることが分かった。一段階で圧縮する従来の方式に比べて、提案方式はメモリ量が増加するが、計算量の低減分が大きく提案方式が有効であることが示された。

データ系列が与えられた下でのパラメータの事後確率分布は, 適当な条件の下で漸近的に正規分布の形状をなす. この性質は漸近正規性とよばれている. 収束の強さという観点では, 概収束などでの導出がなされているが, 本稿では真の分布を想定せず, どのような系列に対しても一様な収束速度で成立するような漸近正規性を導出する. 一方, MDL規準を拡張したSC(Stochastic Complexity)はベイズ符号の符号長, もしくは最尤符号の全符号長を評価することで導出される. SCに対しては一様収束の意味で漸近式が解析されており, これはuniversal modelingの概念で本質的といえる. 本稿では一様収束での漸近正規性を導出することにより, 一様収束の意味でのSCの漸近式が直接導かれることを示す.

機械学習は情報の与えられ方によって例からの学習と質問からの学習に大別される．質問からの学習を考えた場合，現実のシステムでは質問戦略（どの例をどの順序で質問を行えばよいか）によって真の仮説を正しく同定する確率が変わるため，良い質問戦略を用いることが必要である．しかし従来の計算論的学習理論では多項式時間学習可能かどうかを判定することが重要であり，どの質問戦略が良いかまでは評価することができなかった．そこで本稿では質問戦略の評価を行うために質問からの学習問題を決定理論的に定式化し，学習成功基準と学習効率基準の一方を制約条件としたもとで他方を最適化する評価方法を提案する．さらに最適な質問戦略を効率良く求める分枝限定法の下界値の計算法を提案する．本研究は学習においてオラクルの負担を最小にすることを保証するという見地から有効な研究である．There are two main learning paradigms in machine learning.One is leaning from examples and the other is learning from queries.It s necessary in learning from queries to use good query strategy because the probability that the true hypothesis is learned depends on it.However,from the computational learning theory it is important to judge whether it can learn or cannot,and it cannot be decided which query strategy is good.In this paper,we formulate learning from queries by the decision theory and propose a method of evaluating query strategy,where under the conditon that one of learning criteria(success principle,efficiency principle) is restricted,the other is minimized.Furthermore,we propose a new lower bound required for the branch-and-bound algorithm which gets efficiently the optimal query strategy.This paper is an effective study from the viewpoint of guaranteeing that the computational work for an oracle is made the smallest in learning.

データ圧縮技術のなかで, 漸近的に最良の圧縮が可能であるLZ78符号がある.しかし, 従来のLZ78符号は, 符号化された入力列の一部分のみを復号する際, 常に符号化系列の先頭から復号を行わなければならない.そこで, 符号化系列を途中から復号する技術が必要である.LZ77符号に関しては, 岩田らによって, 部分的に復号可能なLZ77符号の修正符号がすでに提案されている.本論文では, LZ78符号を用いて, 辞書の古くなった節点を辞書から削除し参照しないことにより, 部分的な復号を可能にする新しい符号化法を提案する.

Y.Steinberg and M.GutanはLZ77に用いられるString Matchingを有歪み圧縮に応用したアルゴリズムを提案した.さらに小幡らはこのアルゴリズムを有限での性能を向上させるためのアルゴリズムを提案した.このアルゴリズムでは選択された系列から近い新たな符号語を辞書内に生成することにより離散無記憶情報源の場合はよい符号語を生成することができる.しかし, 記憶のある情報源の場合必ずもうまくいくとは限らない.そこで, 本稿ではマルコフ情報源に対し有効なアルゴリズムを提案し, シミュレーションによりその特性を考察する.

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 a parallel construction of the H original GLFSR(δ, 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 time. 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, prediction using side information is studied. This problem has been investigated as predictive inference in the field of Bayesian theory and as on-line learning in the field of learning theory. The prediction problem under consideration is to predict-log p(y mid x)using given side information x.It is regarded as universal coding given side information. The Bayes risk of the Bayes predictive inference and the maxmini risk correspond to the mutual information of a certain multi-terminal channel and its capacity, respectively. In a certain prediction model, I.e., a multi-terminal channel, the Bayes optimum prediction is derived. Moreover, the asymptotic forms of Bayes risk and maximin risk are shown. This maximin risk is regarded as a difficulty measure of predictive inference and learning.

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

本稿では, 階層 (入れ子) 構造のモデル族に対するベイズ決定理論に基づくモデル選択の一致性について考察する. これまで多く提案されている情報量規準による選択の中で, 例えばBICやMDLのように正しい構造を発見することを目的とする規準は一致性を持ち, AICのように予測を目的とする規準は一致性を持たないことが指摘されている. ここでの疑問は, AICの一致性の欠如は, その目的が予測であることに起因するのか?ということである. 本稿ではベイズ決定理論に基づくモデル選択を定式化し, その目的が真のモデルの推定である場合にも, 予測にある場合にも一致性をもつことを示す.

Concatenated codes have many remarkable properties from both the theoretical and practical viewpoints. The minimum distance of a concatenated code is at least the product of the minimum distances of an outer code and an inner code. In this paper, we shall examine some cases that the minimum distance of concatenated codes is beyond the lower bound and get the tighter bound or the true minimum distance of concatenated codes by using the complete weight enumerator of the outer code and the Hamming weight enumerator of the inner code. Furthermore we propose a new decoding method based on Reddy-Robinson algorithm by using the decoding method beyond the BCH bound.

計算論的学習理論のパラダイムの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を求めることを目的とする場合に, 余剰転送数の上界の評価が情報理論の視点から行われた。

トレリス符号を用いて有歪みデータ圧縮を行う場合、現実には全ての符号を探索することは困難であり局所的に探索せざるを得ない。一方、レート歪み理論より平均歪みを最小にする符号の持つ性質が与えられている。そこで本論文では、符号の探索においてできるだけ局所解に陥ることを避けるために、この性質を用いることを提案する。まず予備実験として拘束長が小さい場合に平均歪みを最小とする符号を求め、その性質を調べる。更に拘束長が大きい場合にこの性質を使うことの有効性をシミュレーションにより示す。

本稿では, ベイズ決定理論に基づくモデル選択の漸近的性質について考察する. まず, モデル選択問題の一つであるパラメータの変化位置検出問題を, ベイズ決定理論に基づいて定式化する. その際, より現実的問題に対応できる形の一般的な損失関数を導入する. さらに, 一般的なモデル族を仮定して, この選択方法の選択誤り確率の上界について, 解析を試みる.

L.Valiantによって提案されたPAC学習モデルやS.MuggletonらのU-Learningモデルでは, 事前分布を学習基準の評価に利用するか否かという違いはあるが, アルゴリズムが事前確率を利用しないという点は共通である. 一方, ベイズアルゴリズムは事前確率を利用したアルゴリズムであり, ベイズ流の最適性が保証される. しかし, 一般的に事後確率の計算や平均損失を最小にする決定を探索する手続きは, 計算量的に膨大である. 本稿はこれらの点を考慮し, ベイズアルゴリズムを考える場合にsample complexityだけでなくtime complexityも考えた学習モデルの枠組を導入する. このモデルでは分布族の複雑さと仮説の複雑さの両方によってcomplexityが決定される. このcomplexityの下で, ベイズ学習可能性という新しい概念を提案し, 典型的な概念クラスについて学習可能性を明らかにする.またその性質についても述べ, 有効性を示す.

A new soft-decision maximum-likelihood decoding algorithm is proposed, which generates a set of candidate codewords using hard-decision bounded-distance decoding. BS improving the generating method of input vectors for the bounded-distance decoding due to Kaneko et al., decoding time complexity is reduced without degradation of performance, The space complexity is dependent on the hounded-distance decoding.

1948年, C.E.Shannonは後に情報理論と呼ばれる理論体系を独りで構築した[Sha48]. その中で, 通信路符号化は情報源符号化と並んで情報理論の双壁をなしている. Shannonによる通信路符号化定理 [Sha48] は, その後 A.Feinstein[Fei54], R.M.Fano[fan61], R.G.Gallager[Gal65], A.J.Viterbi[Vit67], S.Arimoto[Ari73]らにより精密化され定量化されたが現在でも尚, 最も重要な結論であることには変わりない. しかも1967年のShannonら[SGB67]の論文以降本質的には何も変わっていない. さて, 通信路符号化は雑音のある通信路において, 符号化により高信頼化を図る問題を取り扱う. そして正の情報伝送速度 R で符号長 N を大とすることにより, 復号誤り確率 P(ε) を指数的に 0 に収束できる符号化が存在するという工学的に極めて重要な結論が導かれている. この P(ε) の 0 への収斂速度を与える信頼度関数に関する研究は, この分野の中心的話題である. 現在でも低情報伝送速度では信頼度関数の上界と下界との間に差があり, 真にきつい限界式は求まっていない. これは情報理論の最も基本的問題であるが, 未だ解決されていない. 漸近的距離比δ(R) がGilbert下界式[Gil52]を等式で満たすという Shannon ら[SGB67]の推測によれば, 削除誤り指数E_<ex>(R)が真の信頼度関数を与えるが, この推測に反例はないが証明もされていない. 1980年代, I.Csiszar と J.Korner[CK81], R.E.Blahut [Bla87]らにより情報理論の再構築が図られ, 通信路符号化に対し新しい視点や新しい解釈が与えられた. しかし上の未解決問題は依然として残されたままである. 一方, 代数学を背景にもつ符号理論は数多くの実用的な誤り訂正符号を与えてきた. 通信路符号化のもう一つの重要な問題は, ランダム符号化により証明された通信路符号化定理を非ランダムな構成的符号化により証明することである. 連接符号を用いた試み[DP82][Tho87]があるが, その信頼度関数の下界は連接符号化誤り指数[For66]には及ばない. 最近, 植松らにより連接符号化誤り指数に一致する代数的符号構成法が示されたことは注目に値する[UMN94]. なお, 通信路符号化定理で存在することが保証された最良符号を求めることも困難とされている[Bla87]. 以下では, 離散的無記憶通信路を仮定し, ブロック符号についてのみとり上げる. たたみ込み符号や連接符号の詳しい議論については, 筆者らの論文[AH90]を参照されたい.

最近, 確率モデルを特定せず, それらの混合をとって符号化関数とするベイズ符号が議論され, 効率的なアルゴリズムが提案されている. このベイズ符号の漸近的性質については, ClarkeとBarronがi.i.d.情報源に対して解析し, ベイズ符号の漸近的冗長度を示すと共に, 漸近的にミニマックス符号を達成する事前分布がJaffreys' priorであるという重要な事実を明らかとしている. しかし, i.i.d.情報源に限定していることの他にも, 通常我々が適用したい現実的なi.i.d.情報源にも厳密には適用できないケースがあるという問題点がある. 本稿ではClarkeとBarronの仮定した条件を緩め, より一般的な情報源に対し同様の結果が導かれることを示す.

本論文では重畳符号とその復号法について考察し,2元BCH符号に基づいて構成した高効率な重畳符号の具体例を示す.この例では復号アルゴリズムを工夫することにより,距離構造に関する従来の制限を緩和し,これによって高効率性を実現している.同程度の符号長を有し,かつ同程度の復号誤り確率を実現するという条件の下に,最適な重畳符号を探索し,復号誤り確率P_<hi>(c)=10^<-1>〜10^<-22>,符号長1023≦n≦16383の範囲で優れた符号化率を有する符号の構成が可能となることを明らかにする.

Recently, the high-speed data transmission techniques that have been developed for communication systems have in turn necessitated the implementation of high-speed error correction circuits. Parallel processing has been found to be an effective method of speeding up operations, since the maximum achievable clock frequency is generally bounded by the physical constraints of the circuit. This paper presents a parallel encoder and decoder architecture which can be applied to both binary and nonbinary cyclic codes. The architecture allows H symbols to be processed in parallel, where H is an arbitrary integer, although its hardware complexity is not proportional to the number of parallel symbols H. As an example, we investigate hardware complexity for a Reed-Solomon code and a binary BCH code. It is shown that both the hardware complexity and the delay for a parallel circuit is much less than that with the parallel operation of H conventional circuits. Although the only problem with this parallel architecture is that the encoder's critical path length increases with H, the proposed architecture is more efficient than a setup using H conventional circuits for high data rate applications. It is also suggested that a parallel Reed-Solomon encoder and decoder, which can keep up with optical transmission rates, i.e., several giga bits/sec, could be implemented on one LSI chip using current CMOS technology.

近年、盛んに行われているユニバーサル符号化法についての研究の一つに、ベイズ符号化法がある。ベイズ符号化法は統計的決定理論に基づいて構築されており、有限時点においてベイズ基準のもとで冗長度最小を目的に符号化確率を決定する。 最近提案された任意の深さのFSMX情報源に対するベイズ符号化法ではFSMX情報源を文脈木でとらえ、符号化確率を文脈木を用いて計算するが、逐次的に文脈木を生成していく方法であるため、系列長が長くなるにつれて莫大なメモリが必要となる。本稿ではまず、メモリに制限のある場合、限られたメモリの中での平均符号長の下限を示す。そして、メモリの制限に対応したベイズ符号化法を構成し、その性能評価を行う。

ユニヴァーサル符号にはZL(Ziv-Lempel)符号とベイズ符号とがある。ZL符号は符号化の時に、暗に情報源の確率構造を仮定していることが明らかにされ、また、ある三つの視点からZL符号とベイズ符号との関連が論じられている[2]。また、これまでの研究から圧縮率に関してはベイズ符号の方が優れ、計算量に関してはZL符号の方が優れていることが知られている。そこで、本稿では実験的なアルゴリズムを導入し、両符号の性能をシミュレーションによって考察する。

本稿では, MDL原理に基づく符号とベイズ符号の符号長の差を, ベイズ理論の面から解析し, その差を明らかにする. MDLが暗に事前分布を仮定し, ベイズ理論にその基礎をおいていることは, 以前から指摘されていた. 一方, 事前分布が仮定できるときに, そのもとでのベイズ最適な符号であるベイズ符号が提案されている. 同じ事前分布のもとでは, 最適化されているベイズ符号の優位性は自明のことともいえるが, その差に関してはこれまで解析がなされていなかった. そこで, 本稿では, MDLが暗に事前分布を仮定している点に着目し, 最適に構成されたベイズ符号との差を示し, 符号長に対するベイズ符号の優位性を明らかにする.

LSIの組み込み自己検査回路として線形帰還シフトレジスタ(LFSR)を用いた各種のシグネチャ解析器が提案されている。特に、被検査回路が複数の出力を持つ場合には、Pradhanらにより提案された多入力LFSR(MLFSR)がエイリアス確率を小さくする意味で優れていることが報告されている。しかし、検査回路への入力ビット数をδとすると、MLFSRの回路規模はδに対して線形以上に増大するため、並列に出力される信号数の多い回路の検査には適さない。ここでは、δビット入力のシグネチャ解析器をHδビット入力(Hは任意の整数)に並列化する方法を提案する。この並列化回路は、入力信号数を大きくしても回路規模が線形以上にはならないため、出力信号数の大きい回路の検査に適している。

This paper proposes a new formulation which minimizes the differential entropy for an optimal control problem. The conventional criterion of the optimal regulator control is a standard quadratic cost function E[M{x(t)}(2) + N{u(t)}(2)], where x(t) is a state variable, u(t) is an input value, and M and N are positive weights. However, increasing the number of the variables of the system it is complex to find the solution of the optimal regulator control. Therefore, the simplicity of the solution is required. In contrast to the optimal regulator control, we propose the minimum entropy control which minimizes a differential entropy of the weighted sum of x(t) and u(t). This solution is derived on the assumptions that the linear control and x(t)u(t) less than or equal to 0 are satisfied. As the result, the formula of the minimum entropy control is very simple and clear. This result will be useful for the further work with multi variables of simple control formulation.

巡回符号の複数の符号シンボルを並列に処理することが可能な並列符号器・復号器の構成について考察する。ここで提案する並列復号器は、従来の復号器におけるシンドローム計算回路と誤り位置検出回路を修正し、他の一部の回路を多重化することにより構成される。GF(2^8)上の(255,251) Reed-Solomon符号について検討結果、この並列符号器・復号器は、従来の符号器・復号器を複数個並列に使用した場合に比べて、かなり小さい回路規模で実現できることが明らかになった。

学習データから情報源の確率構造を学習する場合,その結果は学習データに依存するので,何らかの方法で学習データから真の構造に近い確率モデルを推定する必要がある.そのための方法として,適切な次数のモデルを選択する方法があり,AICやMDLなどの情報量規準が提案されている.AICは期待平均対数尤度最大のモデルを選択することにより,KL情報量の意味で真の構造に近い確率モデルを選択しようとする.MDLは,データの記述長とモデルの記述長の和を最小にするモデルを選択するという規準である.しかし,AICでは評価できない項を無視していることや一致性がないことが指摘されている.MDLではパラメータを量子化する部分が粗い議論であるために,記述長最小という評価規準は密には達成されていない.本稿では,情報源符号化において最近注目されているベイズ符号をモデル選択に応用することを考える.そして,ベイズ決定理論に基づき,次のシンボルを予測符号化したときのベイズ符号長を最小にするという意味で,漸近的に最適なモデルを選択する情報量規準を提案する.

Littlestoneは線形分離可能なブール関数(特に単調連言形,単調選言形)を対象として,リテラルの重み更新による学習アルゴリズムWINNOW1[3]を提案した.しかし計算論的な立場が強いため,重みの更新法についての理論的根拠が希薄であった.これに対し野村らは統計的決定論の立場から最適性を考慮した予測アルゴリズム,重み更新アルゴリズム[1]を提案した.本研究はこの立場に基づき,学習対象を非単調連言形・選言形のクラスまで拡張した場合の学習アルゴリズムを最初に提案する.さらに学習対象をブール関数全体のクラスに対応するアルゴリズムを示し,これらのアルゴリズムの最適性についてベイズ統計学の立場から明らかにする.最後に概念学習の枠組みに適用した場合について論じる.

異なる2種類の2元BCH符号を確率的手法に基づき重畳させることにより比較的単純な回路で優れたパフォーマンスが期待されることが具体例により明らかとなった.本稿ではその結果について考察し報告する.従来,明らかにされていたように確率的手法に基づいて構成された重畳符号は,簡単な復号アルゴリズム"Algorithm I"の適用ができるため復号器が簡単化できしかもパフォーマンスの大幅な改善が期待される[1].本稿では,同一の復号誤り確率およびほぼ同一規模の復号化回路,という条件の基に具体的な符号について解析した結果,従来の符号に比べ重畳符号は符号化効率が3倍程度にまで改善可能であることが確認された.また,雑音の多い通信路で効果的な有限符号長を持つ符号が多数存在することが明らかにされた.

最近,人工知能の学習の分野においては強化学習の研究が盛んに行われている.その中の主だった問題設定として,未知パラメータを含むマルコフ決定過程がある.これに関しては人工知能に限らず,統計,確率過程,OR,制御等多くの分野においても研究がなされてきた.本論においては,過去の研究の内,収束性の視点によるQ-Learnigと収益性の視点によるMartinのアルゴリズムを紹介すると共に,それらの視点をふまえた上でその折衷案的な視点によるアルゴリズムを提案する.

コンピュータ上で行うシミュレーションにおいて、疑似乱数はランダム性を表現するために最も有効な手段として様々な場面で取り込まれている。本論文では、シミュレーションで使用する疑似乱数を従来の統計学的検定手法の複数の検定法を一度に行える手法を情報源符号化で最近用いられているベイズ符号化アルゴリズムから導き出す。本論文はベイズ符号化からのアプローチではあるが、従来行われてきている情報理論的アプローチであるLempel-Ziv法などによる乱数であるかないかの単一的検定とは性質を異とし、ベイズ符号が推定する情報源の確率構造により、どの確率的性質が疑似乱数として不適切かまで解析可能である。

最近,情報圧縮分野におけるユニバーサル符号化問題において,ベイズ符号の研究が盛んに行われている.従来のFSMX情報に対するベイズ符号を実現するアルゴリズムでは,FSMX情報源を表現するための文脈木の深さが固定されていた.本稿では,文脈木の深さを可変とする新しく提案されたアルゴリズムについて圧縮に関する性能の確認および,パラメータの事前分布の相違による冗長度の違いを調査,検討する.

初期状態,状態数,遷移確率未知のある種の定常有限記憶情報源(FSMX)に対するベイズ冗長度基準にもとで最適な符号を構成する.またこの符号の符号化アルゴリズムを提案する.

従来,誤り訂正符号を用いて並列にアクセス可能なディスクにファイルを配置する方法が提案されている.この方法において,質問は属性によらない仮定がなされている.本報告では,属性間に偏りがあるときの属性の定義域の分割を考慮し,改善を行う.質問が属性によらないとき最適な配置となる,GF(p^m)上で構成されたReed-Solomon符号の構造を用い,そのシンボルを部分体のシンボルに展開することにより,定義域の分割数が異なる属性に対応したファイルの構成を行う.また,この方法の特徴を考察する.

帰納的学習においては,主に分類規則を学習対象とした研究がよく知られているが、この他に確率分布を学習対象とした研究も行われている.後者の研究分野の一つに,モデルベース診断における経験的知識を故障原因の確率分布として学習し,この分布を用いてテストを選択する診断システムの研究がある.これは,与えられたデータから推定木を生成しMDL基準で選択するという手法であるが、膨大な計算量がかかるため効率的な探索法が求められている.本研究では,MDL最小となる推定木を探索する効率的なアルゴリズムを提案し,提案アルゴリズムが従来の探索法の問題点を補っていることを示す.

与えられた例からその例を説明する一般的規則を導き出す手法が帰納学習である.その学習結果の知識表現法としては,形式言語や述語論理式,PROLOGProgramなど様々なものが考えられるが,本研究では事例を分類する知識表現である決定木を対象としている.決定木の構成法としてID3がJ.R.Quinlanによって提案されているが,木の生成過程の各段階で1つの属性のみに注目するので複数の属性の相関を捕らえきることができない.その結果,生成された規則の平均質問回数を最小にすることが保証されていない.そこで,木の生成過程の各段階で複数の属性を考慮するアルゴリズムを提案し,より効率的な決定木を構成する.

Valiantによって示された学習モデルでは,伝統的に学習可能性は事例の生起確率に独立であると仮定されている.この確率を利用し,仮説空間の複雑さの新しい尺度,メトリックを提案する.メトリックとは仮説間の識別の難しさを定量的に扱うもので,これを基に空間の複雑さを定義する.その1つが事前情報を利用した平均メトリックであり,仮説空間の複雑さを平均的に測る尺度となる.同様に,最悪の場合についての複雑さを測るのが,最小メトリックである.本研究では,これらの尺度とVC次元の関係を明らかにし,さらにsample complexityの上界を求める.この結果はVC次元が無限のクラスについても利用できる.

軟判定復号法において,限界距離復号法を複数回実行することにより,最尤復号を行う手法を知られている.しかし,最尤性を保証するために行う限界距離復号法の計算量が問題となる.一方,最尤復号を近似的に行う手法としてGMD復号法がよく知られており,近年このGMD復号法を効率的に行う手法が提案され注目されている.そこで本稿ではこのGMD復号法を複数回適用することにより,効率的な最尤復号法を行うアルゴリズムを提案する.また代数的復号法を複数回用いる場合,シンドロームの計算量を低減できることを示す.さらに,最尤の符号語をより早く生成する系列の生成方法を提案し,計算機シミュレーションにより計算量が大幅に低減されることを示す.なお,計算量は主として復号実行時間を占有する乗算回数で評価する.

近年,知識情報処理の分野では,エキスパートシステムの構築に際し,専門家からの知識獲得が問題となっている.これに対する手法として,例からのルールの学習が挙げられる.有限個の事例から得られた不確実な知識を用いて推論を行う場合,その知識に確信度を付与し,適切な信頼区間が与えられる.この手法で求めた知識と専門家から与えられた知識を合成することが可能であれば,より信頼性の高い推論が実現できる.そこで本稿では,専門家から与えられた知識ベースを,後から事例を追加することによって更新する手法を提案する.ただし,追加される事例には観測誤りが存在すると仮定する.

不確実な知識を確率論の観点より取り扱うモデルを提案し定式化する.すなわち,不確実な知識に対する帰納推論と演繹推論を情報源符号化に基づいてモデル化する.これを情報理論と統計的決定理論を用いて記述しその評価を可能とする.損失関数を与えたとき最適な推論方式は統計的決定関数により示される.その結果,不確定性下の意志決定を扱う経営工学の一つのアプローチを与えることができる.

Shannonの通信路符号化定理を構成的な符号化により証明できる符号は,現在のところ,Forney,Jr.の連接符号とEliasの繰返し符号の二つのクラスの符号のみが知られているにすぎない.にもかかわらず,これらの符号は同一の評価尺度による比較がなされていない.前者は,情報理論と符号理論の立場から信頼度関数による平均的な能力と構成的に与えられる符号の漸近的距離比による評価がなされている.一方,後者は構成的に与えられる符号に対してのみ,限られた条件のもとで,2元シンボル当りの復号誤り率がゼロに収束することが示されている.そこで本論文では,復号のために必要な計算量を考慮しながら,同一の評価尺度による連接符号と繰返し符号の比較を行い,連接符号が繰返し符号より優れていることを明らかにする.まず,両符号はともに復号のために必要な計算量が符号長の多項式オーダで実現可能であることを示す.この条件のもとで,漸近的距離比が非ゼロの繰返し符号を構成することはできないことを示す.更に,構成的に与えられている連接符号の一クラスであるJustesen符号と繰返し符号の一クラスであるEliasの繰返し符号の復号誤り確率の上界を符号長の関数とに分離する.そして,符号長を復号のために必要な計算量の関数として表し,両符号が同一の計算量,符号化比率で達成可能な復号誤り確率の上界を比較する.その結果,Justesen符号の復号誤り確率の上界はEliasの繰返し符号のそれに比べ,漸近的に優れていることを明らかにする.

Viterbiアルゴリズムを用いたARQ方式(V-ARQ)において,棄却した受信系列を次の復号に利用しようとするとき,尤度比検定で有意に選択されなかった部分を終端されたブロックの中から抜き出し,いくつかの再送ブロックの中から信頼できる部分だけを選りすぐって復号する考え方がある[2].このときにViterbiアルゴリズム用いて行われるトレリスの部分的消失判定は,Yamamoto[1]などの方式とは異なり,逐次的な検定の問題となる.本稿では,このようなVAで行われる逐次的な検定に対して解析を行う.[1]H.Yamamoto and K.Itoh,"Vitebi decoding algorithm forconvolutional codes with repeat request"IEEE Trans.Inf.Theory,vol.IT-26,pp540-547(Sep.1980).[2]新家,松嶋,平澤:"Viterbiアルゴリズムを用いた棄却情報累積型ARQ方式について"第16回情報理論とその応用シンポジウム予稿集,金沢(1990).

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

Plotkinによって提案された|u|u+v|構成法は既知のいくつかの符号を組み合わせて効率の良い新しい符号を得る有力な方法の1つとして知られている。ここでは先に筆者らによって提案されたPlotkin構成法を用いて得られた符号Cの誤り指数を求める。その結果、従来の単一段符号に比べ通信路容量以下の情報伝速度において、復号誤り確率の上界が小さい優れた符号が得られることを示す。通信路は2元入力加法的白色ガウス雑音通信路を仮定する。

LSIの故障検出やARQシステムなどにおいて,2元線形ブロック符号の見逃し誤り確率は評価基準として重要な役割を果たしている.ランダム符号化により2元線形ブロック符号の平均的な見逃し誤り確率は,符号長nのオーダで指数的にゼロに収束することが良く知られている.また,2元対称通信路の誤り確率p,0【less than or equal】p【less than or equal】1, 2としたとき,対称な重み分布を有する2元線形ブロック符号の見逃し誤り確率も,符号長nのオーダで指数的にゼロに収束することが示されている.そこで本論文では,対称な重み分布を有する繰り返し符号を構成し,これを誤り検出のみの符号として用いた際,単一段の対称な重み分布を有する符号のそれとの比較を行う.見逃し誤り確率は,符号長nのオーダで指数的にゼロに収束し単一段の符号と全く同様であることを示すことができる.そして誤り検出を行うために必要な計算の複雑さが,単一段の符号よりも簡単であることを明らかにする.

ARQ方式は,符号化された受信系列の信頼度が低いと受信側が判断した場合に,帰還通信路を用いて同一の情報を再送要求する方式である.この中で,信頼度が低いと判断した受信系列をすぐに捨るのではなく,様々な形で積極的に利用し,次に送られてくる受信系列の復号に役立てようとする考え方がある.遂次確率比検定に代表されるように,棄却した情報の累積は,次に送られてくる系列の信頼度に対して強力な判定を可能にする.本稿では,累積された棄却情報がに役だっていることを,ランダム符号化を用いて,理論的に可能な限り評価する.その方法として,符号長が十分大のとき,1度目の受信系列が棄却され,2度目の受信系列を受け取った時点での復号誤り確率と再送要求確率について,基本のアルゴリズムとして設定したARQと,同様の基準を設定した棄却情報累積型ARQとの間でForney流の帰還誤り指数を求め,考察を加えている.

自己想起型連想記憶はニューラルネットワークによる連想記憶モデルの中でも歴史的に最初に考案されたものである.従来,その能力について様々な研究が行われてきたが,記憶の想起過程におけるダイナミクスに対する解析はいまだ十分ではない.本研究では自己相関型連想記憶における荷重行列の性質について検討し,それに起因する想起不可能な状態を回避するための手法を明かにする.

本論文は,情報ネットワークの構築において,局を点に、回線を枝に対応させ,情報ネットワークをグラフで表現することにより,遅延すなわち枝パス数の小さい高信頼度情報ネットワークの新しい構成法をグラフ理論的アプローチにより効率的に行う研究を行ったものである.この視点は,情報ネットワーク全体の局数(ノード数)と,回線を設ける対地局数(次数)をパラメータにして,信頼性が高く(連結度最適)最大伝搬時間(直径)ができるかぎり小さいネットワークを構成するものである.従来,主として高信頼性に主眼が置かれ,遅延に対して犠牲が払われている.そこで本研究では,ある制約のもとで,従来方式より遅延を小さくするようなネットワーク構成法を提案し,その有効性を示す.

Shapiroのモデル推論においては,あらかじめ与えられた一階言語で表現可能なモデルだけが推論の対象となっているが,理論名辞まで含めたモデルを想定するのは,一般の概念学習などにおいては不自然な設定となる.また,理論名辞の生成,発見の問題は,機械学習にとって極めて本質的な問題であると考えられるが,非常に困難な問題であるといえる.理論名辞生成手法がいくつか提案されているが,そのモデルが目的の概念を極限同定出来るという保証がない.本研究においては,Shapiroのモデルを少し拡張し,理論名辞が生成されるようなモデルにおいても,目的の概念がある条件のもとで極限同定可能であること示す.

リードソロモン(Reed-Solomon:RS)符号は,ディジタル記憶・通信システムの分野を中心に幅広く実用化がなされている.また,数々の優れた性質を有するため,誤り訂正能力等に関する理論的研究も活発になされている.このRS符号は,最大距離分離(MDS)符号であるが完全符号ではないため,限界距離復号法による訂正能力以上の誤りを訂正できる可能性を有する.そこで本論文では,2値展開されたRS符号において,t+1シンボルの誤りが検出された場合,バースト誤りに対して潜在的な能力を十分に引き出すことが可能な手法を与える.すなわち,あるパラメータのRS符号を基底によって分割した系列それぞれが,BCH符号の符号語になることを利用し,それらの受信系列を重畳することにより,ソリッドバースト誤りの先頭若しくは末尾を含むシンボルを推定するアルゴリズムを提案する.その結果,GF(2^m)上での限界距離復号法による訂正能力を完全に保証し,かつGF(2)上で表現したソリッドバースト誤りに対して,これを上まわる訂正能力を引き出すことが可能となる.更に,この手法を高密度バースト誤り訂正に適用し,その有効性をも示す.

不確実性をもつ論理式で構成される仮説の帰納推論について考察する.著者らは有限個の事実系列からの帰納推論の問題と不確実性を含んだ演繹推論の問題に対して一階述語論理と情報理論を用いた統一的基礎体系より一連の研究を行ってきた.本論文ではこの2つの研究の流れを統合して不確実性をもつ論理式(ルール)で購成される仮説の帰納推論問題について 帰納と演繹を個別で論じるのではなく一連の情報処理過程として情報理論と決定理論の立場から考察を行う.有限個の事実を得た時点で 1)真の仮説を選択する問題 2)新たな論理式の予測を行う問題 3)事実系列を最小の記述長で表現する仮説を選択する問題の3つの評価基準から考察を行い それぞれの基準で最適な推論法を示し その相互の関係についても言及する。

本論文では 具体的な割練例系列から例外を許容する不確実な知識を学習する問題(確率的知識の学習)について検討している.入出力の系列からの学習の問題に限定すれば 確率的な関係をもつ入出力の系列から 各入力を前提にした各出力の条件付確率(確率的知識)を推定する問題として定式化できる.この問題を記述長最小基準から検討する場合に 状態分割の立場からの枠組みは既存のものである.本論文は その修正・拡張およびその際に生ずる問題について解決している具体的には まず系列が入出力の形式になっている前提を除去した一般的な場合を検討している.すなわち 多次元の属性値の確率的な因果関係を見いだす問題についてである.しかしながら 学習の対象を広げることによって 一般には学習の計算量は増カロする・本論文では この視点にたって学習の対象の広さと学習の計算量の相互関係を議論している.そして 学習の対象を若干狭めても学習の計算量を十分に低減させる方策について検討している.その一例として 問題を近似して学習対象をDendroid分布に限定した場合の記述長最小基準における最適解法を導出している.導出した学習アルゴリズムは C K Chowらのアルゴリズムに基づいているが 属性間の依存関係が単一の木構造になる仮定を排除する一般性がある.

　今年度目標とした各項目に対し、下記の結果を得た。１．データマイニング　遺伝的アルゴリズムとk-means法を用いたクラスタリング技法、属性間の関連を考慮した帰納推論について、それぞれ新しいアルゴリズムの提案と性能の評価を行った。いずれも日本経営工学会春季・秋季発表大会で報告した。また、大規模データベースにおける多値属性を考慮した相関ルール抽出法について検討し、従来２値の場合しか処理できなかったものを拡張した。結果は人工知能学会で発表した。２．分散直積ファイルのディスク配置問題　符号理論を応用した効率のよい配置法について検討した。Reed-Solomon符号を用いるとエラスティック（ファイルの数が大きくなる程、わずかな平均アクセス時間の増大を許容すれば大きくディスクの数を減らすことが可能）であることを示した。国際会議で報告した。３．情報検索システム　情報検索システムへの符号化技術の応用としては進展がなかった。近接分野の取り組みとして、これに近い視点からテキストマイニングについて取り上げた。新聞記事を対象にクラスラリングを効率よく行う方法、日本語のキーワード検索において効率よく合成語を見つけ出す方法について検討している。４．その他　符号理論のプロパーなテーマを取り上げた。Ａ＊アルゴリズムを用いて計算量を押えながら最ゆう復号を実行する方法、ＢＣＨたたみこみ符号の新しい構成法を提案し、電子情報通信学会に報告した。前者は論文にまとめ信学会に投稿した。

　本研究は符号化技術について（1）データ圧縮を行う情報源符号化（2）誤り訂正を行う通信路符号化について基礎的な考察と同時に情報システムの応用を図ったものである。（1）情報源符号化　（a）基礎的考察……マルコフ情報源に対し誤り伝播をおさえることができる符号化と、部分的に復号可能なZL符号の拡張について考察した　（b）応用……統計的モデル推定問題はユニバーサル情報源符号化の情報源モデルの推定と同じように考えることができる。ここでは、パラメータが一時間と共に変わるようなモデルが入力されたときのパラメータ変化量を推定する方法と、ベイズ符号の近似アルゴリズムを用いて木構造のモデル族の予測方法について考察した。（２）通信路符号化　（a）基礎的考察……2元BCH符号についてわずかな計算量の増大でBCH限界を越える復号法を示し、これを用いて近似最尤復号への適用を図った。また、たたみ込み符号を用いたARQ方式についてリスト復号を行うことにより従来の復号誤り確率，を低減する方法について考察した。　（b）情報検索における転置ファイルの圧縮について2段階符号化を行うことにより復号・検索が容易になる方法を示し評価した。また並列化したBCH符号化によりLSIの組込みテスト回路の性能を向上させる方式を示した。

本研究は符号化技術について符号理論、情報理論から考察しその応用を図ったものである。対象とする符号化技術は大別にデータ圧縮を行う情報源符号化と誤り訂正を行う通信路符号化である。　通信路符号化については通信符号の真の距離が増加する場合の条件とその復号法を与えている。また、ＢＣＨ符号の最小距離を越える復号法を示し軟判出復号法への応用を図っている。不均一誤り訂正符号についても軟判定復号法を示し誤り確立の低減する方法を明らかにしている。　情報源符号化についてはTunstall符号やＦＧ符号の改良を行い圧縮効率をなるだけ低下させないで途中からの復号を可能とする方法、歪を許した圧縮のアルゴリズムを明らかにし実データに応用したときの評価を行っている。また情報源符号化の応用として、木構造をもつデデuの学習アルゴリズムに用い計算量低減を図っている。研究成果の発表1997年５月"On the minimum distance of binary concalenaled codes" IFICE Trons. E80-A, May 1997. pp.922-923.“An improvement of soft-decision maximum likelihood decoding algorizhm using hand-decision bounded distance decoding,”IEEE Trons. IT-43, July 1997. PP. 1314-1319“Berlekamp-Massey アルゴリズムを用いたＢＣＨ限界を越える復号法の計算量について”、信号論、J80-A、pp. 1554-1558, 1997, 9.1997年11月“On the minimum distance of concatenated cosse and decoding method up to the true minimum distance”, IEICE, Tromo. E80-A, pp. 2111-2116 Nov. 1997.

　本研究は符号化に関する基礎的・応用的研究に関するものである。基礎的研究としては、最尤復号あるいは近似的最尤復号を実行するアルゴリズムの提案とその評価に関するものがある。最尤復号は復号誤り確率を最小にするが計算量は大きい。これを近似的に実行すると、どの程度の符号誤り確率の変化になるかを評価している。また、連接符号の最小距離の下界を改良する符号化の条件とその復号法を明らかにした。GMD復号法と拡張した方法により、実際の最小距離によりきまる誤り訂正可能個数までの訂正ができることを示した。この他、符号化を用いた判定帰還方式について棄却した受信条列を有効に利用し信頼度を向上させる方式 およびViterbi復号法を用いたたたみ込み符号の固定遅延復号について提案・評価結果を明らかにした。いずれも誤り指数を導出し、同時にシュミレーションによりその動作の確認を行った。　応用的研究としては、高速化を目的とした巡回符号の符号器・復号器の並列化方式の提案とその解析を行った。この構成法を用いてFTCにおけるLSIのビルトインテストに応用する場合を考察し、回路規模を小さくできることを明らかにした。　この他、情報源符号化において受信系例の途中から復号する方式、歪のある情報圧縮における代表元を記憶するリスト作成のアルゴリズムを改良する方式などを提案し、それぞれの性格を評価した。情報源符号化のアルゴリズムと性質を利用した知識情報処理における帰納推論への応用を図った。知識表現として決定木を用いるとき、マルコフモデルを推定しモデル選択を行う問題に応用し有効性を確認した。

本研究は情報理論・符号理論に共通の符号化技術に関するもので基礎的研究と応用的研究に分けられる。前者は誤り訂正で実行する新しいアルゴリズムの提案とその評価に関するものであり，後者は主として誤り検出符号のフォールトトレラントシステムの応用である。（1）基礎的研究 誤り訂正を実行する符号アルゴリズムを扱っている。まず，バースト誤りが生起するとき，線形巡回符号の性質を用いて受信系列をずらしたものと重量することにより，誤りを打ち消し合い比較的簡単なアルゴリズムで強力な能力を引き出せることを示した。また，最小距離が偶数の連接符号において，内部符号の復号結果を利用することにより従来検出に止まっていた符号法を改良できることを示した。さらに，線形ブロック符号において，最尤復号をトレリス構造を用いて効率良く実行できることを示した。この他，情報源符号化についても考察している。Ziv-Lempel符号の符号化アルゴリズムを逆にたどることにより，実行しているパラメータ推定の方法を解明した。また，歪のあるデータ圧縮に歪のないデータ圧縮のアルゴリズムを適用して，従来よりさらに圧縮率を上げることが可能であることを示した。（2）応用的研究 LSIなどのBuilt In Self Testでは回路に組み込まれたテスト回路により誤りを検出する。このとき，シグネチャとよぶデータ圧縮技術が用いられる。並列化可能な誤り検出符号の符号器構成を与えることによりテストが高速化できることを示した。また，符号化技術の知識情報処理への応用として，不確実な知識に新しい観測データを加え高信頼化を図るのに有効な判定・評価方法や，パターン認識などに用いられる事後確率の計算法を効率良く実行できる方法を示した。