🧩

数独と畳み込み深層学習

2023/10/16に公開

数独は、9x9の正方形の枠内に1から9までの数字を埋めるパズルゲームです。ただし、同じ数字が行と列の中で重複しないように配置する必要があります。このゲームは数学的に解かれるため、プログラミングを使用して解くことができますが、畳み込み層を持つニューラルネットワークがこのゲームを解くのに適しているのでしょうか?

このタスクは、k次元分類で、モデルは9x9の行列内の各位置にクラスを割り当てる必要があります。クラスは0から8までの数字で、数独の数字は1から9ですが、コンピュータで扱う数字は通常0から始まります。このタスクは、セグメンテーションのように、画像全体の上にピクセルごとにクラスを割り当てるタスクです。

最初のステップ

最初は通常の画像分類アプローチを使用しましたが、うまくいきませんでした。この問題を解決する方法が明確ではありませんでした。後で他の人のアプローチを学び、少し理解が進みました。

最も効率的な方法の1つは、モデルの出力が9x9x9次元のテンソルであることです。ただし、損失関数の問題が多く、モデルを使用できませんでした。私の場合、PyTorchのCrossEntropyLoss関数を使用しましたが、問題はコンピュータが0から数えるという事実でした。ターゲットテンソルは1から9の数字であったため、1を引いて、モデルと同じ0から8の数字で表現する必要がありました。

データ処理

このデータセットはKaggleから取得しました。100万の数独ゲームが含まれています。Kaggleではデータと共にCSVから行列に変換する方法が提供されており、非常に便利でした。最初はPyTorchのテンソルを直接生成するコードを変更しましたが、テンソルを作成する方法が非常に非効率的であることがわかったため、Numpyからテンソルに変換することにしました。

畳み込み層を使用する場合、入力データが[-1, -1]になるように学習しやすいため、すべての学習データを9で割り、0.5を引きます。これにより、すべてのデータが[-0.5, 0.5]の範囲に収まるようになります。ターゲットデータは1を引いて、クラスが0から8になるように正規化されます。

  1. データの分割: まず、トレーニングデータ、および検証データの2つにデータセットを分割します。これにより、モデルのトレーニング、ハイパーパラメータの調整、および性能の評価が可能になります。

  2. データ形状: 入力データは、次の形状を持つ4次元テンソルです。 [バッチサイズ、1、9、9]。このテンソルは、バッチ内の個々のデータポイントを表し、各データポイントには9x9の行列が含まれています。1はクラスを表すための次元です。モデルはこの行列を使用してクラス分類を行います。

  3. モデルの出力: モデルの出力は、次の形状を持つテンソルです。 [バッチサイズ、9、9、9]。このテンソルは、各データポイントに対して9x9の行列を生成します。この行列の各要素は、異なるクラス(9つのクラス)に対応しており、Softmax関数を適用することで確率分布を得ることができます。

  4. 損失関数とクラスの選択: モデルの出力テンソルを使用して、損失関数を計算します。この損失関数は通常、クロスエントロピーなどのもので、各データポイントに対する予測と実際のクラスラベルとの間の誤差を測定します。その後、Softmax関数により、各9x9行列の要素から最も高い確率のクラスを選択します。

要するに、このプロセスは、入力データをモデルに供給し、モデルは各データポイントに対してクラス分類を行い、その結果を評価し、最終的にモデルの性能を評価するためにデータを分割します。モデルはSoftmax関数を使用して、最も適切なクラスを予測します。

学習ループ

主なファイルにはすべてのプログラムがクラスとして含まれています。関数として設定されているのが重要で、変更する場合に便利です。メインの関数は学習ループを実行し、最も重要な部分はcomputeBatchLossという関数です。

損失関数

使用した関数はPyTorchで一般的に使用される関数です。CrossEntropyLossはロジットを入力として受け取り、その後SoftMax関数が適用され、最高の確率を持つクラスが選択されます。この場合、左端の9はクラスの次元数を表しており、SoftMaxを適用すると、その次元から最高確率の次元が選択され、9次元から1つ選択されます。

例えば、左上の位置[0,0]の場合、その9次元を調べて、2次元が最も高い確率を持つ場合、2次元が1の数字を表すため、出力[0,0]の位置には1が表示されます。

メトリクス

モデルの評価には損失だけでなく、他のメトリクスを使用することでより深い理解が得られます。一般的に使用されるメトリクスには、正確度、適合率、再現率、F1スコアなどがあります。

残念ながら、メトリクスの測定方法は完璧ではないため、このモデルの精度は実際よりも高くなっています。数独は最初からすべての数字が分かっているわけではなく、最初から20以上の数字がわかっています。しかし、これらの数字も精度に影響を与えます。より正確な結果が必要な場合、最初にわかっている数字が精度の測定時に影響を与えないように注意する必要があります。

たとえば、モデルがすべての予測を誤った場合でも、81から20以上の数字は正しくなります。そのため、モデルのベースライン正確度はほぼ25%です。

モデル

このプロジェクトの目的は、数独を解くために畳み込みニューラルネットワークを使用することでした。したがって、試したすべてのモデルは畳み込みモデルでした。

最も重要なのは最後の層で、すべてのモデルは最後にストライド1の畳み込み層を使用しています。この層により、出力は9x9x9次元になります。

このモデルでは次元を変更しないことが重要です。通常、画像分類の場合、畳み込み層を使用して次元を減らすことが一般的です。画像認識の出力テンソルは[バッチサイズ、クラスの数]の形状を持っており、次元を減らす必要があります。ただし、数独の場合は異なり、次元を変更せずにチャネルを追加するだけです。

最初は小さなモデルから始めましたが、結果は良好でした。しかし、さらなる精度向上が可能であると考え、段階的にモデルのパラメータ数と層数を増やしました。最も高い精度を達成したモデルは、11つの畳み込み層を使用し、そのうち6つの層は512チャネルを持っていました。

このモデルには約1800万のパラメータが含まれています。一般的に、パラメータ数を増やすと精度が向上しますが、より高いチャネル数は精度を下げる可能性があるため、512チャネルが最適であると言えます。

コード

コードは全部GitHubに登録された。
https://github.com/deeplearningcafe/CNN_Sudoku

Discussion