MOXBOX

Takami Torao #hazmat #moxbox
  • このエントリーをはてなブックマークに追加

基調のブルーは Čerenkov Radiation を意味するヤバいもの置き場。

search

Precaution

MOXBOX は日々のプログラミング経験や学習で習得した知識の理解を深めるために自分の理解の範囲で言語化し、必要になったときにいつでも思い出せるようにした上で安全に忘れて次の興味のための余力を脳に作ることを目的としている (従っていったん終えたことや周辺知識のことの方が多い)。基本的にノートであるため、時に数式の解法であったり実装アルゴリズムであったり、読書から要点抜粋した箇条書きであったり単なるコードのスニペットであったりと体裁はさまざまである。

このよう背景から、理解が及んでない部分には定義の不備、間違いなどが含まれる可能性がある。自分の理解と連動することから必ずしも学術的、時事的に正しい情報を載せていることを保証 (目的と) していない。

MOXBOX は 2017年9月下旬から書き始めた。サイトの Web サーバは Finagle をベースに実装した非同期 I/O サーバである。

Notation

特に明記しない限り \(\log\) の底は \(e\) とする。

最近の更新loading

\(\def\vector#1{\boldsymbol{#1}}\)

B-Tree

B-Tree または B 木は自己平衡型の多分木データ構造である。各ノードがソート済みの複数のキーと子ノードへの参照を持つことで、二分木より高さの低いツリー構造を形成することができる。このため検索や挿入、削除操作の効率が良く、特にディスクや SSD のようなストレージドライブに対する I/O を最適化するように設計できることから、大量のデータを効率的に管理するようなデータベースやファイルシステムなどで広く使用されている。…

sentiment_very_satisfied 2024年12月4日(水) #BTree

木構造

木構造 (tree structure) はデータを階層的に表現するためのデータ構造である。ノード (頂点) とエッジ (辺) で構成されるグラフ構造の一種だが、閉路を持たない DAG である。

edit_note 2024年11月12日(火) #BTree

論文翻訳: An Introduction to Bε-trees and Write-Optimization

B-Tree と似た構造を持ち、更新と挿入で高い性能を持つ Bε-Tree に関する 2015 年の記事。

sentiment_very_satisfied 2024年11月8日(金) 2015年の記事 #BTree #BεTree

論文翻訳: Lower Bounds for External Memory Dictionaries

検索操作においては従来の B-Tree の定数オーダーの性能を維持しながら、更新操作のスループットを大幅に改善する Bε-Tree についての 2003 年の論文。

sentiment_very_satisfied 2024年11月5日(火) 2003年の論文 #BTree #BεTree

論文翻訳: Computing Extremely Accurate Quantiles Using \(t\)-Digests

大規模データセットから \(k\) 番目に小さい要素の近似値を効率的に見つけるためのアルゴリズム \(t\)-digest についての 2019 年の論文。

sentiment_very_satisfied 2024年9月23日(月) 2019年の論文 #TDigest #分位数

分位数

分位数 (quantile) またはクォンタイルはデータや確率の分布を一定の割合で区切るための値を指す。例えばデータを昇順に並べたとき、その累積割合が特定の値 (20%, 50%, 75% など) となる点を示すことで、データのばらつきや中心傾向、偏りなどを把握しやすくするための指標として使用される。…

sentiment_satisfied 2024年9月20日(金) #qdigest #選択アルゴリズム #確率的データ構造 #ストリーミングアルゴリズム

論文翻訳: Sampling From a Moving Window Over Streaming Data

データストリームから得られる最近の \(n\) 個のデータからランダムサンプリングを行うために移動ウィンドウを使用した手法を解説する 2002 年の論文。1 つの「現在選択されているサンプル」と複数の「選択されているサンプルまたはその後継者がウィンドウを外れたときにサンプルとして選択される後継者」をチェーン状に保持することで、サイズ \(n\) の移動ウィンドウの中で常に 1 つの要素をサンプリングする。…

sentiment_very_satisfied 2024年9月16日(月) 2002年の論文

TRANSCRIPT: Various Techniques Used in Connection With Random Digits

A 1951 paper by John von Neumann discussing techniques for generating random numbers, dealing with pseudo-random number generation for Monte Carlo methods and its limitations.

sentiment_very_satisfied 2024年9月8日(日) 1951年の論文

論文翻訳: Ranking and unranking permutations in linear time

順列を識別する一意な整数を計算する「ランク」と、順列のランクに基づいて並びを生成する「アンランク」を効率的に行うアルゴリズムを提案する 2001 年の論文。従来の方法では \(O(n \log n)\) 時間がかかることが多いが、この論文で紹介されている手法では事前計算された階乗を利用して \(O(n)\) の線形時間実行できるようにしている。…

sentiment_very_satisfied 2024年9月3日(火) 2001年の論文 #順列

順列と置換

順列 (permutation) には次の 2 つの意味がある。複数の要素を直線的な順序で配置した状態 \(n\) 個の異なる要素からなる集合 \(A=\{a_0,a_1,\ldots,a_{n-1}\}\) は \(n!\) 通りの順列を構成することができる。例えば 3 個の要素からなる集合 \(\{a,b,c\}\) は \((a,b,c)\), \((a,c,b)\), \((b,a,c)\), \((b,c,a)\), \((c,a,b)\), \((c,b,a)\) の \(3!=6\) 通りの順列を生成できる。…

sentiment_satisfied 2024年9月1日(日)

HyperLogLog

HyperLogLog は多重集合 (multiset) における異なりの数問題 (distinct-count problem) を概算するための確率的アルゴリズム。つまり同じ値が複数存在するデータセットから値の種類の数を概算する。異なりの数 (distinct count) とは SQL で COUNT(DISTINCT item) に相当する数であり、例えば集合 \(\{T,\) \(A,\) \(A,\) \(C,\) \(G,\) \(C,\) \(T,\) \(A\}\) の異なりの数は 4 である。…

sentiment_very_satisfied 2024年8月29日(木) #HyperLogLog #Redis #大規模データ構造 #確率的データ構造 #ストリーミングアルゴリズム

論文翻訳: Hopscotch Hashing

既知のハッシュテーブルアルゴリズムより逐次/並行の両面でパフォーマンスに優れている Hopscotch ハッシュ法に関する 2008 年の論文 (ドラフト)。

sentiment_very_satisfied 2024年8月27日(火) 2008年の論文 #HopscotchHashing #Hashtable

論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

大規模データセットから要素のカーディナリティを推定するアルゴリズムである HyperLogLog に関する 2007 年の論文。HyperLogLog におけるカーディナリティとは distinct つまり「異なりの数」であり、集合論の文脈において「濃度」を意味するカーディナリティとは異なる点に注意。…

sentiment_very_satisfied 2024年8月26日(月) 2007年の論文 #HyperLogLog #BigData #確率的データ構造

Boyer-Moore 過半数票アルゴリズム

Boyer-Moore 過半数票アルゴリズム (Boyer-Moore majority vote algorithm) は多重集合から過半数を占める要素 (\(N/2\) 個より多い要素) を見つけるためのストリーミングアルゴリズムである。(1) において選挙で投票された票の過半数を獲得した候補者を特定するアルゴリズムを例に紹介された。…

done 2024年8月25日(日) #ストリーミングアルゴリズム

Count-Min スケッチ

Count-Min スケッチ (count-min sketch) (1) は大規模データセットにおいて頻度や重み付け合計を効率的に推定するための確率的データ構造である。膨大な数の要素を複数のハッシュ関数を用いて異なるカウンターにマッピングし、その最小値を参照することで頻度を推定する。…

sentiment_very_satisfied 2024年8月22日(木) #CMS #確率的データ構造

論文翻訳: Don't Thrash: How to Cache your Hash on Flash

Quotient フィルターをカスケード上に配置してフラッシュデバイスへ対応した、近似メンバーシップクエリーのための確率的データ構造である Cascade フィルターに関する 2012 年の論文。

sentiment_very_satisfied 2024年8月13日(火) 2012年の論文 #QuotientFilter #CascadeFilter #確率的データ構造

Quotient フィルター

Quotient フィルター (3) または商フィルターは大規模データセットに対する近似メンバーシップクエリー (AMQ; approximately membership query) を行うための確率的データ構造である。Bloom フィルターと似ているが空間とキャッシュをより効率的に利用できる構造を持つ上、テーブルサイズの変更や要素の削除をサポートすることができる。…

sentiment_very_satisfied 2024年8月12日(月) #AMQ #QuotientFilter #確率的データ構造

コンシステントハッシュ法

コンシステントハッシュ法 (consistent hashing) は分散システムにおいて処理やデータを均等に分散させるためのハッシュ技術である。Chord のような分散ハッシュテーブルにおけるオブジェクトロケーションのアルゴリズムとして使用されている。

edit_note 2024年8月10日(土) #DHT

ハッシュテーブル

ハッシュテーブル (hashtable) はさまざまなデータ型のキーをハッシュ化 (hashing) して効率的に管理し検索するためのデータ構造である。一般にキー \(x\) と関連する任意の値 \(y\) (サテライトデータ) を保持して \(y\) を効率的に検索するために用いられる。…

sentiment_very_satisfied 2024年8月8日(木) #Hashtable #Hashing

文字列マッチング

文字列マッチングは、テキストデータに含まれる特定の部分文字列 (パターン) を効率的に検索する技術である。大きな文書や巨大なデータベースで特定の単語やフレーズを見つけ出すために使用される。

sentiment_satisfied 2024年8月7日(水)

Okapi BM25

Okapi BM25 は情報検索における文書のランク付けアルゴリズムの一つである。クエリーに対する文書の関連性を評価するために使用される。BM25 は TF-IDF の発展系として、特に文書の長さや単語の頻度に基づいて関連性スコアを調整するために設計されている。

done 2024年7月23日(火) #OkapiBM25 #BM25

固有値

正方行列 \(A\) について、\(Ax=\lambda x\) を満たす値 \(\lambda\) とベクトル \(x\) をそれぞれ \(A\) の固有値 (eigenvalues)、固有ベクトル (eigenvectors) と呼ぶ。

done 2024年7月17日(水)

全文検索

全文検索 (full-text search) はテキストデータベースや文書集合として存在する構造化されていないテキストから特定の単語やフレーズを検索し、その出現位置や関連する文書を取得するための検索技術である。単純なキーワード検索と異なり、ランキング付けや表記揺れを考慮した検索によってよりユーザの目的に近い検索結果を提供する。…

sentiment_very_satisfied 2024年7月4日(木)

論文翻訳: The Log-Structured Merge-Tree (LSM-Tree)

メモリ内のデータを定期的にストレージ上の大規模構造にマージすることで高い書き込みスループットと効率的なクエリー処理を実現するデータ構造である LSM-Tree に関する 1996 年の論文。

sentiment_very_satisfied 2024年6月18日(火) 1996年の論文 #LSMTree

編集距離

編集距離 (edit distance) は 2 つの文字列間で一方の文字列を他方の文字列と一致させるために必要な最小の操作回数である。これは 2 つの文字列が互いにどれだけ異なるかを定量化している。文字列の類似性を評価するために自然言語処理の分野で広く使用されている。

done 2024年6月11日(火) #Levenshtein

Apache Lucene

Apache Lucene は高性能な全文検索とテキスト解析のためのオープンソースライブラリ。1999 年に Doug Cutting によって最初に開発され、その後 Apache Software Foundation のプロジェクトとして継続的に開発されている。Lucene は Java で書かれており、強力な検索機能はさまざまな規模のアプリケーションに柔軟に対応できる設計となっている。…

done 2024年6月8日(土) Java 21 #Lucene

論文翻訳: FileDAG: A Multi-Version Decentralized Storage Network Built on DAG-based Blockchain

sentiment_very_satisfied 2024年6月3日(月) 2022年の論文 #FileDAG

Kindle Paperwhite: KIOSK 端末化

edit_note 2024年5月13日(月) #Kindle

Kindle Paperwhite

edit_note 2024年5月2日(木) #Kindle

Kindle Paperwhite: Jailbreak & SSH 接続

Amazon Kindle の Jailbreak はその本体がリリースされた当初からコミュニティによって活発に行われてきた。初期の手法はメーリングリストを通じて個々のユーザの作業によって貢献されてきた。しかしその積み重ねによって現在では情報が散在し、情報も口語の英語で書かれていて理解しにくい状況となっている。…

sentiment_very_satisfied 2024年5月2日(木) Kindle Paperwhite 2015 #Kindle

論文翻訳: Cuckoo hashing

衝突時に他の位置へ要素を「追い出す」ことで高速な検索、挿入、削除が可能なハッシュテーブルの一種である Cuckoo Hashing に関する 2014 年の論文。

sentiment_very_satisfied 2024年4月25日(木) 2004年の論文 #CuckooHashing #Hashtable

論文翻訳: Cuckoo Filter: Practically Better Than Bloom

要素が集合に含まれているかを効率的に判断するための確率的データ構造である Bloom フィルターの変種で、削除操作において Bloom フィルターより高い性能を示す Cuckoo フィルターに関する 2014 年の論文。Cuckoo ハッシュテーブルに基づいている。要素を格納する 2 つの位置を決めるのに部分キー Cuckoo ハッシングを導入したことで、元の要素を参照しなくても位置を移動できるようにしている。…

sentiment_very_satisfied 2024年4月21日(日) 2014年の論文 #CuckooFilter #BloomFilter #確率的データ構造

論文翻訳: A Tree Clock Data Structure for Causal Orderings in Concurrent Executions

因果一貫性において、Version Vector の因果履歴をベクトルからツリー構造にすることで処理の計算量をレプリカ数に対する線形から劣線形に改善するという 2022 年の論文。

sentiment_very_satisfied 2024年4月19日(金) 2022年の論文 #TreeClock

論文翻訳: GossipSub: A Secure PubSub Protocol for Unstructured, Decentralised P2P Overlays

非構造化分散型 P2P オーバーレイで使用される安全な pub/sub プロトコルである gosshipsub について説明する 2019 年の論文。

sentiment_very_satisfied 2024年4月16日(火) 2019年の論文 #GossipSub

論文翻訳: Merkle-CRDTs: Merkle-DAGs meet CRDTs

分散システムにおけるデータの同期を効率的に行う、Merkle-DAG と CRDT を組み合わせたデータ構造である Merkle-CRDTs に関する 2020 年の論文。

sentiment_very_satisfied 2024年4月13日(土) 2020年の論文 #MerkleCRDT #CRDT #LogicalClock

企業行動の理論

企業は市場経済における主要な経済主体の一つである。企業の行動は市場の価格や生産量などの経済変数に影響を与え、市場の機能や効率性に大きな影響を及ぼす。その動機は利益最大化であり、生産、価格設定、競争戦略などのさまざまな活動を通じてその目標を実現しようとする。本章では、企業の行動に焦点を当て、企業の意思決定が市場経済に及ぼす影響を考える。…

done 2024年3月7日(木)

消費者行動の理論

ミクロ経済学は個々の主体が自己利益を最大化する合理的な行動をとるという一貫した前提に基づいて経済現象を説明する。経済活動の善し悪しは消費者一人一人の利益や損失に即して民主的に判断される。経済行動を誘因やインセンティブの観点から理解し、消費者の合理的行動がどのように現われるかを理解することが重要である。…

sentiment_very_satisfied 2024年3月5日(火)

ナッシュ均衡

ナッシュ均衡 (Nash equilibrium) は各プレーヤーの戦略が互いに最適反応となっている状態である。つまり、集団の中で 1 人が戦略を変えたとしても本人の利得が増えない状況がすべてのプレーヤーに対して成り立っている状態である。

sentiment_satisfied 2024年2月15日(木)

マルチエージェントシステム

マルチエージェントシステム (MAS; multi-agent system) は、複数の独立したエージェントが相互作用して目的を達成するためのシステムである。各エージェントは独自の目標や知識、能力を持ち、他のエージェントと協調したり競合しながら共通の目的を達成しようとする。マルチエージェントシステムは分散システムの一種である。…

edit_note 2024年2月14日(水) #MAS

ゲーム理論

ゲーム理論 (game theory) は、複数の参加者 (プレイヤー) が互いに影響し合う状況でその戦略や意思決定を数学的にモデル化するための数学的な枠組みである。経済学、政治学、生物学、コンピュータ科学などの様々な分野で応用されている。

edit_note 2024年2月14日(水)

モジュール性

sentiment_satisfied 2023年12月12日(火)

認証と認可

edit_note 2023年11月17日(金)

Signal プロトコル

edit_note 2023年10月8日(日) #Signal

鍵導出アルゴリズム

鍵導出 (key derivation) は 1 つの秘密から複数の秘密を導出する手法である。より具体的には、ある鍵素体 (key material) から暗号論的強度を持つ 1 つ以上の秘密鍵を決定論的に導出するために用いられる。このような鍵導出を行うための関数を鍵導出関数 (key derivation function; KDF) と呼ぶ。…

sentiment_satisfied 2023年10月3日(火) #鍵導出 #KDF #HKDF

JSON Web Token

edit_note 2023年9月28日(木) RFC 7519 #JWT

RFC翻訳: HMAC-based Extract-and-Expand Key Derivation Function (HKDF)

ある秘密鍵に基づいて複数の鍵を生成するスキームを規定している RFC 5869 についての仕様文書。

sentiment_very_satisfied 2023年9月28日(木) RFC 5869 #鍵導出 #KDF

Rust: RISC-V ビルド

edit_note 2023年9月26日(火) Rust 1.72.1 #RISCV

仕様翻訳: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions - 転置に基づくハッシュ関数と拡張可能出力関数

暗号論的ハッシュ関数である SHA-3、および可変長出力が可能な SHAKE に関する 2015 年の NIST 仕様。

sentiment_very_satisfied 2023年9月8日(金) 2015年の仕様 #SHA3 #SHAKE #Keccak #FIPS202

ソフトウェアデザイン

edit_note 2023年9月3日(日)

O'Reilly Japan - ソフトウェアアーキテクチャの基礎

edit_note 2023年9月3日(日) 2019年 IETF Draft 4

TRANSCRIPT: A Fast Algorithm for Finding Dominators in a Flowgraph

A 1979 paper on dominator tree. A transcription of an old PDF for the purpose of reading it in machine translation.

sentiment_very_satisfied 2023年8月31日(木) 1979年の論文

word2vec

分散表現 (distributed representation) とは単語の意味を数値化してベクトル空間に表すことである。単語をベクトル空間に埋め込むことから単語埋め込み (word embedding) とも呼ばれる。一般に分散表現によって一つの単語は数十~数百次元のベクトルに変換される。…

sentiment_very_satisfied 2023年8月25日(金) gensim 4.3.0 #word2vec

論文翻訳: Efficient Estimation of Word Representations in Vector Space

3 層のニューラルネットワークを使用して単語の分散表現 (単語埋め込み) を生成するアルゴリズム Word2vec に関する 2013 年の論文。

sentiment_very_satisfied 2023年8月21日(月) #word2vec

CometBFT: データ構造

done 2023年8月15日(火) CometBFT 0.37.2 #Blockchain #CometBFT #Tendermint #Cosmos

VSCode: 拡張機能開発

この記事では Visual Studio Code (vscode) の拡張機能の作成方法について説明する。拡張機能は vscode の機能を拡張するための小さなプログラムで、vscode の拡張機能エディタを使用して JavaScript または TypeScript で記述することができる。…

done 2023年8月13日(日) node 1.1

論文翻訳: Graph Drawing by Force–Directed Placement

Force-Directed Placement を用いてノード間の引力と反発力を調整してグラフ構造を 2 次元上に均等に配置する手法を提案している 1991 年の論文。Fruchterman-Reingold アルゴリズムとも呼ばれる。

sentiment_very_satisfied 2023年8月7日(月) 1991年の論文 #ForceDirected #FruchtermanReingold

CometBFT: ABCI

ABCI (application blockchain interface) は CometBFT コアの各コンポーネント (コンセンサス層) とブロックチェーンアプリケーションの実装 (アプリケーション層) が通信するためのインターフェース仕様である。ブロックチェーンアプリケーション開発者が CometBFT と連携するための標準的なプロトコルを定義している。…

sentiment_very_satisfied 2023年7月29日(土) CometBFT 0.37.2 #Blockchain #CometBFT #Tendermint #Cosmos

CometBFT: P2P ネットワーク

P2P ネットワーク機能は (例えばコンセンサスアルゴリズムのように) CometBFT ノードが協調しながら進行する必要のある処理のためのフレームワークである。基本はアクターモデルに似た設計であり、ノード間のメッセージングから TCP のような下層の通信レイヤーの詳細を隠蔽し、メッセージの配信とそれを処理するリアクター (サービス) という概念に抽象化する。…

sentiment_very_satisfied 2023年7月24日(月) CometBFT 0.37.2 #Blockchain #CometBFT #Tendermint #Cosmos

仕様翻訳: The RISC-V Instruction Set Manual Volume II: Privileged Architecture

RISC-V 特権 ISA に関する 2021 年の仕様書。

sentiment_very_satisfied 2023年7月18日(火) RISC-V #RISCV #ISA

仕様翻訳: The RISC-V Instruction Set Manual Volume I: Unprivileged ISA

RISC-V 非特権 ISA に関する 2019 年の仕様書。

sentiment_very_satisfied 2023年7月18日(火) RISC-V #RISCV #ISA

CometBFT: コンセンサス

分散システムにおけるコンセンサスとは、分散ネットワーク上のすべての正常なノード間で合意を形成して共通の状態を確立するためのメカニズムである。よりブロックチェーン向けの表現では、コンセンサスに参加しているノードが「提案されたブロックを受理 (または拒否)」という共通の結論に到達するためのメカニズムを意味する。…

sentiment_very_satisfied 2023年7月9日(日) CometBFT 0.37.2 #Blockchain #CometBFT #Tendermint #Cosmos

CometBFT: Mempool

mempool (メモリプール, メムプール) は未確定のトランザクション (unconfirmed transaction) を他のノードと共有し、提案ブロックの生成が行われるまで一時的に保存することを目的とした CometBFT の機構である。

sentiment_very_satisfied 2023年7月9日(日) CometBFT 0.37.2 #Blockchain #CometBFT #Tendermint #Cosmos

CometBFT 構造解説

CometBFT は強い一貫性を持つ分散システムを構築するためのソフトウェアおよびその SDK (software development kit)。プライベート/コンソーシアムブロックチェーン用途に特化している。同じ名前の CometBFT または旧名の Tendermint-BFT と呼ばれる BFT (Byzantine fault tolerance; ビザンチン障害耐性) 特性を持つコンセンサスアルゴリズムを実装し、ステートマシン・レプリケーションによるトランザクション直列化でブロックチェーンのブロックを生成することを目的としている。…

done 2023年6月29日(木) CometBFT 0.37.2 #Blockchain #CometBFT #Tendermint #Cosmos

WebAssembly

WebAssembly または WASM はスタックベースの仮想マシン用バイナリ命令フォーマットである。バイナリを変更せずに様々な OS とアーキテクチャで実行できるように移植性の高い設計が行われている。WebAssembly は C++ や Rust、Go などの高レベル言語のコンパイルターゲットとして生成される。…

edit_note 2023年6月29日(木) #WebAssembly

Rust: WebAssembly プログラミング

WebAssembly は可搬性の高い仮想マシン用バイナリ命令フォーマットです。Rust はターゲットバイナリに WebAssembly を選択することができます。

sentiment_very_satisfied 2023年6月25日(日) wasmer 4.0 #Rust #WebAssembly #WASM #wasmer

集合論

集合論は数学の基礎的な分野であり、数学的対象を扱う上での基本的な概念や枠組みを提供する。これは集合や要素の集まりを厳密に定義し、それらの性質や関係を明確にすることでそれらを形式的に表現したり操作を行うことができる。

sentiment_very_satisfied 2023年6月23日(金) #集合論

符号理論

edit_note 2023年6月22日(木) #CodingTheory

Base64 エンコーディング

Base64 エンコーディングは任意の長さを持つバイナリデータを ASCII テキストに変換するための符号化アルゴリズム。

done 2023年6月3日(土) #Base64

誤り検出訂正

誤り検出訂正 (error detection and correction) はデータの伝送やデータ保存時におけるエラー (誤り) の検出と訂正を行うための手法。データは、伝送やストレージで生じる物理的なノイズや機器の不具合によって情報の欠損が生じ正確性を損なう可能性があるが、誤り検出訂正によってそれらのエラーを検出し訂正することで正確性と信頼性を向上させることができる。…

sentiment_very_satisfied 2023年5月31日(水) #ECC

Erasure コーディング

Erasure コード (erasure code; 末梢符号) はビットの喪失に対する誤り訂正符号である。誤り検出訂正がビットエラーの検出や訂正を対象としていたのに対して、Erasure コードは喪失したデータブロックを他のデータブロックとパリティブロックから復元できることから、高い信頼性が求められる分散ストレージシステムなどで使用されている。…

edit_note 2023年5月30日(火) #ErasureCoding

Blockchain: レイヤー 2

done 2023年3月15日(水)

秘匿共通集合

秘匿共通集合 (PSI; private set intersection) は 2 つパーティ \(P_a\) と \(P_b\) がそれぞれで保持しているデータ集合 \(A\), \(B\) の共通集合 (交差) \(A \cap B\) を特定できる暗号技術。共通集合に含まれない要素の情報は相手に一切明かされないことから二者間のデータプライバシー保護が重要なケースにおいて有用な暗号技術である。…

sentiment_satisfied 2023年3月9日(木) #MPC #PSI #OPRF #セキュアマルチパーティ計算

TRANSCRIBE: Judgement under Uncertainty: Heuristics and Biases

Very prominent 1974 paper on Heuristics and Bias. A transcription of an old PDF for the purpose of reading it in machine translation.

sentiment_very_satisfied 2023年3月1日(水) 1974年の論文

TRANSCRIBE: Non-Interactive Oblivious Transfer

A 1990 paper on non-interactive oblivious transfer. A transcription of an old PDF for the purpose of reading it in machine translation.

sentiment_very_satisfied 2023年2月27日(月) 1990年の論文 #MPC #OT

紛失通信

紛失通信 (oblivious transfer; OT) は送信者の送信する \(n\) 個のデータのうち受信者が \(k\) 個を受信できる二者間の通信プロトコル。ここで送信者は \(n\) 個のうちのどの \(k\) 個が受信されたかを知ることができず、受信者は \(k\) 個以外のデータを知ることができないという暗号論的な性質を持つ。…

sentiment_satisfied 2023年2月26日(日) #OT

基数変換

数の表現ですべての数値に一意の記号を割り当てようとすることは非現実的である。代わりに、古代から有限の記号の組み合わせで任意の数を表現する記数法 (numerical notation) が用いられてきた。現代で一般的に使用されている記数法は位取り記数法 (positional notation) である。…

sentiment_very_satisfied 2023年2月24日(金)

キャッシュ

キャッシュ (cache) はプログラムやシステムのデータアクセスの高速化を目的としたメカニズムおよびその保存領域。アクセス頻度の高いデータや、次にアクセスされることが予測されるデータ、または生成や取得に時間がかかるデータを一時的に高速に読み取りが可能なキャッシュに保存することでアプリケーションの処理時間を短縮することを狙う。…

done 2023年2月21日(火) #LRU #MRU

乱数検定: NIST SP 800-22

NIST SP 800-22 (1) (または単に NIST 検定) は NIST が 2001 年に刊行した論文による (疑似) 乱数生成器のランダム性を検定するための検定スイートである。この検定プログラムは NIST のサイト (2) からダウンロードできる。

sentiment_very_satisfied 2023年2月18日(土) 2001年の論文 #NIST検定 #Randomness

MOXBOX ウィジェット

この MOXBOX で JavaScript や CSS (あるいはサーバサイドの XSLT や REST API など) で実装されたウィジェットおよびツールが正しく機能することを確認するためのページである。このサイトの作者以外には特に有用なものではないが、何かの参考にはなるかも知れない。…

sentiment_satisfied 2023年2月16日(木) MathJax 2

論文翻訳: NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications / 暗号アプリケーションのための乱数・擬似乱数生成器の統計的検定スイート

NIST SP 800-22 として刊行された (疑似) 乱数生成器のランダム性の検定に関する 2001 年の論文。15 の検定で構成されている。この論文に基づいた検定スイートは NIST SP 800-22: Download Documentation and Software からダウンロードできる。…

sentiment_very_satisfied 2023年2月7日(火) 2001年の論文 #NIST #NIST80022

乱数検定: RMT 検定

RMT 検定 (random matrix theory test) (1) はデータ列の乱数性を検定するためのアルゴリズム。与えられたデータ列で相互相関行列を作成し、その固有値分布が RMT に基づく理論曲線と一致すれば検定に合格する。

done 2023年2月7日(火) #RMTTest #RMT検定

論文翻訳: Min-Wise Independent Permutations (Extended abstract)

min-wise 独立置換族 (min-wise independent permutations family) に関する 1998 年の論文。Brahms サンプリングの関連で調べたもの。(厳密) min-wise 独立 (\(\ref{e4}\))、および近似 min-wise 独立 (\(\ref{e6}\))、制限 min-wise 独立 (\(\ref{e7}\)) の定義。…

sentiment_very_satisfied 2023年1月30日(月) #最小値独立置換族

論文翻訳: Time, Clocks, and the Ordering of Events in a Distributed System

論理クロック (Lamport タイムスタンプ) に関する 1978 年の論文。

sentiment_very_satisfied 2023年1月9日(月) 1978年の論文 #LogicalClock #LamportTimestamp #CausalConsistency

論文翻訳: The Byzantine Generals Problem

ビザンチン将軍問題に関する 1982 年の論文。すべてのプロセスが完全グラフで接続している構成において、署名なしのアルゴリズムでビザンチン将軍問題を解くには \(n \ge 3m+1\) が必要。署名ありのアルゴリズムでは \(n \ge m+2\) が必要。完全グラフではない場合、署名なしアルゴリズムは \(3m\)-正則グラフであればビザンチン将軍問題を解くことができる。…

sentiment_very_satisfied 2023年1月2日(月) 1983年の論文 #BFT #ビザンチン将軍問題 #ビザンチン合意

TRANSCRIBE: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation

A 1988 paper on Secure multi-party computation. A transcription of an old PDF for the purpose of reading it in machine translation.

sentiment_very_satisfied 2022年12月28日(水) 1988年の論文 #BFT #SecureMultipartyComputation

論文翻訳: Authenticated Algorithms for Byzantine Agreement

非同期ビザンチンアトミックブロードキャストに関する 1983 年の論文。

sentiment_very_satisfied 2022年12月25日(日) 1983年の論文 #BFT #ビザンチン合意 #ビザンチンアトミックブロードキャスト

TRANSCRIBE: Authenticated Algorithms for Byzantine Agreement

A 1983 paper on asynchronous Byzantine atomic broadcast. A transcription of an old PDF for the purpose of reading it in machine translation.

sentiment_very_satisfied 2022年12月25日(日) 1983年の論文 #BFT #ByzantineAtomicBroadcast

TRANSCRIBE: Consensus in the Presence of Partial Synchrony

A 1988 paper on the partial synchronization model and quorum, known as DLS88. A transcription of an old PDF for the purpose of reading it in machine translation; ja

sentiment_very_satisfied 2022年12月20日(火) 1988年の論文 #DLS88

論文翻訳: Consensus in the Presence of Partial Synchrony

DLS88 として知られる、部分同期モデルおよびクォーラムに関する 1988 年の論文。

sentiment_satisfied 2022年12月20日(火) 1988年の論文

論文翻訳: XFT: Practical Fault Tolerance Beyond Crashes

ビザンチン障害耐性を持つ XPaxos の 2016 の論文。ビザンチン故障、非ビザンチン故障、パーティション分断障害の合計が \(f\) 以下であれば、全体で \(N=2f+1\) プロセスの構成で安全な SMR を行うことができる。

sentiment_very_satisfied 2022年12月4日(日) 2016年の論文 #XFT

論文翻訳: Synchronous Byzantine Agreement with Expected \(O(1)\) Rounds, Expected \(O(n^2)\) Communication, and Optimal Resilience ラウンド期待値 \(O(1)\)、通信期待値 \(O(n^2)\)、そして最適な回復力を備えた同期ビザンチン合意

2019 年の論文。

sentiment_very_satisfied 2022年12月1日(木) 2017年の論文 #BFT #GA

論文翻訳: The Sleepy Model of Consensus

暗号論的ハッシュ関数とゼロ知識証明を使ってプロセスごとに固有の乱数を内密に生成し、その値が既定のしきい値 \(\lambda\) より小さければ当選というスキーマの委員会選出を行う Sleepy Consensus に関する 2017 年の論文。Algorand が VRF をハッシュ関数と ZKP に置き換えたようなアイディア。…

sentiment_very_satisfied 2022年11月25日(金) 2022年の論文 #Sleepy

論文翻訳: Constant Latency in Sleepy Consensus

検証可能な乱数を用いて委員会選出を行う Sleepy コンセンサスで動的な参加を可能にする 2022 年の論文。

sentiment_very_satisfied 2022年11月25日(金) 2022年の論文 #BFT #Sleepy

論文翻訳: DiemBFT v4: State Machine Replication in the Diem Blockchain

Diem Blockchain のコンセンサスアルゴリズム DiemBFT (旧名 LibraBFT) に関する 2021 年の論文。この v4 で 2 ラウンドで確定するように修正された。

sentiment_very_satisfied 2022年11月24日(木) 2021年の論文 #DiemBFT #LibraBFT #HotStuffBFT

Winny

Winny (ウィニー) は Freenet をモデルに実装された P2P ファイル共有のためのアプリケーションまたはネットワークである。匿名性の高さと効率的で高速なキャッシュ機構で日本ユーザのコミュニティで広まり、日本の P2P ファイル共有ブーム、およびそれにまつわる違法コピー行為とハッキング被害の代名詞ともなった。…

sentiment_satisfied 2022年10月8日(土) #Winny #P2P

論文翻訳: Packrat Parsing: Simple, Powerful, Lazy, Linear Time

複数の選択肢をもつ構文解析時に、解析済みのパターンの結果を記録しておき別の選択肢を評価するときに使用する Packrat 構文解析に関する 2002 年の論文。

sentiment_very_satisfied 2022年9月19日(月) 2002年の論文 #packrat #構文解析

プレゼンテーション技法

Microsoft de:code 2014 でマイクロソフトのエバンジェリスト西脇さんの「プレゼンの極意」を聞いてからプレゼンの構成や技法について注意深く見るようになった。自分がプレゼンテーションをどう見てるか、どう作っているかについてこのページに書き残しておく。

sentiment_very_satisfied 2022年9月8日(木) #presentation

論文翻訳: Incremental Packrat Parsing

Packrat 構文解析のメモ表を利用して、構文解析済みの入力テキストが変更されたときに (全体の再パースなしに) テキスト変更分をインクリメンタルに構文解析結果に反映する Packrat 構文解析の改良に関する 2017 年の論文。

sentiment_very_satisfied 2022年9月7日(水) 2017年の論文 #packrat #構文解析

構文解析

一般に構文解析 (syntactic analysis) とは文章を解析してその構文構造を導き出すという意味を持つ。

sentiment_satisfied 2022年9月2日(金)

形式言語

あるオートマトンによって受理することのできる言語である。

sentiment_very_satisfied 2022年8月26日(金)

オートマトン

オートマトン (automaton; ムーア型順序機械) は計算理論における数学的なモデルの総称。ある既定の手続きに従って行う自動計算の機構、つまりプログラミングやインタープリタ、文字列解析などを表すモデルとしてしばしば使われている。

sentiment_very_satisfied 2022年8月19日(金) #automaton

組み合わせ合計

組み合わせ合計 (combination sum) 問題は、正の整数の集合 \(\vector{x} = \{x_0,x_1,\ldots\}\) の中から合計が値 \(y\) になるようなすべての一意の組み合わせを選択する問題。ナップサック問題 (Knapsack problem) の一種でしばしばプログラミング課題として用いられる。…

edit_note 2022年7月22日(金) #CombinationSum

Rust: プロファイリング

ソフトウェア開発におけるプロファイリング (profiling) とは、プログラムのボトルネックやメモリリークを発見することを目的とした CPU 時間やメモリ使用量の計測である。ソフトウェアの最適なパフォーマンスを引き出すためにはソースコードを最適に調整する作業が重要であるが、一般にプロファイリングはその優先順位や費用対効果を推定するための事前調査を目的として実施される。…

sentiment_very_satisfied 2022年7月13日(水) Linux Kernel 5.15 #Rust #Linux #perf

eBPF

eBPF (extended Berkeley packet filter) はカーネルの再構築なしにカーネル空間でプログラムを実行することのできる仮想マシン技術。eBPF のバイトコードは実行時に JIT コンパイラによって検証とネイティブコード変換が行われ、カーネル内の保護された空間 (サンドボックス) で安全かつ効率的に実行することができる。…

sentiment_very_satisfied 2022年5月28日(土) libbpf 0.8 #BPF #eBPF

コード変換

edit_note 2022年4月25日(月) #Base64

Intel SGX

Intel SGX (Intel Software Guard Extensions) はハードウェアによって暗号化されたメモリ領域を提供する TEE (trusted execution environment) 技術の一つである。クラウド環境やユーザの手元の PC といった信頼性の保証できない環境において、機密性の高いアプリケーションコードやデータを暗号化された空間に隔離し安全に動作できるようになる。…

sentiment_very_satisfied 2022年4月9日(土) Ubuntu 20.04 #TEE #SGX

非同期処理

sentiment_satisfied 2022年3月12日(土) Rust 1.48 #Rust #async

並行プログラミング

並行プログラミングとは、そのような環境で効率的な処理を実装するために複数のタスクを同時に実行するプログラミング技法である。並行性によりプログラムは一度に多くのタスクを処理することができるが、並行プログラムを書くことはことさら簡単なことではない。スレッドやロックなどの構造を処理し、競合状態やデッドロックなどを回避することは非常に面倒な作業であり、並行プログラミングの作成が困難である理由でもある。…

sentiment_satisfied 2022年3月9日(水)

Rust: tokio による非同期プログラミング

tokio (トーキョー) は Rust 言語で非同期アプリケーションを作成するためのイベント駆動型フレームワークです。煩雑さを排除し統一された方法で使用できる非同期ランタイムおよびノンブロッキング I/O とネットワークのプラットフォームを提供しています。開発者は tokio を使用することで高度にスケーラブルな設計のネットワークアプリケーションを迅速に開発することができます。…

sentiment_satisfied 2022年3月5日(土) tokio 1.17 #Rust #tokio

Raspberry Pi: RTC の接続

Raspberry Pi は RTC1 (real-time clock) を搭載しておらず、シャットダウン時に時刻を記録して次の起動時にはその時刻から開始するように動作する。ネットワークに接続していれば起動後すぐに NTP サーバと時刻同期を行って概ね正しい時刻で動作するが、オフライン環境や NTPd をオフにしている状態ではシステム時刻が実際の時刻よりどんどん遅れることになる。…

sentiment_very_satisfied 2022年2月7日(月) Raspbian 11 #RaspberryPi

Raspberry Pi: スピーカーの接続

Raspberry Pi をヘッドレス (画面やキーボードを接続しない) 機器として使用するとき、システムで何かエラーが起きていることを通知する手段が必要である。ネットワークと接続しているのであればメールや LINE Bot 等を使用できるが、そうでない場合は別に物理的な手段を用意しなければならない。…

done 2022年2月5日(土) Raspbian 11 #RaspberryPi

Raspberry Pi: ディスプレイの接続

必須ではないが Raspberry Pi でやっておくと良い設定や便利なガジェットなどのメモ。また HDMI キャプチャデバイスを使用することでシステムコンソールを Android 端末や PC に表示することもできる。

sentiment_very_satisfied 2022年1月29日(土) Raspbian 11 #RaspberryPi

Raspberry Pi: カメラの接続

Raspberry Pi は通常の Linux OS 環境と同様に USB 接続のカメラが使用できるほか、専用のカメラモジュールを使用して動画や静止画を撮影することができる。また Pico 以外の全てのモデルに H.264 ハードウェアエンコーダーを搭載していることから、リアルタイムでの映像の加工やフォーマット変換、ストリーミングといった用途も可能である。…

done 2022年1月15日(土) Raspbian 11 #RaspberryPi

Raspberry Pi: 静止画の撮影

カメラの接続が完了したら Raspberry Pi で静止画を撮影してみよう。Raspberry Pi は通常の Linux OS 環境と同様に USB 接続のカメラが使用できるほか、専用のカメラモジュールを使用して動画や静止画を撮影することができる。

done 2022年1月15日(土) Raspbian 11 #RaspberryPi

Raspberry Pi: 動画の撮影

カメラの接続が完了したら Raspberry Pi で動画を撮影してみよう。Raspberry Pi は Pico 以外の全てのモデルに H.264 ハードウェアエンコーダーを搭載していることから、リアルタイムでの映像の加工やフォーマット変換、ストリーミングといった用途も可能である。…

sentiment_very_satisfied 2022年1月15日(土) Raspbian 11 #RaspberryPi

論文翻訳: WHITE-BOX CRYPTOGRAPHY: HIDING KEYS IN SOFTWARE

ホワイトボックス暗号に関する概要と 2012 年時点の現状をサーベイした論文。

sentiment_very_satisfied 2021年12月28日(火) 2012年の論文 #WBC #ホワイトボックス暗号

Carillon

edit_note 2021年12月28日(火) #Carillon

ホワイトボックス暗号

ホワイトボックス暗号 (white-box cryptography; WBC) は攻撃者が暗号プリミティブの実装やその実行プラットフォームに対して特権的アクセスを持つ状況においても暗号鍵そのものの漏洩 (つまり鍵復元) を防止することを目的とした難読化 (obfuscation) の手法である。…

sentiment_very_satisfied 2021年12月22日(水) #WBC #DRM

論文翻訳: On White-Box Cryptography

white-box 暗号について Q&A 形式で解説する 2008 年の論文。発表当時の状況に依存する記述も多いので現状どうなっているかは追加で知る必要がある。

sentiment_very_satisfied 2021年12月20日(月) 2008年の論文

制御理論

自然に変化する系 (システム) に対して、系が目的の状態となるように系の変化率に作用する入力を外部から人為的に与えることを制御 (control) と呼ぶ。

sentiment_satisfied 2021年12月13日(月) #制御理論

Ansible セットアップ

edit_note 2021年12月11日(土) Windows 10 #Ansible

Raspberry Pi: USB ストレージの接続

Raspberry Pi は SD カードから OS 起動する。しかし安価で小さな SD カードは耐久性も低く頻繁な書き込み操作によって寿命が短くなる。データベースのような書き込み操作の多いアプリケーションを動作させるのであれば USB 経由で SSD/HDD ストレージを使用したほうが安心であるし、また書き込み寿命が大きく違わないにしても USB フラッシュメモリをそのような用途にすることでファイルシステム破損時のシステムの再構築の手間を減らすことができる。…

sentiment_satisfied 2021年12月10日(金) Raspbian 11 #RaspberryPi

Raspberry Pi: GPS レシーバーの接続

Raspberry Pi を含む Linux ベースのシステムに USB 接続の GPS レシーバーを接続することで正確な位置情報を得ることができる。Linux ではシリアルまたは USB 接続された GPS とのインターフェースとなる gpsd というデーモンを利用する。gpsd で確認済みのハードウェアは Compatible Hardware 参照。…

sentiment_satisfied 2021年12月10日(金) Raspbian 11 #RaspberryPi

Raspberry Pi: ドライブレコーダー

edit_note 2021年12月9日(木) #RaspberryPi #DriveRecorder

Raspberry Pi: インストールと基本的な設定

この記事では Raspberry Pi 購入直後の状態から ssh で接続して使用するための必要なセットアップ作業を記述している。

sentiment_satisfied 2021年12月4日(土) Raspbian 11 #RaspberryPi

Rust: オブジェクト指向からの移行

done 2021年10月29日(金) Rust 1.56 #Rust

翻訳: ISO/IEC 14977:1996 Information technology — Syntactic metalanguage — Extended BNF

Extended BNF (EBNF) の ISO/IEC 14977:1996 規格。

sentiment_very_satisfied 2021年10月9日(土) ISO/IEC 14977:1996 #EBNF

EBNF

EBNF (extended Backus-Naur form) は BNF を拡張した構文メタ言語 (syntactic meta-language) の一種。プログラミング言語や HTML のようなデータフォーマットの構文定義を記述することができる。

done 2021年10月9日(土) #EBNF

論文翻訳: Paxos Made Simple

Paxos に関する 2001 年の論文。独特のユーモラスにより世間にうまく伝わらなかった先の論文 "The part-time parliament" (5) をサマリーしたような内容となっている。

sentiment_very_satisfied 2021年10月8日(金) 2001年の論文 #Paxos

論文翻訳: The Part-Time Parliament

Paxos に関する 1998 年の論文。戯曲めいた説明がしばしば理解を阻害すると言われるので Paxos Made Simple (2001) をあわせて読むと良い。Paxos 島やその議会は Lamport によるフィクションで実在しない。文中のギリシャ文字で表記されている登場人物は実在する計算機科学者を表しているようである。…

sentiment_very_satisfied 2021年10月4日(月) 1998年の論文 #Paxos

論文翻訳: Zab: High-performance broadcast for primary-backup systems

ZooKeeper のプライマリ-バックアップ間でトランザクションのアトミックブロードキャストに使われている ZAB に関する 2011 年の論文。

sentiment_very_satisfied 2021年9月26日(日) 2011年の論文 #ZAB #ZooKeeper

Federated Byzantine Agreement

Federated Byzantine Agreement (FBA; 連合ビザンチン合意) は合意に参加する参加者それぞれの信頼に基づくクォーラム (quorum) と呼ばれる部分ネットワークを形成する P2P 向けのコンセンサス機構である。従来のビザンチン合意 (BA; Byzantine Agreement) 機構と比べてノードの参加が自由である (permissionless) という点が大きな特徴となっている。…

sentiment_very_satisfied 2021年9月19日(日) #FBA

論文翻訳: Conflict-free Replicated Data Types

因果一貫性を使用する Version Vector のような並行する更新を追跡できるシステムで自動的に競合を解決できるデータ型についての 2011 年の論文。

sentiment_very_satisfied 2021年9月3日(金) 2011年の論文 #CRDT

Blockchain: コンセンサス

一般的な分散システムの文脈でのコンセンサスは、一貫性 (consistency) を達成するための役割選出 (リーダー選挙)、合意、同期、競合の解決や調整といったメカニズムを包括的に指した言葉である。しかし、ブロックチェーンに関する論文やブログではコンセンサスが内包するこれらのメカニズムを分解しないまま論議がなされており、中には選出メカニズムと合意メカニズムが同列で比較されているような間違いも起きている。…

sentiment_very_satisfied 2021年8月30日(月) #Blockchain #Consensus

Version Vector

Version Vector (VV) は並行して発生するイベントの因果関係 (causality, happened-before relation) を追跡するための機構。因果一貫性 (causal consistency) と呼ばれる一貫性モデルにおいて、競合する更新の因果関係を追跡しながら表現するために使用されている。…

sentiment_very_satisfied 2021年8月27日(金) #VV #VersionVector #CausalConsistency

論文翻訳: Scalable and Accurate Causality Tracking for Eventually Consistent Stores

結果整合性を持つ Key-Value ストア間で更新の競合を検出し追跡するための機構である Version Vector を、空間的および時間的に効率化した Dotted Version Vectors (DVV) および Dotted Version Vector Sets (DVVS) に関する 2014 年の論文。…

sentiment_very_satisfied 2021年8月21日(土) 2014年の論文 #DVV

論文翻訳: Detection of Mutual Inconsistency in Distributed Systems

バージョンベクトル (version vector) と起点 (origin point) を使用して、特定ファイルの複数のコピーに対して独立して行った操作による相互不整合 (mutual inconsistency) を検出する方法についての 1983 年の論文。

sentiment_very_satisfied 2021年8月18日(水) 1983年の論文 #VersionVector #VV

ビジネス: ブックマークやメモ

edit_note 2021年8月6日(金)

論文翻訳: Concise Server-Wide Causality Management for Eventually Consistent Data Stores

ノード論理クロックとキー論理クロックを使用して分散システムにおけるデータ更新の因果関係を追跡するための 2015 年の論文。

sentiment_very_satisfied 2021年7月17日(土) 2015年の論文 #BVV

Rust: ベンチマークの計測

sentiment_satisfied 2021年7月15日(木) Rust 1.53 #Rust

暗号プリミティブのパフォーマンス比較

edit_note 2021年7月13日(火) #RSA #ECDSA #Schnorr #BLS

ゼロ知識証明

ゼロ知識証明 (ZKP; zero-knowledge proof) は、ある命題 (statement) が真であるという証明者 (prover) の主張を、それ以上の情報を明かすことなく検証者 (verifier) が確実に知る (受理する/拒否する) ことのできるスキームである。…

sentiment_satisfied 2021年7月12日(月) #zkp #SNARG #SNARK #zk-SNARK #ゼロ知識証明

Banded Hash Tree

現実的なストレージに対して追記効率が良く、累積的な構造変化の完全な履歴を保持するリスト構造 Banded Hash Tree (BHT) について説明します。この構造はデータの追加が可能なハッシュツリー (Merkle ツリー) であり、一般的なハッシュツリーと同様に小さなデータ片を用いてデータの破損や改ざんを検証することができます。…

sentiment_very_satisfied 2021年7月11日(日) #BHT #HashTree #MerkleTree

Rust: スレッド間のデータ共有パターン

edit_note 2021年6月23日(水) Rust 1.53 #Rust

論文翻訳: The latest gossip on BFT consensus

Tendermint のコンセンサスに関する 2018 年の論文。

sentiment_very_satisfied 2021年4月16日(金) 2018年の論文 #Blockchain #Tendermint #BFT

論文翻訳: BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory

NVM (不揮発性メモリ) 向けデータ構造 BzTree に関する 2018 年の論文。Microsoft US #10599485 特許。

sentiment_very_satisfied 2021年4月10日(土) 2018年の論文 #BzTree #B+Tree #NVM #PMwCAS #CAS

PlusCal: 証明アプローチ

このページでは PlusCal を使って記述したシステムが正しいことをどのように証明するかについて説明する。サンプルを実行するための環境セットアップは環境設定と検証の実行を参照。

sentiment_very_satisfied 2021年4月7日(水) TLC2 #PlusCal #TLA+

GraalVM: 入門

edit_note 2021年4月3日(土) #GraalVM

GraalVM

GraalVM は Java や Scala などの JVM 言語、C/C++ や Rust などの LLVM 言語、および JavaScript や Python のような動的型付言語などに向けた高性能ランタイムである。GraalVM を使用することでそれらのプログラミング言語間の相互運用を効率化し、また AOT (ahead of time) コンパイラによって Java アプリケーションを事前にコンパイルして起動時間を短縮しメモリのオーバーヘッドを削減したネイティブ実行ファイルを作成できる。…

edit_note 2021年4月3日(土) #GraalVM

翻訳: PlusCal/TLA+: An Annotated Cheat Sheet

PlusCal と TLA+ のリファレンスとして有用なチートシート。

sentiment_very_satisfied 2021年3月26日(金) 2019年の論文 #PlusCal #TLA+

翻訳: The PlusCal Algorithm Language

sentiment_very_satisfied 2021年3月18日(木) 2009年の論文 #PlusCal #TLA+

TLA+ と PlusCal

TLA+ (temporal logic of actions plus; 1999年) と PlusCal (2009年) は共に並行処理と分散システム向けに設計された仕様記述言語 (高レベルモデリング言語)。システム設計やアルゴリズムなどの重要で危険度の高い部分のエラーを定性的に検出することを目的としている。…

sentiment_very_satisfied 2021年3月13日(土) TLC2 #TLA+ #TLC #PlusCal

PlusCal: 並行システムと非同期処理

このページでは PlusCal を使ってマルチプロセスやマルチスレッド、それらに伴う非同期処理といった並行処理を記述する方法について説明する。サンプルを実行するための環境セットアップは環境設定と検証の実行を参照。

sentiment_satisfied 2021年3月8日(月) TLC2 #PlusCal #TLA+

git: 大規模なマージ

想定: あなたのチームはあるリポジトリ Alice 1.x をフォークしていくつかの機能を修正した Bob 1.x を開発している。いままで Alice 側の修正は alice/master ブランチ上の v1.x.y リリースタグを bob/develop にマージすることで取り込んでいた。…

done 2021年3月7日(日) #git

翻訳: A PlusCal User's Manual

sentiment_very_satisfied 2021年3月7日(日) 2020年の論文 #PlusCal #TLA+

PlusCal: 制御構造

このページではいくつかの例を使って PlusCal の基本的な制御構造を説明する。実行環境のセットアップは PlusCal を参照。

sentiment_very_satisfied 2021年3月7日(日) TLC2 #PlusCal #TLA+

PlusCal: データ構造と演算子

done 2021年3月7日(日) TLC2 #PlusCal #TLA+

英語: 意思伝達のための必須表現

edit_note 2021年2月5日(金)

英語

英語のフレーズなどを記述しておくノート。

edit_note 2021年2月5日(金)

TLA+入門2: 独立した 2 変数のシステム

このページでは TLA+ の例として時相論理演算子を扱う。

sentiment_satisfied 2021年2月4日(木) TLC2 #TLA+ #TLC

TLA+入門1: TickTack

このページでは最初の TLA+ の例として、システム状態に 0 と 1 を交互にとる TickTack システムについて考える。

sentiment_satisfied 2021年2月4日(木) TLC2 #TLA+ #TLC

PlusCal入門1: hello, world

このページでは最初の PlusCal の例として hello, world と表示するプログラムをレビューし、その基本的な記述構造について考える。PlusCal での仕様記述や TLC 実行のための環境設定は環境設定と検証の実行を参照。

done 2021年2月4日(木) TLC2 #TLA+ #TLC

翻訳: Summary of TLA+

sentiment_very_satisfied 2021年2月3日(水) #TLA+ #cheetsheet

記号論理

記号論理 (symbolic logic) は論理的な推論を数学的記号法を用いて研究する分野。

done 2021年1月29日(金)

システム稼働率

システム稼働率 (system availability factor) はシステムに期待できる可用性の指標である。

sentiment_very_satisfied 2021年1月25日(月) #稼働率 #AF

wasmer

wasmer は OS やチップセットから隔離された環境で WebAssembly バイナリを実行できる軽量な仮想マシン。

done 2021年1月8日(金) wasmer 1.0 #wasmer #WASM #WebAssembly

Rust: Non-blocking I/O programming with mio::Poll

Linux カーネルのシステムコール epoll や FreeBSD (Mac OS) の kqueue、またはより古典的な POSIX 準拠の select や poll システムコールは大量のクライアント接続を効率的に処理するノンブロッキング I/O プログラミングに必要な機能である。…

done 2020年12月31日(木) mio 0.7 #Rust #async #poll

論文翻訳: Bulletproofs: Short Proofs for Confidential Transactions and More

高速でデータサイズの小さいレンジプルーフ (範囲証明) のゼロ知識証明である Bulletproofs に関する 2018 年の論文。

sentiment_very_satisfied 2020年12月23日(水) 2018年の論文 #Bulletproofs #zkp #ゼロ知識証明

Rust: async を使った非同期処理

edit_note 2020年12月16日(水) Rust 1.48 #Rust #async

Bumblebees

Bumblebees は互いに非同期メッセージを交換する 2 つのピアアプリケーション向けプロトコル。シンプルな概念と 4 種類のメッセージを使用して、代表的な以下のネットワーク機能を実装することを目的としている。

edit_note 2020年11月30日(月) #Bumblebees

Bloom Filter

Bloom Filter (ブルームフィルタ) は大規模データセットに対する近似メンバーシップクエリー (approximately membership query)、つまり特定の要素が含まれているかを効率的にテストするための確率的データ構造。false positive (偽陽性; 含まれていないのに true となること) を許容するが false negative (偽陰性; 含まれているのに false となること) は発生しないという特徴を持つ。…

sentiment_very_satisfied 2020年11月27日(金) #AMQ #BloomFilter #確率的データ構造

Home-built Computers

done 2020年11月24日(火) #Ryzen

論文翻訳: Fast Multiparty Threshold ECDSA with Fast Trustless Setup

sentiment_very_satisfied 2020年10月26日(月) 2018年の論文

ポスト量子暗号

ポスト量子暗号 (PQC; post-quantum cryptography) は量子計算耐性を持つ暗号アルゴリズムのこと。現在広く使用されている暗号アルゴリズムの多くは素因数分解問題 (RSA など)、または離散対数問題 (楕円曲線や BLS など) の困難性に基づいている。…

done 2020年10月24日(土) #PQC

ハッシュベース暗号

ハッシュベース暗号 (hash-based cryptography) は素因数分解や離散対数のような数学的な問題の困難性を利用するのではなく、暗号論的ハッシュ関数によって確立されるセキュリティに基づいている。量子計算機を使用して暗号論的ハッシュ関数の衝突と見つけることが困難であると同様に、ハッシュベースの暗号も量子計算耐性を持つと考えられている。…

sentiment_satisfied 2020年10月21日(水) #WOTS #MSS

Mix Network

Mix Network は受信者のみが解読できる暗号でメッセージを秘匿し、さらにランダムに選んだ多段のノードで中継させることでメッセージの発信者や伝達経路と通信内容の両方を秘匿することを目的としたネットワーク。メッセージを中継するノードを一般にルーター (router) と呼ぶ。…

sentiment_satisfied 2020年10月19日(月) #MixNetwork #OnionRouting #Tor

論文翻訳: Kademlia: A Peer-to-peer Information System Based on the XOR Metric

二分探索木に基づき距離関数に XOR を使用する分散ハッシュテーブルアルゴリズム Kademlia に関する 2002 年の論文。ネットワーク全体では二分木の構造だが、個々のノードのルーティングテーブルはその部分木として見ることのできるリスト構造となる。ルーティングテーブルの参照先は \(k\)-bucket にまとめられ、駆動時間の長いノードは後の生存率も長いという統計的事実からどのノードを参照するかを決定する。…

sentiment_very_satisfied 2020年8月29日(土) 2002年の論文 #P2P #DHT #Kademlia

Kademlia

Kademlia は二分木構造に基づくシンプルで実用的な分散ハッシュテーブル (DHT; distributed hashtable) アルゴリズム。ネットワークの中から目的のノードを効率よく検索することのできる分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) の一つである。…

