最小二乗法で始めるカーブフィッティング

要旨

本エントリー(WIP)はカーブフィッティング全般に関して記述したものであり, それぞれの原理, 性質について学んだ際のメモとして, より単純なものから広く浅く挙げています. 極力ないようにはしていますが, 本内容は独学で得た知見より書いておりますので, 一部正確さが欠けている可能性があることは否めません. 何かありましたら, コメント等で指摘していただけるとありがたいです. また, 本エントリ内における近似およびプロット等に関する実装は次のリポジトリ

にまとまっています.

目次

  1. 要旨
  2. 線形回帰
    1. 線形最小二乗法
  3. 一般逆行列
    1. 最小二乗形一般逆行列
    2. 最小ノルム形一般逆行列
    3. 制限つき最小二乗法
    4. オーバーフィッティングと正則化およびその評価
    5. 誤差分布が正規分布でない場合の線形回帰
    6. 最小刈込み二乗法
    7. 参考文献

LU 分解

LU 分解に関して初歩的な内容から網羅的にまとめた.

目次

  1. ガウスの消去法
  2. ガウス・ジョルダン法
  3. ピボッティング
  4. LU 分解
  5. 参考文献

Haskell でリンクレイヤーにおける ICMP パケットの構築, 送受信および解析による ping の実装

Haskell で低レイヤーのネットワークプログラミングをそういえばしたことがなかったので, 何か実装してみたかったのだが特別ネタも思いつかないので, とりあえずイーサヘッダ, IP ヘッダ等を含む, 生の ICMP Echo/Reply パケットを扱ってみることとした.

ICMP パケットは IP パケットであるので, 通常は ICMP パケット部分のみを構築してPF_INET等で開いたソケットに送りつけたり, recv 等すれば送受信においては必要十分であるが, これではあまり面白みがないので, リンクレイヤーから扱うこととした.

生の ICMP パケットを扱うということは, ICMP データの自作はもちろん, イーサヘッダ, IP ヘッダの自作が必要となる. またイーサヘッダを自作するということは, MAC アドレスを解決しなければならないので, 最低限 ARP パケットの送受信および解析機能の自作が必要となることを意味する. ARP パケットの自作を要するということは, デフォルトゲートウェイやサブネット環境などを取得する機能も必要である. これらを自作してみた.


Haskell で D-Bus から systemd unit を制御する

D-Bus とはメッセージバスシステムであり, アプリケーション間で互いにやりとりを行うためのプロセス間通信実装の 1 つである. システムデーモン(新しいハードウェアデバイスの追加やプリンタキューの変更などのイベント等)と, ユーザー単位のログインセッションデーモン(ユーザーアプリケーション間の一般的なIPC)を提供する1.

現代的な Linux カーネルの init プロセスにて起動される systemd デーモンおよびその補助デーモンは, D-Bus にいくつかの API を公開している. 私の観測範囲内において, C や Python, Go 等でこれらを利用する例はそこそこ見たことがあるのだが, Haskell での取り組みは一切見たことがなかったので, 少々これらで遊んで見た日記として本エントリに記す.


エルガマル暗号

エルガマル暗号が離散対数問題の応用であることは認知していたものの, きっちりと自分でまとめたことが無かったと思うので, それに関連する諸々の前提についてもふまえて, 一度書くことにした. また, その処理系を実装した. 本エントリでは, 同暗号プロトコルの話の前にまず前提を示し, その後, 実装の観点から見た要点を示す.

目次

  1. ユークリッドの互除法
  2. ガロア体
  3. オイラーの ϕ\phi 関数
  4. フェルマーの小定理
  5. 原始元
  6. 離散対数問題
  7. 実装
    1. フェルマーテスト, Miller-Rabin 素数判定法
    2. 原始根の生成
    3. 鍵と暗号文の生成
    4. 暗号文の復号
    5. 実行
  8. 参考文献