主成分分析を用いたK-SAT問題における相転移現象の可視化(テーマセッション,コンピュータビジョンとパターン認識のための機械学習)
スポンサーリンク
概要
- 論文の詳細を見る
本研究では,充足可能性問題(random K-SAT問題)の相転移現象を数値シミュレーションにより検証する.K-SAT問題は標準的なNP完全問題であるが,K-SAT問題における相転移現象については未だ明らかになっていない.解析的には,系のサイズ(ブール変数の次元数)が無限大の場合に部分的に解かれているのみである.本研究では,Markov chain Monte Carlo(MCMC)シミュレーションと主成分分析(PCA)を組み合わせた手法により,K-SAT問題の系の経験分布を直観的に理解しやすい2次元ヒストグラムの形で表現し,その際の固有値分布についても示す.また,磁化の値やスピングラス秩序変数のヒストグラムについても示し,K-SAT問題の相転移現象について議論する.シミュレーション結果より,3-SAT問題において低温状態のhard-SAT相当の条件下では,混合相(磁化が非零でレプリカ対称性が破れている)となることが示唆されたが,さらなる詳しい検証が必要である.
- 2011-08-29
著者
-
井上 真郷
早稲田大学先進理工学部電気・情報生命工学科
-
岡田 真人
東京大学大学院 新領域創成科学研究科
-
岡田 真人
東大院新領域:理研脳総研:jst Erato
-
井上 真郷
早稲田先進理工
-
岡田 真人
独立行政法人 家畜改良センター奥羽牧場
-
岡田 真人
東大新領域:理研脳総研
-
岡田 真人
理化学研究所脳科学総合研究センター
-
岡田 真人
東大 大学院新領域創成科学研究科
-
赤澤 靖章
早稲田大学大学院先進理工学研究科
-
OKADA Masato
Department of Complexity Science and Engineering, Graduate School of Frontier Sciences, The University of Tokyo:Intelligent Coopertion and Control, PRESTO, JST:Laboratory for Mathematical Neuroscience, Brain Science Institute, RIKEN
関連論文
- 平滑化事前分布を用いた変動2値情報源の事後確率最大化法(研究速報)
- 2体結合モデルによる統計力学的ハプロタイプ推定
- 複層Markov確率場と線形劣化変換に対するBayes超解像 (非線形問題)
- 汎用デジタルカメラを用いたハイスピードムービー撮影による声帯振動の観察
- 誘導運動による運動検出感度の向上と低下を説明する神経回路モデル(ヒトの行動とモデル,神経ダイナミクス,一般)
- 画像領域分割の確率モデルと脳の視覚情報処理 (小特集 ビジョンコンピューティングにおける確率的情報処理の展開)
- IT野ニューロン集団の時間相関を取り入れたクラスタリング
- 混合ベルヌーイ分布を用いたクラスタリングによる連想記憶モデルの解析 (ニューロコンピューティング)
- 粒子フィルタによる細胞内Ca[2+]動態の推定--実データへの応用 (ニューロコンピューティング)
- 位相応答曲線における神経細胞の不応期の影響(脳活動の計測と解析,生命現象の非線形性,一般)
- 非線型状態空間モデルを用いた細胞内カルシウムイオン濃度の推定
- 高次摂動展開による神経振動子のSpike Triggered解析
- 細胞外電場負荷に対するシリンダーケーブルの膜電位変化の数理解析II
- 離散的かつ連続的な情報表現を持つ神経回路モデル(ニューロハードウェア,一般)
- Spike Response Modelの位相応答曲線
- 位相応答曲線の測定と周期外力下でのスパイク間隔分布の予測
- 分布定数型カルマンフィルタを用いた樹状突起膜電位の時空間分布の推定
- パワー拘束条件下での位相応答曲線の推定
- 細胞の摂動応答を用いた樹状突起先端部における膜比抵抗の推定
- 膜比抵抗の急峻な変化による樹状突起上の信号伝播の向上(ニューラルネットワーク画像復元及び一般)
- 膜比抵抗の急峻な変化による樹状突起上の信号伝播の向上
- 海馬CA1錐体細胞の樹状突起遠位部における膜比抵抗の急峻な低下
- 海馬CA1錐体細胞の膜抵抗分布の推定(NCとのテーマセッション : 海馬の情報処理 : 非線形現象とニューロコンピューティング)
- 海馬CA1錐体細胞の膜抵抗分布の推定(テーマセッション : 海馬の情報処理 : 非線形現象とニューロコンピューティング)
- 神経集団符号に基づく自然画像統計量の弁別(視聴覚技術,ヒューマンインターフェース)
- 領域ベース結合MRFモデルによる大局的画像領域分割とCMOS回路実現
- 2.画像領域分割の確率モデルと脳の視覚情報処理(ビジョンコンピューティングにおける確率的情報処理の展開)
- 共通入力による連想記憶モデルの分岐を含む系列の想起(ニューラルネットワーク画像復元及び一般)
- 隠れマルコフモデルの変分ベイズ学習による神経活動パターンの抽出(一般(ベイズ法など),脳インタフェースの技術と応用,一般)
- 脳機能画像の3次元再構築
- 時間領域増幅型デジタル補聴器の効果
- ヘブシナプスを持つH-H系のレート縮約(ニューラルネットワーク画像復元及び一般)
- 側頭葉をモデル化したアトラクターネットワークの安定性解析 : アトラクタの安定性と学習順番の関係(脳活動の計測と解析,生命現象の非線形性,一般)
- Information divergences in local variational approximation of Bayesian posterior distribution (ニューロコンピューティング)
- 側頭葉ニューロン集団の 1 試行活動からの視覚刺激情報の抽出
- 教師が非単調な場合のアンサンブル学習
- ショウジョウバエ第一次嗅覚中枢における非線形変換と局所介在ニューロンの役割(学習,生体モデル,神経ダイナミクス,一般)
- 甲状腺腫瘍 FNA クラスIII症例の手術適応
- 副咽頭腔を占める巨大異所性脳例
- 喉頭制御と聴覚の相互連関 : 中枢における言葉の認知と表出の相互作用
- 耳下部に発生した巨大石灰化上皮腫例
- 閉鎖子音を刺激音とした語音蝸電図
- 一次視覚野情報からの画像再構築
- 並進対称なフィルタの下でのベイズ的に最適な画像再構成(一般(ベイズ法など),脳インタフェースの技術と応用,一般)
- 適応的自然勾配法の特異モデル学習への適用(一般,機械学習によるバイオデータマインニング・生命現象の非線形性,一般)
- ダーツ01ゲーム最適戦略(各種ゲーム)
- 興奮性-抑制性ネットワークにおけるシナプス減衰の機能的役割
- 減衰シナプスをもつアトラクタネットワークの想起特性(バイオサイバネティックス,ニューロコンピューティング)
- スパイクタイミング依存可塑性のLTPとLTDの非対称性が想起状態に与える影響
- 時間非対称ヘブ学習によるシナプス効率の自己調節のメカニズム
- マルコフ確率場モデルにおける確率伝播法をもちいたα波位相,振幅の同時推定 (ニューロコンピューティング)
- どのモデルが発火率のダイナミクス,滑らかさを適切に記述するか?(ヒトの行動とモデル,神経ダイナミクス,一般)
- 計算論的神経科学への統計力学的アプローチ : 一次視覚野モデルを用いて(BCI/BMIとその周辺,一般)
- Bayes推定を用いたRadon変換画像の再構成(イメージング)
- Bayes推定を用いたRadon変換画像の再構成 (医用画像)
- ノードパータベーション学習の統計力学(脳活動の計測と解析,生命現象の非線形性,一般)
- 集団符号化における相転移
- 平滑化事前分布を用いた変動2値情報源の事後確率最大化法
- DS-3-5 スペクトル拡散型電子透かしの復号アルゴリズム(DS-3.マルチメディア情報ハイディング,シンポジウムセッション)
- 複層Markov確率場と線形劣化変換に対するBayes超解像(機械学習によるバイオデータマインニング,生命現象の非線形性,一般)
- NLP2010-10 複層Markov確率場と線形劣化変換に対するBayes超解像(一般,機械学習によるバイオデータマインニング,生命現象の非線形性,一般)
- 変分ベイズ法における確定的アニーリング
- 多様体学習を用いた近似contour treeプロット(セッション4:可視化)
- 階層的な記憶パターンを持つ自己相関型連想記憶モデルのPCAによる解析 (ニューロコンピューティング)
- 位相応答曲線における神経細胞の不応期の影響(脳活動の計測と解析,生命現象の非線形性,一般)
- 樹状突起における電気的応答特性の推定
- スパイクレスポンスモデルの位相応答曲線
- 2ニューロン系の多変量ARモデルに基づいた相互作用系解析
- 小鳥の複雑な歌系列生成に関わる神経回路網のモデル化
- ショウジョウバエ嗅覚回路におけるシナプス前抑制とシナプス後抑制の匂い弁別に対する違い
- 可変長圧縮基準による頻出文字列検出
- 非定常なスパイク列から隠れた構造を読み取る(脳のモデルと生物模倣情報処理2,生物模倣情報処理,機械学習,一般)
- マルコフ確率場モデルにおける確率伝播法をもちいたα波位相,振幅の同時推定
- 混合べルヌーイ分布を用いたクラスタリングによる連想記憶モデルの解析
- 階層的な記憶パターンを持つ自己相関型連想記憶モデルのPCAによる解析
- Fisherの正確確率検定の正確多重検定 : 保守的でない多重検定アルゴリズム(IBIS2010(情報論的学習理論ワークショップ))
- 音響分析ソフト「VA」の開発 : ―軽度嗄声の音響分析―
- 疎な解を得られるカーネルマシンを用いたMultiple Instance Learning問題の一解法
- 主成分分析を用いたK-SAT問題における相転移現象の可視化
- 音響分析ソフト「VA」の開発 : 軽度嗄声の音響分析
- 主成分分析を用いたK-SAT問題における相転移現象の可視化(テーマセッション,コンピュータビジョンとパターン認識のための機械学習)
- 主成分分析を用いたK-SAT問題における相転移現象の可視化(テーマセッション,コンピュータビジョンとパターン認識のための機械学習)
- 疎な解を得られるカーネルマシンを用いたMultiple Instance Learning問題の一解法(テーマセッション,コンピュータビジョンとパターン認識のための機械学習)
- 疎な解を得られるカーネルマシンを用いたMultiple Instance Learning問題の一解法(テーマセッション,コンピュータビジョンとパターン認識のための機械学習)
- 可能パターン完全探索によるminesweeperのsolver生成
- 2項分布に基づく基底関数による混合回帰モデル(ポスターセッション,第14回情報論的学習理論ワークショップ)
- 混合モデルとしての複層Gauss-Markov確率場による画像の修復と領域分割(ポスターセッション,第14回情報論的学習理論ワークショップ)
- Dirichlet過程と変分Bayes法による交叉率推定(ポスターセッション,第14回情報論的学習理論ワークショップ)
- 上位M個の解が得られる疎結合モデルの離散最適化手法(一般,複雑系とニューロコンピューティング)
- Dirichlet 過程と変分 Bayes 法による交叉率推定
- 2項分布に基づく基底関数による混合回帰モデル
- 上位M個の解が得られる疎結合モデルの離散最適化手法
- 混合モデルとしての複層 Gauss-Markov 確率場による画像の修復と領域分割
- 順序回帰のための高速な疎Bayes学習アルゴリズム
- ロジスティック回帰モデルを組み合わせた順序回帰モデルと高速な疎Bayes学習(第15回情報論的学習理論ワークショップ)
- 適応的自然勾配法の特異モデル学習への適用
- SKモデルの独立成分分析を用いた解析 : 1RSB相の場合(ポスターセッション,大規模データベースとパターン認識)
- ハプロタイプ推定に対するモーメント母関数を用いたアプローチ
- 結託攻撃におけるスペクトル拡散型電子透かしの復号性能の評価
- MDL基準の離散混合分布のモデル選択への適用