データベースを設計する

今までもデータベースは触っていたのですが、データベースの設計についてはあまり知らなかったため、

gihyo.jp

を読んで実際にデータベースを設計してみました。データベース設計は概念データモデリング、論理データモデリング、物理データモデリングの3つの工程からなります。この3つを順にやっていくことにします。題材として「本好きのためのSNS」というアプリのためのデータベースをつくることにしてみます。

概念データモデリング

概念データモデリングとは

システム化の準備として、対象範囲にある業務プロセスと関連するデータ項目をすべて洗い出し、業務とデータ項目の関係をデータの集合体の レベルでモデル化すること

です。要するにシステムの対象となるデータとプロセスを明確にすることです。今回の例では次のようにしておきます。

f:id:hedwig1001:20220319164825p:plain
概念データモデル

ER図のリレーションっぽく書いていますが、そこまで厳密な意味をもっては書いてないです。

論理データモデリング

論理データモデリングの目的は2つあり

  1. 信頼性の高いデータを格納する
  2. 将来にわたって一元的にデータを管理できること

です。一つ目の「信頼性の高いデータ」とはデータの不整合が発生しにくいデータの持ち方のことです。例えばある本の名前をbooksという本のデータを持つテーブルとreadというユーザがどの本を読んだか管理するテーブルの両方で管理していたとします。このとき本の名前を変えようと思ったときに 2箇所のデータを間違いなく変更しなければなりません。もしミスがあれば不整合が発生することになります。このような重複をなくすようにデータを持ちます。このような作業は「正規化」と呼ばれることがあります。

2つ目はルールの変更などに強い安定したデータ構造を作るということです。たとえば本のジャンルが一つの本につき一種類しか登録できないとします。しかしある都合で、一つの本に複数のジャンルを登録したくなりました。このようなルールの変更が起こってもできるだけデータベースの変更をせずに済むような構造にするということです。

正規化

とりあえず概念データモデリングが終わって次のような感じでデータを持とうと考えていました。

  • ユーザ
ユーザ(R)
PK user_ID 整数
username 文字列
password 文字列
フレンド(R)
PK,FK follower 整数
PK,FK followee 整数
  • メッセージ
メッセージ(E)
PK message_id 整数
FK sender_id 整数
FK receiver_id 整数
content 文字列
send_at 時刻
  • オープンメッセージ
オープンメッセージ(E)
PK open_message_id 整数
FK sender_id 整数
content 文字列
send_at 時刻
本(R)
PK book_id 整数
FK author_id 整数
FK genre_id 整数
ユーザ本(E)
PK,FK user_id 整数
PK,FK book_id 整数
thoughts(感想) 文字列
read_at 日付
筆者(R)
PK author_id 整数
name 文字列
ジャンル(R)
PK genre_id 整数
name 文字列

ここから正規化を施していきます。 プライマリーキーが一意となるようにするのが第一正規化です。これはプラマリーキーを考えながらつくると達成されてしまっていました。

つぎに複合キーに関する重複を排除します。複合キーのうちなかのあるキーを決めるとそれ以外のキーで一意に決まってしまうアトリビュートがある場合はそれを別のエンティティに分離します。これを第二正規化と言います。これもこのなかにはありません。

最後に非キー同士の重複を排除します。つまりある非キーがきまるとそれから一意に決まってしまうアトリビュートがある場合はそれを別のエンティティに分離します。これを第三正規化と言います。これもこの中にはありません。

software designの記事を一回全部読んでから実際にデータベースを設計したらどうなるんだろうとおもってやってみましたが、読んだ知識にすでに影響を受けて正規化してしまっているような気がします。

何はともあれ、正規化してから作成したER図が以下です。

f:id:hedwig1001:20220319183329p:plain
ER図1
*1

つぎに最適化を行うのですが、扱うエンティティの数がそれほど多くなく、すべてのエンティティを同時に正規化してしまったので飛ばします。

ビジネスルール検証

システム上のルールに従っているかを確認するのがビジネスルール検証です。ここで一つの本に一種類のジャンルしかつけられるようになっていないことに気づきました。「一つの本に複数のジャンルをつけられるようにする」というルールとこれは矛盾します(このルールは概念データモデリングで決めておくべき)。そのため books_genres のような多対多のテーブルを用意することにしました。

安定性検証

つぎに将来の変化に対して強いデータ構造にするのが安定性検証です。ここではプライマリーキーの安定性検証をしたいと思います。たとえば「ユーザ本」のエンティティを見ると、user_id,book_id で複合キーとしています。これではたとえば同じ本を2回読んだことを登録することはできません。 これにはほかの read_id といったPKを新たに作って user_id,book_id を非キーとすることで対応できます。

これらの作業の後に綺麗に作り直したER図が以下になります。

f:id:hedwig1001:20220319185059p:plain
ER図2

これをもとに物理データモデリングを進めていきます。

物理データモデリング

物理データモデリングの目的は

データ構造の安定性を保ちながらRDBMSに実装できる「動くデータベース」にすること

