Minecraftのシード値から標高データを取得してcsv化する方法

背景（読み飛ばし可）

記事としては既存のMinecraftセーブデータから標高データを取得する以下の記事の続きとなります。

toa-hakobune.hatenablog.com

こちらの記事の方法だと既にセーブデータが存在するチャンクの標高データしか取得できません。それ以外の地点について現在のバージョンとシードで生成される地形の標高を取得できれば、任意の場所の標高データを取得できることになります。

※逆に、今回紹介する方法だけでは別バージョンで既に生成された地形部分の標高データが取得できないため、これら二つの方法は組み合わせて利用する必要があります。

cubiomesを利用した標高データ取得

seed mapについて

単に自分がプレイしているMinecraftのバージョンとシード値における地形を調べたいだけであれば、seed mapと呼ばれるマップを生成してくれる以下のようなサイトを利用すれば簡単です。

mcseedmap.net

今回は標高データをプログラムから読み込めるデータ形式で取得することが目的であるため、上のサイトが利用している以下のcubiomeライブラリを利用していきます。

github.com

Google Colaboratoryにおけるデータ生成コード

注意点：cubiomeの都合上、以下で(x,y)に対して生成した標高データは実際は(4x,4z)に対する標高データとなります

cubiomeはC言語で書かれたライブラリであるため、まずは環境整備をしたうえでビルドします。

# 環境整備
!apt-get update
!apt-get install -y gcc g++ make git

# ライブラリビルド
!git clone https://github.com/Cubitect/cubiomes.git
%cd cubiomes
!make libcubiomes

そして以下のようなコードを書きます。

%%writefile gen_map.c
#include "generator.h"
#include "biomes.h"
#include "biomenoise.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    if (argc != 5)
    {
        fprintf(stderr, "利用方法: %s x_min x_max z_min z_max\n", argv[0]);
        return 1;
    }

    int x_min = atoi(argv[1]);
    int x_max = atoi(argv[2]);
    int z_min = atoi(argv[3]);
    int z_max = atoi(argv[4]);

    Generator g;
    // MC_1_20などのバージョンの名前はbiomes.hに一覧がある
    setupGenerator(&g, MC_1_20, LARGE_BIOMES);
    
    uint64_t seed = 7249427650172604303;
    applySeed(&g, DIM_OVERWORLD, seed);

    SurfaceNoise sn;
    initSurfaceNoise(&sn, DIM_OVERWORLD, seed);

    float height;
    int biomeID;

    for (int x=x_min; x<=x_max; x++)
    {
        fprintf(stderr, "現在の処理座標 x = %d\n", x);

        for (int z=z_min; z<=z_max; z++)
        {
            // x,zにおける標高を取得 x,zについてはスケールが1/4になっている点に注意
            mapApproxHeight(&height, &biomeID, &g, &sn, x, z, 1, 1);

            if (z==z_min)
                printf("%.1f", height);
            else
                printf(",%.1f", height);
        }
        printf("\n");
    }

    return 0;
}

このコードは標高データをcsv形式で標準出力に書き出す仕組みになっているので、ビルドして以下のように利用できます。

!gcc gen_map.c libcubiomes.a -fwrapv -lm
!./a.out -1000 1000 -1000 1000 > output.csv

得られたcsvファイルを可視化すると以下のようになります。

生成された標高データ

MinecraftのセーブデータからPythonで標高データを取得する方法

こんなことをやろうとした背景（読み飛ばし可）

割とのんびりMinecraftをプレイしているのですが、調子に乗ってラージバイオームを選択してしまったばかりに最寄りのジャングルバイオームが数千ブロック先にあることがわかりました。せっかくなのでこの際、数千ブロック先まで鉄道を敷設してしまおうということで、Pythonで最適経路を探索するための下準備として地形データを読み込む必要が出てきたのがこの記事の背景です。

Minecraftの地形データ取得

ブロックの情報が保存されているmcaファイルについて

バージョン1.20時点で、Minecraftの地形（正確にはブロックなどの情報を含むチャンク）データはワールドの保存先フォルダ以下の region フォルダ以下に保存されています。

このフォルダ以下には r.0.0.mca というような名前の mcaファイル が複数格納されているはずです。ファイル名における数字の部分は r.{x座標idx}.{z座標idx}.mca のようにそのmcaファイルに対応する位置（絶対座標ではない）を示しています。（Minecraftではx,z軸が水平面上にあり、y軸が鉛直方向にあります。）各mcaファイルには 32x32 チャンクの情報が保存されており、 各チャンクは 16x16 ブロックに対応しているので結果的に一つのmcaファイルには 512x512 ブロックの情報が格納されていることになります。

mcaファイルへのアクセス方法

Pythonからmcaファイルを読み込むために、anvilモジュールを利用します。（こちらは有志の方が開発を継続しているフォーク版です。）

Pipを使ってインストールができます。

pip install anvil-parser2

このモジュールを用いると、チャンクのある座標のブロック情報を以下のように取得できます。

import anvil
import anvil.errors

# mcaファイル名
region_fn = "r.0.0.mca"

# mcaファイル中の対象チャンクの位置 [0,32)
chunk_x = 10
chunk_z = 4

# チャンクの読み込み
# 存在しなければ anvil.errors.ChunkNotFound エラー
chunk = anvil.Chunk.from_region(region_fn, chunk_x, chunk_z)

# チャンク中での相対位置 [0,16)
x = 2
y = 30
z = 4

# ブロック情報の取得
# 範囲外の座標を指定すると anvil.errors.OutOfBoundsCoordinates エラー
block = chunk.get_block(x, y, z)
print(block.id) # "water", "air"など

地形データ取得コード

以上の方法を使えば、セーブデータ上の任意の位置のブロック情報を取得することができます。以下のプログラムは、上空（y=256）から一つずつ高度を下げていき、最初に見つかった地表ブロック（空気、水、植物以外）の高度を取得するプログラムです。

下の方に貼った可視化ツールと組み合わせると、以下のような地形データを得ることができます。

Minecraftセーブデータの地形図

※とりあえず動くものを作ったというだけなので、並列処理を導入してはいるものの結構遅いです。私の環境では、2000x2000くらいのワールドで数十分ほどかかりました。

※ブロックIDなどについては網羅的に調べているわけではないので、コード中のリストには不足・不要な部分があるかもしれません。適宜調整しつつ自己責任で利用をお願いします。

import multiprocessing as mp
import os
import pickle
import re

import anvil
import anvil.errors
import numpy as np
from tqdm import tqdm

def get_region_coordinates(directory):
    """
    あるregionディレクトリ以下にあるmcaファイルの座標リストを取得する
    """
    # 正規表現で x, z の座標を抽出
    pattern = re.compile(r"r\.(-?\d+)\.(-?\d+)\.mca$")
    coordinates = []

    # ディレクトリを再帰的に探索
    for root, _, files in os.walk(directory):
        for file in files:
            match = pattern.match(file)
            if match:
                x = int(match.group(1))
                z = int(match.group(2))
                coordinates.append((x, z))

    return coordinates


