Indeed Machine Learning CodeSprint 2017

www.hackerrank.com

問題

求人の文面が与えられるので,以下のタグを付けるべきかどうかそれぞれのタグについて二値分類してください。

  • アルバイト
  • フルタイム
  • 時給制
  • 月給制
  • 短大卒対象
  • 大卒対象
  • 修士または博士対象
  • 免許が必要
  • 1年の経験が必要
  • 2〜4年の経験が必要
  • 5年以上の経験が必要
  • 管理職

評価

それぞれのタグの真陽性,真陰性,偽陽性偽陰性の数を合計してSTP, STN, SFP, SFNとします。

\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

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のほうが性能が出ることが多いようなのですが,後日試してみるとやっぱりそうなりました。今回のタスクでは特定の単語の有無のみで結果がほとんど決まってしまうので,特徴量のサンプリングは行わずに学習データのサンプリングのみを行うように設定すると良い性能が得られました。

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

入力について

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

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

そこで bufio.ReaderReadLine() を使います。戻り値の 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)
}

偉大な先人の記事

qiita.com

qiita.com

おすすめの本

みんなのGo言語【現場で使える実践テクニック】

みんなのGo言語【現場で使える実践テクニック】

RUPC 2017 Day2 I: Tree-Light

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp17Day2&pid=I

深さ優先探索をしたときの訪問順序によって頂点を並べると,ある頂点を根とする部分木に含まれる頂点が連続した区間に含まれる性質を使います。以下のページが詳しいです。

これを使えば,木を列として扱うことができるようになるので,列に対して以下の2つのクエリに答えられるようにすればよいです。

  • count(l, r, x, y): [l, r) の中でx以上y以下の値をもつ要素の数を答える
  • change(l, r, x, y): [l, r) の中で値がxである要素をすべてyに書き換える

厄介なのはchangeです。ここで注目するのは,各要素が取り得る値の範囲が0〜9の10段階と小さいことです。ここでchangeを置換として表現してみることを考えましょう。change(l, r, 0, 5) というクエリは (5 1 2 3 4 5 6 7 8 9) と表現できたり,change(l, r, 5, 8) というクエリは (0 1 2 3 4 8 6 7 8 9) と表現できたりします。また,置換は合成することができて,change(l, r, 0, 5) を適用してから change(l, r, 5, 8) を適用するようなクエリは (8 1 2 3 4 8 6 7 8 9) と表現できます。ここで重要なのは,置換という作用素はモノイド(結合法則が成り立ち,単位元が存在する)になっているので遅延セグメント木での作用として使うことができるということです。セグメント木に対して適用可能な操作については次の記事が詳しいです。

koba-e964.hatenablog.com

tomcatowl.github.io

遅延セグメント木と同じ要領で範囲に対する置換を実装した平方分割を以下に示します。これを使うことで O(N+Q√N) で解けます。

typedef array<int, 10> ten;
const int sqrtN = 512;
ten multi(ten a, ten b) {
  ten ret;
  for (int i = 0; i < 10; i++) {
    ret[i] = b[a[i]];
  }
  return ret;
}
struct SqrtDecomposition {
  int N, K;
  vector<int> data;
  // blockCount[k][z]: k番目のブロックの中で値がzである要素の数
  vector<ten> blockCount;
  // 遅延された操作を持っているか?
  vector<bool> lazyFlag;
  // 遅延された操作(置換)
  vector<ten> lazyUpdate;
  // 置換の単位元
  ten initialValue;
  SqrtDecomposition(int n) : N(n) {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(K * sqrtN, 0);
    lazyFlag.assign(K, false);
    // 置換の単位元は (0 1 2 ... 7 8 9)
    for (int i = 0; i < 10; i++) {
      initialValue[i] = i;
    }
    lazyUpdate.assign(K, initialValue);
    ten zero;
    zero.fill(0);
    zero[0] = sqrtN;
    blockCount.assign(K, zero);
  }
  // k番目のブロックに対する遅延している操作を適用する
  void eval(int k) {
    if(lazyFlag[k]) {
      lazyFlag[k] = false;
      for (int i = k * sqrtN; i < (k + 1) * sqrtN; i++) {
        data[i] = lazyUpdate[k][data[i]];
      }
      lazyUpdate[k] = initialValue;
    }
  }
  // [a, b) の範囲に対して置換を作用させる
  void put(int a, int b, ten perm) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        lazyFlag[k] = true;
        // 作用を合成する
        lazyUpdate[k] = multi(lazyUpdate[k], perm);
        // blockCountを更新
        ten cnt;
        cnt.fill(0);
        for(int i = 0; i < 10; i++) {
          cnt[perm[i]] += blockCount[k][i];
        }
        blockCount[k] = cnt;
      }
      else {
        eval(k);
        // 置換を適用
        for(int i = max(a, l); i < min(b, r); ++i) {
          data[i] = perm[data[i]];
        }
        // blockCountを数え直す
        blockCount[k].fill(0);
        for (int i = l; i < r; ++i) {
          blockCount[k][data[i]]++;
        }
      }
    }
  }
  // [a, b) の範囲でx以上y以下の値をもつ要素の数を返す
  int get(int a, int b, int x, int y) {
    int ret = 0;
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        for (int i = x; i <= y; i++) {
          ret += blockCount[k][i];
        }
      }
      else {
        eval(k);
        for(int i = max(a, l); i < min(b, r); ++i) {
          if(x <= data[i] && data[i] <= y) {
            ret++;
          }
        }
      }
    }
    return ret;
  }
};