sentiment_very_satisfied 2020年8月29日(土) #P2P #DHT #Kademlia

Chord

Chord はコンシステントハッシュ法 (consistent hashing) に基づく分散ハッシュテーブルである。対数メッシュのリンクを内包する論理リングで表される。

sentiment_very_satisfied 2020年8月26日(水) #P2P #DHT #Chord

論文翻訳: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

Consistent Hashing を使用した分散ハッシュテーブルアルゴリズム Chord に関する 2001 年の論文。2003 年に似た内容で新しい論文 (2) が出ているのでそちらを参照したほうが良いかも知れない。

sentiment_very_satisfied 2020年8月17日(月) 2001年の論文 #P2P #DHT #Chord

Tapestry

Tapestry(2,3) は PRR の論文(1)に基づいた Prefix ルーティングを行う分散ハッシュテーブルルゴリズム。RPP にノードの参加と離脱のアルゴリズムが追加されている。各ノードは SHA-1 を使用した ID (アドレス) が割り当てられ、アプリケーションにもエンドポイント GUID が割り当てられる。…

sentiment_satisfied 2020年8月11日(火) #DHT #Tapestry

Peer to Peer

P2P (peer to peer) は対等な動作をする (明確な主従関係を持たない) ノードによるネットワークまたはシステムのモデル。従来のクライアント/サーバシステム (C/S システム) におけるサーバがクライアントに対して一方的にサービスを提供する役割だったのに対して、P2P ではそれぞれのピアが状況に応じてサーバとクライアント両方の役割を持つ。…