です。まず論理データモデリングで作成した図を用いてCRUD図を書きます。これを書くことでプロセスとデータの関係性が目に見えてわかるようになります。

User Book Author Genre Read Follow Message OpenMessage
ユーザ登録 C
ユーザログイン R
ユーザ画面作成 R R R R
ユーザ消す D D D D D
読んだ本を登録 U C C C C
読んだ本の情報を更新 U U U U U
本を検索 R R R
10年経過 D D D
フレンド追加 C
フレンド削除 D
メッセージ送信 C
オープンメッセージ送信 C

ユーザ画面作成のところが少しざつですが、上のような感じになります。上の図ですべてのエンティティにC,Dがあることなどを確認します。また、イベントエンティティとリソースエンティティに分けて、プロセスを上からイベントエンティティを左から発生順に並び替えてCが左上から右下に並んでいくことを確認します。

Read Follow Message OpenMessage User Book Author Genre
ユーザ登録 C
ユーザログイン R
読んだ本を登録 C U C C C
読んだ本の情報を更新 U U U U U
本を検索 R R R
フレンド追加 C U
フレンド削除 D
メッセージ送信 C U
オープンメッセージ送信 C U
ユーザ画面作成 R R R R
10年経過 D D D
ユーザ消す D D D D D

テーブル設計

つぎにテーブルを実際に設計していきます。これにはテーブル名、カラム名、データ型、制約、インデックスをどのようにするか決める作業が含まれます。ここでは必須項目にNOT NULL制約、また同じジャンルが複数登録されることを防ぐための一意性制約などをつけました。またER図のリレーションに沿って外部キー制約をつけます。UPDATE時の挙動やDELETE時の挙動を決める ON UPDATE ~, ON DELETE ~ は基本的に依存リレーションならば CASCADE, 非依存ならば RESTRICT を指定します。

これらのことを行なってできたのが以下です。

CREATE TABLE users (
    user_id INTEGER PRIMARY KEY,
    username VARCHAR(64) NOT NULL,
    password VARCHAR(128) NOT NULL
);

CREATE TABLE authors (
    author_id INTEGER PRIMARY KEY,
    name VARCHAR(64) NOT NULL UNIQUE
);

CREATE TABLE genres (
    genre_id INTEGER PRIMARY KEY,
    name VARCHAR(128) NOT NULL UNIQUE
);

CREATE TABLE books (
    book_id INTEGER PRIMARY KEY,
    author_id INTEGER NOT NULL,
    name VARCHAR(128) NOT NULL UNIQUE,
    FOREIGN KEY (author_id) REFERENCES authors(author_id) ON DELETE CASCADE
);

CREATE TABLE books_genres (
    book_id INTEGER NOT NULL,
    genre_id INTEGER NOT NULL,
    PRIMARY KEY(book_id,genre_id),
    FOREIGN KEY (book_id) REFERENCES books(book_id) ON DELETE CASCADE,
    FOREIGN KEY (genre_id) REFERENCES genres(genre_id) ON DELETE CASCADE
);

CREATE TABLE reads (
    read_id INTEGER PRIMARY KEY,
    user_id INTEGER NOT NULL,
    book_id INTEGER NOT NULL,
    thoughts VARCHAR(1024),
    read_at DATE NOT NULL,
    FOREIGN KEY (user_id) REFERENCES users(user_id) ON DELETE CASCADE,
    FOREIGN KEY (book_id) REFERENCES books(book_id) ON DELETE CASCADE
);

CREATE TABLE follows (
    follower_id INTEGER NOT NULL,
    followee_id INTEGER NOT NULL,
    PRIMARY KEY(follower_id,followee_id),
    CHECK (followee_id <> follower_id),
    FOREIGN KEY (follower_id) REFERENCES users(user_id) ON DELETE CASCADE,
    FOREIGN KEY (followee_id) REFERENCES users(user_id) ON DELETE CASCADE
);

CREATE TABLE messages (
    message_id INTEGER PRIMARY KEY,
    sender_id INTEGER NOT NULL,
    receiver_id INTEGER NOT NULL,
    content VARCHAR(1024) NOT NULL,
    send_at TIMESTAMP WITH TIME ZONE NOT NULL,
    FOREIGN KEY (sender_id) REFERENCES users(user_id) ON DELETE CASCADE,
    FOREIGN KEY (receiver_id) REFERENCES users(user_id) ON DELETE CASCADE
);

CREATE TABLE open_messages (
    message_id INTEGER PRIMARY KEY,
    sender_id INTEGER NOT NULL,
    content VARCHAR(1024) NOT NULL,
    send_at TIMESTAMP WITH TIME ZONE NOT NULL,
    FOREIGN KEY (sender_id) REFERENCES users(user_id) ON DELETE CASCADE
);

-- view
CREATE VIEW book_author (
    book_id,
    book_name,
    author_name
) AS 
SELECT
    b.book_id,
    b.name AS book_name,
    (SELECT a.name FROM authors AS a WHERE a.author_id = b.author_id) AS author_name
