Updated on 2022/05/26

写真a

 
HORII, Shunsuke
 
Affiliation
Affiliated organization, Center for Data Science
Job title
Associate Professor

Concurrent Post

  • Affiliated organization   Global Education Center

Research Institute

  • 2021
    -
    2022

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

  • 2021
    -
    2022

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

Education

  •  
    -
    2009

    Waseda University   Graduate School of Science and Engineering  

  •  
    -
    2004

    Waseda University   Graduate School of Science and Engineering  

  •  
    -
    2004

    Waseda University   Graduate School of Science and Engineering  

  •  
    -
    2004

    Waseda University   Graduate School of Science and Engineering  

Degree

  • 博士

 

Research Areas

  • Intelligent informatics

Research Interests

  • Information Theory, Coding Theory, Statistical Learning Theory

Papers

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

    Yuji Iikubo, Shunsuke Horii, Toshiyasu Matsushima

    2019 IEEE International Conference on Systems, Man, and Cybernetics (SMC2019)    2019.10  [Refereed]

  • Distributed Stochastic Gradient Descent Using LDGM Codes

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

    Proceedings of 2019 IEEE International Symposium on Information Theory (ISIT2019)     1417 - 1421  2019.07  [Refereed]

    DOI

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

    Yoshifumi Ukita

        22  2017.11  [Refereed]

  • Bayesian Sparse-Smooth Modeling and Variational Inference

    Shunsuke Horii

        16  2017.11  [Refereed]

  • 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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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

  • A Note on the Linear Programming Decoding of Linear Codes for Symbol Pair Read Channel

    Shunsuke Horii

    Proc. of 38th Symposium on information Theory and its Applications    2015.11

  • Online Bayesian estimation of Randomized Response models

    Tota Suko

    IEICE technical report   COMP2015-23   7 - 11  2015.10

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

    Shunsuke Horii

    Technical report of IEICE   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  [Refereed]

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

    須子統太

    日本経営工学会論文誌     78 - 88  2014.07  [Refereed]

  • Privacy-preserving Distributed Calculation Methods of a Least-squares Estimator for Linear Regression Models

    SUKO Tota, HORII Shunsuke, KOBAYASHI Manabu, GOTO Masayuki, MATSUSHIMA Toshiyasu, HIRASAWA Shigeichi

    J. Jpn . Ind. Manage. Assoc.   65 ( 2 ) 78 - 88  2014

     View Summary

    In this paper, we study a privacy preserving linear regression analysis. We propose a new protocol of a distributed calculation method that calculates a least squares estimator, in the case that two parties have different types of explanatory variables. We show the security of privacy in the proposed protocol. Because the protocol have iterative calculations, we evaluate the number of iterations via numerical experiments. Finally, we show an extended protocol that is a distributed calculation method for k parties.

    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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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

     View Summary

    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  [Refereed]

     View Summary

    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

  • A Privacy Preserving Distributed Calculation Method of Least-squares Estimator for Linear Regression Models

    SUKO Tota, HORII Shunsuke, KOBAYASHI Manabu, GOTO Masayuki, MATSUSHIMA Toshiyasu, HIRASAWA Shigeichi

      112 ( 279 ) 107 - 111  2012.10

     View Summary

    In this paper, we study a privacy preserving linear regression analysis. We propose a new protocol of distributed calculation method that calculates a least squares estimator, in case that two parties have different types of explanatory variables. We show security of privacy in the proposed protocol. Because the protocol have iterative calculation, we evaluate the number of iterations with numerical experiments. Finally, we show an extended protocol that is a distributed calculation method for κ parties.

    CiNii

  • Linear Programming Decoding for Multiple Access Channel based on Decomposition Methods

    HORII Shunsuke, MATSUSHIMA Toshiyasu

    IEICE technical report. Information theory   112 ( 215 ) 53 - 58  2012.09

     View Summary

    In this paper, we develop a dual decomposition method based linear-programming (LP) decoding for multiple-access channels with binary linear codes. LP decoding has decoding error rate which is comparable with state-of-the-art Sum-Product decoder for the decoding problem of binary linear codes with stronger theoretical guarantees and it is applied to decoding problems over various channels such as interference channels and multiple-access channels. But the decoder has to solve an LP problem and in general its computational complexity is the polynomial order of the number of variables and the number of constraints. Therefore it needs more decoding time compared to other decoders such as Sum-Product decoder. In order to tackle the complexity problem, many complexity efficient decoders have been developed for single-user memoryless channels. Especially, some previous studies showed that the decoding algorithm based on dual decomposition works well for large scale LDPC codes. In this paper, we apply the dual decomposition methods for the decoding problem over multiple access channels.

    CiNii

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

    堀井俊佑

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

  • Fault Diagnosis Algorithm Based on Linear Programming in Multicomputer Systems

    KOBAYASHI Manabu, HORII Shunsuke, TAKABATAKE Toshinori, HIRASAWA Shigeichi

    The Transactions of the Institute of Electronics, Information and Communication Engineers. A   95 ( 4 ) 375 - 378  2012.04

    CiNii

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

    小林学

    電子情報通信学会論文誌,基礎・境界   Vol.J95-A ( No.4 ) 375 - 378  2012.04  [Refereed]

  • 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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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

        141 - 146  2011.09  [Refereed]

  • A study of statistical modeling of authentication using PUF

    ISHII Satoru, YOSHIDA Takahiro, HORII Shunsuke, MATSUSHIMA Toshiyasu

    IEICE technical report. Information theory   111 ( 142 ) 19 - 24  2011.07

     View Summary

    Nowadays, it is pointed out that storing the secret in nonvolatile memory of the device has a chance to leak the secret because of physical attacks and side channel attacks. In order to solve this, Physical Unclonable Functions(PUF) were proposed. Recently, many encryption methods using PUF have been proposed, and one of typical example is authentication. In this paper, we define response to challenge of PUF as probability distribution, and we define error rate of authentication and success rate of impersonation attack by interpreting authentication using PUF as hypothesis testing problem. In authentication using PUP, we derive lower bound of success rate of impersonation attack when error rate of authentication is 0. And we define arbiter PUF which is one of silicon PUFs as probability distribution. In arbiter PUP, we simulate lower bound of success rate of the impersonation attack when error rate of authentication is 0, and discuss security of arbiter PUF.

    CiNii

  • A Study on Key Estimation of Stream Cipher based on Probabilistic Inference Algorithm

    IIKUBO Yuji, HORII Shunsuke, MATSUSHIMA Toshiyasu

    IEICE technical report. Information theory   111 ( 142 ) 7 - 12  2011.07

     View Summary

    The stream cipher which is a kind of symmetric key algorithm, is a cryptosystem to generate ciphertext by XOR plaintext bits and keystream bits which obtained by input a secret key to pseudorandom number generator. In this paper, we formularize the problem of the attack to stream cipher by statisitical decision theory, and consider the optimal key estimation based on Bayesian criterion. We represent practical pseudorandom number generator as a probabilistic model, and propose the key estimation algorithm based on probabilistic inference one by representing it to graphical model. The proposed algorithm is evaluated by simulation, then consider the safety of the stream cipher.

    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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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

  • A Note on the Inference Algorithm on the Factor Graph based on the Linear Programming

    HORII Shunsuke, MATSUSHIMA Toshiyasu, HIRASAWA Shigeichi

    IEICE technical report. Information theory   110 ( 363 ) 55 - 60  2011.01

     View Summary

    Probabilisitc inference problem on the graphical model is very important since it is arising in many applications which include theory of error-correcting codes, image processing, speech recognition, and so on. Recently, linear programming based decoding algorithm for the error-correcting code has been receiving a lot of attention. Viewing the decoding problem as an example of the probabilistic inference problem on the graphical model, the factor graph corresponds to the problem has some specific structure. The functions in the factor graph can be classified into two classes, indicator functions and non-indicator functions. For the graph corresponds to the decoding problem, each non-indicator function is connected to only one variable node. On the other hand, the factor graph corresponds to the general probabilistic inference problems possibly have non-indicator functions which is connected to more than one variable nodes. The aim of this study is to develop the linear programming based inference algorithm for general inference problems.

    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  [Refereed]

     View Summary

    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  [Refereed]

     View Summary

    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

        489 - 493  2010.11

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

    須子統太

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

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

    HORII Shunsuke, MATSUSHIMA Toshiyasu, HIRASAWA Shigeichi

    IEICE technical report. Information theory   110 ( 205 ) 31 - 36  2010.09

     View Summary

    In this paper, we develop a linear-programming (LP) decoding for the multiple-access channel with binary linear codes. For the single-user channel, LP decoding has been attracting much attention in recent years as a good approximation to the maximum likelihood decoding. We demonstrate that how the maximum likelihood decoding problem for the multiple-access channel with binary linear codes can be formulated as a linear programming problem. It is not straightforward because the objective function of the problem is a non-linear function of the codeword symbols in general. We introduce the auxiliary variables such that the objective function is a linear function of those variables. Then the ML decoding problem reduces to the LP problem however, it is too complex for practical implementation. As the case for the single-user channel, we formulate the relaxed LP problem. Just as in the case of the single-user channel, the proposed decoder has the desirable property called ML certificate property, that is, if the decoder outputs integer solution, it is guaranteed to be the ML codeword. The computational complexity of the proposed algorithm is the exponential order of the number of users, however, we can reduce the computational complexity of the algorithm for the gaussian multiple-access channel. Furthermore, we compare the performance of the proposed decoder with the decoder based on the sum-product algorithm.

    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  [Refereed]

  • On the Web Traffic Modeling under the Opening and Closing Services by the Non-Stationary Poisson Process

    Daiki Koizumi, Shunsuke Horii, Toshiyasu Matsushima

    IEICE Technical Report   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  [Refereed]

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

    Daiki Koizumi

      Vol.IN2009-201   392 - 396  2010.03

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

    Shunsuke Horii

        66 - 70  2009.12

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

    Shunsuke Horii

        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  [Refereed]

     View Summary

    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

  • A Note on Nonstationary Poisson Model with the Consideration of Change Factors

    Koichi Suzuki

      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

