1 of 50
Downloaded 23 times
Ad
Recommended
[DL輪読会]Understanding Black-box Predictions via Influence Functions
[DL輪読会]Understanding Black-box Predictions via Influence Functions Deep Learning JP
?
2017/8/21
Deep Learning JP:
http://deeplearning.jp/seminar-2/
ベイズ统计学の概论的绍介
ベイズ统计学の概论的绍介Naoki Hayashi
?
ベイズ統計学の基礎概念からW理論まで概論的に紹介するスライドです．数理?計算科学チュートリアル実践のチュートリアル資料です．引用しているipynbは
* http://nhayashi.main.jp/codes/BayesStatAbstIntro.zip
* https://github.com/chijan-nh/BayesStatAbstIntro
を参照ください．
以下，エラッタ．
* 52 of 80：KL(q||p)≠KL(q||p)ではなくKL(q||p)≠KL(p||q).
* 67 of 80：2ν=E[V_n]ではなくE[V_n] → 2ν (n→∞).
* 70 of 80：AICの第2項は d/2n ではなく d/n.
* 76 of 80：βH(w)ではなくβ log P(X^n|w) + log φ(w).
- レプリカ交換MCと異なり、逆温度を尤度にのみ乗することはWBIC導出では本質的な仮定となる.机械学习モデルの判断根拠の説明（痴别谤.2）
机械学习モデルの判断根拠の説明（痴别谤.2）Satoshi Hara
?
【第40回AIセミナー】
「説明できるAI ?AIはブラックボックスなのか？?」
https://www.airc.aist.go.jp/seminar_detail/seminar_040.html
【講演タイトル】
機械学習モデルの判断根拠の説明
【講演概要】
本講演では、機械学習モデルの判断根拠を提示するための説明法について紹介する。高精度な認識?識別が可能な機械学習モデルは一般に非常に複雑な構造をしており、どのような基準で判断が下されているかを人間が窺い知ることは困難である。このようなモデルのブラックボックス性を解消するために、近年様々なモデルの説明法が研究?提案されてきている。本講演ではこれら近年の代表的な説明法について紹介する。How Much Position Information Do Convolutional Neural Networks Encode?
How Much Position Information Do Convolutional Neural Networks Encode?Kazuyuki Miyazawa
?
Md Amirul, Sen Jia, and Neil D. B. Bruce, "How Much Position Information Do Convolutional Neural Networks Encode?," ICLR2020.「内積が見えると統計学も見える」第5回 プログラマのための数学勉強会 発表資料
「内積が見えると統計学も見える」第5回 プログラマのための数学勉強会 発表資料 Ken'ichi Matsui
?
「第5回 プログラマのための数学勉強会 発表資料 (2015/11/21[sat])」
内容は統計学の素養がある方には基本的な事項ですが、ベクトルと内積で見方を変えてみたという点と、あまり統計学に親しみがない方にも理解してもらえるようなまとめになっている、というところに本スライドの独自性があると考えていますので、その辺り良ければご覧ください＾＾研究効率化Tips Ver.2
研究効率化Tips Ver.2cvpaper. challenge
?
The document outlines strategies for enhancing research efficiency, emphasizing the importance of effective literature review, management skills, and collaborative efforts among researchers. It discusses two main methods for skill enhancement: learning from peers and leveraging online resources, while highlighting the challenges and advantages of each approach. Additionally, it provides insights into the dynamics of various research labs, communication practices, and the value of sharing knowledge across institutions.最新リリース：Optuna V3の全て - 2022/12/10 Optuna Meetup #2
最新リリース：Optuna V3の全て - 2022/12/10 Optuna Meetup #2Preferred Networks
?
2022年8月にリリースしたOptunaの最新メジャーバージョンV3の開発の様子、アップデート内容等をご紹介します。
イベントサイト: https://optuna.connpass.com/event/260301/[DL輪読会]Set Transformer: A Framework for Attention-based Permutation-Invariant...
[DL輪読会]Set Transformer: A Framework for Attention-based Permutation-Invariant...Deep Learning JP
?
2020/02/21
Deep Learning JP:
http://deeplearning.jp/seminar-2/ モデル高速化百选
モデル高速化百选Yusuke Uchida
?
このドキュメントでは、特定のハードウェアに依存しない畳み込みニューラルネットワーク(颁狈狈)の推论高速化手法を绍介しており、モデルパラメータ数や计算量、モデルファイルサイズの削减に焦点を当てています。具体的な手法として、畳み込みの分解、枝刈り、アーキテクチャ探索などが挙げられ、それぞれのアプローチによる计算効率の改善が説明されています。また、モデル圧缩と速度向上を狙った自动化手法も议论されています。[DL輪読会]Attention is not Explanation (NAACL2019)
[DL輪読会]Attention is not Explanation (NAACL2019)Deep Learning JP
?
2019/04/12
Deep Learning JP:
http://deeplearning.jp/seminar-2/ 工学系大学4年生のための论文の読み方
工学系大学4年生のための论文の読み方ychtanaka
?
The document appears to reference several academic papers and conferences, including submissions to IEEE and ACM journals. It mentions contributors and includes links to grant information. The specific content and findings are not detailed in the provided text.SSII2021 [TS3] 機械学習のアノテーションにおける データ収集? ? 精度向上のための仕組み?倫理や社会性バイアス ?
SSII2021 [TS3] 機械学習のアノテーションにおける データ収集? ? 精度向上のための仕組み?倫理や社会性バイアス ?SSII
?
SSII2021 [TS3] 機械学習のアノテーションにおける データ収集? ? 精度向上のための仕組み?倫理や社会性バイアス ?
6/11 (金) 9:30～10:40
講師：藤本 敬介 氏（ABEJA）
概要：Deep Learning（深層学習）では大量の良質なデータを学習することで、高い精度を発揮してきました。実問題にこれを適用させるためには、如何にして正しくデータを集めるかが重要な課題の一つとなっています。データを集める際に、質が悪いものや偏ったデータを集めてしまうと、適切にモデルを学習できません。本チュートリアルでは、大量の良質なデータを集めるための仕組みや手法、精度?速度面での改善方法、倫理や社会性バイアスに関して解説します。遺伝的アルゴリズム （Genetic Algorithm）を始めよう！
遺伝的アルゴリズム （Genetic Algorithm）を始めよう！Kazuhide Okamura
?
2014年11月度 AITC クラウド?テクノロジー活用部会 勉強会資料
遺伝的アルゴリズム （Genetic Algorithm）を始めよう！CMA-ESサンプラーによるハイパーパラメータ最適化 at Optuna Meetup #1
CMA-ESサンプラーによるハイパーパラメータ最適化 at Optuna Meetup #1Masashi Shibata
?
Optuna Meetup #1
https://optuna.connpass.com/event/207545/罢辞谤肠丑顿补迟补チュートリアル解説
罢辞谤肠丑顿补迟补チュートリアル解説西岡 賢一郎
?
2022/04/29開催された第10回機械学習の社会実装勉強会 (https://machine-learning-workshop.connpass.com/event/243466/) で発表した資料です。強化学習の基礎と深層強化学習（東京大学 松尾研究室 深層強化学習サマースクール講義資料）
強化学習の基礎と深層強化学習（東京大学 松尾研究室 深層強化学習サマースクール講義資料）Shota Imai
?
東京大学 松尾研究室が主催する深層強化学習サマースクールの講義で今井が使用した資料の公開版です．
強化学習の基礎的な概念や理論から最新の深層強化学習アルゴリズムまで解説しています．巻末には強化学習を勉強するにあたって有用な他資料への案内も載せました．
主に以下のような強化学習の概念やアルゴリズムの紹介をしています．
?マルコフ決定過程
?ベルマン方程式
?モデルフリー強化学習
?モデルベース強化学習
?TD学習
?Q学習
?SARSA
?適格度トレース
?関数近似
?方策勾配法
?方策勾配定理
?DPG
?DDPG
?TRPO
?PPO
?SAC
?Actor-Critic
?DQN（Deep Q-Network）
?経験再生
?Double DQN
?Prioritized Experience Replay
?Dueling Network
?Categorical DQN
?Noisy Network
?Rainbow
?A3C
?A2C
?Gorila
?Ape-X
?R2D2
?内発的報酬
?カウントベース
?擬似カウントベース
?RND（Random Network Distillation）
?ICM（Intrinsic Curiosity Module）
?Go-Explore
?世界モデル（World Models）
?MuZero
?SimPLe
?NGU（Never Give Up）
?Agent57
?AlphaGo
?AlphaGo Zero
?AlphaZero
?OpenAI Five
?AlphaStar
?マルチエージェント強化学習
科学と机械学习のあいだ：変量の设计?変换?选択?交互作用?线形性
科学と机械学习のあいだ：変量の设计?変换?选択?交互作用?线形性Ichigaku Takigawa
?
機械学習はそもそも汎用的な枠組みであり基本的には対象分野に依らず利活用できる。従って、分野を限定して物質科学に機械学習を活用するなどと言う場合、その本質的難所の大部分は、有効な変量の設計?変換?選択?交互作用?線形性などに関する、いわゆるfeature engineeringの問題に帰する。特に、科学研究では端的な説明因子や共通パターンの探究こそが目的であることが多く、その場しのぎではない方法論が期待されている。本発表では、医薬品、機能制御剤、有機EL材料、食品、化粧品、と波及範囲が広い有機低分子について、その物性の予測と生物活性の予測の違いを例に、関わってきた問題?方法?課題について紹介する。
http://ibisml.org/ibis2016/session3/キャッシュオブリビアスアルゴリズム
キャッシュオブリビアスアルゴリズムjoisino
?
キャッシュオブリビアスアルゴリズムについての簡単な解説です。
/iwiwi/cacheoblivious-dsirnlp5 と https://erikdemaine.org/papers/BRICS2002/paper.pdf を参考にさせていただきました。
Speakerdeck: https://speakerdeck.com/joisino/kiyatusiyuoburibiasuarugorizumuMetric Recovery from Unweighted k-NN Graphs
Metric Recovery from Unweighted k-NN Graphsjoisino
?
The document discusses metric recovery from unweighted k-nearest neighbor (k-nn) graphs, highlighting its applications in user-side recommender systems and graph neural networks (GNNs). It outlines the challenges in estimating the latent coordinates from the k-nn graphs and presents a systematic approach to address these difficulties, including the importance of edge lengths and densities. The findings suggest that GNNs can successfully recover hidden features from graph structures, even with uninformative input features.More Related Content
What's hot (20)
「内積が見えると統計学も見える」第5回 プログラマのための数学勉強会 発表資料
「内積が見えると統計学も見える」第5回 プログラマのための数学勉強会 発表資料 Ken'ichi Matsui
?
「第5回 プログラマのための数学勉強会 発表資料 (2015/11/21[sat])」
内容は統計学の素養がある方には基本的な事項ですが、ベクトルと内積で見方を変えてみたという点と、あまり統計学に親しみがない方にも理解してもらえるようなまとめになっている、というところに本スライドの独自性があると考えていますので、その辺り良ければご覧ください＾＾研究効率化Tips Ver.2
研究効率化Tips Ver.2cvpaper. challenge
?
The document outlines strategies for enhancing research efficiency, emphasizing the importance of effective literature review, management skills, and collaborative efforts among researchers. It discusses two main methods for skill enhancement: learning from peers and leveraging online resources, while highlighting the challenges and advantages of each approach. Additionally, it provides insights into the dynamics of various research labs, communication practices, and the value of sharing knowledge across institutions.最新リリース：Optuna V3の全て - 2022/12/10 Optuna Meetup #2
最新リリース：Optuna V3の全て - 2022/12/10 Optuna Meetup #2Preferred Networks
?
2022年8月にリリースしたOptunaの最新メジャーバージョンV3の開発の様子、アップデート内容等をご紹介します。
イベントサイト: https://optuna.connpass.com/event/260301/[DL輪読会]Set Transformer: A Framework for Attention-based Permutation-Invariant...
[DL輪読会]Set Transformer: A Framework for Attention-based Permutation-Invariant...Deep Learning JP
?
2020/02/21
Deep Learning JP:
http://deeplearning.jp/seminar-2/ モデル高速化百选
モデル高速化百选Yusuke Uchida
?
このドキュメントでは、特定のハードウェアに依存しない畳み込みニューラルネットワーク(颁狈狈)の推论高速化手法を绍介しており、モデルパラメータ数や计算量、モデルファイルサイズの削减に焦点を当てています。具体的な手法として、畳み込みの分解、枝刈り、アーキテクチャ探索などが挙げられ、それぞれのアプローチによる计算効率の改善が説明されています。また、モデル圧缩と速度向上を狙った自动化手法も议论されています。[DL輪読会]Attention is not Explanation (NAACL2019)
[DL輪読会]Attention is not Explanation (NAACL2019)Deep Learning JP
?
2019/04/12
Deep Learning JP:
http://deeplearning.jp/seminar-2/ 工学系大学4年生のための论文の読み方
工学系大学4年生のための论文の読み方ychtanaka
?
The document appears to reference several academic papers and conferences, including submissions to IEEE and ACM journals. It mentions contributors and includes links to grant information. The specific content and findings are not detailed in the provided text.SSII2021 [TS3] 機械学習のアノテーションにおける データ収集? ? 精度向上のための仕組み?倫理や社会性バイアス ?
SSII2021 [TS3] 機械学習のアノテーションにおける データ収集? ? 精度向上のための仕組み?倫理や社会性バイアス ?SSII
?
SSII2021 [TS3] 機械学習のアノテーションにおける データ収集? ? 精度向上のための仕組み?倫理や社会性バイアス ?
6/11 (金) 9:30～10:40
講師：藤本 敬介 氏（ABEJA）
概要：Deep Learning（深層学習）では大量の良質なデータを学習することで、高い精度を発揮してきました。実問題にこれを適用させるためには、如何にして正しくデータを集めるかが重要な課題の一つとなっています。データを集める際に、質が悪いものや偏ったデータを集めてしまうと、適切にモデルを学習できません。本チュートリアルでは、大量の良質なデータを集めるための仕組みや手法、精度?速度面での改善方法、倫理や社会性バイアスに関して解説します。遺伝的アルゴリズム （Genetic Algorithm）を始めよう！
遺伝的アルゴリズム （Genetic Algorithm）を始めよう！Kazuhide Okamura
?
2014年11月度 AITC クラウド?テクノロジー活用部会 勉強会資料
遺伝的アルゴリズム （Genetic Algorithm）を始めよう！CMA-ESサンプラーによるハイパーパラメータ最適化 at Optuna Meetup #1
CMA-ESサンプラーによるハイパーパラメータ最適化 at Optuna Meetup #1Masashi Shibata
?
Optuna Meetup #1
https://optuna.connpass.com/event/207545/罢辞谤肠丑顿补迟补チュートリアル解説
罢辞谤肠丑顿补迟补チュートリアル解説西岡 賢一郎
?
2022/04/29開催された第10回機械学習の社会実装勉強会 (https://machine-learning-workshop.connpass.com/event/243466/) で発表した資料です。強化学習の基礎と深層強化学習（東京大学 松尾研究室 深層強化学習サマースクール講義資料）
強化学習の基礎と深層強化学習（東京大学 松尾研究室 深層強化学習サマースクール講義資料）Shota Imai
?
東京大学 松尾研究室が主催する深層強化学習サマースクールの講義で今井が使用した資料の公開版です．
強化学習の基礎的な概念や理論から最新の深層強化学習アルゴリズムまで解説しています．巻末には強化学習を勉強するにあたって有用な他資料への案内も載せました．
主に以下のような強化学習の概念やアルゴリズムの紹介をしています．
?マルコフ決定過程
?ベルマン方程式
?モデルフリー強化学習
?モデルベース強化学習
?TD学習
?Q学習
?SARSA
?適格度トレース
?関数近似
?方策勾配法
?方策勾配定理
?DPG
?DDPG
?TRPO
?PPO
?SAC
?Actor-Critic
?DQN（Deep Q-Network）
?経験再生
?Double DQN
?Prioritized Experience Replay
?Dueling Network
?Categorical DQN
?Noisy Network
?Rainbow
?A3C
?A2C
?Gorila
?Ape-X
?R2D2
?内発的報酬
?カウントベース
?擬似カウントベース
?RND（Random Network Distillation）
?ICM（Intrinsic Curiosity Module）
?Go-Explore
?世界モデル（World Models）
?MuZero
?SimPLe
?NGU（Never Give Up）
?Agent57
?AlphaGo
?AlphaGo Zero
?AlphaZero
?OpenAI Five
?AlphaStar
?マルチエージェント強化学習
科学と机械学习のあいだ：変量の设计?変换?选択?交互作用?线形性
科学と机械学习のあいだ：変量の设计?変换?选択?交互作用?线形性Ichigaku Takigawa
?
機械学習はそもそも汎用的な枠組みであり基本的には対象分野に依らず利活用できる。従って、分野を限定して物質科学に機械学習を活用するなどと言う場合、その本質的難所の大部分は、有効な変量の設計?変換?選択?交互作用?線形性などに関する、いわゆるfeature engineeringの問題に帰する。特に、科学研究では端的な説明因子や共通パターンの探究こそが目的であることが多く、その場しのぎではない方法論が期待されている。本発表では、医薬品、機能制御剤、有機EL材料、食品、化粧品、と波及範囲が広い有機低分子について、その物性の予測と生物活性の予測の違いを例に、関わってきた問題?方法?課題について紹介する。
http://ibisml.org/ibis2016/session3/More from joisino (13)
キャッシュオブリビアスアルゴリズム
キャッシュオブリビアスアルゴリズムjoisino
?
キャッシュオブリビアスアルゴリズムについての簡単な解説です。
/iwiwi/cacheoblivious-dsirnlp5 と https://erikdemaine.org/papers/BRICS2002/paper.pdf を参考にさせていただきました。
Speakerdeck: https://speakerdeck.com/joisino/kiyatusiyuoburibiasuarugorizumuMetric Recovery from Unweighted k-NN Graphs
Metric Recovery from Unweighted k-NN Graphsjoisino
?
The document discusses metric recovery from unweighted k-nearest neighbor (k-nn) graphs, highlighting its applications in user-side recommender systems and graph neural networks (GNNs). It outlines the challenges in estimating the latent coordinates from the k-nn graphs and presents a systematic approach to address these difficulties, including the importance of edge lengths and densities. The findings suggest that GNNs can successfully recover hidden features from graph structures, even with uninformative input features.Towards Principled User-side Recommender Systems
Towards Principled User-side Recommender Systemsjoisino
?
Ryoma Sato proposes a method called Consul for building user-side recommender systems when the system provided by a service like Twitter is unsatisfactory. Consul allows users to build recommender systems using only the information available to them through web pages, without having access to the full database. It does this while maintaining consistency with the official system, ensuring diversity in recommendations based on sensitive attributes, and being locally efficient without downloading all pages. Experiments show Consul performs as well as existing methods but is much more efficient due to its localized traversal of the recommendation graph. A case study demonstrates a user successfully building a new recommender system for Twitter using Consul.CLEAR: A Fully User-side Image Search System
CLEAR: A Fully User-side Image Search Systemjoisino
?
This document describes CLEAR, a fully user-side image search system developed by Ryoma Sato at Kyoto University. CLEAR allows users to build and publish their own image search engines without backend servers by formulating image search as a multi-armed bandit problem and implementing the system using only JavaScript on the client-side. This overcomes limitations of traditional search engines which require extensive resources to operate. CLEAR demonstrates that ordinary users can now develop customized image search tools.Private Recommender Systems: How Can Users Build Their Own Fair Recommender S...
Private Recommender Systems: How Can Users Build Their Own Fair Recommender S...joisino
?
JSSST 2022 https://jssst2022.wordpress.com/ における発表スライドです。
論文
Private Recommender Systems: How Can Users Build Their Own Fair Recommender Systems without Log Data? (SDM 2022)
arXiv: https://arxiv.org/abs/2105.12353An Introduction to Spectral Graph Theory
An Introduction to Spectral Graph Theoryjoisino
?
This document provides an introduction to spectral graph theory. It discusses how spectral graph theory connects combinatorics and algebra through studying graphs using eigenvalues and eigenvectors of adjacency matrices. It covers applications of spectral graph theory such as spectral clustering, which uses eigenvectors of the graph Laplacian as features for clustering nodes, and graph convolutional networks, which apply graph filtering and node-wise transformations to classify nodes in a graph.Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem...
Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem...joisino
?
NLP コロキウム https://nlp-colloquium-jp.github.io/ で発表した際のスライドです。
論文: https://arxiv.org/abs/2205.01954
GitHub: https://github.com/joisino/wordtour
概要
単語埋め込みは現代の自然言語処理の中核技術のひとつで、文書分類や類似度測定をはじめとして、さまざまな場面で使用されていることは知っての通りです。しかし、ふつう埋め込み先は何百という高次元であり、使用する時には多くの時間やメモリを消費するうえに、高次元埋め込みを視覚的に表現できないため解釈が難しいことが問題です。そこで本研究では、【一次元】の単語埋め込みを教師なしで得る方法を提案します。とはいえ、単語のあらゆる側面を一次元で捉えるのは不可能であるので、本研究ではまず単語埋め込みが満たすべき性質を健全性と完全性という二つに分解します。提案法の WordTour は、完全性はあきらめ、健全性のみを課すことで一次元埋め込みを可能にし、それでいて、全ての、とまでは言わないまでも、いくつかの応用において有用な一次元埋め込みを得ることに成功しました。最适输送入门
最适输送入门joisino
?
IBIS 2021 https://ibisml.org/ibis2021/ における最適輸送についてのチュートリアルスライドです。
『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144
Speakerdeck にもアップロードしました: https://speakerdeck.com/joisino/zui-shi-shu-song-ru-menユーザーサイド情报検索システム
ユーザーサイド情报検索システムjoisino
?
第6回 統計?機械学習若手シンポジウムの公演で使用したユーザーサイド情报検索システムについてのスライドです。
https://sites.google.com/view/statsmlsymposium21/
Private Recommender Systems: How Can Users Build Their Own Fair Recommender Systems without Log Data? (SDM 2022) https://arxiv.org/abs/2105.12353
Retrieving Black-box Optimal Images from External Databases (WSDM 2022) https://arxiv.org/abs/2112.14921最适输送の解き方
最适输送の解き方joisino
?
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ?アルゴリズムを紹介します。
線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。
1. ネットワークシンプレックス法
2. ハンガリアン法
3. Sinkhorn アルゴリズム
4. ニューラルネットワークによる推定
5. スライス法
このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。
『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144
Speakerdeck にもアップロードしました: https://speakerdeck.com/joisino/zui-shi-shu-song-nojie-kifangRandom Features Strengthen Graph Neural Networks
Random Features Strengthen Graph Neural Networksjoisino
?
This document proposes using random features to strengthen graph neural networks (GNNs) for node classification tasks. It summarizes that GNNs cannot distinguish nodes with identical features and are not universal approximators. By adding random features to each node, GNNs can distinguish nodes and tree views, allowing them to detect graph structures like triangles. Experiments on synthetic and real-world graphs show random feature GNNs outperform standard GNNs and are a simple way to boost GNN expressiveness and performance.Fast Unbalanced Optimal Transport on a Tree
Fast Unbalanced Optimal Transport on a Treejoisino
?
This document presents research by Ryoma Sato of Kyoto University on fast unbalanced optimal transport (UOT) algorithms that efficiently handle the transport of distribution masses while being robust to outliers. It discusses the challenges of UOT in one-dimensional spaces and introduces a new algorithm that reduces the computational complexity to O(n log? n), which is significantly faster than traditional methods. The proposed method extends to tree spaces and demonstrates empirical effectiveness, computing UOT with one million masses in under one second.グラフニューラルネットワークとグラフ组合せ问题
グラフニューラルネットワークとグラフ组合せ问题joisino
?
以下の二つの論文の紹介を中心に、グラフニューラルネットワークとグラフ组合せ问题の交わりについて解説しました。 SIG-FPAI での招待講演の内容に少し修正を加えたものです。
* Learning Combinatorial Optimization Algorithm over Graphs (NIPS 2017)
* Approximation Ratios of Graph Neural Networks for Combinatorial Problems (NeurIPS 2019)Ad
死にたくない
- 3. 問題 囚人がN(= 2n?1 )人いる 囚人は白帽か赤帽をかぶっている 自分の帽子の色は分からないが、他人の帽子の 色は全てわかる 各人は同時に自分の色を言うか何も言わない
- 4. 問題 ● 1人以上が発言し、発言した人全員が正解→勝 利 ● 全員沈黙、または一人でも間違う→死 生存確率が高くなるような作戦を求める
- 5. 例 赤白 →勝利
- 6. 例 白白赤 →死
- 7. N = 3 のとき
- 8. 方針 : 全列挙
- 9. 方針 : 全列挙 ● 囚人から見たパターンは2通り(他の人の色が同 じ、異なる) ● 作戦は全6通り ● この作戦を帽子の全パターンについて試す
- 10. 方針 : 全列挙 帽子の色の全パターンは以下の8通り ● (白、白、白) ● (白、白、赤) ● (白、赤、白) ● (白、赤、赤) ● (赤、白、白) ● (赤、白、赤) ● (赤、赤、白) ● (赤、赤、赤)
- 12. 答え 赤赤赤 →死 勝利:0 死:1
- 13. 答え →勝利 赤 勝利:1 死:1
- 14. 答え 赤 →勝利 勝利:2 死:1
- 15. 答え →勝利 白 勝利:3 死:1
- 16. 答え →勝利 赤 勝利:4 死:1
- 17. 答え 白 →勝利 勝利:5 死:1
- 18. 答え →勝利 白 勝利:6 死:1
- 19. 答え 白白白 →死 勝利:6 死:2
- 20. 答え 8パターン中6パターン勝利(75パーセント) 何故良いか? →各人が当てられる確率は50パーセントだ が、皆が間違うパターンが集中している
- 21. 答え 白白白 →死
- 22. N = 7 のとき
- 23. N = 7 のとき 帽子のパターンは128通り、作戦のパターンは 18通り 囚人にコンピュータは与えられない – 全列挙は難しい
- 24. 方針1 : 妥協
- 25. 方針1 : 妥協 3人選んでN = 3のときの方針をとる 他の4人は黙らせる
- 26. 方針1 : 妥協 赤
- 27. 方針1 : 妥協 勝利確率はN = 3のときと同じで75パーセント 利点 : 楽 難点 : 命を粗末にするのはダメ
- 28. 方針2 : ハミング符号
- 29. 2元ハミング符号 H7 2元ハミング符号 H7 とは？ 誤り訂正符号の1つ – 送りたい情報にノイズが混入しても訂正できるよう な符号 3つの集合A,B,Cに対するベン図を使う それぞれの集合は1,10,100(2進数)を表す
- 30. 2元ハミング符号 B C A H7 u1 u2 u3 u6 u4 u5 u7
- 31. 2元ハミング符号 H7 使い方 4ビットの情報( a1, a2, a3, a4 )を送る ビットをベン図の u3 , u5 , u6 , u7 に割り当てる それぞれの集合に属するビットの和が0になるよう に残りのビットを決める
- 32. 2元ハミング符号 例) = 1 , = 0 , = 1 , = 1 B C 0 1 1 0 1 0 1 A 符号) 0110011 H7 a1 a2 a3 a4
- 33. 2元ハミング符号 符号) 0110011 が 符号) 0100011 になってしまった B C 0 1 0 0 1 0 1 A H7
- 34. 2元ハミング符号 B H7 C 0 1 0 0 1 0 1 A A : 0 + 0 + 1 + 0 = 1(おかしい)
- 35. 2元ハミング符号 B H7 C 0 1 0 0 1 0 1 A B : 1 + 1 + 1 + 0 = 1(おかしい)
- 36. 2元ハミング符号 B H7 C 0 1 0 0 1 0 1 A A : 0 + 0 + 1 + 1 = 0(ただしい)
- 37. 2元ハミング符号 A : おかしい B : おかしい C : ただしい H7 →間違いはA , Bに属していて、Cに属していない →間違いは u3
- 38. 2元ハミング符号 H7 誤り訂正符号としての問題点 2つ以上の間違いが混入したら修正できない 符号) 0110011 が 符号) 0100111 になってしまった →0100101と修正してしまう
- 39. 答え 囚人に番号をつけておく 白帽を0,赤帽を1としてビット列をつくる ● 自分のビットを決めてハミング符号語にできるな ら、ハミング符号語にならないように帽子の色を言 う ● ハミング符号語にできないなら何も言わない
- 40. 答え 全員何も言わない – 任意の7ビット列は1ビット変更してハミング符号語にで きるのであり得ない 間違える – 帽子のビット列がハミング符号語のとき – 4ビットの送る情報それぞれに1つハミング符号語があ るので16通り 全員正解する – それ以外の128-16=112通り 勝利確率は 112/128 (87.5パーセント)
- 42. ハミング符号作戦が最適である証明 もし、他の人の帽子の色が同じで、自分の帽子 の色が変わった場合、死 (自分では変わっても区別できないから) 赤
- 43. ハミング符号作戦が最適である証明 つまり、作戦が成功する帽子のビット列に隣接 するビット列で、失敗するビット列が存在する 成功したビット列で、発言した1人のビットを変更 すると構成できる (隣接: 0110011 と 0100011 など)
- 44. ハミング符号作戦が最適である証明 失敗するビット列の集合をFとすると、Fの元xを 中心とする半径1の球B={y∈ Z2 7 | yはxに隣接し ているまたはy = x}の和は全ての7ビット列を覆 う必要がある 覆われていない元zがあるとすると、zのとき作 戦が成功し、zに隣接する元で失敗する元が存 在しないことになるから矛盾
- 45. ハミング符号作戦が最適である証明 |B| = 8 なので 8|F| ≧ 2^7 |F| ≧ 16 失敗するビット列は16個以上 よって H 7 による作戦が最適となる
- 46. 一般( N = 2 n )の場合?1
- 47. 一般( N=2n?1 )の場合 2元ハミング符号による作戦が最適であることが N = 7と同様に示せる(省略)
- 48. 一般( N=2n?1 )の場合 H2n?1 2n?1?n 2元ハミング符号 が伝える情報は ビットなので失敗するパターン(ハミング符号語 の数)は 22n?1?n 通り。 帽子のパターンは 通り 勝利確率は 22n?1 1?22n?1?n 2n= N 22n?1 =1? 1 N+1 Nが大きくなると勝利確率は限りなく1に近づく
- 50. ご清聴ありがとうございました