FROM books AS b;

最後のビューはよく使うと考えられるため追加しました。

インデックス設計

次にインデックス設計を行います。(ここではインデックスはB木インデックスということにします)。RDBMSにインデックスをつけるメリット、デメリットとしては

メリット

  • WHERE句で特定のデータに絞るようなSELECTなどで高速化できることが期待できる。

デメリット

  • インデックスは定義しても使われない場合があり、ディスクが無駄になる
  • 更新、削除の際のコストは大きくなる。

があります。そのためインデックスをどこにつけるか/つけないか は効率化の上で考えるべきことですし、実際に効果があるかは実際のデータの分布などをみて決めないといけません。

ところで別の本*2にはインデックス作成の方針として

外部キー制約で参照されているすべての列にインデックスをつける。

といったことが書いてありました。なぜなら親行を消すときにかならず子行を参照するようになっているかららしいです。また外部キー制約がつくところで JOIN することが多いということもあるのではないかと思っています。

そこで実際に上のようにインデックスをつけることでクエリの実行時間に変化があるかをみてみたいと思います。上のテーブルとそれにインデックスとして

CREATE INDEX books_01 ON books (author_id);
CREATE INDEX books_genres_01 ON books_genres (book_id);
CREATE INDEX books_genres_02 ON books_genres (genre_id);
CREATE INDEX reads_01 ON reads (user_id);
CREATE INDEX reads_02 ON reads (book_id);
CREATE INDEX follows_01 ON follows (follower_id);
CREATE INDEX follows_02 ON follows (followee_id);
CREATE INDEX messages_01 ON messages (sender_id);
CREATE INDEX messages_02 ON messages (receiver_id);
CREATE INDEX open_messages_01 ON open_messages (sender_id);

を追加したものを比較してみます。テストデータとして約3万件の SELECTINSERT 文を別に実行してみて time コマンドで実行時間(ディスクI/Oの待ちをみるため, real)を5回計測して平均を取ります。色々ファイル書き込みとかのオーバーヘッド込みですが簡易的なものということということで許してください。

実行環境は

です。詳細なコードはこちら を参照してください。結果は以下のようになりました。

1回目/s 2回目/s 3回目/s 4回目/s 5回目/s 平均/s
インデックスなし(INSERT) 6.705 10.332 11.074 8.228 11.562 9.5802
インデックスなし(SELECT) 4.225 4.570 4.259 4.579 7.063 4.8752
インデックスあり(INSERT) 10.657 7.979 7.129 9.352 10.667 9.1568
インデックスあり(SELECT) 3.879 2.862 2.933 3.087 2.983 3.1488

ばらつきはすこしあるようですが、SELECT ではインデックスありの方が平均的に早いように見えます。INSERT では差は小さいものの インデックス有りの方が少し早いです。検定などをして厳密に評価したわけではないですが、外部キーを参照している列にインデックスをつけることの効果はたしかに感じることができます。

おわりに

データベース設計はむずかしいし、奥が深い作業であるとわかりました。データモデリングチェックリストにはもっと多くの確認すべき項目があって、実用に耐えうるデータベースをつくるのはたいへんなのだろうと感じました。

*1:図はdraw.ioで作成しました。以降の図も同様です。

*2:https://www.oreilly.co.jp/books/9784873119588/

Cコンパイラを自作してセルフホストしました

タイトル通りなのですが、CでCのコンパイラを書いてとりあえずセルフホストできるところまでできたのでブログにこれまでやったこととかを残しておこうと思います。作ったものは以下のリンクから見れます。

github.com

どうやって作ったか

これをつくろうと思ったきっかけとして、まず低レイヤを知りたい人のためのCコンパイラ作成入門があります。このサイト自体は未完成らしいのですが、初めのほうでコンパイラ作成の基本的な部分(トークナイズ、パース、コード生成)についてわかりやすく解説しており、コンパイラにそれほど詳しくなくてもコンパイラを作り始めることができます。

このサイトの最初の方で自分のコンパイラが正しく計算結果を出力するのを目にして、さらに段々機能を付け加えていくとだんだんC言語に近づいていくのがとてもおもしろかったため、楽しくつづけることができました。

蛇足ですが(コンパイラ作成とは直接は関係ないですが)、この本で推奨されているインクリメンタルな開発の仕方は常に完成した状態で開発を進めることができるのでいきなりハードルがあがるということがなくてよかったです。

上に書いたように、このサイトでは途中でおわっています。この時点ではまだセルフホストはできないため、セルフホストするためにはさらに機能を追加する必要があります。さらに機能を追加する際には

  1. The syntax of C in Backus-Naur form を見て, 追加したい機能に対応するBNFを確認して
  2. Compiler Explorerでその機能はどのような使い方が許されるのかを確認して
  3. 実際にコードを書く

