賭波的初哥方式－Elo Rating System 的理解

之前在未了解背後數學之前先嘗試個應用。今個周未有空就來了解一下Elo Rating System背後是什麼理論，和如何得出那樣的公式了。

Part A）機率
先來看看「邏輯函数」Logistic Function。在很多地方都會看到它的身影，例如物種的人口增長，統計學上的對True/False這類二元結果的回歸分析。

「邏輯函数」 有這樣的一般型式：$$y = \frac{L}{ 1 + e^{-k(x-x_0)} }$$
$e$  ：自然對數
$x_0$：x 的中間值
$L$  ：y 的最大值
$k$  ：斜度

例子一：Standard Logistic Function：$y = \frac{1}{1 + e^{-x}}$
例子二：國際象棋界 USCF 的 Elo rating system 的勝率期望值：$y = \frac{1}{1 + 10^{-\frac{1}{400}(r_A-r_B)}}$

我們考慮代入的是「分數差」（甲的分數－乙的分數）， 即是$x=(r_A-r_B)$，$x_0=0$。一個函數可以作為「分數」 與「勝負機率」的轉換，大概很多$\mathbb{R} \to (0,1)$ 的函數都可以做到。而這「邏輯函数」還有以下特質：：

• 這函數可以輸入實數的「分數差」，而輸出0到1之間的機率值；而且數值是不斷上升的，所以差異愈大，贏（輸）機率就愈大。（這兩個特質就適合用來作"分數差" 和"輸贏機率"之間的轉換）
• 零作為中間點是反向對稱的 $Pr(x)=1-Pr(-x)$，高分方的勝率等於低分方的負率。當雙方實力相等，也就是"分數差"在等於零的時候，輸贏的機率是0.5。
• 而差異愈接近零的時候機率的變化的速度較大；但差異愈大的時候，這個機率的變化速度就愈不明顯。（這個有點像經濟學上「邊際效益遞減」的概念，現實上有點猶豫）

「邏輯函数」 在統計模型的重要性在於與「邏輯迴歸」Logistic Regression 的關係。

Logistic Regression Model與一般的「簡單線性迴歸」 Ordinary Linear Regression都是屬於GLM的其中一員，分別在於對「應變數」Dependent Variable的分佈，和所謂的「連結函數」Link Function有不同假設。Logistic Regression Model中，Y 的分佈是要配合"勝／負"這類二元結果， 連結函數的不同就得出機會率可以寫成Logistic Function的形式。Logistic Regression ：
$$logit( E [Y | X] ) = ln(\frac{p}{1-p}) = \beta X$$
對觀察值Y的分佈假設為 $Y \sim Binomial (1 , p) $。上式經過移項後會得到：$p = \frac{1}{1 + e^{-\beta X}}$，也就是開始時所見的Logistic Function的形式。

終於，我們回來看看Elo Ratings中的機率公式:
$$S_{expect} = \frac{1}{1 + 10^{-\frac{1}{400}(r_A-r_B)}}$$

1. 從 $e$ 變成 10的次方：因為  $10^x   =  {e^{ln(10)}}^x  =e^{ln(10)x} $，這只是在$k$值的影響。
2. $k$：1/400，這個斜度是雙方選手的分數差如何轉換到 0-1的比例上。例如當同樣估計為A勝B，但估計的機率是60%還是70%就是這k值影響到。在線性回歸中我們會用OLS的方法去求取參數，在 Logistic Regression中參數是用「最大似然估計」Maximum Likelihood Estimation (MLE)找出來。
3. $r_A, r_B$：選手的分數，這裡並不是一個可以直接觀察到的自變數，如何得出這分數就是Elo Rating 的另一重要部份。

**所以，簡單而言Elo Ratings 就是一套Logistic Regression model，（還有加上選手的評分方式，和如何不斷更新分數）**


Part B）分數
每名棋手會有一個初始分數$r_0$，然隨著實際對賽的結果，用以下公式更新棋手成積：

$$r_{post} = r_{pre} + K (S_{actual} - S_{expect})$$
$r_{post}$：對賽後棋手經調整後的分數。
$r_{pre}$：對賽前棋手原來的分數。
$S_{actual}$：實際結果，簡單可以設定：贏=1分，輸=0分，和=0.5分。
$S_{expect}$：預期結果，就是PartA計算甲會贏的機率公式。
$K$：這一般稱作attenuation factor，是調整新結果的影響和原有分數之間的比重。
一般會有這些考慮：假設比賽結果對新手影響較大，假設重要比賽的影響較大。

因為兩個等級的選手對賽，可以預期分數高的有較大贏面。棋手的分數要值得調整，他應該要表現得超越自己原有等級所預期的水準。Elo Rating更新分數的公式的設計就是為了達到這個效果。