sentiment_very_satisfied 2020年8月1日(土) #P2P

P2P ファイル共有

P2P ファイル共有は P2P ネットワーク技術を使用したファイルの配布と共有を行うサービス、アプリケーションまたはネットワーク。ダウンロードのネットワーク負荷をユーザ側で分散することから低コストでサービスを運営することができるが、一方で、データの管理を行うことができず、著作権管理や情報漏えいと言った法的な問題に巻き込まれることも多い。…

done 2020年7月27日(月) #P2P

有向非巡回グラフ

DAG (directed acyclic graph; 有向非巡回グラフ) は有向グラフの中でも閉路をもたない (つまり一度通過した頂点にふたたび戻ることはない) 構造を持つグラフ。ソフトウェアの分野ではジョブ管理システムやビルドシステム、ネットワーク問題で扱う。

edit_note 2020年7月20日(月) #DAG

分散ハッシュテーブル

分散データベースにおいて目的とするオブジェクトを効率的に検索するために特定のスキームに基づいてネットワークに配置する方法を分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) と呼ぶ。一般的にはオブジェクト識別子をノードのアドレス空間にマッピングすることで行われる。…

sentiment_very_satisfied 2020年7月20日(月) #P2P #DHT #DOLR #Tapestry

Merkle Tree

マークルツリー (Merkle tree; ハッシュ木) はあるデータセットのハッシュ値を再帰的にハッシュ化することで得られるツリー構造。このツリーのルートにあたるルートハッシュはすべてのデータのハッシュ特性を含んだ固定サイズの値であるため、後で一部のデータを検証するのに都合が良い。…

