R
MachineLearning
svm
Recommendation

Ranking learningにおけるデータ変換をRで

一般的に使われている検索結果に対する適合フィードバックにおいて、よく用いられるのはrankingの修正を行うものです。様々な推薦エンジンで活用されているもので、応用も多数ありそうです。
要はユーザーが検索結果に対する評価を直接行い、検索のランキングの礎となる評価関数を修正していくというものです。

Learning to rank for IR

Learning from rank

これ自体は古いトピックで最近はあまり見ないですが、deep learningを適用する例が多いようです。
そもそもアプローチはしておいた方がよいので、単純な方法を試しました。
ランキング学習を通常の識別学習や回帰にマッピングする方法はいくつかあります。

  • pointwise
    ランキングの要素1つ1つを独立に識別する。ランキングとして正しいかどうかの指標(学習データ)が必要。

  • pairwise
     ランキングの要素の組(1位と2位とか)について、どちらが優位かを識別する。ランキングとしてどちらが上かを示す指標が必要。

  • listwise
     ランキングの要素すべてを使い、回帰するもの。ランキングの順位(または評価値そのもの)が必要です。ランキングの完全な修正が必要。

こと、実際のシステムとかになると、ランキングすべての修正情報がユーザーからフィードバックされることは中々なく、複数の候補から一つだけ選ぶというものが多いのではないでしょうか?そうなると、完全なデータがなくても機能するpair wiseのアプローチが良いように思えます。

list(ranking) -> pair wise変換

Featuresを k(length of ranking) * nf(feature)の行列とすると、以下のようにすべての組み合わせでペアを生成します。最終列にペアの最初のIDを入れておきます(どのfeatureを元に比較しているかを示すため)

list2pair <- function(Features) {
    k <- nrow(Features)
    nf <- ncol(Features)
    dataset <- matrix(ncol = nf)
    pairs = permutations(v = 1:k, r = 2, n = k, repeats.allowed = F)
    dataset <- cbind(Features[pairs[, 1],] - Features[pairs[, 2],], pairs[, 1])
    return(dataset)
}

学習用データを作る際は、1つだけユーザーフィードバックがあった時を想定すると、以下のような感じで、選択されたfeatureとそれ以外のペアを作るだけです。フィーチャーをひっくり返して正負例を作ることができるので、結果的には(k-1)*2の例ができることになります。

selection2pair <- function(Features, selection) {
    k <- nrow(Features)
    nf <- ncol(Features)
    dataset <- matrix(ncol = nf + 1)
    rest <- (1:k)[-selection]
    pairs <- cbind(rep(selection, k - 1), rest)
    rclass <- ifelse(pairs[, 1] < pairs[, 2], 1, -1)
    dfeature <- cbind(rankedFeatures[pairs[, 1],] - rankedFeatures[pairs[, 2],], rclass)
    dataset <- rbind(dataset, dfeature)
    dataset <- rbind(dataset, -dfeature)
    dataset <- dataset[-1,]
    return(dataset)
}

pair wise -> list(ranking) 変換

それで、ランキングに使う目的関数を求めるには以下のような感じになります。
lapply使えば一発な気がしますが、直感的に。。

pair2obj <- function(model.svm, Features) {
    nf <- ncol(Features) - 1
    pred <- predict(model.svm, Features[,1:nf])
    obj <- data.frame(pred = as.numeric(levels(pred)[pred]), idx = dfeatures[, nf + 1]) %>%
            group_by(idx) %>%
            summarise(obj = sum(pred)) %>%
            ungroup()
    return(obj)    
}

SVMを使う場合はRankingSVMというらしく、PythonやRのライブラリとかもあったりするんですけどね。
なんかランキング以外でもいろいろ使えそう。