2022/01/28 更新

写真a

ホリイ シュンスケ
堀井 俊佑
所属
附属機関・学校 グローバルエデュケーションセンター
職名
准教授

学内研究所等

  • 2021年
    -
    2022年

    データ科学センター   兼任センター員

  • 2021年
    -
    2022年

    大学総合研究センター   兼任センター員

学歴

  •  
    -
    2009年

    早稲田大学   理工学研究科  

  •  
    -
    2004年

    早稲田大学   理工学研究科  

  •  
    -
    2004年

    早稲田大学   理工学研究科  

  •  
    -
    2004年

    早稲田大学   理工学研究科  

学位

  • 博士

 

研究分野

  • 知能情報学

研究キーワード

  • 情報理論、符号理論、統計的学習理論

論文

  • Model Selection of Bayesian Hierarchical Mixture of Experts Based on Variational Inference

    飯窪裕二, 堀井俊佑, 松嶋敏泰

    2019 IEEE International Conference on Systems, Man, and Cybernetics (SMC2019)    2019年10月  [査読有り]

  • Distributed Stochastic Gradient Descent Using LDGM Codes

    堀井俊佑, 吉田隆弘, 小林学, 松嶋敏泰

    Proceedings of 2019 IEEE International Symposium on Information Theory (ISIT2019)     1417 - 1421  2019年07月  [査読有り]

    DOI

  • A Study on Analytical Properties of Bayesian Experimental Design Model based on an Orthonormal System

    Yoshifumi Ukita

        22  2017年11月  [査読有り]

  • Bayesian Sparse-Smooth Modeling and Variational Inference

    Shunsuke Horii

    Proc. of Bayes on the Beach 2017     16  2017年11月  [査読有り]

  • Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channel

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E99A ( 12 ) 2170 - 2178  2016年12月  [査読有り]

     概要を見る

    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.

    DOI

  • Sum-Product アルゴリズムに基づく疎信号のサポート復元に関する一考察

    堀井俊佑

    第39回情報理論とその応用シンポジウム予稿集     330 - 335  2016年12月

  • Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channels

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    2016 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY     1944 - 1948  2016年  [査読有り]

     概要を見る

    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.

  • A Note on Support Recovery of Sparse Signals using Linear Programming

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    PROCEEDINGS OF 2016 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2016)     270 - 274  2016年  [査読有り]

     概要を見る

    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.

  • A new latent class model for analysis of purchasing and browsing histories on EC sites

    Masayuki Goto, Kenta Mikawa, Shigeichi Hirasawa, Manabu Kobayashi, Tota Suko, Shunsuke Horii

    Industrial Engineering and Management Systems   14 ( 4 ) 335 - 346  2015年12月  [査読有り]

     概要を見る

    The electronic commerce site (EC site) has become an important marketing channel where consumers can purchase many kinds of products
    their access logs, including purchase records and browsing histories, are saved in the EC sites' databases. These log data can be utilized for the purpose of web marketing. The customers who purchase many product items are good customers, whereas the other customers, who do not purchase many items, must not be good customers even if they browse many items. If the attributes of good customers and those of other customers are clarified, such information is valuable as input for making a new marketing strategy. Regarding the product items, the characteristics of good items that are bought by many users are valuable information. It is necessary to construct a method to efficiently analyze such characteristics. This paper proposes a new latent class model to analyze both purchasing and browsing histories to make latent item and user clusters. By applying the proposal, an example of data analysis on an EC site is demonstrated. Through the clusters obtained by the proposed latent class model and the classification rule by the decision tree model, new findings are extracted from the data of purchasing and browsing histories.

    DOI

  • 多値ランダム回答法における逐次型ベイズ推定法について

    須子統太

    第38回情報理論とその応用シンポジウム予稿集    2015年11月

  • シンボルペア通信路における線形符号の線形計画復号法に関する一考察

    堀井俊佑

    第38回情報理論とその応用シンポジウム予稿集    2015年11月

  • ランダム回答法におけるオンラインベイズ推定について

    須子統太

    信学記号   COMP2015-23   7 - 11  2015年10月

  • シンボルペア通信路における2元線形符号の線形計画復号法について

    堀井俊佑

    信学技報   Vol. IT2015-34   1 - 6  2015年09月

  • プライバシー保護機能を持つ分散型正則化最小二乗法について

    須子統太

    第37回情報理論とその応用シンポジウム予稿集     300 - 305  2014年12月

  • パラメータが複数存在するLinear Banditに関する一考察

    堀井俊佑

    第37回情報理論とその応用シンポジウム予稿集     506 - 511  2014年12月

  • Parallel Concatenation of Polar Codes and Iterative Decoding

    Akira Kamatsuka

    Proc. of the 2014 International Symposium on Information Theory and its Applications     347  2014年10月  [査読有り]

  • プライバシー保護機能を持つ線形回帰モデルにおける最小二乗推定量の分散計算法について

    須子統太

    日本経営工学会論文誌     78 - 88  2014年07月  [査読有り]

  • プライバシー保護機能を持つ線形回帰モデルにおける最小二乗推定量の分散計算法について

    須子 統太, 堀井 俊佑, 小林 学, 後藤 正幸, 松嶋 敏泰, 平澤 茂一

    日本経営工学会論文誌   65 ( 2 ) 78 - 88  2014年

     概要を見る

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

    CiNii

  • A Note on the Correlated Multiple Matrix Completion based on the Convex Optimization Method

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    2014 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC)   2014-January ( January ) 1618 - 1623  2014年  [査読有り]

     概要を見る

    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.

    DOI

  • A Note on the Correlated Multiple Matrix Completion based on the Convex Optimization Method

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    2014 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC)     1618 - 1623  2014年  [査読有り]

     概要を見る

    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.

  • 凸最適化に基づいた相関のある複数行列の同時補完に関する一考察

    堀井俊佑

    第36回情報理論とその応用シンポジウム予稿集     175 - 180  2013年11月

  • Iterative multiuser joint decoding based on ADMM

    S. Horii, T. Suko, T. Matsushima, S. Hirasawa

    2013 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013 - Proceedings     1097 - 1100  2013年

     概要を見る

    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.

    DOI

  • Iterative multiuser joint decoding based on ADMM

    S. Horii, T. Suko, T. Matsushima, S. Hirasawa

    2013 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013 - Proceedings     1097 - 1100  2013年  [査読有り]

     概要を見る

    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.

    DOI

  • MIMO通信路に対するLDPC符号の線形時間ADMM復号

    小林学

    第35回情報理論とその応用シンポジウム予稿集     201 - 206  2012年12月

  • プライバシー保護を目的とした回帰分析の拡張について

    須子統太

    第35回情報理論とその応用シンポジウム予稿集     562 - 567  2012年12月

  • 木構造を仮定した信号に対する拡張ラグランジュ法に基づいた圧縮センシングについて

    堀井俊佑

    第35回情報理論とその応用シンポジウム予稿集     320 - 325  2012年12月

  • プライバシー保護を目的とした線形回帰モデルにおける最小二乗推定量の分散計算法について

    須子統太

    電子情報通信学会研究技術報告   Vol.IBISML2012-49   107 - 111  2012年11月

  • プライバシー保護を目的とした線形回帰モデルにおける最小二乗推定量の分散計算法について(第15回情報論的学習理論ワークショップ)

    須子 統太, 堀井 俊佑, 小林 学, 後藤 正幸, 松嶋 敏泰, 平澤 茂一

    電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習   112 ( 279 ) 107 - 111  2012年10月

     概要を見る

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

    CiNii

  • 多重アクセス通信に対する双対分解法に基づいた線形計画復号法(誤り訂正符号,一般)

    堀井 俊佑, 松嶋 敏泰

    電子情報通信学会技術研究報告. IT, 情報理論   112 ( 215 ) 53 - 58  2012年09月

     概要を見る

    2元線型符号を用いた多重アクセス通信路に対して,双対分解法に基づいた線形計画復号法を提案する.2元線型符号の最尤復号問題に対して,線形計画復号法はsum-product復号法に近い復号性能を持ち,更により理論的に強い保証が得られる復号法であり,干渉通信路や多重アクセス通信路など様々な通信路上での復号問題に応用されている.しかし,線形計画復号法は復号の際に線形計画問題を解く必要があり,一般的に線形計画法を解くのに必要な計算量は変数・制約の数に対して多項式オーダとなるため,Sum-Product復号法等の復号法と比べて復号に多くの時間を要するという問題がある.そこで,シングル-ユーザの無記憶通信路上での復号問題に対しては,様々な効率的な復号法に関する研究が数多くされている.特に,双対分解に基づいた復号法は符号長の長いLDPC符号に対して有効であることが先行研究により解明されている.本研究では,これらの研究を拡張し,多重アクセス通信路に対する復号問題に対する,双対分解に基づいた効率的な線形計画復号法を提案する.

    CiNii

  • 多重アクセス通信に対する双対分解法に基づいた線形計画復号法

    堀井俊佑

    電子情報通信学会研究技術報告   Vol.IT2012-40   53 - 58  2012年09月

  • マルチコンピュータシステムにおける線形計画法に基づく故障診断(研究速報)

    小林 学, 堀井 俊佑, 高畠 俊徳, 平澤 茂一

    電子情報通信学会論文誌. A, 基礎・境界   95 ( 4 ) 375 - 378  2012年04月

     概要を見る

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

    CiNii

  • マルチコンピュータシステムにおける線形計画法に基づく故障診断

    小林学

    電子情報通信学会論文誌,基礎・境界   Vol.J95-A ( No.4 ) 375 - 378  2012年04月  [査読有り]

  • Fault Diagnosis Algorithm in Multi-Computer Systems based on Lagrangian Relaxation Method

    Shunsuke Horii, Manabu Kobayashi, Toshiyasu Matsushima, Shigeichi Hirasawa

    2012 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2012)     712 - 716  2012年  [査読有り]

     概要を見る

    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.

  • The Optimal Key Estimation of Stream Ciphers and Its Approximation Algorithm Based on a Probabilistic Inference

    Yuji Iikubo, Shunsuke Horii, Toshiyasu Matsushima

    2012 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2012)     531 - 535  2012年  [査読有り]

     概要を見る

    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.

  • Fault Diagnosis Algorithm in Multi-Computer Systems based on Lagrangian Relaxation Method

    Shunsuke Horii, Manabu Kobayashi, Toshiyasu Matsushima, Shigeichi Hirasawa

    2012 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2012)     712 - 716  2012年  [査読有り]

     概要を見る

    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.

  • The Optimal Key Estimation of Stream Ciphers and Its Approximation Algorithm Based on a Probabilistic Inference

    Yuji Iikubo, Shunsuke Horii, Toshiyasu Matsushima

    2012 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2012)     531 - 535  2012年  [査読有り]

     概要を見る

    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.

  • A Note on Linear Programming Based Communication Receivers

    Shunsuke Horii

    Proc. of 3rd International Castle Meeting on Coding Theory and Applications     141 - 146  2011年09月  [査読有り]

  • PUFを利用した認証に対する統計的モデル化に関する一考察(フレッシュマンセッション,一般)

    石井 智, 吉田 隆弘, 堀井 俊佑, 松嶋 敏泰

    電子情報通信学会技術研究報告. IT, 情報理論   111 ( 142 ) 19 - 24  2011年07月

     概要を見る

    近年,デバイス内の不揮発性メモリに秘密情報を格納しておくことは,物理破壊攻撃やサイドチャネル攻撃等によって,秘密情報を漏洩してしまう危険性があると指摘されている.その解決法としてPhysical Unclonable Functions(PUF)が提案された.現在,PUFを利用した様々な暗号方式が提案されているが,その中でも代表的な暗号方式として認証が挙げられる.本研究では,PUFのチャレンジに対するレスポンスを確率分布として定義し,PUFを利用した認証を2値仮説検定問題として定式化を行い,認証者の認証誤り確率及び攻撃者のなりすまし攻撃成功確率を定義する.この時,PUFを利用した認証において認証誤り確率を0とした時のなりすまし攻撃成功確率の下界を導出する.また,半導体上に形成されるシリコンPUFの一つであるアービターPUFのチャレンジに対するレスポンスを具体的な確率分布で表現する.この時,認証誤り確率を0とした時のなりすまし攻撃成功確率の下界をシミュレーションにより導出し,アービターPUFの安全性について考察を行う.

    CiNii

  • 確率推論アルゴリズムに基づくストリーム暗号の鍵推定に関する一考察(フレッシュマンセッション,一般)

    飯窪 祐二, 堀井 俊佑, 松嶋 敏泰

    電子情報通信学会技術研究報告. IT, 情報理論   111 ( 142 ) 7 - 12  2011年07月

     概要を見る

    共通鍵暗号の一種であるストリーム暗号は,鍵を擬似乱数生成器に入力することで得られる鍵系列と平文系列との排他的論理和をとることで暗号文系列を生成する暗号方式である.本研究では,ストリーム暗号への攻撃を統計的決定理論の枠組みから鍵推定問題として定式化し,べイズ基準に基づく最適な鍵推定方法について考える.また実際に用いられている擬似乱数生成器について確率モデルで表し,グラフィカルモデルで表現することで確率推論アルゴリズムに基づく鍵推定アルゴリズムを提案する.提案したアルゴリズムについてはシミュレーションによる評価を行い,ストリーム暗号の安全性について考察を行う.

    CiNii

  • 確率推論アルゴリズムに基づくストリーム暗号の鍵推定に関する一考察

    飯窪裕二

    電子情報通信学会研究技術報告   Vol.IT2011-11   7 - 12  2011年07月

  • PUFを利用した認証に対する統計的モデル化に関する一考察

    石井智

    電子情報通信学会研究技術報告   Vol.IT2011-11   19 - 24  2011年07月

  • A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

    Shunsuke Horii

    IEICE Trans. Fundamentals   Vol.E94-A ( No.6 ) 1230 - 1237  2011年06月  [査読有り]

     概要を見る

    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.

    DOI

  • A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E94A ( 6 ) 1230 - 1237  2011年06月  [査読有り]

     概要を見る

    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.

    DOI

  • 線形計画法に基づいたファクターグラフ上の推論アルゴリズムに関する一考察

    堀井 俊佑, 松嶋 敏泰, 平澤 茂一

    電子情報通信学会技術研究報告. IT, 情報理論   110 ( 363 ) 55 - 60  2011年01月

     概要を見る

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

    CiNii

  • 線形計画法に基づいたファクターグラフ上の推論アルゴリズムに関する一考察

    堀井俊佑

    電子情報通信学会研究技術報告   Vol.IT2010-63   55 - 60  2011年01月

  • A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E93A ( 11 ) 1912 - 1917  2010年11月  [査読有り]

     概要を見る

    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

    DOI

  • A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes

    Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E93A ( 11 ) 1912 - 1917  2010年11月  [査読有り]

     概要を見る

    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

    DOI

  • Maximum Likelihood Detection for DS-CDMA using Grobner Bases

    Shunsuke Horii

    第33回情報理論とその応用シンポジウム予稿集     489 - 493  2010年11月

  • 複数の相関のある情報源に対するベイズ符号化について

    須子統太

    第33回情報理論とその応用シンポジウム予稿集     759 - 763  2010年11月

  • 2元線形符号を用いた多重アクセス通信路に対する線形計画復号について(LDPC符号,一般)

    堀井 俊佑, 松嶋 敏泰, 平澤 茂一

    電子情報通信学会技術研究報告. IT, 情報理論   110 ( 205 ) 31 - 36  2010年09月

     概要を見る

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

    CiNii

  • Linear Programming Decoding of Binary Linear Codes for Multiple Access Channel

    Shunsuke Horii

    電子情報通信学会研究技術報告   Vol.IT2010-39   31 - 36  2010年09月

  • Bayes Universal Source Coding Scheme for Correlated Sources

    Tota Suko

    Proc. of the 1st IEEE African Winter School on Information Theory and Communications     27  2010年06月  [査読有り]

  • サービスの開始と終了を考慮したWebトラヒックの非定常Poisson過程によるモデル化について

    小泉 大城, 堀井 俊佑, 松嶋 敏泰

    電子情報通信学会技術研究報告(IN2009-201)   109 ( 449 ) 343 - 347  2010年03月

  • A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes

    Shunsuke Horii

    Proc. of 2010 International Workshop on Nonlinear Circuits, Communication and Signal Processing     321 - 324  2010年03月  [査読有り]

  • サービスの開始と終了を考慮したWebトラヒックの定常Poisson過程によるモデル化について

    小泉大城

    電子情報通信学会研究技術報告   Vol.IN2009-201   392 - 396  2010年03月

  • 分枝カット法に基づいた線形符号の復号法に関する一考察

    堀井俊佑

    第32回情報理論とその応用シンポジウム予稿集     66 - 70  2009年12月

  • A Note on the Iterative Inference Cancellation and Decoding for Coded CDMA

    Shunsuke Horii

    第31回情報理論とその応用シンポジウム予稿集     66 - 70  2008年10月

  • Multiuser detection algorithm for CDMA based on the belief propagation algorithm

    Shunsuke Horii, Tota Suko, Toshiyasu Matsushima, Shigeichi Hirasawa

    IEEE International Symposium on Spread Spectrum Techniques and Applications     194 - 199  2008年  [査読有り]

     概要を見る

    Optimum detection for the multiuser code-division multiple-access channel is prohibitively complex. This paper considers new iterative multiuser detection algorithm based on the belief propagation algorithm. Previously, the idea to apply the belief propagation algorithm to multiuser detection problem was suggested , however, it was believed that to apply the belief propagation algorithm to the detection problem is impossible because it requires an exponentially large amount of computation. It was the only fact that the parallel interference canceller is derived as an approximation of the belief propagation. In this paper, we show that the belief propagation algorithm can be applied to the detection problem by converting the factor graph structure. Performance of the detector based on the belief propagation algorithm is better than that of the parallel interference canceller. © 2008 IEEE.

    DOI

  • 盗聴・改ざんに対して耐性を持つネットワーク符号化について

    堀井俊佑

    第30回情報理論とその応用シンポジウム予稿集     742 - 745  2007年11月

  • 画像に対する状態表現を用いたモデル化と無歪み符号化

    西村信哉

    第30回情報理論とその応用シンポジウム予稿集     392 - 396  2007年11月

  • 変動要因を考慮した非定常ポアソンモデルに関する一考察

    鈴木晃一

    電子情報通信学会技術研究報告   vol. 106, no. 524 ( IN2006-176 ) 83 - 88  2007年02月

  • Multiuser Detection Algorithms for CDMA based on the Message Passing Algorithms

    Shunsuke Horii

    IEICE Tech Rep. substituted for Proc. of 2006 Hawaii, IEICE and SITA Joint Conference on Information Theory (HISC'06)    2006年05月

  • A Note on Multiuser Detection Algorithms for CDMA based on the Belief Propagation

    Shunsuke Horii

    電子情報通信学会研究技術報告   Vol.IT2007-26   7 - 12

▼全件表示

書籍等出版物

  • 統計リテラシーα -データの整理- 2015年度版

    堀井俊佑( 担当: 単著)

    早稲田大学出版部  2015年04月

Misc

  • 確率伝搬法に基づく疎信号のサポート復元に関する一考察 (情報理論)

    堀井 俊佑, 松嶋 敏泰, 平澤 茂一

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   116 ( 33 ) 19 - 24  2016年05月

    CiNii

  • Iterative Multiuser Joint Decoding based on Augmented Lagrangian Method (情報理論)

    HORII Shunsuke, SUKO Tota, MATSUSHIMA Toshiyasu, HIRASAWA Shigeichi

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   113 ( 228 ) 13 - 17  2013年09月

     概要を見る

    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.

    CiNii

共同研究・競争的資金等の研究課題

  • ネットワークの多様化が経済と心理に及ぼす影響-計量・行動経済学と理系の融合研究-

    研究期間:

    2018年04月
    -
    2023年03月
     

  • スパースモデリングとベイズ決定理論に基づいた因果推論手法の構築

    研究期間:

    2019年04月
    -
    2022年03月
     

     概要を見る

    データ分析から得られた知見を使い,何らかの行動をした場合の結果を統計的に分析する方法として統計的因果推論の研究が注目を浴びている.本研究では特に因果ダイアグラム・構造方程式モデルに基づいた統計的因果推論を扱う.本研究では「介入効果をベイズ最適に推定する場合の有効性はどの程度か?」及び「ベイズ的スパースモデリングの考え方を応用することで,ベイズ最適な介入効果推定を効率的に近似計算することは可能か?」という2つの問いに対し,構造的因果推論,機械学習,最適化理論,ベイズ統計学,統計的決定理論,スパースモデリングの分野の知見を融合したアプローチによって,肯定的な回答を与えることを目指す.本研究の目的は,統計的因果分析における因果効果の推定問題をスパースモデリング・ベイズ統計学・決定理論に基づいてモデル化し,ベイズ最適な決定法,及び効率的な近似アルゴリズムの構築と解析を行うことであった.本研究の予備研究として,真の介入効果と推定介入効果の間の距離をカルバック・ライブラー距離で計る場合のベイズ最適な推定量を導出していたが,その研究の拡張として,平均介入効果の推定問題を扱い,二乗誤差損失を考えた場合のベイズ最適な推定量を導出した.一般的に介入効果を推定する場合,まず変数間の関係性を表す因果ダイアグラムを推定し,推定された因果ダイアグラムのもとで介入効果を推定するという二段階のアプローチがとられるが,本研究で提案した推定法は,各因果ダイアグラムのもとで推定した介入効果の推定量を,因果ダイアグラムの事後確率で期待値をとるというものになる.これにより,サンプルサイズが小さい場合でも平均的に推定精度の良い推定が可能となることを示した.また,操作変数を利用した因果推論の研究を行った.操作変数とは,処置変数と相関を持ち,目的変数とは処置変数を通して以外では相関を持たない変数であり,操作変数を利用した因果推論は経済学の分野で盛んに研究されている.操作変数は除外制約という制約を満たしている必要があるが,この制約はデータからのみでは検証することが出来ない.本研究では,除外制約を満たさない可能性が数多くあるという状況を考え,そのような場合でも効率的に因果推論が可能な手法を構築した.予定では,構造的因果推論に対するベイズ最適な推定法の性質の解明について,既に行っていた予備研究を拡張し,ベイズ的スパースモデリングによるモデル化について,文献調査や手法構築を行う予定であった.この2点について,計画通り研究を遂行し,学会発表により成果を公表できている.2020年度と2021年度は,まず2019年度に行った研究を論文としてまとめる.2019年度に構築した最適なアルゴリズムは,変数の数が多くなると,計算量的に計算が困難になるという問題がある.この問題を解決するために,MCMC法や変分ベイズ法などを応用し,効率的近似アルゴリズムを構築する予定である

  • 空間的分析と時間的制御を融合した、次世代商品推薦システムのための基礎理論の構築

    研究期間:

    2016年04月
    -
    2019年03月
     

     概要を見る

    従来から商品推薦システムでは、同じクラスに属する顧客は同様の商品を購入すると仮定して、顧客や商品の類似度に関する分析結果を商品の推薦に利用している。本課題では、顧客や商品の類似度に関する分析を空間的分析と呼んでいる。また、商品を推薦する本来の目的は売上高の最大化であり、目的を達成するためには商品の推薦と推薦後の顧客の行動(購入/未購入)を時間軸でとらえて分析し、顧客を購買行動へ誘導するような商品を推薦する必要がある。本課題では、このような顧客の誘導を時間的制御と呼んでいる。本課題では、空間的分析と時間的制御を融合した商品推薦問題において、マルコフ決定過程を用いて定式化し、売上高を最大化する次世代商品推薦システムのための基礎理論を構築することを目的としている。今年度は従来技術に関する調査・分析を実施後に、顧客が属するクラスが時間の経過に伴って変化するような顧客クラスのモデルをマルコフ連鎖によって表現した。従来から検討されているマルコフ決定過程による顧客への推薦と顧客による購買を表現したモデルに、マルコフ連鎖による顧客クラスのモデルを加味して拡張することにより、空間的分析と時間的制御の融合を試みた。顧客のクラス変化を考慮した拡張モデルにおける顧客の所属クラスが未知という問題設定に対して、売上高をベイズ基準のもとで最大化する定式化を行い、実際にベイズ最適な推薦商品を算出する動的計画法を用いた提案アルゴリズムを導出した。さらに、数値計算例によって提案アルゴリズムの検証も行い、その有効性を確認した。実施計画では平成28年度は空間的分析と時間的制御を融合させた商品推薦問題の定式化を行うこととし、平成29年度の実施計画として空間的分析方法の提案と空間的分析と時間的制御を融合させた商品推薦方法の提案を挙げ、平成30年度の実施計画として提案方法の検証を挙げていた。平成28年度の実績は上記のとおり、顧客のクラス変化を考慮した拡張モデルにおける顧客の所属クラスが未知という問題設定に対して、売上高をベイズ基準のもとで最大化する定式化を行い、実際にベイズ最適な推薦商品を算出する動的計画法を用いた提案アルゴリズムを導出した。さらに、数値計算例によって提案アルゴリズムの検証も行い、その有効性を確認した。このように平成28年度の実績は、平成29年度以降の実施計画の一部を包含している。よって、進捗としては当初計画以上に進展していると判断する。平成28年度には、従来技術の調査・分析後に、顧客のクラス変化を考慮した拡張モデルにおける顧客の所属クラスが未知という問題設定のもとで検討を進め、定式化・提案アルゴリズムの導出・検証をおこなった。平成28年度の検討結果より、何も事前情報がない新規顧客に関する情報を当該顧客から入手するための新規顧客問題、利用する各種確率モデルの真のパラメータが未知の場合の機械学習問題など、検討すべき課題が多々存在することも明らかになった。そこで、本研究課題の今後の推進方策としては、検討の必要性が明らかになった新規顧客問題などを加味した空間的分析と時間的制御を融合させた商品推薦方法に関する定式化・提案アルゴリズムの導出・検証を進めていきたい。当初平成28年度に予定していた計算機の購入を平成29年度に実施することを計画している

  • 大規模データ時代のビジネスアナリティクス手法に関する基礎的研究

    研究期間:

    2014年04月
    -
    2017年03月
     

     概要を見る

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

  • 確率的要素を含む情報セキュリティシステムの利便性と安全性からの最適化と統合評価

    研究期間:

    2013年04月
    -
    2016年03月
     

     概要を見る

    確率的要素を含む情報セキュリティ問題に対し確率モデルにより定式化を行い,安全性や利便性等の評価基準を明確にし,最適な攻撃法や認証法等を理論的に明らかにした.個々の符号やシステムに対して安全性を評価するのではなく,統一的数理モデルの枠組のもとで安全性の理論的な限界を不変的に評価した.さらに,安全性と利便性のトレードオフ関係についても,理論的限界や最適性を明らかにし,情報セキュリティシステムの新たな評価指標を示した.また,学習理論や最適化理論等の周辺研究分野における等価な確率モデルを用いた問題の成果を応用することで,最適法を近似する高性能アルゴリズムを構成し,安全性や利便性を具体的に評価した

講演・口頭発表等

  • 分散コンピューティングへの誤り訂正符号の応用に関する研究動向

    堀井俊佑  [招待有り]

    第7回 誤り訂正符号のワークショップ   (岩手)  電子情報通信学会 情報理論とその応用サブソサイエティ  

    発表年月: 2018年09月

  • Bayesian Compressed Sensing with Hybrid hierarchical Prior

    Shunsuke Horii

    2018 ISBA World Meeting   (エディンバラ) 

    発表年月: 2018年06月

  • Sparse Bayesian Logistic Regression with Hierarchical Prior and Variational Inference

    Shunsuke Horii

    AABI2017, NIPS workshop "Advances in Approximate Bayesian Inference"  

    発表年月: 2017年12月

  • 分散最適化手法の線形符号の復号への応用

    堀井俊佑  [招待有り]

    誤り訂正符号ワークショップ  

    発表年月: 2013年09月

  • メッセージ伝搬アルゴリズムとその応用

    堀井俊佑

    数理人セミナー  

特定課題研究

  • 操作変数に基づく因果推論に対するスパースモデリングとベイズ決定理論の応用

    2020年  

     概要を見る

    ベイズ的スパースモデリングの考え方を応用し,ベイズ最適な因果効果推定を効率的に近似計算するアルゴリズムを導出した.その成果を第23回情報論的学習理論ワークショップ(IBIS2020),13th International Conference of the ERCIM WG on Computational and Methodological Statistics (CMStatistics 2020)で発表した.

  • スパースモデリングとベイズ決定理論に基づいた因果推論手法の構築

    2019年  

     概要を見る

    統計的因果推論の問題を決定理論に基づいて定式化し,二乗誤差損失にたいしてベイズ最適な決定法を導出した.その成果を11th Asia-Europe Workshop on concepts in Information theoryで発表した.また,操作変数を用いた因果推論の問題に対して,ベイズ的スパースモデリングを応用した手法を構築した.その成果を第22回情報論的学習理論ワークショップ(IBIS2019),第42回情報理論とその応用シンポジウム(SITA2019),12th International Conference of the ERCIM WG on Computational and Methodological Statistics (CMStatistics 2019)で発表した.

  • スパースモデリングとベイズ決定理論に基づいた意思決定手法の構築

    2018年  

     概要を見る

    圧縮センシングの問題において,画像の疎性・滑らかさを考慮に入れた変分ベイズ法に基づいた復元アルゴリズムを構築した.その成果を国際会議Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC 2018)で発表した.統計的因果推論の問題を決定理論に基づいて定式化し,ベイズ最適な決定法を導出した.その成果を53rd Annual Conference on Information Science and Systems (CISS 2019)で発表した.

  • スパースモデリングとベイズ決定理論に基づいた意思決定手法の構築

    2018年  

     概要を見る

    圧縮センシングの問題において,画像の疎性・滑らかさを考慮に入れた変分ベイズ法に基づいた復元アルゴリズムを構築した.その成果を国際会議Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC 2018)で発表した.統計的因果推論の問題を決定理論に基づいて定式化し,ベイズ最適な決定法を導出した.その成果を53rd Annual Conference on Information Science and Systems (CISS 2019)で発表した.

  • 多端子型学習問題に対する分散最適化に基づいた学習アルゴリズムの研究

    2014年  

     概要を見る

    関連データを用いた学習問題,マルチタスク学習問題,並列分散環境における学習問題を統合的に 扱い,これらの問題を凸最適化問題として定式化し,分散最適化に基づいた効率的学習アルゴリズムを構築する研究を行った.得られた研究成果をIEEE SMC2014において発表を行った.

  • 凸最適化と確率伝搬法に基づいた高性能な確率推論アルゴリズムの開発

    2013年  

     概要を見る

    確率変数の間に存在する因果関係をグラフで表現したグラフィカルモデルにおいて,観測できる変数から観測できない変数を推定する確率推論の問題を扱った.確率推論は、誤り訂正符号の復号問題や、自然言語処理における統計的係り受け解析、画像処理における画像セグメンテーションなど様々な問題に応用されている.本研究では,凸最適化に基づいた推論アルゴリズムの設計を行い,その性能を解析的・実験的に評価した.本研究のポイントは,1) 様々な問題をグラフィカルモデル上の確率推論問題として定式化し,2) 各問題に適した形で凸最適化に基づいた高速な推論アルゴリズムを構築することであった.様々な問題に対して高性能な推論アルゴリズムを得ることが主な研究目的であった.理論的な側面からは,確率推論の問題は整数計画問題の部分クラスを与えていると考えられるが,どのような問題のクラスが効率的に,また良い近似精度で解く事が出来るかを明らかにすることは意義がある.現実の様々な問題をグラフィカルモデルの確率推論の問題として定式化した場合の性質を,問題の数学的構造により分類し,それぞれの問題に対して従来提案されている推論アルゴリズムを整理した.また,確率伝搬法・線形計画法・双対分解などを組み合わせた新たなアルゴリズムを提案し,アルゴリズムの計算量などの理論評価,コンピュータシミュレーションによる数値実験での評価を行った.問題の一つとして,符号化CDMAシステムにおける復号問題を扱った.この問題をグラフィカルモデル上の確率推論問題として定式化し,拡張ラグランジュ法とADMMとよばれるアルゴリズムを適用することで,効率的かつ高性能な復号アルゴリズムを得ることができた.また,他の問題として,相関を有する複数の低ランク行列の補完問題を扱った.この問題を凸最適化問題として定式化し,拡張ラグランジュ法とADMMを適用することで,従来のものよりも精度の良い補完アルゴリズムを得ることができた.

  • 整数計画法に基づいた高性能な確率推論アルゴリズムの開発

    2011年  

     概要を見る

    確率変数の間に存在する因果関係をグラフで表現したグラフィカルモデルにおいて,観測できる変数から観測できない変数を推定する確率推論の問題を扱った.グラフィカルモデルにおける標準的な確率推論アルゴリズムとして確率伝搬法が広く知られているが,近年,凸最適化に基づいた推論アルゴリズムの研究が盛んに行われるようになっている.本研究では,主に凸最適化に基づいた推論アルゴリズムの設計を行い,その性能を解析的・実験的に評価した.特に,応用としてストリーム暗号の鍵推定,誤り訂正符号の復号,マルチコンピュータシステムにおける故障診断の問題を扱った.ストリーム暗号は,平文をビット単位あるいはバイト単位などで逐次、暗号化する暗号方式である.暗号の安全性評価のため,暗号の鍵推定に関する研究が重要な研究課題となる. 本研究においては,一部のストリーム暗号のクラスにおいて確率推論アルゴリズムによる鍵推定が効率的に行えることを示した.誤り訂正符号は,ノイズのある通信チャネルを通してメッセージを高信頼度で通信する為の技術の1つで,LDPC 符号と呼ばれる符号に対して確率伝搬法に基づく復号を行うことで,シャノン限界と呼ばれる理論的限界に近い性能を得られることが知られている.近年,LDPC 符号の復号法として,確率伝搬法に代わる新たな復号法として,線形計画法に基づいた復号法に関する研究が盛んに行われているが,本研究では,複雑な通信路モデルにおいても凸最適化に基づいた推論アルゴリズムが有効に働くことを示した.マルチプロセッサシステムあるいはマルチコンピュータシステムにおける故障ノードを発見する問題は,古くから様々なモデルに対して研究が行われてきた.本研究では,この問題が確率推論の問題として定式化が可能であり,凸最適化に基づいた故障診断システムを構築した.数値シミュレーションにより,提案したアルゴリズムが従来のものより良い性能を示すことを確認した.

  • 様々な通信の問題に対する最適化理論に基づいた復号法に関する研究

    2009年  

     概要を見る

    通信において雑音が発生する状況において,効率的に品質の良い通信を行うためには,誤り訂正符号の研究は非常に重要である.また,限りある通信資源を効率的に使うためには,符号分割多重アクセス(CDMA)に関する研究が盛んに行われている。本研究は,これらの各種通信における復号の問題を統一的に扱うものであった。一般的に,どのような通信において,最適な復号方法は既に明らかにされている。ところが,それらは多くの場合,膨大な計算資源を要するものであり,実用的なものではない。一方で,各種通信における復号問題の多くは最適化問題として定式化することが可能である。そこで本研究は,凸最適化理論・組み合わせ最適化理論における研究成果を応用することで,効率的な復号アルゴリズムを提案した。まず,組み合わせ最適化理論の分野で提案されている分枝カット法と呼ばれるアルゴリズムを応用した,誤り訂正符号に対する復号アルゴリズムを提案し,国内外の学会で発表を行った。従来提案されている幾つかの有効な復号アルゴリズムがこのアルゴリズムの一例であることが明らかになり,アルゴリズムの一部を変更することで,様々な有効なアルゴリズムが構築された。数値実験により,提案したアルゴリズムの有効性を示した。また,CDMA通信に対しては,一般化確率伝搬法と呼ばれるアルゴリズムを応用した復号アルゴリズムを提案した。この結果については,現在国際学会への投稿を予定している。

▼全件表示

 

現在担当している科目

▼全件表示