done 2020年7月16日(木) #merkletree #hash

非復元ランダムサンプリングにおける公平性

Inverse (逆数) の重み分布に対して ×1,000 を実行してみれば明らかなように、それぞれの要素の選択頻度の分布 (Actual Win Rate) は重みの分布とはかけ離れた挙動となる。唯一一致する分布は Flat だけだが、これはすべての要素の重みが等価であることから一様ランダムサンプリングと同じ意味である。…

sentiment_very_satisfied 2020年7月11日(土) #RandomSampling #WRS #fairness

読書メモ: Science Research Writing for Non-native Speakers of English

英語が母国語ではない研究者が英語で研究文書を作成するためのガイド本。

done 2020年7月10日(金)

InterPlanetary File System

IPFS (InterPlanetary File System) は Protocol Labs 社を中心に開発されている P2P 技術を使用したファイル配信のための分散ストレージおよびそのプロトコルの名称である。Gnutella や BitTorrent といった P2P ファイル共有と同類の技術だが、Web (HTTP) に代わるプロトコルや分散ファイルシステムとなることを目的としている。…

sentiment_satisfied 2020年7月10日(金) IPFS 0.6.0 #P2P #ipfs

χ² 検定

χ² 検定 (chi-square test) は χ² 分布を確率分布とする確率変数 \(\chi^2\) を求めることで行う検定。その利便性によって広く普及している。期待した分布と観測した分布が適合しているかを調べる適合度検定と、2 つの事象が関連しているかを調べる独立性検定がよく利用されている。…

sentiment_very_satisfied 2020年7月9日(木) #chisquare

F 検定

F 検定 (F test) は 2 つの標本の分散 (標準偏差) が異なっているかを測定する統計的仮説検定。代表的な利用例は t 検定の予備検定である。

sentiment_very_satisfied 2020年7月6日(月) #ftest

t 検定

\(t\) 検定 (t-test; スチューデントの t) は正規分布に従う母集団から無作為に抽出した 2 つの標本が互いに異なるかを計測する仮説検定である。母集団の標準偏差が不明な場合は Z 検定の代わりに t 検定を使用する

sentiment_very_satisfied 2020年6月30日(火) #ttest

東京都人口統計のデータ

以下の 2 つの CSV ファイルは東京都の人口(推計)-過去の推計-の「次の国勢調査人口が公表されるまでの人口推計」から入手できる (人が読む形式の) Excel 形式の統計表1から抽出した数値をプログラムから利用できる形式で出力したものである (いつ時点のデータかは version カラムを参照)。…

done 2020年6月12日(金)

統計的仮説検定

観測値の背景にある母集団の構造を仮定し、観測値の統計からその仮定が受け入れられるか、さもなくば拒否されるかを判断する統計的手法を統計的仮説検定 (statistical hypothesis testing) と呼ぶ。このとき仮定した構造のことを仮説 (hypothesis) と呼ぶ。…

sentiment_very_satisfied 2020年6月6日(土)

論文翻訳: Fast Generation of Discrete Random Variables

Walker のエイリアス法を改良して正方ヒストグラムを使う方法で高速に重み付きランダムサンプリングを行うアルゴリズムに関する 2004 年の論文。

sentiment_very_satisfied 2020年5月30日(土) 2004年の論文 #WeightedRandomSampling #SquareHistogram

ランダムサンプリング

ランダムサンプリング (RS; random sampling) は統計学やデータ分析において大規模な集合 (母集団) から無作為にデータを抽出する手法である。母集団の各要素が等しい確率で選ばれるサンプリングでは、得られたサンプルは母集団全体の特性を統計的に正しく反映していることが期待される。…

sentiment_very_satisfied 2020年5月28日(木) #RandomSampling #WRS #ReservoirSampling

論文翻訳: Weighted Random Sampling (2005; Efraimidis, Spirakis)

重み付きランダムサンプリング (乱択) のアルゴリズムに関する 2005 年の論文。重み付き非復元ランダムサンプリング (weighted random sampling without replacement) に基づいて、開始時点でサイズが未知の母集団から 1 パスでサイズ \(m\) の部分集合を生成することができる。…

sentiment_very_satisfied 2020年5月21日(木) 2005年の論文 #WeightedRandomSampling #ReservoirSampling

XML: Extensible Markup Language

XML (extensible markup language) は構造化されたデータを表現するための W3C が規定するマークアップ言語。ドキュメント指向のデータ向けに高機能で非常に高い柔軟性と拡張性を持っており、また人間が読みやすいように設計されているため、データ交換から設定ファイルまで様々な分野で広く使用されている。…

done 2020年4月24日(金) XML 1.1 #xml

XML-Schema

XML Schema は XML 文書の構造と内容を定義するためのスキーマ言語である。スキーマには XML によるインターフェースを定義し、XML 文書の整合性を検証することでデータの信頼性と相互運用性を高める役割がある。

done 2020年4月24日(金) XML Schema 1.1 #XMLSchema

XPath: XML Path Language

XPath (XML path language) は、主に XSLT で使用されるクエリー言語である。XML 文書上で目的のノードを特定するアドレッシングや、ノード集合から特定のノードを抽出するフィルタリングを行うことを目的としている (目的としてはリレーショナルデータベースに対する SQL に似ている)。…

edit_note 2020年4月24日(金) XPath 1.1 #xml #xpath

論文翻訳: Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin

優先度を重みづけされたプロセッサにラウンドロビンでジョブを割り当てるアルゴリズムに関する 2009 年の論文。

sentiment_very_satisfied 2020年4月24日(金) 2009年の論文

雑記: 2019 新型コロナウイルス

done 2020年4月2日(木) #2019nCoV #COVID19

格子暗号

格子暗号 (lattice-based cryptography) は多次元の格子構造を用いた公開鍵暗号スキーム。証明可能な強力なセキュリティの保証や量子計算耐性、完全準同型暗号へ応用可能といった特性を持っている。

sentiment_satisfied 2020年3月31日(火) #NTRU

読書メモ: スパンプログラム

Karchmer and Wegderson は 1993 年にブール関数を計算する興味深い線形代数モデルスパンプログラム (span program) を発表した。ある関数 \(f(x_1,\ldots,x_n)\) に対するスパンプログラムは、変数 \(x_i\) とその否定 \(\bar{x}_i\) でラベル付けされた行を持つ、ある体 (field) 上の行列として表される (一つの変数が複数の行をラベル付けしてもよい)。…

sentiment_very_satisfied 2020年3月7日(土) #SpanProgram #BooleanFunction #BooleanNetwork

準同型暗号

