$\displaystyle \begin{align} \mathit{STP}&=\sum_{i=1}^{12}\mathit{TP}_i \\ \mathit{STN}&=\sum_{i=1}^{12}\mathit{TN}_i \\ \mathit{SFP}&=\sum_{i=1}^{12}\mathit{FP}_i \\ \mathit{SFN}&=\sum_{i=1}^{12}\mathit{FN}_i \\ \end{align}$

STP, STN, SFP, SFNを使ってF値を計算したものが評価指標となります。

$\displaystyle \begin{align} P&=\frac{\mathit{STP}}{\mathit{STP}+\mathit{SFP}} \\ R&=\frac{\mathit{STP}}{\mathit{STP}+\mathit{SFN}} \end{align}$

$\displaystyle F_1=\frac{2PR}{P+R}$

方針

コンテスト終了まで残り12時間しかないタイミングで始めたので，テキスト分類でベースライン的に使われている手法だけ試しました。

それぞれのタグについて二値分類問題を解いてもいいわけですが，アルバイトとフルタイムや時給制と月給制は排他的なはずなので，「アルバイト or フルタイム or それ以外」や「時給制 or 月給制 or それ以外」で多値分類問題を解くというアプローチも考えられます。ただし今回は評価指標がかなり独特で，それぞれのタグについて二値分類問題として解いたほうが最終的な評価値は高くなりそうな気がしたのでそのアプローチを試しました。

前処理

Unicodeにはスペースっぽい文字，ハイフンっぽい文字，整形のための制御コードなどが多数収録されています。テキスト分類の問題ではそのあたりの文字は消したり正規化したりしたほうが都合が良いので，最初にどんな文字種が含まれているか調べました。ASCIIコード範囲内で表示可能文字以外の文字を列挙するには以下のような処理を実行します。

chrs = set()
for desc in descs:
    for c in desc:
        if ord(c) <= 0x19 or ord(c) >= 0x7f:
            chrs.add(c)
chrs = sorted(list(chrs))
for c in chrs:
    print(repr(c), hex(ord(c)))

実行してみたところ，極少数ですが日本語，ポルトガル語，スペイン語などで書かれた求人の文面もあることが分かりました。あまりリソースを避けそうにないので英語のみに対象を絞ろうと思い，漢字やひらがな，カタカナは消すことにしました。

あとはU+2010のハイフンは半角ハイフンに置換したり，書字方向指定コードやゼロ幅スペースなど（具体的には0xAD, U+200B, U+202A, U+202C, U+FEFF, U+FFFC, U+FFFD）を消しました。

あとはユニコード範囲外にある無効なコードポイントを消したりしました。これは以下のように書いたのですが，もっと良い方法があるはずです。

t = ''
for c in s:
    try:
        unicodedata.name(c)
        t += c
    except ValueError:
        pass

単語分割・レンマ化

英語の単語分割はスペースで区切るだけだと思うかもしれませんが，実際には例外処理がいくつかあるので専用のトークナイザを使ったほうが良いです。専用のツールとしては Stanford Tokenizer などがあります。

テキスト分類でやったほうが良い処理として，語のステミング（語幹以外の部分の除去）やレンマ化（見出し語化）などがあります。ステミングのアルゴリズムはPorter stemmerとSnowball stemmerというものが有名で，どちらもNLTKで使えます。レンマ化の処理はNLTKやStanford POS Taggerに収録されています。本来であればどの処理が最も適切であるか全部試すべきなのですが，あまり時間がなかったのでStanford POS Taggerのレンマ化のみ試しました。

特徴ベクトルの作成

TFとBM25だけ試しました。作り方は以下のページを見てください。

kujira16.hateblo.jp

分類

時間がなかったので最初にNaive BayesとPassive Aggressiveを試しましたが全く性能が出ませんでした。

データを眺めてみたのですが，例えばpart-timeというタグを付けるべきかどうかは “part” か “time” か “part-time” が入っているかどうかだけで決まっているなど，全体の極性でタグが決まるというよりは極少数の単語の有無のみでタグが決まっているようでした。そのため，意外と決定木が強いのではないかと思い試してみるとなかなかよい性能が出ました。max_depth をグリッドサーチしていると締め切りが来てしまったので，これで提出しました。

結果

順位表は以下のURLにあります。

https://www.hackerrank.com/contests/indeed-ml-codesprint-2017/challenges/tagging-raw-job-descriptions/leaderboard

テストデータに対する解答を送信すると，テストデータ全体の2922件のうち約半数の1446件のデータについての解答のみが評価され，その結果が仮スコアとして順位表に掲載されます。最終的な順位はコンテスト終了後にテストデータ全体に対する解答が評価されます。これはデータ分析コンペにおいて参加者にフィードバックを与えつつもモデルの過学習を防ぐための工夫です。

まだ最終テストが行われていないので最終的な順位分かりませんが，仮スコアは628.80で52位でした。オーバーフィッティングする要素をそんなに入れていないので最終テストが行われてもそんなに悪くならないと嬉しいですね…

ソースコードは以下のリポジトリに置いています。