# 植物ブロック（リストは不完全かもしれません）
plant_blocks = {
    "oak_sapling",
    "spruce_sapling",
    "birch_sapling",
    "jungle_sapling",
    "acacia_sapling",
    "dark_oak_sapling",
    "oak_leaves",
    "spruce_leaves",
    "birch_leaves",
    "jungle_leaves",
    "acacia_leaves",
    "dark_oak_leaves",
    "dead_bush",
    "tall_grass",
    "fern",
    "wheat",
    "cactus",
    "sugar_canes",
    "pumpkin",
    "melon_block",
    "pumpkin_stem",
    "melon_stem",
    "vine",
    "lily_pad",
    "nether_wart",
    "beetroots",
    "chorus_flower",
    "chorus_plant",
    "double_plant",
    "sunflower",
    "lilac",
    "double_tallgrass",
    "large_fern",
    "rose_bush",
    "peony",
    "brown_mushroom",
    "red_mushroom",
    "brown_mushroom_block",
    "red_mushroom_block",
    "hay_block",
    "flower_pot",
    "carrots",
    "potatoes",
    "bamboo",
    "dandelion",
    "grass",
}
water_blocks = {"water", "kelp", "bubble_column"}


def get_highest_ground_blocks_region(region_fn):
    block_ids = set()
    blocks = {}
    is_water_map = {}
    with tqdm(total=32 * 32) as pbar:
        for chunk_x in range(32):
            for chunk_z in range(32):
                try:
                    chunk = anvil.Chunk.from_region(region_fn, chunk_x, chunk_z)
                except anvil.errors.ChunkNotFound:
                    continue
                offset_x = chunk_x * 16
                offset_z = chunk_z * 16

                for x in range(16):
                    for z in range(16):
                        y = 256
                        is_water = False
                        while True:
                            try:
                                block = chunk.get_block(x, y, z)
                            except anvil.errors.OutOfBoundsCoordinates:
                                if y == 256:
                                    # (x,z)が範囲外
                                    break
                                else:
                                    # yが範囲外
                                    blocks[x + offset_x, z + offset_z] = (y, "null")
                                    is_water_map[x + offset_x, z + offset_z] = False
                                    break

                            if block.id in water_blocks:
                                is_water = True
                                y -= 1
                                continue

                            if (
                                block.id in {"air", "cave_air"}
                                or block.id in plant_blocks
                                or "seagrass" in block.id
                                or "log" in block.id
                            ):
                                y -= 1
                                continue
                            blocks[x + offset_x, z + offset_z] = (y, block.id)
                            block_ids.add(block.id)
                            is_water_map[x + offset_x, z + offset_z] = is_water

                            break

                pbar.update()
    print(block_ids)
    return blocks, is_water_map


def func_process(args):
    region_fn, meta = args
    return get_highest_ground_blocks_region(region_fn), meta


if __name__ == "__main__":
    region_dirname = "path/to/save_directory/region"
    save_fn = "surface_map2.pickle"

    region_coords = get_region_coordinates(region_dirname)
    print(region_coords)
    region_coords = np.array(region_coords)

    region_x_min = np.min(region_coords[:, 0])
    region_x_max = np.max(region_coords[:, 0]) + 1
    region_z_min = np.min(region_coords[:, 1])
    region_z_max = np.max(region_coords[:, 1]) + 1

    print(region_x_min, region_x_max, region_z_min, region_z_max)

    height_map = np.zeros(
        (
            (region_x_max - region_x_min) * 16 * 32,
            (region_z_max - region_z_min) * 16 * 32,
        ),
        dtype=np.int16,
    )
    is_water_map = (
        np.ones(
            (
                (region_x_max - region_x_min) * 16 * 32,
                (region_z_max - region_z_min) * 16 * 32,
            ),
            dtype=np.int8,
        )
        * -1
    )
    surface_block_map = {}

    def fn_generator():
        for region_x, region_z in tqdm(region_coords, desc="Regions"):
            yield (
                f"{region_dirname}\\r.{region_x}.{region_z}.mca",
                (region_x, region_z),
            )

    with mp.Pool(mp.cpu_count() - 1) as pool:
        for (heights, is_water), (region_x, region_z) in pool.imap_unordered(
            func_process, fn_generator()
        ):
            for (raw_x, raw_z), (y, block_id) in heights.items():
                x = raw_x + 16 * 32 * (region_x - region_x_min)
                z = raw_z + 16 * 32 * (region_z - region_z_min)

                height_map[x, z] = y
                is_water_map[x, z] = int(is_water[raw_x, raw_z])
                surface_block_map[x, z] = block_id

    with open(save_fn, "wb") as h:
        pickle.dump(
            (
                (region_x_min, region_x_max, region_z_min, region_z_max),
                height_map,
                is_water_map,
                surface_block_map,
            ),
            h,
        )

可視化コード

出力された地形データを可視化するコードです。

※こちらも自己責任でご使用ください。

import matplotlib.pyplot as plt
import numpy as np
import pickle
from matplotlib.patches import Patch
from matplotlib.colors import ListedColormap

with open("surface_map.pickle", "rb") as h:
    (region_x_min, region_x_max, region_z_min, region_z_max), height_map, is_water_map, surface_block_map = pickle.load(h)

# X軸を垂直下向き、Z軸を水平右向きにするために、配列を調整
height_map_rotated = np.rot90(height_map, k=1)
is_water_map_rotated = np.rot90(is_water_map, k=1)
height_map_flipped = np.flipud(height_map_rotated)
is_water_map_flipped = np.flipud(is_water_map_rotated)

fig, ax = plt.subplots(figsize=(10, 10))

cax = ax.imshow(height_map_flipped, cmap='terrain', interpolation='nearest')

# カラーバーを追加
cbar = fig.colorbar(cax, ax=ax, label='Height (Y)')
cbar.set_label('Height (Y)')

# 上下反転させた水の部分（is_water_map == 1）を青色の斜線で重ねて表示
water_overlay = np.zeros_like(is_water_map_flipped, dtype=float)
water_overlay[is_water_map_flipped == 1] = 1  # is_water_mapが1の部分にマスクを作成

cmap = ListedColormap(['none', 'blue'])

# alpha=0.5で透明度を調整
ax.imshow(water_overlay, cmap=cmap, interpolation='nearest', alpha=0.5)

# 座標のオフセットをtickに反映
x_ticks = np.arange(0, height_map_flipped.shape[1], 16 * 32)
x_tick_labels = (x_ticks + region_z_min * 16 * 32).astype(int)