準同型暗号 (homomorphic encryption; HE) は暗号化したデータを復号化せず演算することで、復号化により計算結果を得ることができる暗号スキーム。データの内容を秘匿したままクラウドのようなサードパーティの計算リソースを使用することができる。準同型暗号の概念は最初に (1) で紹介された。…

sentiment_very_satisfied 2020年2月28日(金) #準同型暗号 #HE #FHE

論文翻訳: On Span Programs

Span Program に関する 1993 年の論文。

sentiment_very_satisfied 2020年2月24日(月) 1993年の論文 #SP

論文翻訳: DFINITY Technology Overview Series Consensus System

Dfinity のテクニカルオーバービューを記述した 2018 年の論文。公証 (notalization) がブロックの承認を表している? 少し用語の言い替えがある。

sentiment_very_satisfied 2020年2月15日(土) 2018年の論文 #Blockchain #DFINITY

疑似乱数生成

乱数 (random number) はランダムに選択された数のこと。特定の出現パターンを持たず、選択される値が予測できないという性質を持っており、ゲームや科学技術シミュレーション、暗号セキュリティの分野で重要な役割を持っている。

sentiment_very_satisfied 2020年2月1日(土) #PRNG #MersenneTwister #xorshift

論文翻訳: Xorshift RNGs

ビット演算のみを使用した非常に高速でコンパクトな Xorshift 擬似乱数生成アルゴリズムに関する 2003 年の論文。著者はキャリー付き乗算の論文にも携わっている。Abstract にあるようにこの論文自体はアイディアの説明であり、良い乱数・悪い乱数で何点かの間違いが指摘されている。…

sentiment_very_satisfied 2020年2月1日(土) 2003年の論文 #Xorshift #PRNG

Rust: nom によるパーサー実装

nom は Rust で実装された字句解析ライブラリ (Lexer, Lexical Analyzer, Tokenizer) およびパーサコンビネーターです。プログラムのソースコードや DSL (domain specific language) のようなテキストデータの字句解析を実装できるのに加えて、バイナリデータの解析も前提に設計されています (実際、nom の作者は nom を使って GIF 画像ファイルのデコーダーを実装しています)。…

sentiment_very_satisfied 2020年1月11日(土) nom 5.1.0 #Rust #nom

論文翻訳: Graph learning: How humans infer and represent networks

話し言葉や音楽といった人間が認知できる刺激ははグラフ構造で表すことができる。人間がどのように時系列のグラフ構造を認識しているかに関する最近の研究をまとめた 2019 年の論文。

sentiment_very_satisfied 2019年12月25日(水) 2019年の論文 #認知科学 #GraphLearning #CognitiveEngineering

公開鍵暗号アルゴリズム

公開鍵は「A から B を計算するのは容易だが B から A を計算するのは困難」といった計算の非対称性を利用した暗号アルゴリズム。公開鍵アルゴリズムを応用した技術として鍵共有、暗号、電子署名が広く使われている。また近年では公開鍵の特性を利用してゼロ知識証明といったようなアルゴリズムの研究も進んでいる。…

edit_note 2019年12月14日(土) #DLP #DH #ElGamal #DSA #ECDH #ECC #ECDSA #RSA

RSA 暗号

RSA 公開鍵暗号 (RSA public-key encryption) は大きな数の素因数分解の困難性を利用した公開鍵暗号。最初の実用的な公開鍵暗号で 2000 年に特許が切れている。より鍵の小さい楕円曲線暗号に置き換えられつつあるが現在においても広く利用されている。

sentiment_satisfied 2019年12月14日(土) #RSA

楕円曲線暗号

楕円曲線は離散対数問題に対して有限体よりも効率的で高いセキュリティを持つ有限体である。これらはどちらも DLP の数式上の循環群 \(G\) として使用できるため、旧来の Diffie-Hellman や ElGamal といったアルゴリズムをほぼそのまま楕円曲線に置き換えることができる。…

sentiment_satisfied 2019年12月14日(土) #ECDH #ECC #ECDSA #EdDSA #ed25519 #ed448

離散対数問題と公開鍵暗号

離散対数問題に基づく暗号アルゴリズムは古くから研究されてきたが、公開鍵暗号が世間に広く利用されるようになったのは素因数分解に基づく RSA を待たなければならなかった。しかし旧来の欠点を克服した DSA や、楕円曲線への応用によって、近年では RSA に比べてより高いパフォーマンスを得られるようになった。…

sentiment_very_satisfied 2019年12月14日(土) #DLP #DH #ElGamal #DSA #Schnorr

論文翻訳: On the Size of Pairing-based Non-interactive Arguments\(\star\)

2016 年の論文。

sentiment_very_satisfied 2019年11月30日(土) 2016年の論文 #zk-SNARK

論文翻訳: Quadratic Span Programs and Succinct NIZKs without PCPs

sentiment_very_satisfied 2019年11月24日(日) 2013年の論文 #zk-SNARK

論文翻訳: Pinocchio: Nearly Practical Verifiable Computation

sentiment_very_satisfied 2019年11月24日(日) 2013年の論文 #zk-SNARK #Pinocchio

論文翻訳: High-speed high-security signatures

楕円曲線暗号アルゴリズムの一種であるエドワーズ曲線デジタル署名 (EdDSA; ed25519, ed448) の速度やセキュリティ優位性に関する 2011 年の論文。

sentiment_very_satisfied 2019年11月24日(日) 2011年の論文 #楕円曲線暗号 #EdDSA #Ed25519 #Ed448

RFC翻訳: Edwards-Curve Digital Signature Algorithm (EdDSA)

sentiment_very_satisfied 2019年11月9日(土) RFC 8032 #楕円曲線暗号 #EdDSA #Ed25519 #Ed448

論文翻訳: Curve25519: new Diffie-Hellman speed records

通常の楕円曲線アルゴリズム (EC) より高速で鍵の小さい Curve25519 を使用した暗号計算に関する 2006 年の論文。

sentiment_very_satisfied 2019年11月6日(水) 2006年の論文 #楕円曲線暗号 #curve25519 #ed25519

読書メモ: プログラミング言語 Rust 公式ガイド

The Rust Programming Language (日本語版) の邦訳版で ASCII DWANGO から出版されている「プログラミング言語 Rust 公式ガイド」の読書メモ。レベルとしては1つ2つの汎用プログラミング言語を使いこなすことができるプログラマ向けの入門書で、特に C/C++ と関数型言語を使える人ならすんなり読める内容だろう。…

sentiment_very_satisfied 2019年11月3日(日) Rust 1.38 #Rust

秘密分散共有

秘密分散共有 (secret sharing) または単に秘密分散は秘密情報 \(S\) を \(n\) 個の分散情報に符号化する暗号化アルゴリズムの一種。特に (k,n) しきい値法では \(n\) 個の分散情報のうち任意の \(k\) 個が揃えば元の秘密情報 \(S\) を再構築することができる (\(k\) 個に満たない場合は再構築することができない)。…

sentiment_very_satisfied 2019年11月2日(土) #SecretSharing #VSS #セキュアマルチパーティ計算

論文翻訳: Compact Multi-Signatures for Smaller Blockchains

マルチ署名、公開鍵集約を使用してブロックチェーンサイズを小さくするための 2018 年の論文。

sentiment_very_satisfied 2019年10月14日(月) 2018年の論文 #マルチ署名

群論

集合とその演算や作用によって定まる構造を代数的構造という。ある集合 \(G\) 上の要素 \(a,b \in G\) に対して \(c = a \ast b \in G\) となるような何らかの演算 \(\ast\) が定義されているとき、集合 \(G\) は代数系であり \((G,\ast)\) や単に \(\mathbb{G}\) と表される。…

sentiment_very_satisfied 2019年10月9日(水) #群論

論文翻訳: Aggregate and Verifiably Encrypted Signatures from Bilinear Maps

GAP Diffie-Hellman と双線形写像を使用して BLS 署名派生スキーム、集約署名、ブラインド署名、リング署名を紹介する 2003 年の論文。集約署名は異なるユーザによる異なるメッセージに対する署名を単一の署名に集約する

sentiment_very_satisfied 2019年10月7日(月) 2003年の論文

翻訳: Introduction to Transaction Management

sentiment_very_satisfied 2019年10月6日(日)

論文翻訳: Byzantine Finality Gadgets

Polkadot で検討されている、重み付き PoW を使った分岐の発生するコンセンサスにファイナリティ特性を追加するための PoS に基づいたアルゴリズムに関する 2019 年の提示文書。原文は誤字、脱字、曖昧で難解な言い回しが多く非常に読みづらい。

sentiment_very_satisfied 2019年9月25日(水) 2019年の論文 #Blockchain #Polkadot #GRANDPA

Blockchain: Polkadot

done 2019年9月25日(水) #polkadot

Blockchain: 用語

sentiment_satisfied 2019年9月16日(月) #Blockchain

鍵共有アルゴリズム

暗号技術における鍵共有 (key exchange) とは、共通の秘匿情報を持たない当事者間で公にされている情報のみを用いて、すべての当事者サイドで通信内容を保護するための共通の鍵を生成する方法。現代の暗号通信では通信の双方が共有鍵 (もしくはそのシード) を作成するために使用している。…

done 2019年9月16日(月) #鍵共有 #DH #PTP

ペアリング暗号

ペアリング暗号 (pairing-based cryptography) は双線形写像 (bilinear map) の構造を持った暗号アルゴリズム。楕円曲線暗号ではある同一の群 \(G\) 上での写像 \(e:G \times G \to G\) の写像だったが、ペアリングでは 2 つの暗号化群から別の群への写像 \(e:G_1 \times G_2 \to G_T\) という構造を持つ。…

sentiment_very_satisfied 2019年9月15日(日) #Pairing #IBE #BLS

論文翻訳: Short Signatures from the Weil Pairing

Gap Diffie-Hellman 群でのヴェイユペアリングを使用することで、一般的な RSA や DSA での署名と比べて同じ強度で短い署名を生成する方法を示す 2001 年の論文。

sentiment_very_satisfied 2019年9月14日(土) 2001年の論文 #BLS署名 #GDH

Unihertz Atom

Uniherts Atom は小型軽量で防水、防塵に対応したいわゆるタフネス携帯。

done 2019年9月14日(土) #Unihertz #Atom

論文翻訳: Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme

(8) の Gap Diffie-Hellman 群を 1) BLS 署名を秘密分散のスキームに拡張したしきい値署名、2) 複数の署名分散から一つの署名を作成するマルチ署名、3) メッセージを秘匿するブラインド署名のそれぞれに応用した 2002 年の論文。

sentiment_very_satisfied 2019年9月7日(土) 2002年の論文 #BLS署名 #署名分散 #しきい値署名 #マルチ署名 #ブラインド署名

論文翻訳: Practical Threshold Signatures

RSA に基づく非インタラクティブな署名分散の方法についての 1999 年の論文。

sentiment_very_satisfied 2019年9月3日(火) 2000年の論文 #SignatureSharing #ThresholdSignature #署名分散 #しきい値署名

論文翻訳: Verifiable Random Functions

sentiment_very_satisfied 2019年9月1日(日) 1999年の論文 #VRF

Verifiable Random Function

VRF (verifiable random function) は公開鍵ペアを使用する暗号学的ハッシュ関数である。VRF 関数は秘密鍵を使ってある入力値に対するハッシュ値を算出することができる。加えて、第三者がその公開鍵を使って、受信したハッシュ値が本当にその秘密鍵を使って生成されたものであるかを検証することができる。…

sentiment_very_satisfied 2019年8月31日(土) #VRF #暗号抽選 #暗号選挙

論文翻訳: HotStuff: BFT Consensus in the Lens of Blockchain

State Machine Replication を行うための BFT 合意アルゴリズム HotStuff に関する 2019 年の論文。ブロックチェーンのような頻繁なリーダー変更を行う環境向けに、通信コストが \(O(n^2)\) から \(O(n)\) となっている。

sentiment_very_satisfied 2019年8月24日(土) 2019年の論文 #HotStuff #LibraBFT

属性ベース暗号

属性ベース暗号 (ABE; attribute-based encryption) は特定の属性を持った対象者のみが情報を復号化できる暗号方式。共通鍵暗号や公開鍵暗号は暗号化/復号化に使用する鍵が 1:1 であるのに対して、それが 1:n や n:1 という特徴を持つ。秘密分散と ID ベース暗号で構成されている。…

edit_note 2019年8月20日(火) #ABE

論文翻訳: Algorand: Scaling Byzantine Agreements for Cryptocurrencies

PoS に VRF (Verifiable Random Function) を組み合わせた選出を行う BFT 合意アルゴリズム Algorand に関する 2017 年の論文。

sentiment_very_satisfied 2019年8月19日(月) 2017年の論文 #Algorand

Tendermint

done 2019年7月15日(月) Tendermint 0.32 #Blockchain #Tendermint

論文翻訳: Practical Byzantine Fault Tolerance

Byzantine Fault Tolerance 合意アルゴリズムを実装面で補強した 1999 年の論文。

sentiment_very_satisfied 2019年7月6日(土) 1999年の論文 #PBFT

ビザンチン障害耐性

BFT (Byzantine fault-tolerance) またはビザンチン障害耐性はビザンチン障害プロセスが含まれていても安全な合意を達成することのできる性質である (あるいはその性質を持つ合意アルゴリズムを BFT とも呼ぶ)。またそのような性質を持つ合意をビザンチン合意 (Byzantine agreement) と呼ぶ。…

sentiment_very_satisfied 2019年6月23日(日) #Byzantine #BFT #BA

CAP 定理

CAP 定理は分散データベースシステムにおいてネットワーク分断 (partitioning) が発生したときに一貫性 (consistensy) か可用性 (availability) のどちらかしか取ることができないという原則。一般的な定理や原理といった強い制約ではなく、現在では分散データベースの特性や傾向、設計方針を分類する目的の言葉として使用されている。…

sentiment_satisfied 2019年6月17日(月) #CAPTheorem

論文翻訳: Reaching Agreement in the Presence of Faults

ビザンチン故障を含むネットワークでの分散合意が可能な条件についての 1979 年の論文。

sentiment_very_satisfied 2019年6月15日(土) 1979年の論文 #BFT

Go: インストール

sentiment_satisfied 2019年6月3日(月) #golang #chocolatey

Bitcoin

sentiment_very_satisfied 2019年6月3日(月) #Blockchain #Bitcoin #暗号通貨

翻訳: Verifiable Random Functions (VRFs)

Verifiable Random Functions (VRF) は公開鍵をキーとする暗号化ハッシュのバージョンである。秘密鍵の所有者のみがハッシュを算出できるが、公開鍵を持つ人であれば誰でもハッシュの正当性を検証できる。VRF はハッシュに基づくデータ構造の列挙を防ぐのに役に立つ。…

sentiment_very_satisfied 2019年5月28日(火) 2019年 IETF Draft 4 #VRF #IETF

論文翻訳: In Search of an Understandable Consensus Algorithm (Extended Version)

Raft は複製されたログを管理するためのコンセンサスアルゴリズムである。これは (Multi-) Paxosと同等の結果を生み出し Paxos と同程度に効率的だが、その構造は Paxos とは異なる; Raft によって Paxos よりも理解しやすく実用的なシステムを構築するためのより良い基盤が提供される。…

sentiment_very_satisfied 2019年5月19日(日) 2014年の論文 #Raft

Java: 公開鍵生成アルゴリズム

Java では KeyPairGenerator クラスを使用して作成することができる。

edit_note 2019年5月1日(水) Java 11 #ECDSA

分散システム

分散システム (distributed system) は、クライアント (エンドユーザ) から単一のシステムとして見えるように動作する、協調して動作する複数のコンピュータで構成されるシステム。複数のコンポーネントが異なるノードに配置されており、個別のノードが故障してもシステム全体がそれを見せないように動作し続けることができる。…

sentiment_very_satisfied 2019年4月24日(水)

論文翻訳: Impossibility of Distributed Consensus with One Faulty Process

コンセンサスの問題にはプロセスの非同期システムが含まれており、そのいくつかは信頼性が欠落していることがある。課題は、信頼できるプロセスが 2 値の下で合意することである。本論文では、この課題に対するどのようなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示している。…

sentiment_very_satisfied 2019年4月24日(水) 1985年の論文 #FLP #Reliability

論文翻訳: Skip Graphs

Skip Graph は、要素を格納する分散システムでバランスツリーの全機能を提供する、Skip List に基づく新しい分散データ構造である。要素はいつでも失敗する可能性のある別々のノードに格納される。これらは peer-to-peer ネットワークでの検索に使用されるように設計されており、キーの順序付けに基づいてクエリーを実行する機能を提供することで、ハッシュテーブル機能のみを提要する既存の検索ツールを改善している。…

done 2019年4月20日(土) 2003年の論文 #SkipGraph

etcd

etcd (etc distributed) は Raft に基づいた分散トランザクションを実装した分散 Key-Value ストア。コンテナ仮想化に特化した軽量 Linux ディストリビューションである CoreOS においてコンテナ間で設定を共有するために実装されたが、移植性の高い golang で実装されているため現在では様々な OS に移植されている。…

done 2019年4月11日(木) etc 3.3 #etcd