▼display all

Books and Other Publications

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

    堀井俊佑( Part: Sole author)

    早稲田大学出版部  2015.04

Misc

  • Iterative Multiuser Joint Decoding based on Augmented Lagrangian Method

    HORII Shunsuke, SUKO Tota, MATSUSHIMA Toshiyasu, HIRASAWA Shigeichi

    IEICE technical report. Information theory   113 ( 228 ) 13 - 17  2013.09

     View Summary

    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

Research Projects

  • Economic and psychological effects of network diversification

    Project Year :

    2018.04
    -
    2023.03
     

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

    Project Year :

    2019.04
    -
    2022.03
     

     View Summary

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

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

    Project Year :

    2016.04
    -
    2019.03
     

     View Summary

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

  • Fundamental study on business analytics technologies on big data era

    Project Year :

    2014.04
    -
    2017.03
     

     View Summary

    The objective of this study is to develop and deepen large-scale and diverse business data analytical technology (business analytics), propose new analytical models corresponding to various business data.Specifically, we promoted research on the following individual themes: 1) development of data analytics technology for database information on EC sites, 2) development of analytical technique of marketing information accumulated as text data, 3) development of statistical model for recommendar systems, 4) Theoretical analysis of Web marketing model using information retrieval and recommendation technology, 5) Development of analytical method for high dimensional and sparse large scale data, 6) Development of privacy protection data analysis technology

  • A Unified Analysis and Optimization of Information Security System with Probabilistic Components from Viewpoints of Convenience and Safety

    Project Year :

    2013.04
    -
    2016.03
     

     View Summary

    Information security problem with probabilistic components has been formulated by probabilistic models. Theoretical criteria for evaluation such as convenience and safety have been defined clearly and optimal attack or an authentication method has been derived theoretically. Theoretical safety bounds have been evaluated with respect to mathematical models with unified framework for each cipher or security system. A theoretical safety bound or optimality has been clarified with respect to a tradeoff between convenience and safety. New theoretical criteria have been derived for information security systems. Approximation algorithms with high performance for optimal attack or an authentication method have been constructed applying results of studies on problems in related fields such as learning or optimization theory that is formulated by probabilistic models equivalent to our study. Convenience or safety of information security systems has been simulated by applying these algorithms

