LearningToRank
#InformationRetrieval
#PairWise
#NLP
#LanguageModel
#Prompting
#NAACL
Issue Date: 2023-07-11 Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting, Zhen Qin+, N_A, NAACL'24 SummaryLLMsを使用してドキュメントをランキングする際に、Pairwise Ranking Prompting（PRP）という新しい技術を提案する。PRPは、LLMsへの負荷を軽減し、最先端のランキングパフォーマンスを達成することができる。具体的には、20Bパラメータを持つFlan-UL2モデルに基づくPRPは、商用のGPT-4に基づく従来の手法を上回る結果を示した。さらに、PRPのバリアントを提案し、効率を改善することができることを示した。PRPは生成とスコアリングのLLM APIの両方をサポートし、入力の順序に対して無感度であることも示された。 Commentopen source LLMにおいてスタンダードなランキングタスクのベンチマークでSoTAを達成できるようなprompting技術を提案従来のランキングのためのpromptingはpoint-wiseとlist wiseしかなかったが、前者は複数のスコアを比較するためにスコアのcalibrationが必要だったり、OpenAIなどのAPIはlog probabilityを提供しないため、ランキングのためのソートができないという欠点があった。後者はinputのorderingに非常にsensitiveであるが、listのすべての組み合わせについてorderingを試すのはexpensiveなので厳しいというものであった。このため（古典的なlearning to rankでもおなじみや）pairwiseでサンプルを比較するランキング手法PRPを提案している。
PRPはペアワイズなのでorderを入れ替えて評価をするのは容易である。また、generation modeとscoring mode（outputしたラベルのlog probabilityを利用する; OpenLLMを使うのでlog probabilityを計算できる）の2種類を採用できる。ソートの方法についても、すべてのペアの勝敗からから単一のスコアを計算する方法（AllPair), HeapSortを利用する方法、LLMからのoutputを得る度にon the flyでリストの順番を正しくするSliding Windowの3種類を提案して比較している。
下表はscoring modeでの性能の比較で、GPT4に当時は性能が及んでいなかった20BのOpenLLMで近しい性能を達成している。
また、PRPがinputのorderに対してロバストなことも示されている。
#Tutorial
#InformationRetrieval
#Online/Interactive
#SIGIR
Issue Date: 2018-01-01 Online Learning to Rank for Information Retrieval, Grotov+, SIGIR'16 #RecommenderSystems #Citations #ACL
Issue Date: 2018-01-01 News Citation Recommendation with Implicit and Explicit Semantics, Peng+, ACL'16 Commenttarget text中に記述されているイベントや意見に対して、それらをサポートするような他のニュース記事を推薦する研究。
たとえば、target text中に「北朝鮮が先日ミサイルの発射に失敗したが...」、といった記述があったときに、このイベントについて報道しているニュース記事を推薦するといったことを、target text中の様々なcontextに対して行う。
このようなシステムの利用により、target textの著者の執筆支援（自身の主張をサポートするためのreferenceの自動獲得）や、target textの読者の読解支援（text中の記述について詳細な情報を知りたい場合に、検索の手間が省ける）などの利点があると主張。
タスクとしては、target text中のあるcontextと、推薦の候補となるニュース記事の集合が与えられたときに、ニュース記事をre-rankingする タスク。
提案手法はシンプルで、contextとニュース記事間で、様々な指標を用いてsimilarityを測り、それらをlearning-to-rankで学習した重みで組み合わせてre-rankingを行うだけ。 similarityを測る際は、表記揺れや曖昧性の問題に対処するためにEmbeddingを用いる手法と、groundingされたentityの情報を用いる手法を提案。
Bing news中のAnchor textと、hyperlink先のニュース記事の対から、contextと正解ニュース記事の対を取得し、30000件規模の実験データを作成し、評価。その結果、baselineよりも提案手法の性能が高いことを示した。
Issue Date: 2023-07-11 Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting, Zhen Qin+, N_A, NAACL'24 SummaryLLMsを使用してドキュメントをランキングする際に、Pairwise Ranking Prompting（PRP）という新しい技術を提案する。PRPは、LLMsへの負荷を軽減し、最先端のランキングパフォーマンスを達成することができる。具体的には、20Bパラメータを持つFlan-UL2モデルに基づくPRPは、商用のGPT-4に基づく従来の手法を上回る結果を示した。さらに、PRPのバリアントを提案し、効率を改善することができることを示した。PRPは生成とスコアリングのLLM APIの両方をサポートし、入力の順序に対して無感度であることも示された。 Commentopen source LLMにおいてスタンダードなランキングタスクのベンチマークでSoTAを達成できるようなprompting技術を提案従来のランキングのためのpromptingはpoint-wiseとlist wiseしかなかったが、前者は複数のスコアを比較するためにスコアのcalibrationが必要だったり、OpenAIなどのAPIはlog probabilityを提供しないため、ランキングのためのソートができないという欠点があった。後者はinputのorderingに非常にsensitiveであるが、listのすべての組み合わせについてorderingを試すのはexpensiveなので厳しいというものであった。このため（古典的なlearning to rankでもおなじみや）pairwiseでサンプルを比較するランキング手法PRPを提案している。
PRPはペアワイズなのでorderを入れ替えて評価をするのは容易である。また、generation modeとscoring mode（outputしたラベルのlog probabilityを利用する; OpenLLMを使うのでlog probabilityを計算できる）の2種類を採用できる。ソートの方法についても、すべてのペアの勝敗からから単一のスコアを計算する方法（AllPair), HeapSortを利用する方法、LLMからのoutputを得る度にon the flyでリストの順番を正しくするSliding Windowの3種類を提案して比較している。
下表はscoring modeでの性能の比較で、GPT4に当時は性能が及んでいなかった20BのOpenLLMで近しい性能を達成している。
また、PRPがinputのorderに対してロバストなことも示されている。
Issue Date: 2018-01-01 Online Learning to Rank for Information Retrieval, Grotov+, SIGIR'16 #RecommenderSystems #Citations #ACL
Issue Date: 2018-01-01 News Citation Recommendation with Implicit and Explicit Semantics, Peng+, ACL'16 Commenttarget text中に記述されているイベントや意見に対して、それらをサポートするような他のニュース記事を推薦する研究。
たとえば、target text中に「北朝鮮が先日ミサイルの発射に失敗したが...」、といった記述があったときに、このイベントについて報道しているニュース記事を推薦するといったことを、target text中の様々なcontextに対して行う。
このようなシステムの利用により、target textの著者の執筆支援（自身の主張をサポートするためのreferenceの自動獲得）や、target textの読者の読解支援（text中の記述について詳細な情報を知りたい場合に、検索の手間が省ける）などの利点があると主張。
タスクとしては、target text中のあるcontextと、推薦の候補となるニュース記事の集合が与えられたときに、ニュース記事をre-rankingする タスク。
提案手法はシンプルで、contextとニュース記事間で、様々な指標を用いてsimilarityを測り、それらをlearning-to-rankで学習した重みで組み合わせてre-rankingを行うだけ。 similarityを測る際は、表記揺れや曖昧性の問題に対処するためにEmbeddingを用いる手法と、groundingされたentityの情報を用いる手法を提案。
Bing news中のAnchor textと、hyperlink先のニュース記事の対から、contextと正解ニュース記事の対を取得し、30000件規模の実験データを作成し、評価。その結果、baselineよりも提案手法の性能が高いことを示した。
#InformationRetrieval
#Online/Interactive
#Pocket
Issue Date: 2018-01-01
Contextual Dueling Bandits, Dudik+, JMLR'15
#Tutorial
#InformationRetrieval
Issue Date: 2018-01-01
Machine Learning for Information Retrieval, Hofmann, ESSIR'15
#InformationRetrieval
#Online/Interactive
#Interleaved
#WSDM
Issue Date: 2018-01-01
Reusing Historical Interaction Data for Faster Online Learning to Rank for IR, Hofmann+, WSDM'13
Comment197 DBGDを拡張した手法を提案している。
アルゴリズムが細かく書いてあるので、追っていくとDBGD等について理解が深まると思われる。
Interleavemethodについても。 #InformationRetrieval #Online/Interactive #ICML Issue Date: 2018-01-01 Interactively Optimizing Information Retrieval Systems as a Dueling Bandits Problem, Yue+, ICML'09 Commentonline learning to rankに関する論文でよくreferされる論文
提案手法は、Dueling Bandit Gradient Descent(DBGD)と呼ばれる.
onlineでlearning to rankを行える手法で、現在の重みwとwをランダムな方向に動かした新たな重みw'を使って、予測を行い、duelを行う。
duelを行った結果、新たな重みw'の方が買ったら、重みwをその方向に学習率分更新するというシンプルな手法
duelのやり方は、詳しく書いてないからなんともよくわからなかったが、Interleavedなlist(二つのモデルのoutputを混合したリスト)などを作り、実際にユーザにリストを提示してユーザがどのアイテムをクリックしたかなどから勝敗の確率値を算出し利用する、といったやり方が、IRの分野では行われている。
onlineでユーザのフィードバックから直接モデルを学習したい場合などに用いられる。
offlineに持っているデータを使って、なんらかのmetricを計算してduelをするという使い方をしたかったのだが、その使い方はこの手法の本来の使い方ではない（単純に何らかのmetricに最適化するというのであれば目的関数が設計できるのでそっちの手法を使ったほうが良さそうだし）。
そもそもこの手法は単純にMetricとかで表現できないもの（ユーザの満足度とか）を満たすようなweightをexploration/exploitationを繰り返して見つけていこう、というような気持ちだと思われる。 #RecommenderSystems #ImplicitFeedback #UAI #Admin'sPick Issue Date: 2017-12-28 BPR: Bayesian Personalized Ranking from Implicit Feedback, Rendle+, UAI'09, 2009.06 Comment重要論文
ユーザのアイテムに対するExplicit/Implicit Ratingを利用したlearning2rank。
AUCを最適化するようなイメージ。
負例はNegative Sampling。
計算量が軽く、拡張がしやすい。
Implicitデータを使ったTop-N Recsysを構築する際には検討しても良い。
また、MFのみならず、Item-Based KNNに活用することなども可能。
http://tech.vasily.jp/entry/2016/07/01/134825参考: https://techblog.zozo.com/entry/2016/07/01/134825pytorchでのBPR実装: https://github.com/guoyang9/BPR-pytorch #InformationRetrieval #Interleaved #CIKM Issue Date: 2018-01-01 How Does Clickthrough Data Reflect Retrieval Quality?, Radlijnski+, CIKM'08 #InformationRetrieval #Online/Interactive #WSDM Issue Date: 2018-01-01 Fast Learning of Document Ranking Functions with the Committee Perceptrion, Elsas+, WSDM'08 #InformationRetrieval #ListWise #Pocket #ICML Issue Date: 2018-01-01 Listwise Approach to Learning to Rank - Theory and Algorithm （ListMLE）, Xia+, ICML'2008 #InformationRetrieval #ListWise #ICML #Admin'sPick Issue Date: 2018-01-01 Learning to Rank: From Pairwise Approach to Listwise Approach （ListNet）, Cao+, ICML'2007 Comment解説スライド：http://www.nactem.ac.uk/tsujii/T-FaNT2/T-FaNT.files/Slides/liu.pdf
解説ブログ：https://qiita.com/koreyou/items/a69750696fd0b9d88608従来行われてきたLearning to Rankはpairwiseな手法が主流であったが、pairwiseな手法は2つのインスタンス間の順序が正しく識別されるように学習されているだけであった。
pairwiseなアプローチには以下の問題点があった：
インスタンスのペアのclassification errorを最小化しているだけで、インスタンスのランキングのerrorを最小化しているわけではない。
インスタンスペアが i.i.d な分布から生成されるという制約は強すぎる制約
queryごとに生成されるインスタンスペアは大きく異なるので、インスタンスペアよりもクエリに対してバイアスのかかった学習のされ方がされてしまう
これらを解決するために、listwiseなアプローチを提案。
listwiseなアプローチを用いると、インスタンスのペアの順序を最適化するのではなく、ランキング全体を最適化できる。
listwiseなアプローチを用いるために、Permutation Probabilityに基づくloss functionを提案。loss functionは、2つのインスタンスのスコアのリストが与えられたとき、Permutation Probability Distributionを計算し、これらを用いてcross-entropy lossを計算するようなもの。
また、Permutation Probabilityを計算するのは計算量が多すぎるので、top-k probabilityを提案。
top-k probabilityはPermutation Probabilityの計算を行う際のインスタンスをtop-kに限定するもの。
論文中ではk=1を採用しており、k=1はsoftmaxと一致する。
パラメータを学習する際は、Gradient Descentを用いる。k=1の設定で計算するのが普通なようなので、普通にoutputがsoftmaxでlossがsoftmax cross-entropyなモデルとほぼ等価なのでは。 #InformationRetrieval #PairWise #ICML #Admin'sPick Issue Date: 2018-01-01 Learning to Rank using Gradient Descent （RankNet）, Burges+, ICML'2005 Commentpair-wiseのlearning2rankで代表的なRankNet論文
解説ブログ：https://qiita.com/sz_dr/items/0e50120318527a928407
lossは2個のインスタンスのpair、A, Bが与えられたとき、AがBよりも高くランクされる場合は確率1, AがBよりも低くランクされる場合は確率0、そうでない場合は1/2に近くなるように、スコア関数を学習すれば良い。 #InformationRetrieval #PointWise #NeurIPS #Admin'sPick Issue Date: 2018-01-01 PRanking with Ranking, Crammer+, NIPS'01 CommentPoint-WiseなLearning2Rankの有名手法 #Article #Tools #InformationRetrieval #Online/Interactive Issue Date: 2018-01-01 Lerot: Online Learning to rank Framework #Article #Survey #InformationRetrieval #Online/Interactive Issue Date: 2018-01-01 Fast and Reliable Online Learning to Rank for Information Retrieeval, Katja Hofmann, Doctoral Thesis, 2013 #Article #InformationRetrieval #ListWise Issue Date: 2018-01-01 A General Approximation Framework for Direct Optimization of Information Retrieval Measures （ApproxAP, ApproxNDCG）, Qin+, Information Retrieval, 2010 Comment実装してみたが、バグありそう感・・・
https://github.com/AkihikoWatanabe/ApproxAP #Article #InformationRetrieval #PairWise #NeurIPS Issue Date: 2018-01-01 Large Scale Learning to Rank, Sculley+, NIPS 2009 Commentsofia-mlの実装内容について記述されている論文
よくonline学習の文脈で触れられるが、気をつけないと罠にはまる。
というのは、sofia-ml内のMethodsによって、最適化している目的関数が異なるからだ。
実装をみると、全てのmethodsがonlineでできちゃいそうに見える（学習済みのモデルをinputして学習を再開させられるため）が、落とし穴。
まず、SGD SVM, Pegasos SVM,については、最適化している目的関数がbatchになっているため、online learningではない。
passive-aggressive perceptrionは目的関数が個別の事例に対して定式化される(要確認)のでonline learningといえる。
(ROMMAは調べないとわからん)
pairwiseのlearning to rankでは、サンプルのペアを使って学習するので、最悪の場合O(n^2)の計算量がかかってしまってめっちゃ遅いのだが、実は学習データを一部サンプリングして重みを更新するってのをたくさん繰り返すだけで、高速に学習できちゃうという話。
実際、sofia-mlを使って見たら、liblinearのranking SVM実装で40分かかった学習が数秒で終わり、なおかつ精度も良かった。
#Article #Tutorial #InformationRetrieval Issue Date: 2018-01-01 From RankNet to LambdaRank to LambdaMART: An Overview, Burges, Microsoft Research Technical Report, 2010 #Article #Tutorial #InformationRetrieval #Slide Issue Date: 2018-01-01 Confidence Weightedでランク学習を実装してみた, 徳永拓之, 第4回 自然言語処理勉強会@東京 #Article #Tutorial #InformationRetrieval #Slide Issue Date: 2018-01-01 ランキング学習ことはじめ, DSIRNLP#1, 2011 #Article #Survey #InformationRetrieval Issue Date: 2018-01-01 Learning to Rank for Information Retriefval, Liu+, 2009
アルゴリズムが細かく書いてあるので、追っていくとDBGD等について理解が深まると思われる。
Interleavemethodについても。 #InformationRetrieval #Online/Interactive #ICML Issue Date: 2018-01-01 Interactively Optimizing Information Retrieval Systems as a Dueling Bandits Problem, Yue+, ICML'09 Commentonline learning to rankに関する論文でよくreferされる論文
提案手法は、Dueling Bandit Gradient Descent(DBGD)と呼ばれる.
onlineでlearning to rankを行える手法で、現在の重みwとwをランダムな方向に動かした新たな重みw'を使って、予測を行い、duelを行う。
duelを行った結果、新たな重みw'の方が買ったら、重みwをその方向に学習率分更新するというシンプルな手法
duelのやり方は、詳しく書いてないからなんともよくわからなかったが、Interleavedなlist(二つのモデルのoutputを混合したリスト)などを作り、実際にユーザにリストを提示してユーザがどのアイテムをクリックしたかなどから勝敗の確率値を算出し利用する、といったやり方が、IRの分野では行われている。
onlineでユーザのフィードバックから直接モデルを学習したい場合などに用いられる。
offlineに持っているデータを使って、なんらかのmetricを計算してduelをするという使い方をしたかったのだが、その使い方はこの手法の本来の使い方ではない（単純に何らかのmetricに最適化するというのであれば目的関数が設計できるのでそっちの手法を使ったほうが良さそうだし）。
そもそもこの手法は単純にMetricとかで表現できないもの（ユーザの満足度とか）を満たすようなweightをexploration/exploitationを繰り返して見つけていこう、というような気持ちだと思われる。 #RecommenderSystems #ImplicitFeedback #UAI #Admin'sPick Issue Date: 2017-12-28 BPR: Bayesian Personalized Ranking from Implicit Feedback, Rendle+, UAI'09, 2009.06 Comment重要論文
ユーザのアイテムに対するExplicit/Implicit Ratingを利用したlearning2rank。
AUCを最適化するようなイメージ。
負例はNegative Sampling。
計算量が軽く、拡張がしやすい。
Implicitデータを使ったTop-N Recsysを構築する際には検討しても良い。
また、MFのみならず、Item-Based KNNに活用することなども可能。
http://tech.vasily.jp/entry/2016/07/01/134825参考: https://techblog.zozo.com/entry/2016/07/01/134825pytorchでのBPR実装: https://github.com/guoyang9/BPR-pytorch #InformationRetrieval #Interleaved #CIKM Issue Date: 2018-01-01 How Does Clickthrough Data Reflect Retrieval Quality?, Radlijnski+, CIKM'08 #InformationRetrieval #Online/Interactive #WSDM Issue Date: 2018-01-01 Fast Learning of Document Ranking Functions with the Committee Perceptrion, Elsas+, WSDM'08 #InformationRetrieval #ListWise #Pocket #ICML Issue Date: 2018-01-01 Listwise Approach to Learning to Rank - Theory and Algorithm （ListMLE）, Xia+, ICML'2008 #InformationRetrieval #ListWise #ICML #Admin'sPick Issue Date: 2018-01-01 Learning to Rank: From Pairwise Approach to Listwise Approach （ListNet）, Cao+, ICML'2007 Comment解説スライド：http://www.nactem.ac.uk/tsujii/T-FaNT2/T-FaNT.files/Slides/liu.pdf
解説ブログ：https://qiita.com/koreyou/items/a69750696fd0b9d88608従来行われてきたLearning to Rankはpairwiseな手法が主流であったが、pairwiseな手法は2つのインスタンス間の順序が正しく識別されるように学習されているだけであった。
pairwiseなアプローチには以下の問題点があった：
インスタンスのペアのclassification errorを最小化しているだけで、インスタンスのランキングのerrorを最小化しているわけではない。
インスタンスペアが i.i.d な分布から生成されるという制約は強すぎる制約
queryごとに生成されるインスタンスペアは大きく異なるので、インスタンスペアよりもクエリに対してバイアスのかかった学習のされ方がされてしまう
これらを解決するために、listwiseなアプローチを提案。
listwiseなアプローチを用いると、インスタンスのペアの順序を最適化するのではなく、ランキング全体を最適化できる。
listwiseなアプローチを用いるために、Permutation Probabilityに基づくloss functionを提案。loss functionは、2つのインスタンスのスコアのリストが与えられたとき、Permutation Probability Distributionを計算し、これらを用いてcross-entropy lossを計算するようなもの。
また、Permutation Probabilityを計算するのは計算量が多すぎるので、top-k probabilityを提案。
top-k probabilityはPermutation Probabilityの計算を行う際のインスタンスをtop-kに限定するもの。
論文中ではk=1を採用しており、k=1はsoftmaxと一致する。
パラメータを学習する際は、Gradient Descentを用いる。k=1の設定で計算するのが普通なようなので、普通にoutputがsoftmaxでlossがsoftmax cross-entropyなモデルとほぼ等価なのでは。 #InformationRetrieval #PairWise #ICML #Admin'sPick Issue Date: 2018-01-01 Learning to Rank using Gradient Descent （RankNet）, Burges+, ICML'2005 Commentpair-wiseのlearning2rankで代表的なRankNet論文
解説ブログ：https://qiita.com/sz_dr/items/0e50120318527a928407
lossは2個のインスタンスのpair、A, Bが与えられたとき、AがBよりも高くランクされる場合は確率1, AがBよりも低くランクされる場合は確率0、そうでない場合は1/2に近くなるように、スコア関数を学習すれば良い。 #InformationRetrieval #PointWise #NeurIPS #Admin'sPick Issue Date: 2018-01-01 PRanking with Ranking, Crammer+, NIPS'01 CommentPoint-WiseなLearning2Rankの有名手法 #Article #Tools #InformationRetrieval #Online/Interactive Issue Date: 2018-01-01 Lerot: Online Learning to rank Framework #Article #Survey #InformationRetrieval #Online/Interactive Issue Date: 2018-01-01 Fast and Reliable Online Learning to Rank for Information Retrieeval, Katja Hofmann, Doctoral Thesis, 2013 #Article #InformationRetrieval #ListWise Issue Date: 2018-01-01 A General Approximation Framework for Direct Optimization of Information Retrieval Measures （ApproxAP, ApproxNDCG）, Qin+, Information Retrieval, 2010 Comment実装してみたが、バグありそう感・・・
https://github.com/AkihikoWatanabe/ApproxAP #Article #InformationRetrieval #PairWise #NeurIPS Issue Date: 2018-01-01 Large Scale Learning to Rank, Sculley+, NIPS 2009 Commentsofia-mlの実装内容について記述されている論文
よくonline学習の文脈で触れられるが、気をつけないと罠にはまる。
というのは、sofia-ml内のMethodsによって、最適化している目的関数が異なるからだ。
実装をみると、全てのmethodsがonlineでできちゃいそうに見える（学習済みのモデルをinputして学習を再開させられるため）が、落とし穴。
まず、SGD SVM, Pegasos SVM,については、最適化している目的関数がbatchになっているため、online learningではない。
passive-aggressive perceptrionは目的関数が個別の事例に対して定式化される(要確認)のでonline learningといえる。
(ROMMAは調べないとわからん)
pairwiseのlearning to rankでは、サンプルのペアを使って学習するので、最悪の場合O(n^2)の計算量がかかってしまってめっちゃ遅いのだが、実は学習データを一部サンプリングして重みを更新するってのをたくさん繰り返すだけで、高速に学習できちゃうという話。
実際、sofia-mlを使って見たら、liblinearのranking SVM実装で40分かかった学習が数秒で終わり、なおかつ精度も良かった。
#Article #Tutorial #InformationRetrieval Issue Date: 2018-01-01 From RankNet to LambdaRank to LambdaMART: An Overview, Burges, Microsoft Research Technical Report, 2010 #Article #Tutorial #InformationRetrieval #Slide Issue Date: 2018-01-01 Confidence Weightedでランク学習を実装してみた, 徳永拓之, 第4回 自然言語処理勉強会@東京 #Article #Tutorial #InformationRetrieval #Slide Issue Date: 2018-01-01 ランキング学習ことはじめ, DSIRNLP#1, 2011 #Article #Survey #InformationRetrieval Issue Date: 2018-01-01 Learning to Rank for Information Retriefval, Liu+, 2009