Java: Transport Layer Security

TLS (transport layer security) は TCP 上で安全な通信を行うためのプロトコル。PKI (public key infrastructure; 公開鍵基盤) に基づいて通信相手を認証し、暗号化されたストリームを通じて改ざん不可能なデータのやり取りを行うことができる。…

sentiment_very_satisfied 2019年3月23日(土) Java 11 #SSL #TLS #JSSE

OpenSSL リファレンス

複雑な OpenSSL コマンドを目的別にまとめる。

done 2019年3月20日(水) #openssl #ECDSA #X509

メッセージ認証コード

メッセージ認証コード (MAC; message authentication code) はメッセージの完全性を認証付きで保証する暗号学的手法である。鍵の所有者 \(A\) によりメッセージが発行されてから破損や改ざんを受けていないことを同じ鍵の所有者 \(B\) が検証することができる (\(A\) と \(B\) は同一でも良い)。…

done 2019年3月16日(土) Java 11 #MAC #HMAC

クロック同期

edit_note 2019年3月13日(水)

ゴシッププロトコル

ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上で情報をマルチキャストする方法の一つ。現実社会でうわさ話や感染症が伝播する過程と似たモデルのプロトコルである。ランダムグラフに基づく非構造化 P2P ネットワークや、強い調整者の存在しない分散ハッシュテーブルといった分散システムにおいて、緩やかな方法で最新の情報を共有する (anti-entropy) 目的でよく使用されている。…

sentiment_satisfied 2019年3月11日(月) #Gossip

Upper Intermediate S

英語のフレーズなどを記述しておくノート。

edit_note 2019年3月1日(金)

Service Provider Interface

SPI (service provider interface) は特定のインターフェースに一致する実装を Java のエコシステムが検出して暗黙的にロードするための機能。Java 6 において正式に導入された。アプリケーションは SPI を利用することで実行時に拡張可能な設計を行うことができる。…

done 2019年2月25日(月) Java 11

Java: 署名アルゴリズム

Java では Signature クラスを使用して任意のメッセージ (バイナリデータ) に対して電子署名を作成することができる。

done 2019年2月17日(日) Java 11 #ECDSA

Java: ハッシュ関数

ハッシュ関数 (hash function)、または Java ではメッセージダイジェスト (message digest) と呼ばれる機能は、ある任意の大きさのバイナリデータから固定長のバイナリを生成するためのアルゴリズムである。データ破損を検出するチェックサム (checksum) と似ているが、以下のような特徴を持つ。…

done 2019年2月17日(日) Java 11 #CRC #SHA

プライベート認証局

done 2019年2月13日(水)

ハッシュ関数

ハッシュ関数 (hash function) は任意長のビット列をある固定の長さのビット列に変換する関数。この操作は \(h\) は数学記号で \(h: \{0,1\}^* \to \{0,1\}^k=\{0,\ldots,2^k-1\}\) と記述することができる。ここで出力ビット長 \(k\) は 256 や 512 といった比較的小さな値である。…

sentiment_very_satisfied 2019年2月3日(日) #SHA3 #SHAKE

Rocks DB

Rocks DB は C++ で実装された key-value ストアの組み込み用ライブラリ。key 及び value は任意のバイナリデータが使用できる。メモリや極低レイテンシーな Flash ドライブのような物理ストレージと他コア CPU の実行環境に最適化されている。

done 2019年1月30日(水) #RocksDB

翻訳: The ZILLIQA Technical Whitepaper

既存の暗号通貨及びスマートコントラクトプラットフォームはスケーラビリティの問題を抱えている。すなはち、1秒間に処理できるトランザクションの数が制限されており、通常 10 未満であることが知られている。パブリック暗号通貨およびスマートコントラクトプラットフォームを利用するアプリケーションの数が増えるにつれ、数百から数千 Tx/s オーダーの高いトランザクションレートを処理することに対する需要が高まっている。…

sentiment_very_satisfied 2019年1月27日(日) 2017年の論文 #Blockchain #Zilliqa

Blockchain

分散システムにおけるブロックチェーン (blockchain) とは、ビザンチン障害耐性をもつ分散合意アルゴリズムを使ったステートマシンレプリケーション (SRM) として機能する Peer-to-Peer ネットワークである。特に、合意によって生成された命令シーケンスは暗号技術を使用してリンクされた不変のブロックのリストとして分散共有される (データ構造の文脈ではこのブロックのリストをブロックチェーンと呼ぶ)。…

sentiment_very_satisfied 2019年1月4日(金) #Blockchain #Bitcoin #Ethereum #DistributedLedger #暗号通貨 #UTXO

Proof of Work

Proof of Work (PoW) は何らかの作業を行ったことを証明することで目的の行為を行う許可が与えられるスキームである。サービス要求者に何らかの作業を強制することで、DoS 攻撃やスパムメールの送信といった短時間で大量の要求を繰り返して発行する悪意的なコンピューティング能力を利用を防止するための実用上の対策である。…

edit_note 2018年12月28日(金) #Blockchain #PoW

Practical Byzantine Fault Tolerance

PBFT (practical Byzantine Fault Tolerance) はビザンチン障害耐性をもつ分散合意アルゴリズムの 1 つ。それ以前に提案されていた研究レベルのいくつかの BFT アルゴリズムを改良し、実用的に利用できる水準となった最初の BFT アルゴリズムである。…

done 2018年12月24日(月) #PBFT #BFT

Resource Pooing 実装

リソースプーリング (resource pooling) は有限のリソースをプールしアプリケーション内の複数の処理で共有 (resource sharing) する仕組み。一般的に、生成や消滅のコストの高いリソースを初期化を終えた状態で共有、再利用することによるパフォーマンス向上の効果を目的としている。…

edit_note 2018年11月26日(月) #ResourcePool

Future 機能

CompletableFuture は Java での非同期プログラミングで使用するクラス。非同期プログラミングはアプリケーションのメインスレッドとは別のスレッドを使用して非ブロッキングにタスクを行うための手段である。一般にこのような並列化によってプログラムのパフォーマンスは大幅に向上する。…

sentiment_very_satisfied 2018年10月29日(月) Java 8

HDFS

HDFS (Hadoop distributed file system) は Hadoop で使用されている分散ファイルシステム。データを複数の計算機上に分散配置し、MapReduce を用いて各計算機上で並列分散処理を行うことができる。

edit_note 2018年10月22日(月) #HDFS

Redis:インストール

Redis は C で書かれており、gcc や libc 以外に依存するライブラリを持たないことから公式の Redis Quick Start では最新版をソースからコンパイルすることを薦めている。ここでは開発環境として利用するために Docker や OS 標準のパッケージ管理を使用する。…

done 2018年10月19日(金) Redis 4 #Redis

Lettuce 5

done 2018年10月9日(火) Lettuce 5 #Redis #Lettuce

Redis

Redis はデータベースやキャッシュ、メッセージブローカーとして使用することのできるインメモリデータベース。NoSQL DB の一つとしてよく知られている。主に Unix 系の OS を対象としており Windows での実行は難しい。

done 2018年10月9日(火) Redis 4 #Redis

覚知の限界

交渉や駆け引きにおける注意の狭窄と焦点化、またそれらによって引き起こされる合理性の欠ける判断は覚知の限界 (bounded awareness; Bazerman, Chugh, 2005) と呼ばれる。

sentiment_very_satisfied 2018年9月7日(金) #BoundedAwareness

Keras: 超解像

超解像 (super resolution) は解像度の低い画像や動画、音声などの信号からより高解像度なバージョンを生成する技術。

done 2018年8月12日(日) TensorFlow 1.8 #Keras #TensorFlow #RSCNN

オープンデータセット

edit_note 2018年8月12日(日)

畳み込みニューラルネットワーク

畳み込みニューラルネットワーク (convnet, CNN; convolutional neural network) はフィードフォーワード型の深層ニューラルネットワーク (DNN; deep neural network) の一種。主に画像や映像に対する物体認識分野において良好な性能を示している。…

sentiment_very_satisfied 2018年8月12日(日) #ConvNet

Keras: CNN中間層フィルタの可視化

edit_note 2018年8月6日(月) TensorFlow 1.8 #Keras #TensorFlow #Conv

Matplotlib TIPS

edit_note 2018年8月5日(日) Python 3.5 #matplotlib

論文翻訳: Deep Clustering for Unsupervised Learning of Visual Features

概要: クラスタリングはコンピュータ・ビジョンで広く適用され研究されている教師なし学習方法の一種である。しかし大規模なデータセット上での視覚的特徴量の end-to-end 学習にクラスタリングを適用させる研究は殆ど行われていない。本研究では、ニューラルネットワークのパラメータと、その結果として得られた特徴量のクラスタ割り当てを組み合わせて学習するクラスタリング手法である DeepCluster を提示する。…

sentiment_very_satisfied 2018年7月26日(木) 2018年の論文 #DeepCluster #CNN

OpenCV: 画像クラスタリング (PCA/DBSCAN)

edit_note 2018年7月24日(火) OpenCV 3 #OpenCV

React:逆引き

edit_note 2018年7月22日(日) React 16 #nodejs #reactjs

Ubuntu18.04: CUDA+Docker セットアップ

Ubuntu 18.04 (bionic beaver) の Docker コンテナ上からホストに設置されている GPU を使用するための環境構築手順を記述する。

sentiment_very_satisfied 2018年7月20日(金) GTX-1050TI #ubuntu #nvidia #cuda

ローカルサーバ: Cobalt

CPU 処理と常時起動サーバのためのマシン。

done 2018年7月15日(日) Ubuntu 18.04 #ubuntu

Keras: 画像生成 (変分オートエンコーダー)

オートエンコーダー (autoencoder, 自動符号化器) はニューラルネットワークを使用した次元削減手法。次元の小さい中間層を設置した多層ニューラルネットワークを、入力と同じデータを出力するように学習することで、中間層部分の出力からより特徴的な表現を少ない次元で得ることができる。…

done 2018年7月13日(金) TensorFlow 1.8 #Keras #TensorFlow #VAE

Keras: CNN画像分類 (Keras-provided CNN)

Keras は過去のコンテストで優秀な成績を収めた CNN がすぐに利用可能な形で含まれている。ここではこれらの CNN を独自のデータセットで学習して画像分類を行う。

done 2018年7月10日(火) TensorFlow 1.8 #Keras #TensorFlow #Xception

Keras: CNN画像分類 (クラスの可視化)

edit_note 2018年7月9日(月) TensorFlow 1.8 #Keras #TensorFlow #VGG16

Keras: CNN中間層出力の可視化

Keras 2.2 を使用して CNN の中間層がどのような出力を行っているかを可視化する。ここでは学習済みモデルに VGG16 + ImageNet を使用しカワセミの写真のどの部分を特徴としてとらえているかを示すためのヒートマップを作成する (このヒートマップで示される特徴に対する反応の強さをこのページでは暫定的に特徴強度と呼ぶ)。…

sentiment_very_satisfied 2018年7月8日(日) TensorFlow 1.8 #Keras #TensorFlow #Conv

CIFAR-10

CIFAR-10 は 10 種に分類された 32×32 の 60,000 画像からなるデータセット。80 Million Tiny Images から画像認識のために抽出/分類したサブセットである。

done 2018年7月5日(木) Keras 2.2 #CIFAR10 #CNN

Keras: ImageDataGenerator

Keras 2.2 に付属するデータ拡張と正規化のための多機能前処理ユーティリティ ImageDataGenerator のパラメータごとの効果を整理する。明文化されていない部分については Github のソースを参照する必要がある。

sentiment_very_satisfied 2018年7月3日(火) TensorFlow 1.8 #Keras #TensorFlow

Keras: CNN画像分類 (転移学習/Fine Tuning)

転移学習 (transfer learning) はネットワークをゼロから学習させる代わりに、別のタスクで学習したネットワークを元に目的のタスクに最学習させることで、学習のための計算コストや学習に必要なデータセットの数を削減する手法。その際に行われる再学習は fine tuning (微調整) と呼ばれる。…

done 2018年6月30日(土) TensorFlow 1.8 #Keras #TensorFlow #VGG16

Keras: ImageNet分類ラベル一覧

ImageNet データセットに基づく Keras 2.2.0 で利用可能な CNN 学習済みモデルの分類ラベルとその意味 (./keras/models/imagenet_class_index.json に保存されている)。サムネールは該当するラベルに分類されている画像を ImageNet からいくつかサンプリングしたもの。…

edit_note 2018年6月27日(水) TensorFlow 1.8 #Keras #TensorFlow #VGG16

Keras: CNN画像分類 (Pre-trained CNN Model)

CNN モデルを使用した画像分類スクリプトを作成する。Keras は自分でニューラルネットワークを組み立てデータセットを用意してモデルを構築することもできるが、過去のコンペで優秀な成績を収めたいくつかの CNN がすぐに利用可能な形で含まれていて、推測部分にフォーカスして試すのであればそれらを利用するのが早い。…

sentiment_very_satisfied 2018年6月27日(水) TensorFlow 1.8 #Keras #TensorFlow #VGG16

Lucene: 類似画像検索

AKAZE, ORB, SIFT, SURF などを使用して画像から特徴点とスケール・回転・輝度・Blur 耐性を持つ特徴量を抽出し、それらから Bug of Visual Words (Bag of Features) を使用して全文検索エンジンである Lucene

edit_note 2018年6月26日(火) Lucene 6 #Lucene #Lire

JavaVM 仕様読書会ノート

The Java® Virtual Machine Specification Java SE 10 Edition 読書会のノート。Connpass イベント。

edit_note 2018年6月22日(金) JavaVM Spec 10 #JVMSpec_Reading

認知バイアス

意思決定において根拠の一つ一つを吟味し合理的な判断を下すコストは決して低いものではない。人は重要ではない判断に対して、過去に経験したり記憶から導き出しやすい材料に基づいて意思決定を行っている。例えばシェフが 1 コース分の料理を作り上げるまでに、プログラマが 1 つのソースファイルを書き上げるまでに、小説家が 1 ページ分を書き上げるまでに数百から数千もの軽微な判断が行われている。…

sentiment_very_satisfied 2018年6月17日(日) #認知バイアス #CognitiveBias

TensorFlow + Keras セットアップ

edit_note 2018年6月12日(火) Python 3.6 #keras #tensorflow

OpenCV: 局所特徴量による類似画像検索/分類

画像の局所特徴量は回転や拡大縮小によって分布が変換しない特徴ベクトルである。つまり特徴量の分布の形が似ている画像は特徴点の配置が似ている画像であることが予想される。この局所特徴量を \(n\) 次元空間上でクラスタ化し、画像ごとに算出した Bag of Visual Words (Bag of Features とも) を使用して画像の類似度を得ることで、撮影されている物体の特徴に基づいた画像検索を行うことを目的とする。…

sentiment_very_satisfied 2018年6月10日(日) Python 3 #OpenCV

OpenCV: セットアップ

Windows / Java 環境で OpenCV を使うまでのセットアップ手順。OpenCV の Java バインディングは JAR ファイルとその JNI のネイティブライブラリ (Windows であれば DLL) の 2 ファイルで構成されている。これらをプロジェクトに追加してやれば良い。…

done 2018年6月5日(火) OpenCV 3 #OpenCV

OpenCV: 特徴点/特徴量の抽出

edit_note 2018年6月5日(火) Python 3 #OpenCV

Julia: 目的別機能

done 2018年5月31日(木) Julia 0.6 #julialang

判断の選好逆転

完全に合理的な判断ができているのであれば前提条件が変わらない限り判断が変わることはない。しかし人は問題のとらえ方に流されて異なる判断を行いがちである。

done 2018年5月30日(水)

Julia: グラフの描画

PyPlot はプロットライブラリである matplotlib.python のインターフェースを Julia から使えるようにしたパッケージ。ローカルに導入する場合は REPL で PyPlot パッケージを導入しておく。

done 2018年5月29日(火) Julia 0.6 #julialang

OpenCV: 目的別機能

done 2018年5月29日(火) OpenCV 3 #OpenCV

OpenCV 3

edit_note 2018年5月27日(日) OpenCV 3 #OpenCV

画像収集

機械学習を行う目的で対象物の画像を収集する方法について現時点での手順をまとめておく。処理は大まかに以下のステップを想定しているが:

sentiment_very_satisfied 2018年5月23日(水) ES2015 #Azure #GCP #Flickr #AWS

ボロノイ領域

ボロノイ領域 (Volonoi region) は

edit_note 2018年5月12日(土)

意思決定

edit_note 2018年5月11日(金)

最大エントロピー法

最大エントロピー法 (maximum entropy model) は前提条件だけで明確な確率分布を導き出せない事象に対して、全体のエントロピーが最大化する方向に確率分布を割り当てる方法。条件が設定されていないのであれば、条件外の余計な偏りを含まない最も不確かなモデルが採用されるべきという考え方に基づく。…

sentiment_satisfied 2018年5月9日(水) #NLP #MaximumEntropy

論文翻訳: A Simple Introduction to Maximum Entropy Models for Natural Language Processing