另外，例如有 1200分的棋手A 和 1000分的棋手B 比賽：A，B的預期贏面分別算出是76%, 24%。 A勝出只會增加$0.24K$的分數，B勝出卻會增加$0.74K$的分數。所以：贏（輸）了該贏（輸）的比賽，分數不會有大幅調整；但如果出現戲劇性的結果，分數的調整就會較大。

Part C）應用
這套Elo Rating System在以下幾方面都有被應用：
遊戲：
    League Of Legends
http://leagueoflegends.wikia.com/wiki/Elo_rating_system

國際象棋界：
    World Chess Federation (FIDE)
https://www.fide.com/fide/handbook.html?id=172&view=article

足球：
    World Football Elo Ratings
http://www.eloratings.net/system.html

    FIFA Women's World Rankings
http://www.fifa.com/worldranking/procedureandschedule/womenprocedure/index.html
http://resources.fifa.com/mm/document/fifafacts/r%26a-wwr/52/00/99/fs-590_06e_wwr-new.pdf

     Footballdatabase.com (雖然無提供背後的模型，但如果沒有數據作自行測試的話也可以一看)
http://footballdatabase.com/ranking/europe/1

因為各方面的比賽有不同特質，所以模型參數略有不同。用以上的 FIFA Women’s World Ranking (WWR) 的模型去看足球方面的實際運作（這裡修改了官方符號方便表示）：
$$S_{expect} = 1 / (1 + 10^{x/2})$$
$$ r_{new}  = r_{old}  +  K ( S_{actual} - S_{expect} )$$

文件中稱當中 $x = [r_A - r_B] / (\text{scaling factor})$。scaling factor是為了令新隊伍從1000分開始；對賽中每100分的差距做成64%的的機會勝出。用Excel模擬一下會得到它的scaling factor = -200，所以一樣是這條式：$S_{expect} = 1 / (1 + 10^{-\frac{1}{400}(r_A-r_B)})$

• 它們對模型的修改上考慮到入球數目的不同：

• 主場的優勢：主隊加100分

"A glance at the historical results shows that teams perform better at home than away; the home teams keep 66% of the points, while the opponents return home with 34%. To neutralise this effect, a correction is made by enhancing the rating of the home team by a value of 100 points (corresponding to 64%)."

• 對於賽事重要性：

• 參考的時間歷史：45年的比賽紀錄，在評分的角度上還可以接受，但我覺得對勝負機會率的目的來說就太多。現在的球隊隊員跟好幾年前的早就不同了吧。

"Solid foundation: some 6500 games since 1971"

• 開始評分所需的數據：其實我覺得這套方式比較適合LOL遊戲平台上的計分，那時每次分數更新反映的是一個學習過程。但在象棋／足球這類大量練習，然後參加一場聯賽的情況中，每次分數更新就像是尋求反映真正實力的過程，這就要有足夠對實往績能達到效果。事實上，也因為Logistic Regression 的參數是用到MLE的方法，一般需要的樣本數也要較大。

"The ranking of a team is deemed official when：They have played at least 5 matches against teams with an official ranking. etc..."

－－－－－－－－－－－－
最後一部份，我是懷疑是否有關的，是這套評分和Exponential Distribution的關係。
因為：$A, B \sim Exp(1)  \Rightarrow   x_0 - \beta ln(A/B) \sim Logistic(x_0, \beta)$

設$R_A, R_B \sim Exp(\dot)$   A,B 是某種實力的量度。Exponential distribution 的圖明顯與Normal Distribution 不同的，它假設選手的$R_A, R_B$ 大多是在低實力區，高手則愈來愈少。它還有一個特點，是分佈上的「無記憶性質」（Memoryless)：$Pr(X>m+n|X>m) = Pr(X>n)$ 。對給定的任意一個參考分數而言，比你高同樣n級的比例是一樣的。用一個效果比喻：無論是在哪一級的角色，在下一個等級之前，總是有面前的人當中最弱的3%等著你去超越。
( 以$Exp(1/30)$為例。平均等級是30級。R：pexp(1, rate=1/30) )

設$R_a=ln(R_A), R_b=ln(R_B)$ 。用$ln()$將實力的比例尺轉變成方便比較的分數，$log()$這個運算的起源，是當年在未有計算機的發明之前，有一樣叫對數表的工具，為了方便計算大數的乘法。
$a-b = ln(exp(Ra-Rb)) = ln(exp(Ra)/exp(Rb)) = ln(A/B) \sim Logistic(0,1)$
這就得出分數差會符合Logistic Distribution.

但這是否有什麼意義呢？未想清楚。。。
－－－－－－－－－－－－