github.com

その後

一般にこの手のコンペでは決定木よりもRandom Forestのほうが性能が出ることが多いようなのですが，後日試してみるとやっぱりそうなりました。今回のタスクでは特定の単語の有無のみで結果がほとんど決まってしまうので，特徴量のサンプリングは行わずに学習データのサンプリングのみを行うように設定すると良い性能が得られました。

@odan3240 「学習を行いたい観測データから〜サブサンプルを生成する」は行いますが，「トレーニングデータの説明変数のうち、m 個をランダムに選択する」は行わずに説明変数を全部使うという意味ですhttps://t.co/e5ZK2TIfp2
— しょラー (@shora_kujira16) 2017年4月9日

2017-04-09

Go言語で競技プログラミングするときに使ってる入出力

入力について

普通は fmt.Scan で問題ないのですが，高速な入力が要求される問題では fmt.Scan だと遅すぎることがあります。fmt.Scan では 3*10⁶ 個の整数の入力に10秒以上かかりました。

高速な入力のためには bufio を使います。bufio を使った方法では 3*10⁶ 個の整数の入力にかかる時間は0.1秒以下でした。bufio.Scanner の Scan() と Text() の組み合わせで多くの場合は事足りるのですが，これにも少し問題があります。Scan() で読み取れるトークンの最大長は MaxScanTokenSize という定数で定義されており，Go 1.8 では 64*1024 でした。これでは 10⁵ や 10⁶ 程度の長さの文字列の処理を要求する問題に対応することができません。Buffer([]byte, int) でバッファの大きさを変えることができますが，バッファの長さを変えるのを忘れてWAになってしまいそうです。

そこで bufio.Reader の ReadLine() を使います。戻り値の isPrefix を確認して ReadLine() を複数回呼び出すことで長い文字列でも読み取ることができます。

出力について

os.Stdout はバッファされないため，毎回flushしているのと同じような状態で遅いです。os.Stdout を直接利用している fmt.Printf なども同様です。これを解決するために bufio を利用しています。プログラム終了前にはflushしてやる必要がありますが，忘れやすいのでmainの先頭で defer io.Flush() としてやるほうが良いと思います。

配列の中身を空白区切りで出力したい場合が多々ありますが，...interface{} の実引数として []int や []string を与えることはできません。そのため []intと[]stringのためだけに配列の中身を空白区切りで出力する関数を定義しています。

[]int や []string から []interface{} への変換についての話題が気になる方は以下のページを参照してください。

InterfaceSlice · golang/go Wiki · GitHub

その他

maxやminの関数はint用だけ特別に用意しています。Go言語にはジェネリクスが導入される予定がないので筋肉で解決しましょう。以下のリポジトリがすごくおもしろいです。

github.com

Go言語のPrintfのフォーマット指定子には，構造体の中身が見られる ‘%+v’ というものがあり，デバッグに便利です。printfデバッグするためにLog関数を定義しています。IntelliJ IDEAのデバッガが使いやすいのでprintfデバッグを使わないことも多いですが。

ソースコード

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

type Io struct {
    reader    *bufio.Reader
    writer    *bufio.Writer
    tokens    []string
    nextToken int
}

func NewIo() *Io {
    return &Io{
        reader: bufio.NewReader(os.Stdin),
        writer: bufio.NewWriter(os.Stdout),
    }
}

func (io *Io) Flush() {
    err := io.writer.Flush()
    if err != nil {
        panic(err)
    }
}

func (io *Io) NextLine() string {
    var buffer []byte
    for {
        line, isPrefix, err := io.reader.ReadLine()
        if err != nil {
            panic(err)
        }
        buffer = append(buffer, line...)
        if !isPrefix {
            break
        }
    }
    return string(buffer)
}

func (io *Io) Next() string {
    for io.nextToken >= len(io.tokens) {
        line := io.NextLine()
        io.tokens = strings.Fields(line)
        io.nextToken = 0
    }
    r := io.tokens[io.nextToken]
    io.nextToken++
    return r
}

func (io *Io) NextInt() int {
    i, err := strconv.Atoi(io.Next())
    if err != nil {
        panic(err)
    }
    return i
}

func (io *Io) NextFloat() float64 {
    i, err := strconv.ParseFloat(io.Next(), 64)
    if err != nil {
        panic(err)
    }
    return i
}

func (io *Io) PrintLn(a ...interface{}) {
    fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
    fmt.Fprintf(io.writer, format, a...)
}

func (io *Io) PrintIntLn(a []int) {
    b := []interface{}{}
    for _, x := range a {
        b = append(b, x)
    }
    io.PrintLn(b...)
}

func (io *Io) PrintStringLn(a []string) {
    b := []interface{}{}
    for _, x := range a {
        b = append(b, x)
    }
    io.PrintLn(b...)
}

func Log(name string, value interface{}) {
    fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}

func intMin(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func intMax(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    io := NewIo()
    defer io.Flush()
    A := io.NextInt()
    B := io.NextInt()
    C := io.NextInt()
    S := io.Next()
    io.PrintLn(A+B+C, S)
}