第1章 導入 (6～54 ページ) 第2章 P 対 NP 問題の定義 (55～90 ページ) 第3章 P=NP の場合にわかること (91～111 ページ) 第4章 P≠NP の場合にわかること (112～226 ページ) 第5章 まとめ (227～234 ページ)
90 分で学ぶ P 対 NP 問題
第1章 導入 (6～54 ページ) 第2章 P 対 NP 問題の定義 (55～90 ページ) 第3章 P=NP の場合にわかること (91～111 ページ) 第4章 P≠NP の場合にわかること (112～226 ページ) 第5章 まとめ (227～234 ページ)
世界一わかりやすいゼロ知識証明 Vol.2: Zero-Knowledge Proofs in the Context of Modern Cryptography
このブログシリーズをグラントプロジェクトとしてサポートしてくださっているイーサリアム財団、また執筆に際してフィードバックとレビューをしてくださった末神奏宙さんに感謝します。 Special thanks to Ethereum Foundation for awarding grants to this blog post series, and Sora Suegami for feedback and review. このブログシリーズは、ソフトウェアエンジニアに限らず、あらゆる日本の読者のみなさんに向けて、最先端の暗号技術とその重要性をわかりやすく説明するという趣旨で書かれています。それぞれ単体の記事としてもお読みいただけますが、順番に読み進めていくことでより理解が深まります。まだお読みでない方は、ブロックチェーンやコンセンサスアルゴリズムの仕組みについて解説しているVol.1を先に
世界一わかりやすいゼロ知識証明 Vol.1: A Gentle Primer on Ethereum
執筆に際して、フィードバックとレビューをしてくださった堤隆道さんに感謝します。 Special thanks to Takamichi Tsutsumi for feedback and review. 1. はじめに 「すべて偉大なものは単純である。」 『音と言葉』・フルトヴェングラー 日本語で書かれた技術系記事の課題 トピックに限らず、日本語で特定の技術に関して検索をかけると、検索結果が英語での検索に比べて圧倒的に少ないことに加えて、検索結果の99%は以下のいずれかに該当することがわかるでしょう。 幅広い読者層を意識するあまり、解説が表面的すぎる 解説自体は詳しいが、数学や技術に偏りすぎていて、読者層が限定される 海外の有名な記事の直訳 検索結果の絶対量については、テクノロジー分野が英語圏を中心として発展してきたことに起因するため、日本語化に至るまでに多少のタイムラグがあるのは仕方がな
線形代数学+Rustで画像圧縮のアルゴリズムを実装する - Qiita
こんにちは👋 長く暑い夏が終わろうとしている今ですが、筆者は秋の季節を満喫しております。 LabBaseでは線形代数学の基礎を使って検索エンジンを構築していますが、レコメンド、検索アルゴリズムによく使われる王道の手法について記事を書くことにしました。 概要 線形代数学の特異値分解（SVD）の知識を活かして、原始的な画像圧縮アルゴリズムをRustで実装します。 SVDとは？ SVDは、線形代数学でよく使われる行列の分解です。行列の分解は、同じマトリックスを他のマトリックスに分けて表現することです。SVDの他に、LU三角分解、QR分解などがあります。 SVDは、あるAというマトリックスの列空間と行空間の固有ベクトルを計算して、それぞれをUとVというマトリックスに収めます。さらに、Σという対角行列に、固有値の平方根を入れます。Vの転置行列をV'と定義しますが、以下の分解になります。 Σの体格行
自分でRaftを書いてみた話
Raftって？ 分散合意アルゴリズムの一種で、サーバー間のデータ一貫性保障や可用性担保に使われるやつ。 Raft登場以前は理解が難しい物ばかりだったが、Raftは理解の面でも実装の面でも容易なのが売り。(といっても僕には難しかったですが...) レポジトリ なぜ既存実装を見ずに書いたか、車輪の再発明をしたか ・なぜ車輪の再発明をしたか 「Goによる分散サービス」という本をやっていてRaftを使って分散ログシステムを実装する箇所があり、この時Raftの実装に興味を持ちました。 Raftの仕組み自体は大まかには知っていたんですが、もっとよく理解してみるには自分で実装するのが一番と思いやりました。 ・なぜ既存実装を見なかったか 今回は論文から自分で書き起こすという体験をしてみたかったからです。 既存実装を見ながらだと論文そっちのけになってしまったり、人が書いてるからもういいかな...みたいになっ
Raftとは？ 仕組みから考える得意なこと苦手なこと/What is Raft? Strengths and Weaknesses Based on Its Mechanism
-- 追記-- > termの説明で「今のリーダーが何代目のリーダーかを表す」と書かれていますが、あるterm内でリーダーが1人も選出されないことがあるので、termで何代目のリーダーかは表せなくないですか？ https://x.com/11Takanori/status/1801212885…
ED法と3値(+1,-1,0)のアイデアを元に新しい活性化関数(ExP2)を作ってGELU、ELUと性能比較してみた。MINIST精度 99.43%以上達成 - Qiita
ED法と3値(+1,-1,0)のアイデアを元に新しい活性化関数(ExP2)を作ってGELU、ELUと性能比較してみた。MINIST精度 99.43%以上達成DeepLearningPyTorch活性化関数誤差逆伝播法ED法 追記 ELUとの比較を追加しました、金子さんのアイデアの凄さが明確に結果に出ています。 また最後にニューロンが正・負どちらに発火しているのか可視化したチャートも追加しました。 初めに 誤差逆伝播法を用いずに、興奮性・抑制性ニューロンの出力を調整することでニューラルネットワークの学習を進める金子さんの誤差拡散法はとても衝撃的でした。 しかし、誤差拡散法は現在広く使用されているニューラルネットワークのアーキテクチャとは互換性がないため、 今すでに利用されているニューラルネットワークに興奮性、抑制性ニューロンのアイデアを直接反映できません。 そのため、今の誤差逆伝播法の範囲内
金子勇さんのED法の解説と弱点、行列積を使用した効率的な実装 - Qiita
はじめに 先日以下の記事が話題となり、とてもワクワクしたので自分も実装して色々実験してみました。 実装するうちに理解が深まったので一度、 誤差拡散法の元ネタ紹介から 数式の解説、 ED法の弱点、 行列計算を使用した実装と簡単なテスト結果、 実装上の工夫 までまとめてみたいと思います。 誤差拡散（Error Diffusion）法 もともとは画像の2値化において失われる情報を周囲のピクセルで補うことで、遠目に元の画像の濃淡が残っているように見せる技術（ハーフトーン処理の一種）です。 Error diffusion -Wikipedia（英語版） 左の画像をちょうど半分の明るさをしきい値として2値化すると中央の画像のようになりますが、誤差拡散法を適用すると2値化後も右の画像のようにある程度濃淡を保存・表現できます。 誤差拡散法（画像処理）のサンプルコード コメントアウト箇所はFloyd, St
LEIA: 言語間転移学習でLLMを賢くする新しい方法
Studio Ousiaと理化学研究所に所属している山田育矢です。 この記事では、大規模言語モデル（LLM）の性能を向上させる新しい方法であるLEIA（Lightweight Entity-based Inter-language Adaptation）を紹介します。 LLMは言語によって性能に顕著な差があり、訓練に使われるテキストが最も多い英語において特に性能が高い傾向があることが知られています。LEIAは、LLMが蓄えている英語の知識を他の言語から使えるようにする訓練を施すことで、英語以外の言語でのLLMの性能を向上させる新しい手法です。 この度、英語・日本語の2言語LLMであるSwallowの7Bと13Bのモデルに対してLEIAによる訓練を施して性能向上を行ったモデルを公開します。 ライセンスは、Swallowと同様のLlama 2 Community Licenseです。これらのモ
金子勇さんのED法のシンプルな解説を試みた - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに @pocokhc(ちぃがぅ)さんが、金子勇さんのED法を実装してMNISTの学習に成功しました。 金子勇さんの失われたED法 金子勇さんの失われたED法発掘の経緯 ここではちぃがぅさんのコードを元に、ED法をシンプルに解説していきたいと思います。 ED法をわかりやすく解説するため、今入力を(1,0)としたとき(0)を推論するXOR問題を考えてみましょう。 ED法の場合, 入力、重みともに正負(p,n)２つ分の変数を用意する必要があります。 例えば 入力を(1,0)とすると 1 (p) ,1 (n), 0 (p), 0 (n)
Winnyの金子さんのED法について | やねうら王 公式サイト
Winnyの金子勇さんが考案された機械学習アルゴリズムED法を再現して実装した人がいていま話題になっている。 『Winny』の金子勇さんの失われたED法を求めて…いたら見つかりました https://qiita.com/kanekanekaneko/items/901ee2837401750dfdad いまから書くことは私の記憶頼りなので間違ってたらコメント欄で教えて欲しい。 1998年ごろだと思うのだが、私はWinnyの金子勇さんのホームページの熱心な読者だった。(ページも全部保存してたので私のHDDを漁れば出てくると思うが、すぐには出せない。) Winnyのβ版が発表されたのが2002年なのでそれよりはずいぶん前である。 当時、金子さんはNekoFightという3D格闘ゲームを公開されていた。そのゲームには、自動的に対戦から学習するAIが搭載されていた。 当時の金子さんのホームページの
『Winny』の金子勇さんの失われたED法を求めて - Qiita
結論から言うと、この記事を読んだ @pocokhc (ちぃがぅ)さんという方が金子勇さんが書いたED法のサンプルプログラムを見つけてくださいました。 ちぃがぅさんの記事はこちら 自分で解明したかったという気持ちも無いことは無いですが、バズった時点で誰かが実装してくれそうな気はしていました。新卒からIT業界に入って4年目が始まったところですが、業務以外で初めて業界にコントリビュートできた気がして嬉しいです！ 追記ついでに、謝罪します。初回公開時に記事タイトル含め本文中で何か所か「Winney」と書いてしまっていた箇所がありました。失礼いたしました。誤字修正してあります。指摘してくださった何人かの方に感謝申し上げます。 はじめに 今更ですが映画『winny』を見ました。 劇中で、金子勇さんのセリフにED法という聞いたことのないアルゴリズムが登場しました。 『このNekoFightにはAIを搭載
（続）ファッションにおける類似商品検索アルゴリズムの性能評価 - DROBEプロダクト開発ブログ
概要 背景・目的 関連研究 提案手法 実験 アルゴリズムの説明 順位相関の確認 定量評価 定量評価の内訳 定性評価 おわりに 参考文献 DROBEで機械学習エンジニアをしております、藤崎です。 概要 ファッションアイテムを特徴づけるための情報として、画像とテキストがある。これらは異なる情報を含んでいると考えられる。 類似のファッションアイテムを検索する場面で、画像とテキストの情報を両方活用することで、検索の精度を向上させることができると推測される。 類似のファッションアイテムを検索するタスクで、両方の情報を活用した提案手法の性能を評価し、片方の情報だけを活用するよりも、大幅に性能が改善することを確認した。 背景・目的 この記事は以下の記事の続編です。 tech.drobe.co.jp 以前の記事で、私たちはプロのスタイリストが作成した評価データセットを用いて、複数のアルゴリズムを類似商品検
Othello is Solved 論文解説 (私見) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう
いろんなバンディットアルゴリズムを理解しよう - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今回は、何も知らないところからバンディットアルゴリズムを学びました。 シンプルなバンディットアルゴリズムから、各ユーザーごとに最適化するContextual Bandit、順序を最適化するCascading Banditまで解説します。 学んでいて疑問に思ったことを解消しつつ記載しています。 ソースコード https://github.com/birdwatcherYT/bandit 対象読者 バンディットアルゴリズムを理解して実装したい人 ユーザーごとにカスタマイズしたバンディットを理解して実装したい人（Contextual Band
プロンプトを遺伝的アルゴリズムで自動最適化するプロンプトエンジニアリング手法『Promptbreeder（プロンプトブリーダー）』 | AIDB
DeepMindによる最新の研究で、プロンプトエンジニアリングの新たな手法が発表されました。その手法は遺伝的アルゴリズムを用いてプロンプトを最適化するもので『Promptbreeder（プロンプトブリーダー）』と名付けられています。 Promptbreederは、従来のCoT（ステップバイステップ）手法を上回る性能を持つとされています。プロンプトエンジニアリングの分野において、新たな可能性を切り開くかもしれません。 参照論文情報 タイトル：Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution 著者：Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, Tim Rocktäschel 所属：Google DeepMin
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ 端的に言うと性能が良いからです。 これを理解するにはバッファプールへの理解が必要です。ディスク指向のデータベースの上では有限のメモリを最大限活用することでメモリに入り切らない巨大なデータ群に対して良好な参照性能を出す必要があります。バッファプールとはディスク上のデータの羅列を固定サイズのページ（InnoDBの場合16KB）の羅列であるとして読み書きに必要な分だけをメモリに移し取り複数の書き込みをできる限りメモリ内で受け止めて後でまとめてディスクに書き戻すという、ライトバック型のキャッシュのような機構です。 この中においてバッファプールは有限のサイズしか無いので適宜プール内のデータを書き戻して入れ替えながら上手くやっていく必要があります。 さてB+treeとB-treeの最大の違いは木のリ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
LLMの効率化を支えるアルゴリズム
【実践】エンジニアの基礎教養-アルゴリズムを学べる本
グラフアルゴリズム実践活用術