自然言語処理における多くの問題は、言語学的文脈を用いて言語学的クラスを予測する言語学的分類問題と考えることができる。最大エントロピーモデルは特定の言語学的コンテキストで発生する特定の言語学的クラスの確率を推定するために、様々な文脈的根拠を組み合わせるクリーンな方法を提供する。このレポートでは例問題で特定の最大エントロピーモデルを使用して、そのモデルに関するいくつかの関連する数学的事実を簡単かつアクセス可能な方法で証明する。…

sentiment_very_satisfied 2018年5月7日(月) 1997年の論文 #NLP #MaximumEntropy

The Rust Programming Language ノート

The Rust Programming Language 2nd ED. からのメモ書き。

done 2018年4月26日(木) Rust 1.25 #Rust

Rust 開発環境

edit_note 2018年4月26日(木) Rust 1.25 #Rust

S2 Geometry Library

S2 Geometry Library は球面上の領域を扱うための空間インデクシング (spatial indexing) ライブラリ。主に地球を対象としており、地理データを分割統治や索引付けのためのセル (区画) に分割することを目的としている。また非常にコンパクトで 64bit 整数で地球表面上の 1cm 四方を表す解像度を持つ。…

done 2018年4月19日(木) #S2

B+Tree

B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケースに適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。…

done 2018年4月14日(土) #BTree

R-Tree

R-Tree は深さ平衡木 (depth-balanced tree)。葉ノード

edit_note 2018年4月6日(金) #RTree

論文翻訳: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree

空間インデックス (spatial index) のためのアルゴリズム Priority R-Tree (2004) に関する論文。

sentiment_very_satisfied 2018年4月4日(水) 2004年の論文 #RTree

論文翻訳: From Word Embeddings To Document Distances

我々はテキスト文書間の新しい距離関数である Word Mover's Distance (WMD) を提示する。我々の研究は文中の局所的な共起から単語の意味的に重要な表現を学習する単語埋め込み (word embedding) の最近の研究結果に基づいている。WMD 距離は、2 つのテキスト文書間の非類似度を、一方の文書に埋め込まれた単語が別の文書に埋め込まれた単語に到達するまでに「移動」する必要がある最小の距離量として算出する。…

sentiment_very_satisfied 2018年3月28日(水) 2015年の論文 #NLP #WordMoversDistance #WMD

論文翻訳: PositionRank: An Unsupervised Approach to Keyphrase Extraction from Scholarly Documents

学術論文からキーフレーズを抽出するためのアルゴリズム PositionRank (2017) に関する論文。

sentiment_very_satisfied 2018年3月27日(火) 2017年の論文 #NLP #PositionRank

可変長整数エンコーディング

いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。

done 2018年3月25日(日)

社会心理学

done 2018年3月18日(日)

React

React は SPA (Single Page Application) を開発するためのフレームワーク。JSX を含む JavaScript ソースやその依存ファイルをブラウザが解釈可能な形式にトランスコンパイルし、最終的に一般的な HTTP サーバにデプロイできる形の静的なファイルセットを作成する。…

sentiment_very_satisfied 2018年3月5日(月) React 16 #nodejs #reactjs

英語ノート

英語のフレーズなどを記述しておくノート。

sentiment_very_satisfied 2018年2月26日(月)

npm

npm (Node package manager) は JavaScript 用のパッケージマネージャで世界最大級のソフトウェアレジストリ。JavaScript 実行環境である Node.js のデフォルトのパッケージマネージャとして使用されている。公開されている再利用可能なコードを検索したり、それらをダウンロードしプロジェクトで利用することができる。…

sentiment_satisfied 2018年2月22日(木) npm 5 #nodejs #npm

Node.js セットアップ

edit_note 2018年2月21日(水) npm 5 #nodejs #npm

Docker セットアップ

done 2018年2月21日(水) Docker 17 #Docker

最小経路問題

重み付きグラフ上のある頂点 \(s\) から別の頂点 \(t\) まで到達する経路の中で最もコストの低い経路を求める問題 (重みなしグラフの場合は各辺の重みを 1 とする)。最小シュタイナー木問題において 2 点を使った最小コストの部分グラフを作成することと同じ。

done 2018年2月19日(月) #graphtheory

最小全域木問題

いくつかの頂点と、各頂点の間をつなげるコスト (辺の重み) が定義されており、最も小さいコストですべての頂点をつなぐ最適化問題。コストは 0 より大きく接続不能 (つまりコスト \(\infty\)) も取り得る。すべての頂点がつながることから連結グラフでなければならず、また閉路はいずれか 1 本分の辺のコストが無駄であることから存在しない。…

done 2018年2月17日(土) #graphtheory

タグ抽出

タグ抽出 (tag extraction) またはキーワード抽出の目的は文書の内容を代表していると思われる単語を選択する処理。他に自然文の構文構造を素性として重み付けする方法などいくつか過去の研究ある。

done 2018年2月14日(水) JUNG 2.1 #NLP

グラフ理論 序説

グラフ理論 (graph theory) は数学的概念であるグラフを説明する理論。問題を頂点と辺からなるグラフに抽象化し、その離散構造そのものを論議の対象とする。

sentiment_very_satisfied 2018年2月13日(火) #graphtheory

論文翻訳: The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries

本稿はテキスト検索と要約の文脈において情報関連性とクエリー関連性を統合する方法を提示する。Maximal Marginal Relevance (MMR) の判定基準は、検索された文書の順位を変更したり、テキスト要約のための適切な一節を選択する際に、クエリーの関連性を維持しながら冗長性を減らすことを目的としている。…

sentiment_very_satisfied 2018年2月11日(日) 1998年の論文 #NLP #MMR

コサイン類似度

ベクトル空間モデル (vector space model)、または単語ベクトルモデル (term vector model) はテキスト文書やそれに類似する任意のオブジェクトを識別子のベクトルとして表現するための代数空間モデルである。ここで識別子とは索引として使用できる n-gram や形態素ような情報を指している。…

sentiment_satisfied 2018年2月7日(水)

自動要約

自動要約 (auto summarization) または文書要約は文書の要約を作成することを目的としたテキスト短縮の処理。対象とする文書が一つの場合を単一文書要約、特定の文書セットを要約する場合を複数文書要約と呼ぶ。単一文書要約は一般的に長い文章から重要な部分のみを取り出すことを目的とする。…

sentiment_very_satisfied 2018年1月31日(水) JUNG 2.1 #NLP

論文翻訳: TextRank: Bringing Order into Texts

この論文ではテキスト処理において graph-based ランキングモデルである TextRank を導入し、このモデルが自然言語アプリケーションにおいて有効に機能するかを示す。特に、キーワード抽出と文抽出の 2 つの革新的な教師なし学習の方法を提案し、得られた結果が既存のベンチマークで過去に公表された結果と適合することを示す。…

sentiment_very_satisfied 2018年1月31日(水) 2004年の論文 #NLP #TextRank

論文翻訳: LexRank: Graph-based Lexical Centrality as Salience in Text Summarization

我々は推計学的な graph-based のグラフに基づいて自然言語処理におけるテキスト単位の相対的重要度を算出する方法を導入し、テキスト要約 (TS; text summarization) 問題でこの手法をテストする。抽出型要約 (extractive TS) は文書または文書セット内のもっとも重要な文を識別する要点文の概念に依る。…

sentiment_very_satisfied 2018年1月31日(水) 2004年の論文 #NLP #LexRank

Holt-Winters 法

ホルト-ウィンターズ法 (Holt-Winters method) は指数平滑化法における時系列の変動にトレンドと季節変動を追加し、それぞれの指数平滑の重ね合わせを期待値として算出する方法。このため 3 重指数平滑化法 (triple exponential smoothing) とも呼ばれる。…

sentiment_satisfied 2018年1月30日(火) #HoltWinters

行動経済学

edit_note 2018年1月27日(土)

指数平滑化法

指数平滑化法 (exponential smoothing) は時系列データを平滑化する代表的な時系列分析手法。観測値の中でより新しいデータに大きな重みを設定し、過去になるほど指数関数的に重みを減少させた期待値 (移動平均) を算出する。直近の観測値の変動に従属させたいような比較的短期間の期待値を決めるのに適している。…

done 2018年1月21日(日)

Julia 言語の特徴

sentiment_satisfied 2018年1月15日(月) Julia 0.6.2 #julialang

Jupyter Notebook

Jupyter Notebook はライブコード、方程式、視覚化、テキストを含むドキュメントを作成して共有できるオープンソースの Web アプリケーション。データのクリーニングと変換、数値シミュレーション、統計モデリング、データの視覚化、機械学習などを目的として使用される。

sentiment_satisfied 2018年1月4日(木) Jupyter Notebook 4.4.0 #JupyterNotebook

Python 3 セットアップ

この記述では Python 3 を使用して virtualenv で環境を切り替え pip でライブラリの管理を行うことをゴールとする。

edit_note 2017年12月15日(金) Ubuntu 16.04 #python

Chainer セットアップ

Chainer はニューラルネットワークを記述するためのフレームワーク。既存の命令型フレームワークよりも "Define and Run" で柔軟性を重視しており宣言的にネットワークを記述することができる。

done 2017年12月15日(金) CuPy 2.2 #chainer

メタプログラミング - Julia

Julia はコードを AST (abstract syntax tree; 抽象構文木) として評価する機能を持っている。ここでの評価とはコード上に AST を展開し実行することを意味する。このようなコード展開による評価は、強固なコンテキスト分離を持つ関数の呼び出しなどと異なり、実行コンテキストに強く影響する (黒魔術的な) 機能を実装することができる。…

sentiment_satisfied 2017年12月11日(月) Julia 0.6.2 #julialang

MXNet セットアップ

Apache MXNet は高速でスケーラブルな機械学習フレームワーク。Gluon という高レベル API が付属しており AWS が正式にサポートしている。

done 2017年12月11日(月) Ubuntu 16.04 #mxnet

多層パーセプトロン

多層パーセプトロン (MLP; multilayer perceptron) または Feedforward Neural Network, Deep Feedforward Network は典型的な深層機械学習のためのネットワークモデル。多層パーセプトロンはある関数 \(f\) の近似を目的とし、写像 \(\vector{y} = f(\vector{x}; \vector{\theta})\) が最良の近似関数となるようなパラメータ \(\vector{\theta}\) を学習する。…

sentiment_satisfied 2017年11月30日(木) #MLP #DNN #deeplearning

Recurrent Neural Network

Recurrent Neural Network (RNN; 再帰型ニューラルネットワーク) は時系列の情報パターンを認識するように設計されたニューラルネットワーク。自然言語処理、遺伝子、センサーデータ、株式など、データのシーケンスを節に分解して時系列として扱うことができるデータを対象としている。…

done 2017年11月30日(木) #RNN

React Native

React Native

edit_note 2017年11月29日(水) React Native 0.49

Fusion Tables Client for Java/Scala

Java やその他の JavaVM 言語は Maven, Gradle, sbt などのビルドツールを利用して Maven リポジトリの Fusion Tables API のクライアントライブラリを利用するのが早いだろう。

sentiment_very_satisfied 2017年11月24日(金) Scala 2.12

Google Fusion Tables

Google Fusion Tables は Google が提供するデータベース。

edit_note 2017年11月24日(金) Fusion Tables API v2

MXBean

edit_note 2017年11月22日(水) Java 9 #MXBean

Service Worker

Service Worker はブラウザネイティブと同じ UI でユーザに通知を行うことができる。通知方法には 2 種類あり、ユーザがアプリを起動していないときでもローカルで起動しているアプリからユーザに通知を行う方法。もうひとつがサーバから通知を受ける方法である。

edit_note 2017年11月21日(火) Chrome 61 #ServiceWorker

Service Worker

Service Worker の目的の一つはキャッシュ制御によるサイトの高速化である。ブラウザのキャッシュをサイト実装者が詳細に制御することで、動的に変化しないコンテンツ (HTML, CSS, JS, 画像等) をデバイスローカルにキャッシュし Web アプリケーションの表示を高速化する。…

done 2017年11月21日(火) Chrome 61 #ServiceWorker

Service Worker

edit_note 2017年11月19日(日) Chrome 61

Service Worker

サービスワーカー (service worker) はクライアント (ブラウザ) のバックグランドで実行される JavaScript 処理。HTML を操作するユーザインターフェースのスクリプトとは別のコンテキストで動作する。現在のところブラウザでのバックグラウンド同期、キャッシュ制御、ユーザ通知などを目的とした仕様策定と実装が進められている。…

sentiment_satisfied 2017年11月18日(土) Chrome 61 #ServiceWorker

メルカトル図法

メルカトル図法 (Mercator projection) またはメルカトル投影は円筒投影法を用いて球体表面の 2 次元座標を \(x\),\(y\) 座標の平面に投影する方法。ここでは地球上の地理の投影について述べている。

sentiment_satisfied 2017年11月15日(水)

Getting Started with Progressive Web Apps

Progressive Web Apps (PWA) は Google が開発したスマートフォン/タブレット向けのアプリケーションアーキテクチャ。HTML, JavaScript, CSS で作成できる。

done 2017年11月15日(水)

Latent Dirichlet Allocation

sentiment_satisfied 2017年10月29日(日) #LDA

Note: ビットコインのブロックチェーン

BCCC 2017 で行った bitcon のブロックチェーン技術に関するノート。

sentiment_satisfied 2017年10月26日(木) #bitcoin #blockchain

制御構文

sentiment_very_satisfied 2017年10月24日(火) Julia 0.6 #java #scala #julialang

データ型

sentiment_satisfied 2017年10月24日(火) Julia 0.6 #java #scala #julialang

ロケール一覧

Locale で定義されている通貨の一覧。

edit_note 2017年10月20日(金) Java 9

通貨一覧

Currency で定義されている通貨の一覧。

edit_note 2017年10月20日(金) Java 9

文字セット一覧

Charset に定義されている文字セット。

edit_note 2017年10月20日(金) Java 9

システムプロパティ一覧

System で定義されている通貨の一覧。

edit_note 2017年10月20日(金) Java 9

タイムゾーン一覧

TimeZone で定義されている通貨の一覧。

edit_note 2017年10月20日(金) Java 9

ポアソン分布

単位時間あたりに平均 \(\mu\) 回観測される事象が、単位時間あたりに \(r\) 回観測される確率はポアソン分布 (poison distribution) に従う。\( P(X=r) = \frac{e^{-\lambda} \lambda^r}{r!}, \ \ r=0,1,\ldots\s \)

edit_note 2017年10月18日(水)

文字列の操作

sentiment_very_satisfied 2017年10月16日(月) Julia 0.6 #java #scala #julialang

数値の操作

sentiment_very_satisfied 2017年10月16日(月) Julia 0.6 #java #scala #julialang

Julia - 演算子

Julia の特徴的な演算子機能としては、べき乗と逆除算が用意されていること、そして言語機能のレベルで演算子のベクトル化が可能であることが挙げられる。C/C++ や Java などの言語知識があれば多くは読み飛ばしてもかまわない。

done 2017年10月14日(土) Julia 0.6.0 #julialang

機械イプシロン

機械イプシロン (machine epsilon) は浮動小数点演算の丸めによって発生する相対誤差の上限を意味する。これはコンピュータ演算を使った数値解析特有のトピックである。macheps, unit roundoff または計算機イプシロンとも呼ばれ記号 \(\epsilon\), \({\bf u}\) で表される。…

done 2017年10月13日(金)

相関係数