y_ticks = np.arange(0, height_map_flipped.shape[0], 16 * 32)
y_tick_labels = (y_ticks + region_x_min * 16 * 32).astype(int)

ax.set_xticks(x_ticks)
ax.set_xticklabels(x_tick_labels)
ax.set_yticks(y_ticks)
ax.set_yticklabels(y_tick_labels)

ax.set_title("Minecraft Height Map with Water Overlay (Flipped, Rotated, and Offset)")
ax.set_xlabel("Z-axis (Right)")
ax.set_ylabel("X-axis (Down)")

legend_elements = [Patch(facecolor='blue', edgecolor='blue', label='Water Area', alpha=0.5)]
ax.legend(handles=legend_elements, loc='upper right')

plt.show()

ペアワイズな評価を用いたLLM性能比較：Bradley-Terryモデルとモデルペア動的サンプリング

機械学習 自然言語処理

はじめに

大規模言語モデル （LLM）の性能評価を行う際に、「モデルAとモデルBのどちらの出力の方が望ましいか？」というペアワイズな評価を収集してモデルの性能を比較することが増えています。
その代表例はChatbot Arena (https://huggingface.co/spaces/lmsys/chatbot-arena-leaderboard)ですが、今回は彼らの取り組みを紹介する以下の論文[Chiang+24]を読んで、どのようにユーザーによってアノテーションされたペアワイズな評価結果からモデルごとのスコアが計算されているのかを勉強してみました。

arxiv.org

定式化

M個のモデルを比較する状況を考えます。今回はペアワイズな評価を行うので、全てのユニークなモデルペアの集合

\mathcal{A}=\left\{ (m,m') : m \lt m' \text{ and } m,m'\in\{1,...,M\} \right\}

を定義します。

評価プロセスが始まると、各時刻 t ごとにユーザーに対してモデルペア A_t\in \mathcal{A} が何らかの確率分布 P_t(A_t) に従って選ばれ提示されます。

そして人間は提示されたペア A_t=(A_{t1}, A_{t2})のモデルが生成した出力を比較し、どちらが良かったかのアノテーション H_t \in \{0,1\} を付与します。 A_{t2}の方が良かった場合は H_t=1であり、 A_{t1}の方が良かった場合は H_t=0です。

モデルスコアの計算

Bradley-Terryモデル

モデル mに対するスコア \xi_mという概念を導入し、このスコアが高いモデルほどペアワイズな評価で勝利しやすいというモデル化を行います。

論文中で採用されているBradley-Terryモデル[Bradley+52]は、あるモデルペアが与えられたときに片方が勝利する確率、すなわちモデルペア A=(A_1,A_2) に対して H=1となる（ A_2が勝つ）確率を以下のように定義します。

\mathbb{P}(H=1)=\frac{1}{1+e^{\xi_{A_1}-\xi_{A_2}}}

このモデルを実際の Hの分布に対してフィッティングすることで、パラメータであるスコア \xiを推定できます。最小化する損失関数 \mathcal{L}は以下の通りです。（ここでは、モデルペア Aに対しては \mathcal{A}からの一様分布を仮定していることに注意してください。）

\displaystyle \mathcal{L}(\xi) = \underset{ \substack{A\sim \text{Uniform}(\mathcal{A}) \\ H\sim \mathbb{P}(H|A)} }{\mathbb{E}} \left[ l\left(H, \frac{1}{1+e^{\xi_{A_1}-\xi_{A_2}}}\right) \right]

ここで、 l(h,p)は以下のクロスエントロピー損失です。

l(h,p)=-(h\log p - (1-h)\log (1-p))

実装

上の損失関数の最小化は、ロジスティック回帰の実装を利用することで簡単に実装することができます。

アノテーション結果 \{ (A_t, H_t) \}_tが得られている時、 (T\times M)の特徴量行列 X_{tm}を作成し、 X_{tA_{t2}}=1および X_{tA_{t1}}=-1、それ以外のモデル mに対しては X_{tm}=0とします。

この特徴量 X_{tm}から H_tを予測するロジスティック回帰モデルをバイアス無しの設定で学習すれば、パラメータとして所望の \xi_mが得られます。

scikit-learnの実装を利用するなら、例えば以下のようになります。

from sklearn.linear_model import LogisticRegression

model = LogisticRegression(fit_intercept=False) # fit_intercept=False: バイアス無し
model.fit(X, H)

xi = model.coef_[0]

実際のサンプル分布への補正

実際にはモデルペアは時刻 t ごとに異なる分布 P_t(A_t) に従ってサンプルされます。この影響を補正するため、重点サンプリングと同様の考え方を使って（3行目）以下のように変形します。

\displaystyle \begin{align} \mathcal{L}(\xi) &= \underset{ \substack{A\sim \text{Uniform}(\mathcal{A}) \\ H\sim \mathbb{P}(H|A)} }{\mathbb{E}} \left[ l\left(H, \frac{1}{1+e^{\xi_{A_1}-\xi_{A_2}}}\right) \right] \\ &=\frac{1}{T} \sum_{t=1}^{T} \underset{ \substack{A_t\sim \text{Uniform}(\mathcal{A}) \\ H_t\sim \mathbb{P}(H_t|A_t)} }{\mathbb{E}} \left[ l\left(H_t, \frac{1}{1+e^{\xi_{A_{t1}}-\xi_{A_{t2}}}}\right) \right] \\ &=\frac{1}{T} \sum_{t=1}^{T}\underset{ \substack{A_t\sim P_t(A_t) \\ H_t\sim \mathbb{P}(H_t|A_t)} }{\mathbb{E}} \left[ \frac{1}{|\mathcal{A}|P_t(A_t)} l\left(H_t, \frac{1}{1+e^{\xi_{A_{t1}}-\xi_{A_{t2}}}}\right) \right] \\ &= \frac{1}{T|\mathcal{A}|} \sum_{t=1}^{T}\underset{ \substack{A_t\sim P_t(A_t) \\ H_t\sim \mathbb{P}(H_t|A_t)} }{\mathbb{E}} \left[ \frac{1}{P_t(A_t)} l\left(H_t, \frac{1}{1+e^{\xi_{A_{t1}}-\xi_{A_{t2}}}}\right) \right] \end{align}

以上の結果から、 P_t(A_t)を用いてサンプルされたモデルペアに対するアノテーション集合 \mathcal{D}=\{ (A_t, H_t) \}_tを用いて、論文中の式(7)に相当する以下の式に従って \xiを推定すればよいことがわかります。

\displaystyle \xi^* = \underset{\xi}{\text{argmin}}\sum_{(A_t, H_t)\in\mathcal{D}}\frac{1}{P_t(A_t)}l\left(H_t, \frac{1}{1+e^{\xi_{A_{t1}}-\xi_{A_{t2}}}}\right)

スコアの信頼区間の推定

論文にはpivot bootstrapと"sandwich" robust standard errorsをそれぞれ用いて信頼区間の計算を行っていると書かれていました。Appendix Aによると、これらの手法で得られた信頼区間はどちらも同程度の品質であったようです。

これらの手法が具体的にどういった方法を指すのかは論文では割愛されていたので現在調査中ですが、pivot bootstrapは検索してもあまりはっきりとした定義がヒットしないなどやや難航中です。

そこで、ここではChatbot Arenaのチームが公開している以下のノートブック[Chatbot Arena 24]で実装されている信頼区間の計算方法を追ってみたいと思います。

信頼区間の計算方法はいくつか実装されていますが、モデルペアを一様にサンプルした状況を仮定した場合のbootstrap信頼区間の計算は以下の通りです[Chatbot Arena 24]。

※ここで、彼らは重点サンプルの重み \frac{1}{P_t(A_t)}をかける代わりに、モデルペアごとに同じ数をサンプルすることで一様分布への補正を行っているようです。

def sample_battle_even(battles, n_per_battle):
    groups = battles.groupby(["model_a", "model_b"], as_index=False)
    resampled = (groups
                 .apply(lambda grp: grp.sample(n_per_battle, replace=True))
                 .reset_index(drop=True))
    return resampled

# Sampling Battles Evenly
def get_bootstrap_even_sample(battles, n_per_battle, func_compute_elo, num_round=BOOTSTRAP_ROUNDS):
    rows = []
    for n in tqdm(range(num_round), desc="sampling battles evenly"):
        resampled = sample_battle_even(battles, n_per_battle)
        rows.append(func_compute_elo(resampled))
    df = pd.DataFrame(rows)
    return df[df.median().sort_values(ascending=False).index]

シンプルにモデルペアごとに固定個（ノートブックでは50個）のアノテーションを復元サンプルし、得られたアノテーション集合を使ってモデルスコア（ここではEloスコア）を推定しています。この処理を指定回数（ノートブックでは100回）繰り返すと、モデルスコアの分布を得ることができます。ノートブックではこの分布の2.5%分位点から97.5%分位点までが信頼区間として図示されていました。

モデルペアの動的サンプリング

より効率的に人手評価のアノテーションを収集するため、モデルペアの分布 P_t(A_t) は情報が不足しているようなモデルペアが優先してサンプルされるように設計します。以下では、論文で紹介されていたwin rateの推定のばらつきが小さくなるようにモデルペアをサンプルする方法を紹介します。

まず、あるモデルペア a に関するwin rate（ a_2 が a_1 に勝つ確率） \theta^*(a)について考えます。

\displaystyle \begin{align} \theta^*(a)&=\underset{H_t\sim \mathbb{P}(H_t|A_t=a)}{\mathbb{E}}[H_t] \\ &= \underset{\substack{A_t\sim P_t(A_t) \\ H_t\sim \mathbb{P}(H_t|A_t)}}{\mathbb{E}} \left[ \frac{1}{P_t(A_t)}H_t \mathbb{1} [A_t=a] \right] \end{align}

のように変換できるので、 X_{ta}=\frac{1}{P_t(A_t)}H_t \mathbb{1} [A_t=a] のように定義すると、 \hat{\theta}_a^{(T)}=\frac{1}{T}\sum_{t=1}^{T}X_{ta}は \theta^*(a)の不偏推定量であることがわかります。

この X_{ta}の共分散行列 \hat\Sigma^{(T)}を以下のように求めます。

\displaystyle \Sigma^{(T)}=\frac{1}{T}\sum_{t=1}^T(X_t-\hat\theta^{(T)})(X_t-\hat\theta^{(T)})^T

この共分散行列を用いて、新しくアノテーションを増やすことでwin rateの推定のばらつきが小さくなるようなモデルペア aを優先してサンプルする分布を P_t(a)として利用します。

P_t(a)\propto \sqrt{\frac{\hat\Sigma_{a,a}^{(T)}}{|\{t: A_t=a\}|}} - \sqrt{\frac{\hat\Sigma_{a,a}^{(T)}}{|\{t: A_t=a\}|+1}}

その他

論文にはこのほかにもrankingの計算方法や、アノテーションの品質が悪い外れ値的なユーザーを検知する方法についても述べられていました。今回の記事では省略してしまいましたが、興味がある方は論文の方をご参照ください。

参考文献

[Bradley+52] Bradley, Ralph Allan, and Milton E. Terry. "Rank analysis of incomplete block designs: I. The method of paired comparisons." Biometrika 39.3/4 (1952): 324-345.
[Chatbot Arena 24] "Chatbot Arena: MLE Elo Rating (Bradley-Terry model) Calculation (March 13, 2024)." Google Colab, Accessed 17 Mar. 2024, https://colab.research.google.com/drive/1KdwokPjirkTmpO_P1WByFNFiqxWQquwH#scrollTo=mSizG3Pzglte.
[Chiang+24] Chiang, Wei-Lin, et al. "Chatbot arena: An open platform for evaluating LLMs by human preference." arXiv preprint arXiv:2403.04132 (2024).

少ない画像データでGANを学習する ~Data-Efficient GANs with DiffAutment~

機械学習 画像処理

以下のレポジトリに公開されているコードを用いて数百枚程度の少ない画像でGANを学習できたので、二番煎じ感がありますが備忘録がてら手順を記事にしておきます。

github.com

環境

学習手順

以下では上記レポジトリをcloneしてある状態を仮定しています。

Dockerイメージの作成：

cd data-efficient-gans/DiffAugment-stylegan2-pytorch
sudo docker build -t stylegan:0.0 .

訓練データの作成：

解像度が512の画像データセットの場合です。

※いろいろオプションがあるようなので、helpも確認してみるといいかもしれません。

# data-efficient-gans/DiffAugment-stylegan2-pytorch以下で
python dataset_tool.py --source <訓練画像が含まれるディレクトリ> --dest dataset_name.zip --width 512 --height 512

訓練：

学習にまとまった時間がかかることを考えてバックグラウンドで学習を回したかったため、以下のようなシェルスクリプトを書きました。(以下ではrun_background.shという名前で作成したと仮定。)

#!/bin/bash

cd /stylegan
python -u train.py \
    --outdir=output_directory_name --data=dataset_name.zip --gpus 1 \
    --kimg 25000 --mirror True --gamma 1 --batch 64 1>out.out 2>&1

続いてdockerコンテナをバックグラウンドで起動して実行します。

sudo docker run -d --gpus all -v <DiffAugment-stylegan2-pytorchの絶対パス>:/stylegan \
    --shm-size=16g stylegan:0.0 bash -c "/stylegan/run_background.sh"

学習コードの標準出力は data-efficient-gans/DiffAugment-stylegan2-pytorch以下のout.outに、学習済みの重みファイルなどはoutput_directory_name以下に出力されます。

gradient accumulationについて：

上の例ではバッチサイズを64にしていますが、解像度512の画像ではGPUメモリが足りずに1ステップでは処理できません。そこでgradient accumulationを利用したいのですが、デフォルトの学習コードではaccumulation stepを外部から明示的に指定できるようにはなっていませんでした。

そこで訓練コードの一部を以下のように修正することで対応します。

# 旧：args.batch_gpu = batch // gpus を以下のように変更
args.batch_gpu = 8 # こちらの数値はお好みで

ハイパーパラメータについて

主に変更することになるハイパーパラメータは、学習の長さ（利用するのべ画像枚数）であるkimgと、正則化係数gamma、バッチサイズbatch（以下のデフォルト値の辞書ではmbが相当）あたりになるかと思います。

king, gammaについてはデータセットや画像の解像度によって望ましい値が異なるようですが、学習コードのデフォルト値が参考になるかもしれません。

※ちなみに上で紹介した学習実行例でのパラメータ設定は、私が1000枚程度で解像度が512の画像データセットで学習を行った際のものです。

自動着色データセット作成のためのイラストの線画+ベタ塗り化

機械学習 画像処理 イラスト

最近自由研究でイラストの自動着色システムを開発しようと試行錯誤しています。 その過程で訓練データ用の線画やベタ塗りを抽出するコードを実装したので、メモ書きがてらご紹介したいと思います。

以下の前者のイラストを後者のような線画＋ベタ塗りのイラストに変換することが目的です。

線画抽出

まずはイラストから線画部分を抽出します。

自動着色に関する既存研究[Ci et al.,2018; Hati et al.,2019]では、データセット作成のためにXDoG [Winnemöller et al.,2012]と呼ばれるエッジ抽出フィルターを用いて着色済みのイラストから線画を人工的に生成していました。 これに倣い、今回の取り組みでもこのフィルターを使って線画を抽出しました。

XDoGフィルター

詳細な説明は論文や解説記事を見ていただくとして、ここでは論文や解説記事を参考にしたPython実装を共有します。デフォルト値は線画着色の論文で利用されていた値です。sigmaに関しては0.3, 0.4, 0.5の中からランダムに選ぶようです。

import cv2
import numpy as np

def XDoG(img, sigma, tau=0.95, k=4.5, phi=1e9, epsilon=0):
    """
    OpenCVの画像に対してXDoGフィルターを適用する。
    """
    img = np.repeat(np.mean(img, axis=2, keepdims=True), 3, axis=2)
    g_sigma = cv2.GaussianBlur(img, (0, 0), sigma)
    g_ksigma = cv2.GaussianBlur(img, (0, 0), k * sigma)
    d = g_sigma - tau * g_ksigma
    print(d.shape)
    t = np.where(
        d >= epsilon,
        np.array([255]),
        255*(1+np.tanh(phi*(d-epsilon)))
    )
    print(t.shape)
    t = t.clip(0.0, 255.0)
    return t.astype(np.uint8)

実際にこのフィルターをイラストに適用してみると、きちんと以下のように線画らしいものが取り出せていることが確認できます。

f:id:ronwall1701:20210503203111p:plain

ベタ塗り抽出

続いて完成品のイラストからベタ塗り状態のイラストを抽出する必要があります。シンプルにイラストの各領域ごとに色を平均してしまえば良さそうですが、この領域をどうやって抽出するのかという問題があります。

実はこのイラストからの領域抽出にはDanbooRegion [Zhang et al.,2020]という既存研究があり、以下のレポジトリにデータセット、ソースコード、事前学習済みモデルなどが公開されています。この手法はイラストの領域をスケルトンマップの形で表現し、イラスト→スケルトンマップの変換を学習することによりイラスト上の領域を抽出します。

github.com

pix2pixHDの学習

私の環境ではなぜか事前学習済みモデルがきちんと動かなかったので、image-to-image translationモデルであるpix2pixHD [Wang et al.,2018]を用いてこのスケルトンマップへの変換を学習しました。

PyTorch実装がgithubに公開されているので、そちらを利用させていただくことにします。‘

github.com

Anacondaを用いた環境構築は以下のように実行しました。

conda create -n pix2pixhd python=3.7
conda activate pix2pixhd
conda install pytorch torchvision torchaudio cudatoolkit=11.1 -c pytorch -c nvidia
pip install dominate scipy==1.2.0

git clone https://github.com/NVIDIA/apex
cd apex
pip install -v --disable-pip-version-check --no-cache-dir --global-option="--cpp_ext" --global-option="--cuda_ext" ./

学習のためには自作データセット用に新しくディレクトリを作成し、その中にtrain_A, train_Bというそれぞれ変換前、変換後の画像を含むディレクトリを作成する必要があります。画像の名前は並べ替えたときにペアとなる画像が同じ順序になるようにすれば良さそうでした。今回はDanbooRegionデータセットのイラストを変換前画像に、スケルトンマップを変換後画像にします。

以上の準備の後、以下を実行すると学習が実行されます。DanbooRegionはデータセット用に作ったディレクトリです。特にvalidationなどはしてくれないのですが、今回のケースでは1-3エポック程度でそれらしい結果になったのでえいやで学習を打ち切ってしまいました。

python -m torch.distributed.launch train.py --name train_danboo_region --label_nc 0 --dataroot DanbooRegion --tf_log --no_instance --fp16 --resize_or_crop none

イラスト→スケルトンマップ→ベタ塗り　の変換

上の手順で学習したpix2pixHDモデルを使ってスケルトンマップを作るラッパークラスと、スケルトンマップを用いてイラストをベタ塗り化するコードを以下で公開しました。

pix2pixHDモデルのラッパークラス: https://gist.github.com/kosuke1701/4e2ac722bb0c4af9cbf9acfec3d91c3f

イラストベタ塗り化コード: https://gist.github.com/kosuke1701/6874ec7e10090ea9a59ba655b5905bc6

以上のコードを使って実際にイラストからベタ塗りを抽出してみた結果が以下になります。多少おかしいところもありますが、おおむね良くベタ塗りが抽出できていることがわかります。

f:id:ronwall1701:20210506080030p:plain
左からオリジナル画像、スケルトンマップ、ベタ塗り化された画像

参考文献

[Ci et al.,2018] Ci, Yuanzheng, et al. "User-guided deep anime line art colorization with conditional adversarial networks." Proceedings of the 26th ACM international conference on Multimedia. 2018.

[Hati et al.,2019] Hati, Yliess, et al. "PaintsTorch: a User-Guided Anime Line Art Colorization Tool with Double Generator Conditional Adversarial Network." European Conference on Visual Media Production. 2019.

[Wang et al.,2018] Wang, Ting-Chun, et al. "High-Resolution Image Synthesis and Semantic Manipulation with Conditional GANs." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018.

[Winnemöller et al.,2012] Winnemöller, Holger, Jan Eric Kyprianidis, and Sven C. Olsen. "Xdog: an extended difference-of-gaussians compendium including advanced image stylization." Computers & Graphics 36.6 (2012): 740-753.

[Zhang et al.,2020] Zhang, Lvmin, et al. "DanbooRegion: An Illustration Region Dataset." European Conference on Computer Vision (ECCV). 2020.

AutoPhraseのセグメント結果を用いた分かち書きを行う

自然言語処理

以前別の記事でAutoPhraseによりコーパスからキーワード抽出を行う方法を紹介しました。

今回は以下の例のように、AutoPhraseによって用語（キーワード）位置にアノテーションがなされたテキストから用語が１単語となるよう分かち書きを行う方法について紹介します。

入力例：

私は<phrase>ぽんぽんぺいんコーポレーション</phrase>に属しています。

出力例：

["私", "は", "ぽんぽんぺいんコーポレーション", "に", "属し", "て", "い", "ます", "。"]

mecabのインストール

分かち書きを行うエンジンにはMecabを利用します。辞書を含めたインストール手順は以下の通りです。

sudo apt install mecab
sudo apt install libmecab-dev
sudo apt install mecab-ipadic-utf8

git clone --depth 1 https://github.com/neologd/mecab-ipadic-neologd.git
# 辞書更新時はここから
cd mecab-ipadic-neologd
./bin/install-mecab-ipadic-neologd -n -a

pip install mecab-python

セグメントタグの辞書への登録

続いてMecabのユーザー辞書追加機能を用いて、セグメントタグである<phrase>や</phrase>が分かち書きされないように登録します。方法は以下の記事を参考にしました。

UbuntuでMeCabのユーザ辞書に単語を追加してPythonで使えるようにする - Qiita

まずは以下のようなcsvファイルを作成します。(仮にphrase_dict.csvとします。)

<phrase>,,,1,名詞,一般,*,*,*,*,<phrase>,フレーズ,フレーズ,追加エントリ
</phrase>,,,1,名詞,一般,*,*,*,*,</phrase>,フレーズ,フレーズ,追加エントリ

続いて先ほどMecabインストール時にダウンロードしたシステム辞書のパス(/usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd)と辞書の出力先パス(仮にdict/phrase.dic)を指定して以下のように辞書を作成します。

sudo /usr/lib/mecab/mecab-dict-index -d /usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd -u dict/phrase.dic -f utf-8 -t utf-8 phrase_dict.csv

分かち書きの実行

以上で環境の準備は完了です。最後にMecabによる分かち書き結果とAutoPhraseによる用語アノテーションを用いて分かち書きを行います。

以下のスクリプトを実行すると、出力先ファイルの各行に各文の分かち書き結果のリストが出力されます。（jsonモジュールを用いて出力したため日本語がエスケープされていますが、json.loads(line)のようにjsonモジュールを用いれば正しく読み込めるはずです。）

Note:

  • コマンド引数には<AutoPhraseにより出力されたセグメント結果> <出力先ファイル名> を与えます。
  • 冒頭に利用する辞書ファイルを SYSTEM_DICTやUSER_DICT変数にしていますが、こちらは実際の環境に合わせて書き換えてください。
import json
import re
import sys

import MeCab

# 利用する辞書
SYSTEM_DICT = "/usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd"
USER_DICT = "dict/phrase.dic"

# 除外するトークン
IGNORE_TOKENS = {"EOS", ""}

def process_text(mecab, text):
    # <phrase>や</phrase>の前後に記号があると正しく分かち書きされないことがあるため
    # 全てのタグ前後に空白を入れる
    text = re.sub(r"<phrase>", " <phrase> ", text)
    text = re.sub(r"</phrase>", " </phrase> ", text)

    result = mecab.parse(text)
    tokens = [line.split("\t")[0] for line in result.split("\n")]
    tokens = [tok for tok in tokens if tok not in IGNORE_TOKENS]
    
    # <phrase> </phrase>で挟まれた単語列を１単語にまとめる
    buffer = None
    new_tokens = []
    for tok in tokens:
        if tok == "<phrase>":
            buffer = []
        elif tok == "</phrase>":
            if buffer is None:
                raise Exception(str(tokens))
            new_tokens.append("".join(buffer))
            buffer = None
        else:
            if buffer is not None:
                buffer.append(tok)
            else:
                new_tokens.append(tok)
    return new_tokens

if __name__=="__main__":
    # コマンド引数に <AutoPhraseにより出力されたセグメント結果> <出力先ファイル名>
    input_fn, output_fn = sys.argv[1:]

    mecab = MeCab.Tagger(f"-d {SYSTEM_DICT} -u {USER_DICT}")

    with open(input_fn) as h, open(output_fn, "w") as h_out:
        for line in h:
            line = line.replace("\n", "")
            if len(line) > 0:
                tokens = process_text(mecab, line)
                h_out.write(f"{json.dumps(tokens)}\n")

AutoPhrase: 人手による訓練データ作成不要でコーパスから用語を自動抽出する技術の紹介

機械学習 自然言語処理

概要

今回はテキストコーパスから用語を自動抽出する技術である、AutoPhraseを紹介したいと思います。

この技術の特徴は対象コーパスに対して人手アノテーションが不要であるという点です。

論文リンク： [1702.04457] Automated Phrase Mining from Massive Text Corpora

Githubレポジトリ：GitHub - shangjingbo1226/AutoPhrase: AutoPhrase: Automated Phrase Mining from Massive Text Corpora

日本語での利用法

技術の詳細に移る前に、日本語でAutoPhraseを試すための方法について紹介したいと思います。

幸い著者らによる実装が公開されていますが、新しい言語でAutoPhraseを利用するにはストップワードのリストや知識ベースから抽出した用語リストなどの必要なファイルを準備する必要があります。

これらをWikipediaやGinzaを利用して作成済みの実装をGithubにアップロードしましたので、ここではこちらの実装を利用して実験を行います。

github.com

準備

まず前提となる環境を整えます。

sudo apt install g++ openjdk-8-jdk curl

続いてコンパイルなどを行います。

bash compile.sh
chmod 755 tools/treetagger/bin/tree-tagger

入力コーパス

入力コーパスは各行に1つの文章が記述されたテキストファイルの形にしておきます。

今回は実験用としてAPIを通して取得した2018年の国会議事録コーパスを利用しました。

実行

以下のコマンドによりAutoPhraseによる用語抽出を行います。

MODEL=model/kokkai RAW_TRAIN=corpus.txt THREAD=$(nproc) ./auto_phrase.sh

設定する環境変数の意味はそれぞれ以下の通りです。

  • MODEL
    • 学習されたモデルや用語リストなどの出力先ディレクトリ
  • RAW_TRAIN
  • THREAD
    • 使用するコア数

非常に大きなコーパスに対して処理する場合：

12GBほどのコーパスに対して上記処理を行おうとしたところ、以下のエラーが表示されてしまいました。

terminate called after throwing an instance of 'std::bad_array_new_length'
  what():  std::bad_array_new_length
./auto_phrase.sh: 129 行: 152487 中止                  (コアダンプ) ./bin/segphrase_train --pos_tag --thread $THREAD --pos_prune ${DATA_DIR}/BAD_POS_TAGS.txt --label_method $LABEL_METHOD --label $LABEL_FILE --max_positives $MAX_POSITIVES --min_sup $MIN_SUP

issueでやり取りされているように、この場合はsrc/utils/parameters.hの#define LARGEの箇所をコメントアウトする必要があるようです。

出力

実行後MODEL に指定したディレクトリが作成され、内部に様々な出力ファイルが保存されています。主に利用することになるのは以下の2つかと思います。

  • Autophrase_multi-words.txt
    • 複数単語により構成される用語リスト。スコアが大きい順に並んでいる。
  • Autophrase_single-word.txt
    • 単一の単語により構成される用語リスト。同じくスコアが大きい順に並んでいる。

実際に国会議事録コーパスで得られた用語について確認すると、スコア上位と下位はそれぞれ以下のようになっています。実際に用語らしい単語列が用語として選ばれていることがわかります。トークナイザーによって複数単語に分かち書きされてしまっても、コーパス中で用語としてまとめて使われる傾向のある単語列をこのように抽出できる点がAutoPhraseの利点です。

0.9672302699 退 所
0.9670377906    小売 店
0.9667992563    非違 行為
0.9667326281    留置 権
0.9666839416    皆 伐
0.9666048674    臨床 研修
0.9665188348    行方 不明
0.9664195190    名誉 校長
0.9663571678    言葉 遣い
0.9663410581    国庫 補助
0.9661804795    関税 撤廃
0.0112053909 を 講ずる こと が
0.0112053909    で いる から
0.0112053909    し た と 言っ て
0.0112053909    を 評価 を し
0.0112053909    を 知っ た の
0.0112053909    の は 事実 で
0.0112053909    で 変わっ て
0.0111783639    が 認識 さ れ
0.0110249359    で あっ
0.0100696418    なし で

コーパスのアノテーション

学習されたモデルによって、コーパスに対して用語箇所のアノテーションを行うこともできます。コマンド例は以下の通りです。

MODEL=model/kokkai TEXT_TO_SEG=corpus.txt HIGHLIGHT_MULTI=0.5 HIGHLIGHT_SINGLE=0.7 ./phrasal_segmentation.sh

指定する環境変数の意味は：

  • MODEL
  • TEXT_TO_SEG
  • HIGHLIGHT_MULTI, HIGHLIGHT_SINGLE
    • それぞれ複数単語、単一単語の用語について、用語と扱うスコアの閾値。経験的に複数単語に対する閾値は大きめとするとよいらしい。

アノテーション結果

MODELで指定したディレクトリ以下に、segmentation.txtというファイル名でアノテーション結果が出力されます。

具体例は以下の通りです。<phrase></phrase>のタグにより用語部分がアノテーションされています。（オリジナルの文章は『国会会議録検索システム』により収集した文章であり、2018/6/1の『参議院沖縄及び北方問題に関する特別委員会』の議事録より抜粋したもの。）

○<phrase>国務大臣</phrase>（<phrase>福井照君</phrase>）　ＯＩＳＴにつきましては、<phrase>世界最高水準</phrase>を目指して<phrase>科学技術に関する</phrase><phrase>教育研究</phrase>を推進しております。その中で、<phrase>沖縄</phrase>の特性や<phrase>資源</phrase>を生かした<phrase>研究</phrase>を行っております。例えば、<phrase>サンゴ</phrase>の保全につながる<phrase>研究</phrase>、<phrase>サンゴ</phrase>を食い荒らす<phrase>オニヒトデ</phrase>の<phrase>全</phrase><phrase>ゲノム</phrase>解読に成功いたしまして、<phrase>サンゴ</phrase>の保全につながる<phrase>研究</phrase>を実際に実施しているところと伺っております。また、ＯＩＳＴ<phrase>発のベンチャー</phrase><phrase>企業</phrase>、たんぱく質<phrase>分子構造</phrase>の<phrase>解析</phrase><phrase>サービス</phrase>を提供する<phrase>企業</phrase>でありますけれども、が<phrase>誕生</phrase>しているほか、県内の小中学生や高校生を<phrase>対象</phrase>に<phrase>科学</phrase><phrase>教室</phrase>を行うなど、<phrase>沖縄</phrase>の<phrase>人材</phrase>育成に資する<phrase>取組</phrase>も行っており、<phrase>沖縄</phrase>の振興に貢献していると<phrase>認識</phrase>をしてございます。 　ＯＩＳＴはまだ<phrase>開学</phrase>から<phrase>日</phrase>が浅い<phrase>大学院大学</phrase>でございます。引き続き、<phrase>教育研究活動</phrase>を深化させることにより、<phrase>沖縄</phrase>の振興に<phrase>一層</phrase>貢献いただくことを<phrase>期待</phrase>しております。

結果を見るとおおむね良さそうですが、「OIST」が用語として認識されていなかったり「発のベンチャー」のようなおかしなフレーズが用語として認識されてしまっているところなどが気になります。この手法は複数単語の用語の方が強みがあるようなので、トークナイザ部分の改良などで改善する余地があるのかもしれません。

技術紹介

ここからは興味のある方へ向けてAutoPhraseの手法の詳細について書いていきたいと思います。基本的に原論文に書かれている内容となります。

そもそも用語とは？

AutoPhraseでは抽出対象である用語 (quality phrase)を以下の4条件を満たす単語列であると定義しています。

  • 頻出する (popularity)
  • 偶然の産物でない (concordance)
    • 用語中の単語がたまたまその順序で出現しているわけではない
  • 情報的に価値がある (informativeness)
    • 特定のトピックや概念を表現している
  • 意味的に完全である (completeness)
    • 文中において意味的に解釈できる完全な要素となっている
    • たとえば、より長い用語（New York）の一部分 (York)は、それ単体で意味が通らなければ用語でない

AutoPhraseの処理の流れ

以上で定義された用語を抽出するためのAutoPhraseの処理の流れを追っていきます。

AutoPhraseの処理はおおまかに以下のようになっています：

  • 用語候補の抽出 (candidate selection)
    • 頻度がある閾値(例えば30)より大きく、単語列としての長さが一定以下(例えば6以下)の単語列を候補として抽出します
  • 単語列が用語であるかの評価モデル、phrase quality estimator、を学習する
  • コーパス中の各文を適切な分割(segmentation)に区切る (phrasal segmentation)
    • 適切な分割とは、　私 | は | 大手食品メーカー | に | いま | す　のように、用語がそれ単体で１つのユニットになっているような分割です
  • phrasal segmentation後の単語列頻度（その単語列がそのままsegmentとなった頻度）を用いて特徴量を再計算し、phrase quality estimatorを再学習する

このうちcandidate selectionは頻度情報を用いることでpopularityの条件を担保し、phrase quality estimatorは統計的な特徴量を用いることでconcordance, informativenessの条件に合致する用語をフィルタリングします。そしてphrasal segmentationは用語ごとに区切ってから頻度情報を計算し直すことでcompleteness条件を満たす用語をフィルタリングすることにつながります。

Phrase Quality Estimatorの学習について

Phrase Quality Estimatorは与えられた単語列が用語として抽出されるべき単語列かどうかを分類するモデルです。このモデルは機械学習によってデータから学習されます。

訓練データのデータインスタンスにはcandidate selectionにより得られたn-gram集合とその特徴量を利用することができますが、学習のためにはさらに用語として抽出すべき単語列（正例）か、もしくは抽出すべきでない単語列（負例）なのかのラベルをこれらの単語列に付与する必要があります。このラベル付与にかかる人手作業を不要とするため、AutoPhraseは以下のようなアイデアを利用しています。

  • 公開されている大規模知識ベースから抽出した用語リストに含まれている場合に正例ラベルを付ける
    • 利用した知識ベース中に含まれる単語列は用語として妥当であることと、ある程度大規模な知識ベースを利用すれば手元のコーパスにマッチする単語列がそれなりに存在するであろう、という２つの仮定を置いています
    • 例えばWikipediaのタイトル一覧のリストに含まれる単語列（「東京都」、「東京ディズニーランド」）に正例を付与します
  • 最初のステップで取り出した用語候補のうち正例とならなかったものを（ノイズを含みうる）負例として扱ってしまう
    • AutoPhraseは最初のcandidate selectionのステップで、高頻度なn-gramを用語候補として取り出しました。この候補のうち正例ラベルがつけられなかったもの、すなわち知識ベース中に出現していない単語列を負例として扱うアイデアです
    • このように作成した負例には本来は用語である（つまり正例として扱うべき）単語列も含まれてしまいますが、経験的にその割合は小さいです（コーパス中の全nグラムの種類と用語の種類の大きさを想像すれば直感的には妥当だと思います）

以上のように自動的にアノテーションされた単語列の集合を訓練データとしてランダムフォレストを学習しますが、それぞれの木の学習にはランダムにそれぞれK個サンプルされた正例と負例を用います。

このようにランダムにサンプルされた訓練データを用いて学習された木をアンサンブルすることで、負例中のノイズ（本来正例として扱うべき単語列）の影響を効果的に軽減することができます。

Phrase Quality Estimatorの特徴量について

特徴量については論文中では詳細は割愛されており、実装を確認する必要がありました。

  • 統計的な特徴量
    • 単語列ABを分割後の部分単語列の出現確率の積 P(A)P(B) が最大となるようにA,Bと分割
      • point-wise mutual information (PMI)
        • \frac{P(AB)}{P(A)P(B)}
      • point-wise KL divergence (と著者が呼んでいるもの？)
        • P(AB)\log{\frac{P(AB)}{P(A)P(B)}}
      • \frac{P(AB)}{\sqrt{P(A)P(B)}}
    • 単語列 W 中の単語 i\in Wについて、inverse document frequency (IDF) \text{idf}(i)と Wのコーパス中の周辺文脈（前後1文）における出現頻度 \text{context}_W(i), 周辺文脈数 \text{num_contexts}(W)を用いる
      • \frac{ \sum_{i\in W}\text{context}_W(i)\text{idf}(i)}{\text{num_contexts}(W)\sum_{i\in W}\text{idf(i)}}
  • 文字列的な特徴量
    • 出現文脈で前後に括弧、引用符がそれぞれあるか、後ろにダッシュがあるか、全ての単語の最初が大文字(capitalizedされている)か
  • ストップワードに関する特徴量
  • 意味的な完全さを評価する特徴量
    • 単語列 W の最初または最後の単語を除いた部分文字列 sub の頻度を用いる
      • \frac{P(W)}{P(\text{sub})}
    • 単語列 W について、Wの前後どちらかにもう１つ単語が加わった単語列 superをコーパス中から探し頻度を比較 (superは複数ありえる)
      • \frac{\max_{\text{super}}P(\text{super})}{P(W)}

単語列がunigramの場合には部分単語列を用いる特徴量は利用しません。また統計的な特徴量も対数頻度 \log (\text{freq}(W) + 1)とindependent ratioのみとなります。(independent ratioは公開実装で定義されている特徴量。頻度の比のようだが、何を表しているのかは読み解けませんでした。)

論文中ではunigramのphrase qualityは常に1にすると記載されていますが、どうも実装を見る限りモデルを用いて予測しているように見えます。このあたりは謎です。

Phrasal Segmentationについて

POSタグを用いた分割手法であるPOS-guided phrasal segmentationについて説明します。

POS-guided phrasal segmentationは、POSタグが付与された単語列 \Omega=\Omega_1\Omega_2...\Omega_n (ただし \Omega_i=\lt w_i, t_i\gtは単語w_iとPOSタグt_iのペア)と分割時の境界位置集合 B=\{ b_1,...,b_{m+1}\} (1=b_1\lt ...\lt b_{m+1}=n+1)に対する生成モデルを仮定します。具体的な生成プロセスは以下の通りです：

  • p(b_{i+1}|b_i,t)=T(t_{[b_i,b_{i+1})})に従い次の境界位置をサンプルする
    • ここでPOS quality T(t_{[b_i,b_{i+1})}) は境界位置 b_iと b_{i+1}の間に境界が存在しない確率で、境界位置の間のPOSタグによって決まります。
    • は2つのPOSタグ t_x, t_yの間に境界が存在する確率 \delta(t_x, t_y)がPOSタグの種類ごとにパラメータとして定義されており、この確率からPOS qualityが計算されます。
  • 境界位置 b_1, b_{i+1}の間の単語列が、長さ b_{i+1}-b_iの単語列集合のカテゴリ分布からサンプルされる
    • 論文中では多項分布とされていましたが、カテゴリ分布の誤りか？
  • 境界位置 b_1, b_{i+1}の間の単語列が用語であるかのindicator関数が、quality phrase estimatorの出力確率によってサンプルされる

以上の生成モデルのパラメータをViterbiアルゴリズムによるsegment分けなどのMAP推定を用いたHard EMによって学習し、そのモデルによって得られた分割を出力します。