ということを繰り返していきました。ちなみにセルフホストまでに必要な機能としては(自分の場合は)

  • 構造体定義 .,->
  • ++var,--var,var++,var--
  • void,bool
  • break,continue
  • switch ~ case ~ default ~
  • enum
  • charリテラル, エスケープシーケンス
  • %,<<,>>,|,&,||,&&,!三項演算子
  • +=,-=,*=
  • typedef
  • 可変長引数
  • (簡単な)キャスト

などでした。ちなみに今のところマクロ展開とリンクはサポートしていないため

  1. gccにマクロ展開してもらう
  2. マクロ展開したものを自分のコンパイラコンパイルする
  3. それらをgccでリンクしてもらう

のようにしてセルフホストしました。また最適化等は全く行っていません。

f:id:hedwig1001:20220315102938p:plain
セルフホストしてhcc2とhcc3が同じであることを確認した

面白かったポイント

なんといっても自分の書いたコードでコンパイルできるものが増えていくのを見るのがとても面白いです。はじめはただの計算しかできなかったのにfor文, 配列, 構造体などと追加していくとコンパイルできるコードが増えて、だんだん自分のコンパイラが成長しているのを感じることができます。成長過程をリンクで貼っておきます。

セルフホストできたときの感動もひとしおでした。

つらかったポイント

セグフォ

これはCで書くなら仕方ないかもしれないですが, ヌルポインタにアクセスしようとするとセグフォします。できるだけそれは防ぎたいのでエラー処理はしますが、完全に防ぐことはできないためセグフォすることがあります。そのためエラー出力を適当な箇所に入れて、セグフォしても「ここまでは正しく動いているはず」ということがわかるようにしました。

またコンパイラを書いているのでセグフォは自分の書いたコンパイラコンパイルしたアセンブリを実行しようとした時も起こる可能性があります。こうなったらまずアセンブリを見てどこでセグフォしているか確認します。これでわかればokですがわからない場合はgdbで実行してどの行でセグフォしているか確かめてコードを修正していました。

可変長引数

構造体やenumの追加も比較的スムーズにできたのですが、可変長引数の実装にすこし苦戦しました。そもそも va_list,va_start とかは stdarg.h で定義されていると思っていたのですが、これらの実態は __builtin_hogehoge というやつらでこれはコンパイラが実装するものだとわかりました。なのでこれらを実装しなければなりません。そのために

などを参考にしました。これらをみてもよくわからないところは前述のCompiler Explorerをつかってアセンブリを実際に出力してみて、どうなっているか確かめたりしました。vfprintf() を使っているので gcc と互換性があるように実装する必要もあると思います。

また関数呼び出しで引数の数が6個以下(すべて整数orポインタ)だと引数はレジスタにセットするのですが、6個より多いとスタックにpushします。 自分のコードでは7個以上の引数を持つ関数呼び出しがあったため、これもサポートしました(可変長とは関係なかった)。

知見

コンパイラ作成の過程でいろんなことを知りました。

C言語について詳しくなった

コンパイラをつくるにあたって, どういう書き方が許されてどういう書き方が許されないのかを考えることになります。そのため, C言語についての知識が増えます。たとえば

int a=1,b=2;
a,b = b,a;

という書き方はCでは合法なのですが, これはPythonの時のように a,bスワップするという意味にはなりません。Cではexpression(正確にはassign)をカンマ区切りで何回か並べたものをexpressionとしています(くわしくは The syntax of C in Backus-Naur form を参照してください)。そのため上のコードは a; b = b; a; を並べたものと同じです。なのでスワップではなく a,b の値は変化しないということになります。

またCの構文解析がしにくいというのも身をもって実感しました。たとえば