Presentations

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

    堀井俊佑  [Invited]

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

    Presentation date: 2018.09

  • Bayesian Compressed Sensing with Hybrid hierarchical Prior

    Shunsuke Horii

    2018 ISBA World Meeting  (Edinburgh) 

    Presentation date: 2018.06

  • Sparse Bayesian Logistic Regression with Hierarchical Prior and Variational Inference

    Shunsuke Horii

    AABI2017, NIPS workshop "Advances in Approximate Bayesian Inference" 

    Presentation date: 2017.12

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

    堀井俊佑  [Invited]

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

    Presentation date: 2013.09

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

    堀井俊佑

    数理人セミナー 

Specific Research

  • 高次元統計学におけるベイズ推論の統計的因果推論への応用

    2021  

     View Summary

    ノンパラメトリックベイズの考え方を応用し,ベイズ最適な因果効果推定アルゴリズムを導出し,その理論的性質を明らかにした.その成果を第24回情報論的学習理論ワークショップ(IBIS2021),14th International Conference of the ERCIM WG on Computational and Methodological Statistics (CMStatistics 2021)で発表した.

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

    2020  

     View Summary

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

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

    2019  

     View Summary

    統計的因果推論の問題を決定理論に基づいて定式化し,二乗誤差損失にたいしてベイズ最適な決定法を導出した.その成果を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  

     View Summary

    圧縮センシングの問題において,画像の疎性・滑らかさを考慮に入れた変分ベイズ法に基づいた復元アルゴリズムを構築した.その成果を国際会議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  

     View Summary

    圧縮センシングの問題において,画像の疎性・滑らかさを考慮に入れた変分ベイズ法に基づいた復元アルゴリズムを構築した.その成果を国際会議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  

     View Summary

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

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

    2013  

     View Summary

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

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

    2011  

     View Summary

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

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

    2009  

     View Summary

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

▼display all

 

Syllabus

▼display all