Othello is Solved 論文解説 (私見) - Qiita
今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどうやら、チェッカーというゲームが以前弱解決された際の論文"Checkers Is Solved"のオマージュだろうという話です。 この記事には専門用語が出てくるので、最後の方に基礎知識として重要な用語や知識をまとめました。 お詫びと訂正 この記事の内容は、私が
50分で学ぶアルゴリズム / Algorithms in 50 minutes
本スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただくことを目標にします。 第 1 部：アルゴリズムとは 第 2 部：学年を当ててみよう 第 3 部：代表的なアルゴリズム問題 第 4 部：コンピュータとアルゴリズム
GPT-3生成のブログ、ハッカーニュースで1位に
カルフォルニア大学バークリー校の学部生Liam Porrが言語生成AIツール「GPT-3」を使って偽のブログ記事を作成したところ、ハッカーニュースで1位になったとMIT Technology Reviewが報じた。Porrは、GPT-3によって生成されたコンテンツが人間によって書かれたものと信じ込ませることができることを実証した。彼は「実際、超簡単だった、それが怖いところだった」と語っている。 彼のブログが完全にAIが生成したものだと気づいた人はほとんどいなかった。何人かは「購読」を押した。これまでで最も強力な言語生成AIツールであるGPT-3がコンテンツ制作にどのような影響を与えるかについては、多くの人が推測してきたが、今回のケースはその脅威を例証した。 GPT-3はサンフランシスコに拠点を置くOpenAIによって設計された機械学習モデルである。GPT-3は、あらゆる種類の情報を網羅した
コーディングインタビューの対策とその意義 (1/2) - 16bitのメモランダム
１．コーディングインタビューとは何か コーディングインタビュー（Coding Interview、またはProgramming Interview）とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。プログラマー、またはデータサイエンティストなどの採用試験として、米国を含むいくつかの国で用いられている。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。Googleなどは自社のYoutubeチャンネル動画でも説明している。 出題される問題としては、例えば、「複数の数字numbersと整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」といったものがある。この問題は有名なので通称が付いており、Two Sumと呼ばれる。 Two Sumの一例。与えられた数値の並
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
[論文紹介]グラフニューラルネットワークによる推薦アルゴリズム - Qiita
はじめに 昨今、サービスに推薦システムを導入することでUXを向上させることが多くなり、様々な推薦アルゴリズムが取り入れられております。学術界でも推薦は大きなテーマであり、様々なアルゴリズムが提案されております。 本記事では、推薦をする際に、「メディア上で、どんな人とと繋がっているか、どのアイテムにライクをしたか、どんなページを閲覧しがちか」など、人やアイテムとのつながりを重視して推薦するSocial Recommendationの最新論文であるGraphRec[1]を紹介します。GraphRecは2019年にWeb系のTop Coferenceの一つであるWWWで採択された論文です。 GraphRecは、近年グラフ界隈を盛り上げているグラフニューラルネットワーク(以下GNNs)を用いております。GNNsでは、あるノードiの特徴量に近傍ノードの特徴量を足し合わせること(aggregation
![[論文紹介]グラフニューラルネットワークによる推薦アルゴリズム - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/9eeaa576e4ce565745e431fea5d67643b4ee3c9e/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZ0eHQ9JTVCJUU4JUFCJTk2JUU2JTk2JTg3JUU3JUI0JUI5JUU0JUJCJThCJTVEJUUzJTgyJUIwJUUzJTgzJUE5JUUzJTgzJTk1JUUzJTgzJThCJUUzJTgzJUE1JUUzJTgzJUJDJUUzJTgzJUE5JUUzJTgzJUFCJUUzJTgzJThEJUUzJTgzJTgzJUUzJTgzJTg4JUUzJTgzJUFGJUUzJTgzJUJDJUUzJTgyJUFGJUUzJTgxJUFCJUUzJTgyJTg4JUUzJTgyJThCJUU2JThFJUE4JUU4JTk2JUE2JUUzJTgyJUEyJUUzJTgzJUFCJUUzJTgyJUI0JUUzJTgzJUFBJUUzJTgyJUJBJUUzJTgzJUEwJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWNsaXA9ZWxsaXBzaXMmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz04NGI0NGQ4MDMxODNiYjRiYjIwOGFiMmJhMGY3ZjdjOA%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTYxNiZ0eHQ9JTQwc2toaXVrJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz0zYWZhM2U3NmJlZGI2OGYyMDliYTRlZGRiNjY5NmIxYg%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D8456c28062a009db7fb7dd1be4e7f4a2)
TCPを（少しは）理解しておくべきその理由 | POSTD
この記事はTCPの 全て を理解する、あるいは 『TCP/IP Illustrated』 （訳注：日本語版: 『詳解TCP/IP〈Vol.1〉プロトコル』 ）を読破しようとか、そういうことではありません。ほんの少しのTCPの知識がどれほど欠かせないものなのかについてお話します。まずはその理由をお話しましょう。 私が Recurse Center で働いているとき、PythonでTCPスタックを書きました（ またPythonでTCPスタックを書いたらどうなるかについても書きました ）。それはとても楽しく、ためになる経験でした。またそれでいいと思っていたんです。 そこから1年ぐらい経って、仕事で、誰かが「NSQへメッセージを送ったんだが、毎回40ミリ秒かかる」とSlackに投稿しているのを見つけました。私はこの問題についてすでに1週間ほど考え込んでいましたが、さっぱり答えがでませんでした。 こ
SFC版風来のシレンの乱数生成アルゴリズムの話 考察編 - Qiita
この記事は続編です。 前回の記事で、SFC版風来のシレンのROMデータの解析内容を元に乱数がどのようにして生成されているかを解説しています。そちらを読んでからこの記事を読んでいただくと、より内容を理解しやすいかと思います。 前回の記事：SFC版風来のシレンの乱数生成アルゴリズムの話 解析編 SFC版風来のシレンの乱数の品質を調べる さて前回の記事でSFC版風来のシレンの乱数生成アルゴリズムが線形帰還シフトレジスタの一種であることが分かりました。 しかし乱数生成アルゴリズムは理解したものの、それによって生成された乱数が妥当な物なのかというのはアルゴリズムを見ただけでは分かりません。 シレンの乱数は偏りやすいと断言できるような目に見えて質が悪いものなのでしょうか。 この項でそれを考察してみたいと思います。 先にお断りしておきますが、本気で定量的・客観的に乱数の品質を検証しようと思うと本格的な統
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
珍しいSHA1ハッシュを追い求めて - プログラムモグモグ
「SHA1ハッシュってあるだろう？」 放課後、いつものように情報処理室に行くと、高山先輩が嬉しそうな顔でそう言った。 「ええ、SHA1、ありますね」 「SHA1って何桁か覚えているかい？」 「えっと…」 一年下の後輩、岡村が口を開いた。 「50桁くらいはありましたっけ…？」 先輩はパソコンに向かって何かを打ちはじめた。 現在、情報部の部員は三人しかいない。部長の高山先輩と、二年の自分と、後輩の岡村だ。いや、正確に言うと、先輩の学年にはもう少しいたのだが、もうほとんど部室に来ることはなくなってしまった。無理もない、この季節になると先輩たちは受験勉強で忙しくなる。 「例えば、こういうふうに… 適当なSHA1の長さを…」 echo -n | openssl sha1 | awk '{print length}' 部長だけは今も部活に来てこうやって色々なことを教えてくれている。本人曰く、普通に勉強
Graph Classes and Algorithms
[概要] 計算機で扱う問題は，多くの場合グラフ上の問題として定式化できる． 計算量の理論により，これまで多くの問題が``手に負えない''ことが示されてきた． 一方でこうした問題に対する現実的なアプローチがいくつか提案されてきた． 本稿ではグラフに制限を加えるアプローチについて解説する．DNA の切片間の関係などは， モデル化すると特別なグラフになる．こうしたグラフ上では， これまで手に負えないとされてきた問題が効率良く解けることがある． 本稿では，代表的なグラフクラスと，関連したアルゴリズムの最近の研究動向を解説する． [キーワード] アルゴリズム，グラフクラス，計算の複雑さ，理想グラフ [お断り] このページは，電子情報通信学会に掲載予定の同名の解説論文を加筆修正したものです． せっかく書いたので，より広く公開して，かつ，ときどきは更新して行こうかと思っています． リンクも少しずつ充実さ
ソフトな推論Markov Logic Networkの紹介 - Preferred Networks Research & Development
予約したもののインフォバーを手に入れられない海野です． 人間の高度な知的処理の一つが、推論処理です．今日はその推論を、述語論理と機械学習の組み合わせで模倣したMarkov Logic Networkという手法と、そのOSS実装であるAlchemyの紹介です． 鳥とはなんですか？という質問に対してどう答えるでしょうか．大雑把には、以下のように考えるでしょう． 鳥とは、空を飛ぶ動物です． この回答に対して、「ペンギンは飛ばないよ」と反論する人がいるかも知れません． 鳥とは、くちばしを持った動物です． すると、「カモノハシは鳥じゃないよ」と言われるでしょう．人間は初めて見た生き物が鳥かそうじゃないか判断するとき、どうしているのでしょうか．思うに、少数の規則（飛ぶかどうか．くちばしをもつか）から総合的に判断しているように思われます．人間の推論というのは概ね以下のような特徴を持っているのではないかと
「ルールは突然変わる」グーグル、アマゾン、フェイスブックの危険度
オークションの「イーベイ」はグーグルでの順位を大幅に下げ、出版社の「アシェット」（※訂正あり）はアマゾンから〝締め上げ〟を受け、そしてフェイスブックがメディアに逆上する――。 ネットで先週、そんな不可解な事例が相次いだ。 共通するのは、いずれもネットを席巻する巨大サービスの〝ルール〟にまつわるということだ。 ネットサービスの〝ルール〟は、システム変更によって突然変わる。だが大抵は、そもそものルールも、それがどう変わったのかもわからぬまま、どこかで誰かが思いもよらぬダメージを受ける。 そして、ネット社会のインフラと化した巨大サービスが、それを具体的に説明することはまずない。 グーグル、アマゾン、フェイスブック。ガリバーが支配する市場の危うさを、ブログニュースサイト「ギガオム」のマシュー・イングラムさんが、改めてまとめている。 「巨人たちの悪行：グーグル、フェイスブック、アマゾンが独占とブラッ
ISM-2012-TopicModels.ppt
統計数理研究所 H24年度公開講座 「確率的トピックモデル」 持橋大地 (統計数理研究所) 石黒勝彦 (NTTコミュニケーション科学基礎 研究所) 2013/1/15-16 統計数理研究所 会議室1 本講座の構成 1日目: トピックモデルの基礎 – トピックモデルとは, Naïve Bayes, PLSI, LDA – EMアルゴリズム, VB-EMアルゴリズム, Gibbsサンプラー, 他のモデルとの関係 2日目: トピックモデルの応用 – 複雑なトピックモデル、時系列モデル – 画像、音声、ネットワークデータ – 半教師あり学習、補助情報あり学習 無限モデル(ノンパラメトリックベイズ)は本講座では扱わない 2 講義予定 3 1日目 – AM/ 導入, LSI, ナイーブベイズ, PLSI, EMアルゴリ
ゼロから始めるDeepLearning_その1_ニューラルネットとは - 分からんこと多すぎ
対象とする人 ディープラーニングすごい！ ←聞き飽きた チュートリアルあるよ！ ←ふわっとしすぎて具体的なところが分からん こういう論文あるよ！ ←読めるわけないだろ そういう人向け。（たぶん学部四年程度向け） ニューラルネット初学者が、書ききるまで怪しいところ満載でも突っ走ります。 ニューラルネット（この記事） →（AutoEncoder） →（DenoisingAutoEncoder） →ホップフィールドネットワーク →ボルツマンマシン →Restrictedボルツマンマシン →（Gaussian Binary - Restricted Boltzmann Machines） →（DeepBeliefNetwork） →（DeepNeuralNetworks） →畳み込みニューラルネット（後日） までやる。 太線以外は読み飛ばしてOK 本文中では怖い式は使わない。（Appendixに書
5次魔方陣を一般的なコンピュータで10分で実行したという記事に対しての考察 : mswinvksの忘備録
[急いで打ったので文がぐちゃぐちゃですし強調等もないです。すみません。] [定期的に記事の一番下にこっそりと僕のコメントを追加しています。一応ご確認ください] このような記事を発見しました。 スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++） 魔方陣の総数を求める、ということを、僕はスーパーコンピュータT2K-Tsukubaで約2時間30分で計算しましたが、この記事では一般的なコンピュータで10分で計算した、というものです。挑発的ですね。 僕のプログラムを1コア上で実行すると約200時間かかりました。(2012年ごろのAMD Opteron) (TODO:スパコンでの実行時間から1コア上での実行時間を割り出すと、200時間からかけ離れてるけどなんでだろう?) そして、この記事での実行環境は12コアなので、1コア換算すると実行時間は10分*12コア=
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現
自然言語処理の最新手法"word2vec"で艦これ加賀さんから乳を引いてみる - あんちべ！
概要 この記事は自然言語処理という分野の最新手法word2vec を利用して誰でも遊べるようにするための手順を説明するものです。 word2vecを利用すると意味の計算が実現できます。 例えば"king"から"man"を引いて"woman"を足すと"queen"が出てきたり、 "東京"から"日本"を引いて"フランス"を足すと"パリ"が出てくるという面白い手法です。 自然言語処理とは人間が日常的に用いる自然言語をコンピュータに処理させ、 翻訳や要約、文字入力支援や質問応答システムを作るなどに活用されている分野です。 自然言語処理と言うと耳慣れない言葉かもしれませんが、 実は検索や推薦などで私たちが日常的に利用しているなじみ深い技術でもあります。 自然言語処理の適用範囲や要素技術は幅広いのですが、 その中でもword2vecの特色は、 冒頭でも挙げたように「意味の計算」が出来ることです。 これ
GoogleNewsのレコメンドの中身 - UMEko Branding
先日、全体ゼミで発表したときの内容ですが、ここにまとめときます。。GoogleNewsのレコメンドの中身を追った論文の要約です。少し前の全体ゼミで用いた資料です。ソース：Abhinandan Das,Mayur Datar,Ashutosh Garg,Shyam Rajaram,"Google News Personalization: Scalable OnlineCollaborative Filtering",WWW2007不勉強な個所が多々ありますので、誤っている箇所等ありましたら、是非ご指摘ください。 個人的には、最近のモデルベースの手法の勉強・おさらいという意味で用いているので、GoogleNews独自の拡張なり実装の部分の内容が省かれている場合があります。また、データ構造やMapReduceを用いた計算の仕組みの部分は、ここでは省略しています。。一応、 全体像 ・LSH(Lo
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
機械学習を用いた予測モデル構築・評価