相関係数 (correlation coefficient) は確率変数 \(X\) に対する別の確率変数 \(Y\) の線形従属性を示す尺度。最も一般的なものは線形相関係数 (linear correlation coefficient) で積率相関係数 (product-moment correlation coefficient)、Peason の \(r\) (Pearson's r) とも呼ばれる。…

sentiment_satisfied 2017年10月13日(金)

スクラップブック

done 2017年10月13日(金) Julia 0.6.0 #julialang

有効数字

有効数字 (significant figures of number) は実数の分解能を意味する数字。数値のどの桁までが意味を持つかを表している。

done 2017年10月13日(金)

データ型・変数・関数

edit_note 2017年10月13日(金) Julia 0.6.0 #julialang

形態素解析

自然言語処理ではよく単語を文章を構成する「意味を持つ情報」の最小単位として扱っている。ラテン語圏の言語は単語の区切りに空白を使用しているためプログラムでの抽出は比較的容易だが、日本語の場合は文の中から単語を識別し適切に分割する実装が必要となる。このような単語分割処理は対象とする言語圏ごとに実装する必要がある。…

sentiment_satisfied 2017年10月11日(水) Kuromoji #kuromoji #形態素解析

TF-IDF

TF-IDF (term frequency - inverse document frequency) はある単語がコーパス内の文書に対してどれほど重要であるかを示す統計的数値。TF-IDF 値は文書内に単語が出現する回数に比例して増加するが、コーパス内での単語の出現頻度によって相殺されることが多く、一般に頻繁に出現する単語を調整する利点をもつ。…

sentiment_satisfied 2017年10月11日(水) #TF-IDF

疑似乱数サンプリング

疑似乱数サンプリング (pseudo-random number sampling) は与えられた確率分布に従う擬似乱数を生成する数値的手法。一般に一様乱数 \(u\) を利用して一様ではない分布のサンプリングを行う。

sentiment_very_satisfied 2017年10月9日(月)

マルコフ連鎖モンテカルロ法

マルコフ連鎖モンテカルロ法 (Markov chain Monte Carlo methods; MCMC 法) は確率分布から疑似乱数サンプリングを行うためのアルゴリズム。ある時点の状態 \(x^{(t)}\) からランダムに採択した次の状態 \(x^{(t+1)}\) へ確率付きで移動することから "マルコフ連鎖", "モンテカルロ法" の名前で呼ばれる。…

sentiment_satisfied 2017年10月9日(月) #MCMC

マルコフ連鎖

時刻やステップの推移で状態空間 \(\{1, 2, \ldots, k\}\) のいずれかの値を持つ確率変数について考える。ある時点 \(t\in(0, 1, \ldots)\) での確率変数を \(x^{(t)}\) とする。

done 2017年10月9日(月)

ベータ分布

ベータ分布 (beta distribution) は以下の式で表される連続確率分布。確率変数は \(0 \lt x \lt 1\) の範囲を取る。\( P(x; \alpha, \beta) = \frac{x^{\alpha-1}(1-x)^{\beta-1}}{B(\alpha,\beta)}, \,\,\, \alpha \gt 0, \beta\gt 0 \) ここで \(B(\alpha,\beta)\) はベータ関数である。…

done 2017年10月7日(土)

不動点反復法

集合 \(X\) からそれ自身への写像 \(f\) が与えられたとき、\(f(x)=x\) を満たす元 \(x\) を不動点 (fixed-point) または固定点と言う。グラフ上では、連続関数 \(f:\mathbb{R} \Rightarrow \mathbb{R}\) の不動点は曲線 \(y=f(x)\) と対角線 \(y=x\) の交点の \(x\) 座標である。…

done 2017年10月5日(木)

モンティ・ホール問題

1990 年に話題になったとき、著名な数学者を含む多くの人が「同じ確率だから選択を変える必要はない」と答えた問題。最終的な状況を客観視すると、選択可能な箱が 2 つあってそのうちのどちらかが当たりであることから、どちらを選んでも確率は 1/2 に思える。司会者がハズレの箱を間引いたところで当たりの箱は何も影響を受けていないので確率が 1/3 から 1/2 に変化しただけだろう、ということだ。…

sentiment_satisfied 2017年10月4日(水)

ベルヌーイ分布

結果が {0, 1}、{true, false}、{OK, NG} といった 2 値しかとりえない独立した事象の試みをベルヌーイ試行 (bernoulli trial) と呼ぶ。これらの結果は統計で扱う便宜上 \(b \in \{0,1\}\) に置き換えて考える。

done 2017年10月3日(火)

カテゴリカル分布

それぞれ独立した確率 \(p_k\) を持つ \(K\) 個の事象 (カテゴリカル変数; categorical variable) が存在し、1 回の独立した試行でそのいずれか一つが観測される離散確率分布をカテゴリカル分布 (categorical distribution) と呼ぶ。…

done 2017年10月1日(日)

多項分布の推定

事象 \(k \in \{1,2,\cdots,K\}\) がそれぞれ生起確率 \(\vector{p} = (p_1,p_2,\cdots,p_K)\) に従って観測されるとき、標本 \(x=k\) が観測される確率 \(P(k)=p_k\) の分布はカテゴリカル分布に従う。さらにカテゴリカル分布に従う試行を \(n\) 回行ったとき、それぞれの事象の観測数を \(\vector{x} = (x_1, x_2, \cdots, x_K)\) とすると、ある標本 \(\vector{x}\) が観測される確率分布は多項分布 (\(\ref{multinomial_distribution}\)) に従う。…

sentiment_very_satisfied 2017年9月30日(土)

カイ二乗分布

\(\vector{x} = (x_1, x_2, \cdots, x_k)\) が標準正規分布に従う確率変数であるとき、その自乗和 \( Z = \sum_{i=1}^k x_i^2 \) は自由度 \(k\) のカイ二乗分布に従う (\(\chi_k^2\) と表す)。確率密度関数は \( f(z;k) = \frac{e^{-\frac{1}{2}z}z^{\frac{1}{2}k-1}}{2^{\frac{1}{2}k}\Gamma(\frac{1}{2}k)}, z \gt 0 \) 平均 \(k\)、分散 \(2k\)、最頻値は \(k \leq 2\) のとき 0 となりそれ以外では \(k-2\)。…

edit_note 2017年9月30日(土)

多項分布

独立した \(K\) 個の事象 \(k \in \{1, 2, \ldots, K\}\) のいずれか一つが観測される確率をそれぞれ \(\vector{p} = (p_1, p_2, \ldots, p_K)\) とする。この試行を \(n\) 回繰り返したときに各事象の観測された回数を確率変数 \(x_k\) とする。…

sentiment_satisfied 2017年9月29日(金) #multinomial

二項分布

試行において 1 が観測される確率 \(p\) のベルヌーイ試行を \(n\) 回行ったとき (あるいは \(n\) 個同時に行ったとき) に 1 が \(x\) 個観測される確率は \(p\) と \(n\) をパラメータとした以下の確率質量関数で表される。\( P(x; n,p) = \binom nx p^{x} (1-p)^{n-x} \) ここで二項係数は以下のように表される。…

done 2017年9月29日(金)

浮動小数点数

浮動小数点演算 (floating-point arithmetic) は実数をある範囲の精度で近似した数式表現で行う算術演算のこと。この近似表現を浮動小数点数という。科学技術計算では非常に大きな値や小さな値を扱う代わりに、観測精度の限界から必要な有効数字が保証されていれば十分であることが多い。…

sentiment_satisfied 2017年9月28日(木)

高速逆二乗根

高速逆二乗根 (fast inverse square root) は浮動小数点と定数を用いて \(\frac{1}{\sqrt{x}}\) を高速に演算する方法。

edit_note 2017年9月28日(木)

Numerical Algorithms for Scala

学生の頃に Numerical Recipes in C という多くの実数演算アルゴリズムの載った書籍があった。英語版は 3rd Ed. が出ているようだが日本語版は出ていない。アルゴリズム辞典や数値演算ライブラリを作る気はないのだが系統としてはあの本の方向で行ければ良いと思っている。…

done 2017年9月26日(火)

正規分布の推定

平均 \(\mu\)、分散 \(\sigma^2\) をパラメータとする正規分布 \({\rm Norm}(\mu,\sigma^2)\) にもとづいて確率変数 \(x\) が観測されるとき、その確率密度関数は以下のように表される。\( P(x|\mu,\sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} {\rm exp}\left\{-\frac{(x-\mu)^2}{2\sigma^2}\right\} \)

sentiment_very_satisfied 2017年9月17日(日)

二項分布の推定

事象 \(b \in \{0,1\}\) のベルヌーイ試行で \(b=1\) となる確率を \(p\)、試行回数を \(n\) とした時、1 が \(x\) 回観測される (出た数の合計が \(x\) となる) 確率関数は二項分布 \(P(x;n,p)\) に従う。ここで \(x=k\) となる確率は以下のように表される。…

sentiment_very_satisfied 2017年9月17日(日)

最尤推定とMAP推定

ある生起確率 \(\vector{\theta}=(\theta_1, \ldots, \theta_N)\) に基づいてデータ \(\vector{X} = (x_1, x_2, \ldots, x_N)\) が観測されるとき、あるデータ \(\vector{X}\) が観測される確率は \(\vector{p}(\vector{X}|\vector{\theta})\) で表される (条件付き確率)。…

done 2017年9月16日(土)

ND4J ユーザガイド

sentiment_very_satisfied 2017年9月16日(土)

ベータ関数

ベータ関数 (beta function) は以下の積分で定義される特殊関数。\( B(x, y) = B(y, x) = \int_0^1 t^{x-1} (1-t)^{y-1} dt \) またガンマ関数を使用して以下のように表すこともできる。\( \begin{equation} B(x, y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)} \label{beta_expressed_gamma} \end{equation} \) したがって \(x\) と \(y\) が正の整数であれば階乗として表すことができる。…

done 2017年9月13日(水)

ガンマ関数と階乗

ガンマ関数 (gamma function) は 0 または負の整数以外の複素数に対して以下の積分で定義される特殊関数。\( \Gamma(z) = \int_0^\infty t^{z-1} e^{-t} dt \) また漸化式 \(\Gamma(z+1) = z \Gamma(z)\) でも表すことができる。…

sentiment_very_satisfied 2017年9月13日(水)

ラグランジュの未定乗数法

ラグランジュの未定乗数法 (method of Lagrange multiplier) は制約付き最適化問題で極値を求めるための手法である。ある 1 つ以上の条件 \(g(x)=0\) の下で関数 \(f(x)\) が最大値/最小値を取ることを式 (\(\ref{optimal_consumption}\)) のように表す。…

done 2017年9月9日(土)

ディリクレ分布

ディリクレ分布 (dirichlet distribution) は独立した事象 \(k \in \{1, 2, \cdots, K\}\) がそれぞれ \(x_k=\alpha_k - 1\) 回観測されたときに各事象の生起確率が \(p_k\) である確率を示す連続した確率密度関数。…

sentiment_very_satisfied 2017年9月9日(土)

usb4j の機能

usb4j は USB デバイスと通信する Java アプリケーションを開発するためのライブラリです。Java の高い移植性を生かしてプラットフォームごとに異なる USB 実装をより抽象化した API で利用することを目的としています。

edit_note 2009年5月20日(水) #usb4j

USB for Java

done 2009年5月20日(水) #usb4j

USB for Java

USB for Java は Java から USB デバイスと通信するためのライブラリです。

edit_note 2009年5月5日(火) #usb4j

HTTP Sniffer Proxy

Java 製のプロキシ型 HTTP リクエスト/レスポンス Sniffer。クライアントから想定通りのリクエストが出ているか、サーバがきちんと Cookie を返しているかなど、ブラウザのソース表示だけでは分からない通信プロトコルを調査する Web ディベロッパー向けツールです。…

done 2009年4月15日(水) #HTTPRroxy

1. 導入

edit_note 2008年10月21日(火) #Garmin #GPS

7. データ型

sentiment_very_satisfied 2008年10月21日(火) #Garmin #GPS

6. アプリケーションプロトコル

sentiment_very_satisfied 2008年10月21日(火) #Garmin #GPS

Garmin Device Interface Specification

sentiment_very_satisfied 2008年10月21日(火) #Garmin #GPS

4. リンクプロトコル

done 2008年10月21日(火) #Garmin #GPS

2. プロトコル層

edit_note 2008年10月21日(火) #Garmin #GPS

3. 物理プロトコル

sentiment_very_satisfied 2008年10月21日(火) #Garmin #GPS

5. アプリケーションプロトコルの概要

sentiment_satisfied 2008年10月21日(火) #Garmin #GPS

Standard Widget Toolkit

SWT (Standard Widget Toolkit) は IBM が Eclipse 用に開発した GUI ライブラリです。JNI を使用することで昔の Swing で問題となっていたグラフィック描画のボトルネックを回避し、当時の Swing ベースのアプリケーションと比較して格段の速さを誇っていました。…

done 2008年3月21日(金) Java 6

SWT レイアウトマネージャ

SWT は AWT とは別に専用のレイアウトマネージャを用意していますが、機能や役割は AWT のそれと同じです。

sentiment_very_satisfied 2008年3月21日(金) Java 6

公開鍵暗号 入門

異なる鍵 A と B が存在した場合、A で暗号化したデータが B でしか復号化できないといった特殊な鍵の組み合わせを非対称鍵 (asymmetric key) と言う。公開鍵暗号 (public-key encryption) は非対称鍵の特性を利用して鍵の片方を暗号化用に相手に公開し (公開鍵)、もう片方を復号化用に非公開にしておく (秘密鍵) 方式。…

done 2008年3月21日(金)

共通鍵暗号

done 2008年3月21日(金) #AES

Secure Sockets Layer

SSL (secure sockets layer) は公開鍵暗号と共通鍵暗号、電子署名、公開鍵証明書などの技術を組み合わせ、暗号化による盗聴防止、改ざん・破損の検出、通信相手の証明などを一度に実現している通信技術。

done 2008年3月21日(金) #SSL

Java GUI

現在 Java で利用されている主な GUI (Graphical User Interface) ライブラリは AWT、Swing、SWT の 3 つです。ただし AWT のみによる GUI アプリケーション開発は既にほとんど行われておりません。

sentiment_very_satisfied 2008年3月21日(金) Java 6

電子署名

電子署名 (digital signature) は文書に対する承認と、文書内容の保障を電子的に付け加えるための暗号技術。公開鍵を使用することにより他人によって行われた署名でないことと、署名された時点から文書内容に変更がないことの 2 点を証明することができる。また電子署名法により 2001 年から電子商取引などにおける法的根拠としても利用可能となっている。…

sentiment_satisfied 2008年3月20日(木)

Swing

Swing はプラットフォーム依存のウィジェットに頼らず、全てのコンポーネント描画と状態の管理を Java で実装した GUI ライブラリです。元々 AWT の機能の薄さを補うために Sun が Netscape 社 (当時) と共同で開発した Java Foundation Class (JFC) という GUI ライブラリが J2SE 1.2 から標準となりました。…

edit_note 2008年3月18日(火) Java 6

システムトレイ

Java SE 6 からシステムトレイ (タスクトレイ) が利用できるようになりました。メール着信のお知らせツール (biff) やウィンドウレスで常駐するアプリケーションで便利な機能です。この機能は Windows, Macintosh, GNOME, KDE など、デスクトップ用途を前提としたウィンドウマネージャであれば大抵は利用可能です。…

done 2008年3月14日(金) Java 6

Abstract Window Toolkit

AWT (Abstract Window Toolkit) は初期の Java で標準として用意されていた GUI ライブラリです。それまでプラットフォームごとに使い方が異なっていたウィジェット (GUI コンポーネント) を抽象化し、Java から統一した標準 API として使用できるようにしています。…

edit_note 2008年3月14日(金) Java 6

Jython

Jython は動的オブジェクト指向スクリプト言語 Python の Java 実装版です。java.net スクリプトプロジェクトの一つとしてとして開発が進められています。

done 2008年3月14日(金) Java 6

Rhino

Rhino は元々 Mozilla プロジェクトで開発されていた Pure Java 製の JavaScript (ECMAScript) エンジンです。JDK 1.1 からの長い歴史を持ち (そして一時期の暗黒時代を経て)、Java SE 6 の Scripting API 実装として標準バンドルされています。…

sentiment_satisfied 2008年3月14日(金) Java 6

Google Fusion Tables

Berkeley DB はカリフォルニア大バークレイ校で開発されたデータベースライブラリ。データベースと言っても RDBMS のように SQL が使用できたり関連モデルで設計されているわけではなく、ファイル上にインデックス付けされたデータ構造をプロシジャ形式のインターフェースを用いて検索、更新出来るライブラリ (Database Manager) です。…

done 2008年3月3日(月) Berkeley DB

Scripting for the Java™ Platform

Scripting for the Java™ Platform は JSR 223 で標準化され Java SE 6 から導入されたスクリプト API。文字列や外部ファイルに記述されているスクリプトを Java 上で実行することができる。

done 2008年2月29日(金) Java 6

Solaris 10 セットアップ

導入直後の root ユーザのホームディレクトリは / に設定されているがセキュリティ面でも運用面でもろしくないので変更する。

sentiment_satisfied 2008年2月29日(金) Solaris 10

Solaris 10 for x86 インストール

Solaris 10 8/07 for x86 のダウンロードから起動までの手順を解説する。なお作業は VMWare のゲスト OS として行っているため通常のインストールと異なる部分が若干あるかもしれない。

sentiment_satisfied 2008年2月29日(金) Solaris 10

GIF 画像出力

米 Unisys 社が取得していた GIF の LZW 圧縮に関する特許が2004年6月20日に切れ Java SE 6 から GIF への出力がサポートされた。このページでは Java SE 6 の Image I/O を使用してアニメーション GIF を作成する方法について述べる。…

sentiment_very_satisfied 2008年1月26日(土) Java 6

Date and Time Formats

done 2007年8月15日(水)

XML Path Language (XPath) 2.0

sentiment_very_satisfied 2007年8月13日(月)

The Content-MD5 Header Field

edit_note 2006年3月22日(水)

The Content-Disposition Header

edit_note 2000年7月4日(火)

HTTP State Management Mechanism

edit_note 1999年11月6日(土)

The Finger User Information Protocol

edit_note 1999年10月21日(木)

The Internet Gopher Protocol

edit_note 1999年10月17日(日)

The Internet Gopher Protocol

edit_note 1999年10月17日(日)

SIMPLE MAIL TRANSFER PROTOCOL

edit_note 1999年10月8日(金)

SIMPLE MAIL TRANSFER PROTOCOL

edit_note 1999年10月8日(金)

Echo Protocol

edit_note 1999年8月1日(日)

UTF-8, a transformation format of Unicode and ISO 10646

edit_note 1999年7月7日(水)

Hypertext Transfer Protocol - HTTP/1.1

sentiment_very_satisfied 1999年6月10日(木)

Uniform Resource Locators (URL)

edit_note 1999年3月20日(土)