int a;
int f(int x) { ...

の二つを考えると int f(.. のカッコにくるまで変数の定義をしているのか, それとも関数の定義をしているのかわかりません。できるだけ最初の1文字を読んだ時点でなにをパースしようとしているのかはわかると楽です。Pythondef ... ですし, Goは var ... ,func ... ですし Rustも let ..., fn ... でこれが考慮されているらしいことがわかります。Cは昔の言語なのでしょうがないですが, Goは構文解析しやすいようにつくられているという話もなるほどなと納得できました。

アセンブリをかけるようになる。

あまりアセンブリを書いたことがなかったため, 実践的低レイヤプログラミングをみてちょっと勉強してから始めたのですが, コンパイラを作っていく過程でアセンブリを生成することになるのでアセンブリの知識がつきます。

結局アセンブリ

  • データを動かすmov
  • 計算する add,sub,cmp
  • ジャンプする je,jmp

の3種類がほとんどで、これらを組み合わせてプログラムは動いているのだなとわかりました。

f:id:hedwig1001:20220315111103p:plain
アセンブリを見てデバッグ!

プログラムが実行される様子が(なんとなく)わかる

関数呼び出し, どのように配列アクセスしているのか, 構造体はどのようにメモリ上にのっているのか, 構造体の->は何をしているのか, 参照を渡すとはどういうことか, ポインタとはなんなのか, etc. についてきちんと理解することができます。理解しないとコンパイラが書けないので。いままでブラックボックス化していたものをひとつづつ明らかにしていく感じがありました。

いまはまだ何に役に立つかはわかりませんが, 省メモリなプログラムを書いたり, 効率の良いプログラムを書いたりするのに役立てられれば良いなと思っています。

展望

セルフホストはしましたが, 実はまだ結構サポートしていない機能や中途半端な実装になっているところがあります。

  • structの引数, 値渡し, 初期化式
  • const-expressionをコンパイル時にきちんと評価する
  • unsigned系
  • short,long,_Bool
  • staticの関数をファイルスコープにする
  • enum,typedef,local variableの同じスコープで同じ識別子となるものを宣言できないようにする。
  • 関数ポインタの型をきちんと実装する。
  • #define #include とかのマクロ展開
  • 浮動小数点数

などです。これらの機能も追加していけたら良いなと思っています。

おわりに

コンパイラ作成は面白いと思うので, 低レイヤを知りたい人のためのCコンパイラ作成入門読んでやってみてください!

TCP/IPをGoで自作しました。

タイトルにある通りですが、TCP/IPプロトコルスタックをGoで実装しました。デバイス, IP, ARP ...などと実装してとりあえずTCPの最低限の機能までは実装したため、 ここに書いておこうと思います。つくったものは以下になります。

github.com

経緯

大学の授業やhttpあたりを勉強しているとTCP/IPという単語が登場します。マスタリングTCP/IPを一通り読みましたが、実装することでわかることは多いだろうということで実装してみました。実装に当たっては

を参考にさせていただきました。Cで実装するかGoで実装するか迷いましたが、Goにもっと慣れたいというのとchannel,goroutineを使っていい感じに並行処理してみたいということ でGoで書くことにしました。

ちなみにまったく5日では終わらず、約2週間ほどかけて実装しました。実装していく中で知らなかったGoの便利なライブラリや、Linuxのデバイス周りのこと、デバイスプロトコルの抽象化の方法などネットワークとは直接関係ない部分についても知見が得られました。

実装したもの

バイスからEthernet, IPv4,ARP,ICMP,UDP,ICMPなどの主要なプロトコルの機能の一部を実装しました。デバイスなどの下のレイヤから実装していきました。最終的にTCPでthree-way hand shakeができたときは「あのthree-way hand shakeができた...」と感動を覚えました。

f:id:hedwig1001:20220220151954p:plain
three-way hand shake

しかし、現状では「TCPはヘッダのオプションを無視している、IPフラグメンテーションに対応していない」などの問題があり、実装すべきところは まだあるかなという感じです。

知見、苦労したところ

バイスまわり

まず最初の関門がデバイス周りでした。デバイスとしてはLinuxのtapデバイスを用いています。tapデバイスについて書かれた本家のドキュメントはおそらく https://www.kernel.org/doc/Documentation/networking/tuntap.txtです。これと Man page of NETDEVICEを参考にしつつ、Goのsyscallパッケージを使ってlinuxシステムコールをよぶことで実装します。

より具体的には ifreq 構造体をつくって適切なシステムコールを読んで、その情報を取り出すということを行います。この辺のデバイスシステムコールを触ったことがなかったため苦労しました。tapデバイスを理解するためには Linux bridge、Tapインタフェースとは - passacaglia自作プロトコルスタック(全体像の理解〜ARPリプライ) - おしぼりの日常を読みました。 とくに前者の記事でtapデバイスとはそもそもなにか、後者の記事でデバイスの具体的な動作について理解が深まったような気がします。

binaryパッケージ

ネットワークを勉強したことある方はご存知だと思いますが、ネットワークを流れるパケットはビッグエンディアン、多くのハードウェアはリトルエンディアンで動きます。これは32bitや16bitの数をどのような順で並べるかという話です。このバイトオーダーの変換にGoの binary パッケージが有用でした。下位プロトコルペイロードをヘッダにパースする際に 「ビッグエンディアン -> リトルエンディアン」と変換する必要があるのですが、TCPヘッダ構造体のフィールドをヘッダの上から順に並ぶようにしておき、

var hdr TCPHeader
r := bytes.NewReader(payload)
err := binary.Read(r, binary.BigEndian, &hdr)

とすることで実現できます。逆にヘッダ->バイト列の変換も簡単です。「ヘッダ <-> データ」の変換はよくでてくるので便利でした。

TCP

TCPの実装が大変でした。TCP/IP プロトコルスタックを自作した - kawasin73のブログ のブログを見て、僕もRFC793を読んでみる ことにしました。RFC793は91ページあったのですが、21ページ以降のFUNCTIONAL SPECIFICATION以降を中心に読み、58ページ以降のEvent Processingを実装していくという感じでした。

TCPはデータが送られたことを確認するためにシーケンス番号を持ちます。シーケンス番号はTCPの送ったペイロードのバイトサイズ分だけ大きくなります。実はそれだけでなく、SYNとFINを送った時にもシーケンス番号が1だけ増えます。これはSYNとFINが再送されたり、きちんとACKが返ってくることを保証するためです。これは26ページに書いてあります。

FINがあったときにシーケンス番号を増やすというこの仕様をきちんと読めていなかったためうまく動かず、micropsの方を見てバグに気づきました。 仕様は隅から隅まで読まなければ正しく実装できないのだということを実感できました。

おわりに

TCP/IPをGoで実装して、デバイス、ネットワーク、Goについての知識が得られました。一石三鳥くらいあると思うので面白そうだと思った方はぜひやってみてはどうでしょうか。

mainからgoroutineの終了を通知する

下で書いたやり方でもできるけど同じことはcontext.Contextを用いて行った方が筋が良いらしい

main関数にあるgoroutineが終了したことを通知するにはsync.WaitGroup()を使えば良いです。 しかし, maiinからあるgoroutineに終了通知をするには同様にはできないため, 別の方法を使う必要があります。doneという終了通知チャンネルを 用意してそれをつかうことで実現できます。

package main

import (
    "fmt"
    "time"
)

func protocol(ch chan int, done chan struct{}) {
    for {
        select {
        case a := <-ch:
            // aをパケットだと思って処理
            fmt.Println(a)
        case <-done:
            fmt.Println("done")
            return
        default:
            continue
        }
    }
}

func main() {
    ch := make(chan int, 10)
    done := make(chan struct{})

    // 通信開始
    go protocol(ch, done)

    for i := 0; i < 7; i++ {
        ch <- i // パケットがネットワークを通じて届く
        time.Sleep(time.Second)
    }

    // 通信終了
    close(done)
}

select 文の中身がa := <- ch<-doneで入れ替わらないようにしましょう。

prmlを実装しました


prml(Pattern Recognition and Machine Learning)をpythonで実装しました。パターン認識機械学習, 通称prmlベイズ的な機械学習の教科書として有名ですが この本に載っているアルゴリズムを実装しました。gitリポジトリにあります。まだ完璧にすべて実装したわけではないですが、とりあえず 14章まで一通り実装し終わり、区切りがいいのでブログ記事を書きます。

f:id:hedwig1001:20211003152319p:plain
rvmでの予測


なんで実装したのか

prmlを一通り読み演習問題も文中で示されているものは解いたもののやっぱり実装してほんとうにうまくいくのかとか試してみたかったからです。 prmlは有名な本なので先人たちがいろいろと実装していますがそれを見るだけでは意味がないので自分で実装しようと思いました。

よかったこと

意味がわからなかったところがわかるようになった

ハイブリッドモンテカルロのところやRVMなどの理解が深まりました。前にprmlを読んでいたときは結局ハイブリッドモンテカルロってどうやってサンプリングするんだ??となっていましたが実装するという観点で読み直すことでサンプリングの仕方や周辺の数学的なことの理解が深まりました。

またRVMは本当に予測に必要なデータ点がトレーニングデータの10%ぐらいになっていて感動します。

numpyの仕様にすこし慣れた

numpyのブロードキャストとかの仕組みをいまいち理解していなかったんですが、この実装をしていく上でブロードキャストがどういうふうに動くかがとてもわかるようになってきました。ほかにも axis とか4次元とかになると微妙に慣れづらいところも理解が進みました。

その他副次的なこと

sphinxでdocumentをつくったり, docstringの書き方やライセンスの種類などをほんのちょっとだけですが知ることができました。

f:id:hedwig1001:20211003152831p:plain
ハイブリッドモンテカルロによるサンプリング

展望

ニューラルネットワークの章はまだ十分ではないと思うのでそのあたりといろいろとうまくいっていない実装があるのでそのあたりを直したいです(EP法, ロジスティック回帰の混合モデル など)。


終わりに

ちょっと数学的に面白いと思ったところや工夫ポイントは別の記事に書こうかなと思っています。

Shopee参加記2

shopeeの上位解法の自分用まとめ

GitHub - hedwig100/kaggle-shopee: kaggleのshopeeコンペのレポジトリ

↑自分のリポジトリ

1位

Shopee - Price Match Guarantee | Kaggle

  • モデルのスコアの伸びより, embeddingsを後処理した方がスコアが伸びた.
  • eca_nfnet_f1とbertをもちいてarcfaceをつかった
  • 大きいマージンの方が良かったが大きすぎると収束しなかったため, だんだんマージンを大きくした.
  • 最後の重みそうだけ学習率を大きくすると収束するようになったし, Cvもよくなった.
  • テキスト, 画像のみでそれぞれ類似度を測るのと, テキストと画像の類似度の和で類似度を測った.
  • Iterative Neighbor Blending(類似度の重みをつけた辺をはってグラフを作り, 類似度が近いもの同士が同じグループに分けられるように グラフを作り替える. -> またテキストと画像の類似度から近いものを見つける -> を繰り返す.) が効いた.
  • cutmixが0.1くらい効いた
  • augmentationはhorizontal flipしかしていない.

  • 後処理のINBが一番重要らしい.

3位

  • いい感じのモデルを使ってembeddingをつくって近傍をつくる.
  • そのembeddingsの距離や周りの点の密度などを特徴としてcatboostでpairwiseに同じ製品かどうか判定する.
  • つまり embeddings -> catboost -> 同じかどうか判定 ということをした.
  • embeddingを作るモデルをtriplet lossでfine tuningした.

4位

  • infoldなものもvalidation setとして用いた(leakしてるけど)
  • image,bert,tfidfをつかった
  • Query Expansionをした. これも近傍をグラフみたいに探索することらしい.

  • GeM = Generalized-mean poolingのことらしい.

5位

Shopee - Price Match Guarantee | Kaggle

6位

www.kaggle.com

  • imgとtextのfeatureをつくってからlinearしたのが効いた.
  • img,text,concatの三つのembeddingsをつかった
  • 一つではなくてかならず2つ以上は同じ商品だと判定するようにした.
  • 単位が合わないものは取り除いた.
  • 学習率をfcとbert(本体)で変えた.

  • 少なくとも2つは同じものが存在するは確かにってなった.

  • ことなる学習率を使うのは重要らしい.

8位

Shopee - Price Match Guarantee | Kaggle

  •  \alphaQEとDBAというものを使った.

18位

https://www.kaggle.com/c/shopee-product-matching/discussion/237972

  • 近傍の数の分布をtrainとtestで合わせるというところがなるほどとなった.

ほかにも読んだが長いので割愛.

感想

  • Bert,nfnetあたりは入賞者はほとんど全員使っていた.
  • 学習率の調整が必要なのは初めて知った.
  • post processが大事だった.
  • グラフみたいな構造に注目するのはたしかに正しかったが, 深く考えずに全結合にするだけでは意味がなかった.
  • クラスターみたいな構造に注目するのは大事だったらしい.
  • 同じ商品だと予測したものが一つもない時に2個目を見つけるのは重要だったっぽい.
  • QEとかDBAとかそういうことはぜんぜんdiscussionでは言われてなかった気がするけどそういう知識はどこから手に入れているんだろう.

Shopee参加記1

kaggleのshopeeのコンペに参加しました。このコンペで学んだことを書きたいと思います。コンペはJaneStreet, Ranzcrに引き続き, 3回目の挑戦でした。

Privateで1278位でした。

概要

Shopeeが持っている商品のデータから同じクラスに属する商品を予測するコンペでした。データとしては主に商品の画像とタイトルが与えられており , その二つを主に用いて同じクラスの商品を予測します。
あらかじめ与えられたクラスに分類するような問題はクラス分類ですが, ここではクラスは与えられていません。ラベルが同じものが近く, 異なるものが遠くなるように予測することが目的です。このように学習することを距離学習(Metric Learning)といいます。

CV

CVはlabelと画像をGroupとした, GroupKFold(K = 5)でした。画像が同じでもlabelが異なるものがあったため, 画像も考慮してGroupを作りました*1。 わりとCVとLBの相関は常に取れていました。solutionをチラッと見た感じ, data全体を使って学習させるとよかったと書いてあるものもあった*2ため, それもやってみてもよかったのかなと思いました。

自分が試した手法

ArcFace Loss

距離学習で用いられる手法でネットワーク自体は普通のクラス分類の場合と同じですが, lossを普通のcross_entropy()からArcfaceというlossを用います。ネットワークの出力を   x  \in \mathbb{R}^D として, クラスごとの重みを w \in \mathbb{R}^Cとします。これらをL2ノルムで正規化してから内積をとると \cos類似度がはかれますが, この類似度を xが属するクラスについては \cos{(\theta + m)}のように変えてからsoftmaxに入れます。

上記のようにすることで,  xが属するクラスについて他のクラスとの角度が m以上離れて, かつ \cos{(\theta + m)} が1に近づくように学習することになります。この mはマージンと呼ばれます。下の記事が詳しいです。

qiita.com

このlossを使うとモデルの中心部分は普通のクラス分類で用いたものを使うことができるのでたとえばEffcientnetやDensenetなどのpretrained modelの重みを使ってfine tuningすることができ, そのような手法を使いました。notebookやdiscussionを見る限り, わりと多くの参加者が使っていたと思います。

自分はeffcientnet_b3, effcientnet_b1, densenet_121, eca_nfnet_l0の4つを試しました。eca_nfnet_l0は自分で学習させるといろいろパラメータを変えてみてもlossがnanにしかならず学習させることができませんでした。ほかのかたのnotebookを見る限りnfnetはよいスコアを出せていたので自分で学習させられなかったのは悔しいところです。

それ以外は effcientnet_b1 < effcientnet_b3  \simeq densenet_121 という感じでした。effcientnet_b4,b5も試したかったのですが, timmのpretrained weightが見つからず, (どこにあるのかわからず)できませんでした...

Symmetric Loss

このコンペのラベルは少々noisyであることがdiscussionなどで報告されていました。よくわからないですが, e-commerceのデータはラベル付けがまちがっていることが多いかららしい(?)です。そのためnoisyなラベルを処理することが大事なのではないかと思いました。Cassavaコンペは出てはいませんでしたが, noisy labelだったらしく以下の記事を参考にしてやってみたのがSymmetric Lossでした。

Noisy label 対抗記~Cassava Leaf Disease Classification~ / Diary against the noisy label - Speaker Deck

Symmetric Lossは要するにCross Entropyのlabelが真の分布を表すことだけではなく, predictionもある程度真の分布を表すことを考慮したlossです。 普通のcross entropyとtargetとpredictionを逆にしたcross entropyの平均をとるような感じです。
これは少しCVが向上しました。

Tfidf

こちらは商品のタイトルの分類で使いました。tfidfでタイトルをベクトル化し, そのタイトルの \cos類似度を測りました。タイトルをみたところ絵文字が多いのでそれを除去したり, インドネシア語など様々な言語が含まれていたのでdiscussionにあったインドネシア語と英語を対応させたdictionaryを使って翻訳してから...とかやりましたが, ほとんどCVに寄与しませんでした...

いらない記号(+,-,!,?)や絵文字などを除去してから翻訳したものはすこしCVが上昇しましたが, LBは変わらずでした。

Word2vec

CVが全然良くなかったので採用しませんでした。英語やインドネシア語などその他いろいろな言語があったので, あまり役に立たなかったのではないかと思います。

Bert

bertはdiscussionやnotebookで紹介されていたので使ってみようと思い, 学習済みモデルのfine tuningをしようとしました。しかし, CVで全く精度がでませんでした。discussionを見ている限り多くの人がこれを使っていそうで, しかもtfidfだけよりも精度がでていたらしいのでこれをちゃんと学習させることはメダルを取るには必要だと感じました。

原因不明ですが, 英語の学習済みモデルを使っていたので多言語学習済みモデルを使えばよかったのかなと思います。英語の学習済みモデルで精度が出ている人がいるのだから, これの調節をすればうまく学習するはずだとおもっていたのが間違いで, いろいろな選択肢を試すのが先だったような気がします。

単位について

手元のtrain-validの予測で間違っていたものを確認していたのですが, わりとimageではこの二つの画像の差を見分けるのは(人間にも)無理そうなものがありました。これらはなぜ異なるラベルが付けられているのだろうと考えたところ, 微妙な機種や, サイズ(100gと200g)などの違いであることがタイトルとあわせて見ることでわかりました。

これをなんとか利用しようと, タイトルから単位部分を抽出してその数値を比較することで同じ単位で違う数字を持っているもの(15cmと20cmなど)は絶対に同じ商品としないとしました。これもCVで機能しませんでした。「絶対に同じにしない」だと強すぎるのかなと思いました。単位だけ取ってきたものでtfidfをして類似度を測るということもやってみましたが, それもうまくいきませんでした。

OCR

OCRで画像からテキスト情報を取り出し, その情報を利用する方法です。過去の同様なコンペで使われていたようです。しかし, これを使ってtfidfをしてみてまともに使えなかったので使用しませんでした。過去コンペのsolutionでも本やCDなどの形ではなく, テキスト情報のほうが判別に重要と考えられる画像について用いており, ただ使えばいいというものでもないのできちんとした意図があって使わないと意味がないのかなと思いました。

今回のコンペのsolutionでもあまり使われていなかったように思います。

全結合にしたい

AとBが同じ商品で, BとCが同じ商品ならAとCも同じ商品であるべきです。これはつまりAとBが同じ商品であるときにAとBの間に辺を貼ったようなグラフを考えると、これが完全グラフになるべきだということです。

そのためこのようにする後処理をしました。このためには類似度を測る閾値を少し小さめにして全結合にするということをすべきだと思いました。 閾値を調整しましたが, この後処理をしてもCV、LBともに向上しませんでした。

やれなかったもの

Siamese net

概念を理解する時間がなく, 公開notebookを一回動かしただけでほとんど何もできませんでした。

その他反省

この記事を書いていて気づいたのですが, いろいろな情報がdiscussionなどに流れている中, それをあまり活用し切れていないなと思いました。初期のころに取り組んだアプローチ(今回の場合はarcface loss, tfidfなど)に執着してしまい, そのアプローチの微調整などに力を入れてしまうことが多かったです. 確かにそうするとコードの管理などは楽になるのですが, 成長していないのであまりスコアも伸びません。

また, これもこの記事を書いていて気づいたことですが異なる手法に取り組んだとしてもそれがうまくいくまでやらないと意味がないのでそういう根気が必要だということを実感しました。

notebookやdiscussionを追って, 新しいアプローチを理解してその方法も自分のCVできちんと確かめるというサイクルを作ることでスコアも伸びやすくなるのかもしれないと思いました. notebookやdiscussionから流れてくる情報を把握して有用かどうか, きちんと確かめることをこれからのコンペでは意識したいと思いました。

上位のsolutionをみてより学びたいと思います。