8

假设:

  • 团队从未改变
  • 球队的技术没有提高
  • 每个团队与其他团队的某些子集的表现的整个历史是已知的
  • 球队之间的比赛数量很多,但可能很少(每支球队都没有与其他球队交手)

例如:

我有一长串比赛结果,如下所示:

Team A beats Team B
Team B beats Team A
Team A beats Team B
Team C beats Team A
Team A beats Team C

问题:

预测任何球队击败任何其他球队的正确投注赔率。

在上面的例子中,也许我们得出的结论是 A 应该在 66% 的时间内击败 B。这是基于直接观察并且非常简单。然而,找到 C 击败 B 的概率似乎更难。他们从来没有一起玩过,但似乎最有可能 C > B,信心不足。

我做过的研究:

我已经阅读了一些关于技巧游戏的不同排名系统的文章,例如国际象棋的 Elo 和 Glicko 评级系统。这些不足,因为它们对所涉及的概率分布做出假设。例如,Elo 的中心假设是每个棋手在每场比赛中的国际象棋表现是一个正态分布的随机变量。但是,根据维基百科,还有其他分布更适合现有数据。

我不想假设分布。在我看来,手头有 10,000 多个匹配结果,我应该能够从证据中推断出分布(我不知道该怎么做),或者使用某种无关紧要的强化学习方案分布是什么。

4

7 回答 7

6

您希望对概率(或多个概率)做出最佳估计,并随着更多数据的可用不断更新您的估计。这需要贝叶斯推理!贝叶斯推理是基于这样的观察,即 A 和 B 两件事同时成为情况的概率(分布)等于 A 成为情况的概率(分布),因为 B 是情况乘以概率那B就是这样。以公式形式:

P(A,B) = P(A|B)P(B)

并且

P(A,B) = P(B|A)P(A)

因此

P(A|B)P(B) = P(B|A)P(A)

将 P(B) 带到另一边,我们得到贝叶斯更新规则

P(A|B)' = P(B|A)P(A)/P(B)

通常,A 代表您试图估计的任何变量(例如“团队 x 击败团队 y”),而 B 代表您的观察结果(例如,团队之间赢球和输球的完整历史记录)。我写了素数(即P(A|B)'中的引号)来表示等式的左手代表你的信念的更新。具体来说,在给定到目前为止的所有观察结果的情况下,您对 x 团队击败 y 团队的概率的新估计是在给定您之前的估计的情况下进行这些观察的概率乘以您之前的估计值,除以您看到的观察结果的总体概率(即没有假设球队之间的相对实力;一支球队大部分时间获胜的可能性低于两支球队获胜的概率相同)。

当前更新左侧的 P(A|B)' 成为下一次更新右侧的新 P(A)。随着更多数据的进入,您只需不断重复此操作。通常,为了尽可能不偏不倚,您从 P(A) 的完全平坦分布开始。随着时间的推移,P(A) 将变得越来越确定,尽管该算法能够很好地处理您试图估计的潜在概率的突然变化(例如,如果团队 x 突然变得更强大,因为有新玩家加入团队)。

好消息是贝叶斯推理在ElKamina 也提到的beta 分布中效果很好。事实上,这两者经常结合在旨在学习概率分布的人工智能系统中。虽然 beta 分布本身仍然是一个假设,但它的优势在于它可以采用多种形式(包括完全平坦和极度尖峰),因此相对而言没有理由担心您选择的分布可能会影响您的结果。

一个坏消息是,除了 beta 分布之外,您仍然需要做出假设。例如,假设您有以下变量:

A: x 队击败 y 队

B:y队击败z队

C:x队击败z队

并且您可以从 x 和 y 之间的直接匹配以及 y 和 z 之间的匹配中观察到,但从 ​​x 和 z 之间的匹配中没有观察到。估计 P(C) 的一种简单(尽管幼稚)的方法可能是假设传递性:

P(C) = P(A)P(B)

无论您的方法多么复杂,您都必须定义某种概率结构来处理数据中的差距和相互依赖性。无论您选择何种结构,它始终是一个假设。

另一个坏消息是这种方法非常复杂,我无法完整说明如何将其应用于您的问题。鉴于您需要一个相互依赖的概率结构(在涉及团队 x、y 和 z 的其他分布的情况下,团队 x 击败团队 y 的概率),您可能希望使用贝叶斯网络或相关分析(例如马尔可夫随机场路径分析)。

我希望这有帮助。无论如何,请随时要求澄清。

于 2014-11-13T21:57:18.210 回答
2

我们需要做一些假设,从下面的例子可以看出:

Team Rock beats Team Scissors
Team Paper beats Team Rock
Team Rock beats Team Scissors

现在我们有剪刀队和纸队之间的战斗。由于 Paper 队击败了 Team Rock,后者又两次击败了 Scissors 队,我们可以假设最好的赔率是 Paper 击败 Scissors。

然而,在上面我们假设了一个传递模型,这显然是不适用的。它可能更适合足球等某些运动,但仍不完全适合。

ELO 所做的是假设所有团队都具有某种“内在力量”,范围从0infinity。很明显,没有任何技能能像这样真正发挥作用,但事实证明它是预测游戏的有用模型。另请注意,此模型不适用于 Rock、Paper、Scissors 游戏。

国际象棋中的下一个假设是,“固有实力”的绝对差异创建了一个玩家击败另一个玩家的可能性的概率分布。同样,这显然是不正确的,因为诸如白/黑棋子也参与其中。但是,通过查看多场比赛的获胜机会可以使其更加精确(显示证据)。

通过以上两个假设,我们可以计算获胜机会,如果模型结果非常适合游戏,它们可能相当精确。不幸的是,这种建模不是一门精确的科学,无论您做出什么假设,您总能找到不适用的游戏/情况。

我希望这能给你一些灵感,让你为你的模型提出更多假设 :) 一旦你有了它们,你就可以测试它的工作情况,看看它是否可以预测你在训练集中已经得到的一些结果。有一整个世界的机器学习和统计文献供您欣赏:)

于 2014-11-11T22:30:02.163 回答
2

评级百分比指数 - 在下面的 C# 中实现:

// <copyright file="RPICalculator.cs" company="Steve Stokes Consulting, LLC">
//  Copyright © Steve Stokes Consulting, LLC. All Rights Reserved.
// </copyright>

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RPI.Calculator
{
    public class RPICalculator
    {
        public void Test()
        {
            //Home      Score   Away        Score
            //UConn     64      Kansas      57
            //UConn     82      Duke        68
            //Minnesota 71      UConn       72
            //Kansas    69      UConn       62
            //Duke      81      Minnesota   70
            //Minnesota 52      Kansas      62

            //resulting in the following ratings:
            //UConn: 0.6660
            //Kansas: 0.6378
            //Duke: 0.3840
            //Minnesota: 0.3403

            List<Team> Teams = new List<Team>();
            List<Match> Matches = new List<Match>();

            Teams.Add(new Team()
            {
                Name = "UConn",
            });
            Teams.Add(new Team()
            {
                Name = "Kansas",
            });
            Teams.Add(new Team()
            {
                Name = "Duke",
            });
            Teams.Add(new Team()
            {
                Name = "Minnesota",
            });

            Matches.Add(new Match()
            {
                HomeTeam = Teams.Where(t => t.Name == "UConn").First(),
                AwayTeam = Teams.Where(t => t.Name == "Kansas").First(),
                Winner = Teams.Where(t => t.Name == "UConn").First(),
            });
            Matches.Add(new Match()
            {
                HomeTeam = Teams.Where(t => t.Name == "UConn").First(),
                AwayTeam = Teams.Where(t => t.Name == "Duke").First(),
                Winner = Teams.Where(t => t.Name == "UConn").First(),
            });
            Matches.Add(new Match()
            {
                HomeTeam = Teams.Where(t => t.Name == "Minnesota").First(),
                AwayTeam = Teams.Where(t => t.Name == "UConn").First(),
                Winner = Teams.Where(t => t.Name == "UConn").First(),
            });
            Matches.Add(new Match()
            {
                HomeTeam = Teams.Where(t => t.Name == "Kansas").First(),
                AwayTeam = Teams.Where(t => t.Name == "UConn").First(),
                Winner = Teams.Where(t => t.Name == "Kansas").First(),
            });
            Matches.Add(new Match()
            {
                HomeTeam = Teams.Where(t => t.Name == "Duke").First(),
                AwayTeam = Teams.Where(t => t.Name == "Minnesota").First(),
                Winner = Teams.Where(t => t.Name == "Duke").First(),
            });
            Matches.Add(new Match()
            {
                HomeTeam = Teams.Where(t => t.Name == "Minnesota").First(),
                AwayTeam = Teams.Where(t => t.Name == "Kansas").First(),
                Winner = Teams.Where(t => t.Name == "Kansas").First(),
            });

            var results = Calculate(Teams, Matches, Sport.NCAA_Basketball);

            foreach (var team in results)
            {
                Debug.WriteLine(string.Format("{0} - {1}", team.Name.PadRight(Teams.Select(t => t.Name).Max(s => s.Length)), team.RPI));
            }
        }

        private decimal defaultHomeWinValue = 1.0m;
        private decimal defaultAwayWinValue = 1.0m;
        private decimal homeWinValue = 1.0m;
        private decimal awayWinValue = 1.0m;

        public IEnumerable<TTeam> Calculate<TTeam, TMatch>(IEnumerable<TTeam> Teams, IEnumerable<TMatch> Matches, Sport Sport)
        {
            // TODO: transform a user team to our internal team type
        }

        /// <summary>
        /// Calculate the RPI of each team
        /// </summary>
        /// <param name="Teams">The list of teams to calculate RPI for</param>
        /// <param name="Matches">The list of matches and results of the matches the teams played in a period</param>
        /// <param name="Sport">The sport the teams played - this modifies home/away weighting based on NCAA rules</param>
        /// <returns>The list of teams with calculated RPI's</returns>
        public IEnumerable<Team> Calculate(IEnumerable<Team> Teams, IEnumerable<Match> Matches, Sport Sport)
        {
            SetWeightingBasedOnSport(Sport);

            foreach (var team in Teams)
            {
                // calculate the WP of each team
                team.WP = CalculateWinPercent(team, Matches, homeWinValue, awayWinValue);

                // calculate the OWP of each team
                team.OWP = CalculateOpponentsWinPercent(team, Matches);

                // calculate the OOWP of each team
                team.OOWP = CalculateOpponentsOpponentsWinPercent(team, Teams, Matches);

                // calculate the RPI for each team
                team.RPI = CalculateRPI(team);
            }

            return Teams.OrderByDescending(t => t.RPI);
        }

        private decimal CalculateRPI(Team team)
        {
            //RPI = (WP * 0.25) + (OWP * 0.50) + (OOWP * 0.25)

            //UConn: 0.6660
            //Kansas: 0.6378
            //Duke: 0.3840
            //Minnesota: 0.3403

            var RPI = (team.WP * 0.25m) + (team.OWP * 0.50m) + (team.OOWP * 0.25m);

            return Math.Round(RPI, 4);
        }

        private decimal CalculateOpponentsOpponentsWinPercent(Team teamInQuestion, IEnumerable<Team> Teams, IEnumerable<Match> Matches)
        {
            //UConn: ((Kansas 0.6667) + (Kansas 0.6667) + (Duke 0.3333) + (Minnesota 0.3889)) / (4 games) = 0.5139
            //Kansas: ((UConn 0.7500) + (UConn 0.7500) + (Minnesota 0.3889)) / (3 games) = 0.6296
            //Duke: ((UConn 0.7500) + (Minnesota 0.3889)) / (2 games) = 0.5694
            //Minnesota: ((UConn 0.7500) + (Duke 0.3333) + (Kansas 0.6667)) / (3 games) = 0.5833

            // get each team i've played this season (not unique)
            var teamsIvePlayed = Matches.Where(m => m.AwayTeam == teamInQuestion || m.HomeTeam == teamInQuestion).Select(s => s.HomeTeam == teamInQuestion ? s.AwayTeam : s.HomeTeam);

            // get the opponent win percent (OWP) of each team I played
            var teamsIvePlayedOpponentWinPercent = teamsIvePlayed.Select(t => new { Team = t, OWP = CalculateOpponentsWinPercent(t, Matches) });

            // calculate the OOWP
            return (decimal)(teamsIvePlayedOpponentWinPercent.Sum(t => t.OWP) / teamsIvePlayed.Count());
        }

        private decimal CalculateOpponentsWinPercent(Team teamInQuestion, IEnumerable<Match> Matches)
        {
            // get each teams WP without the team in question

            //Home      Score   Away        Score
            //UConn     64      Kansas      57
            //UConn     82      Duke        68
            //Minnesota 71      UConn       72
            //Kansas    69      UConn       62
            //Duke      81      Minnesota   70
            //Minnesota 52      Kansas      62

            //UConn: ((Kansas 1.0) + (Kansas 1.0) + (Duke 1.0) + (Minnesota 0)) / (4 games) = 0.7500
            //Kansas: ((UConn 1.0) + (UConn 1.0) + (Minnesota 0.0)) / (3 games) = 0.6667
            //Duke: ((UConn 0.6667) + (Minnesota 0.0)) / (2 games) = 0.3333
            //Minnesota: ((UConn 0.6667) + (Duke 0.0) + (Kansas 0.5)) / (3 games) = 0.3889

            // get each team i've played this season (not unique)
            var teamsIvePlayed = Matches.Where(m => m.AwayTeam == teamInQuestion || m.HomeTeam == teamInQuestion).Select(s => s.HomeTeam == teamInQuestion ? s.AwayTeam : s.HomeTeam);

            // get the win percent of each team I played excluding matches with me
            var teamsIvePlayedWinPercent = teamsIvePlayed.Select(t => new 
            { 
                Team = t, 
                WP = CalculateWinPercent(t, Matches.Where(m => m.AwayTeam != teamInQuestion && m.HomeTeam != teamInQuestion), defaultHomeWinValue, defaultAwayWinValue) 
            });

            // calculate the OWP
            return (decimal)(teamsIvePlayedWinPercent.Sum(t => t.WP) / teamsIvePlayed.Count());
        }

        private decimal CalculateWinPercent(Team teamInQuestion, IEnumerable<Match> Matches, decimal HomeWinValue, decimal AwayWinValue)
        {
            // get the teams win percent - sometimes weighted based on NCAA rules

            //UConn: (0.6 + 0.6 + 1.4 + 0) / (0.6 + 0.6 + 1.4 + 1.4) = 0.6500
            //Kansas: (0 + 0.6 + 1.4) / (1.4 + 0.6 + 1.4) = 0.5882
            //Duke: (0 + 0.6) / (1.4 + 0.6) = 0.3000
            //Minnesota: (0 + 0 + 0) / (0.6 + 1.4 + 0.6) = 0.0000

            // get my wins and sum with weighting
            var wins = Matches.Where(m => m.Winner == teamInQuestion).Sum(s => s.HomeTeam == teamInQuestion ? HomeWinValue : AwayWinValue);

            // get my games played count weighted
            var gamesPlayed = Matches.Where(m => m.HomeTeam == teamInQuestion || m.AwayTeam == teamInQuestion).Sum(s => s.HomeTeam == teamInQuestion ? HomeWinValue : AwayWinValue);

            // get the WP
            return wins / gamesPlayed;
        }

        private void SetWeightingBasedOnSport(Sport Sport)
        {
            switch (Sport)
            {
                case Sport.NCAA_Basketball:
                    homeWinValue = 0.6m;
                    awayWinValue = 1.4m;
                    break;
                case Sport.NCAA_Baseball:
                    homeWinValue = 0.7m;
                    awayWinValue = 1.3m;
                    break;
                default:
                    homeWinValue = defaultHomeWinValue;
                    awayWinValue = defaultAwayWinValue;
                    break;
            }
        }
    }

    public enum Sport
    {
        NoHomeOrAwayWeighting = 1,
        NCAA_Basketball = 2,
        NCAA_Baseball = 3,
    }

    public class Team
    {
        public string Name { get; set; }
        public decimal RPI { get; internal set; }
        public decimal WP { get; internal set; }
        public decimal OWP { get; internal set; }
        public decimal OOWP { get; internal set; }
    }

    public class Match
    {
        public Team HomeTeam { get; set; }
        public Team AwayTeam { get; set; }
        public Team Winner { get; set; }
    }
}
于 2014-12-03T21:50:23.557 回答
1

为什么不直接使用维基百科的评分百分比指数。您可以在那里找到更好的解释,但作为快速介绍,您使用以下公式:

RPI = (WP * 0.25) + (OWP * 0.50) + (OOWP * 0.25)

WP : Winning Percentage wins / games_played

OWP:通过取每个球队对手的 WP 平均值计算,并要求从计算中删除所有与相关球队的比赛

OOWP : 每个对手 OWP 的平均值。

Google Code Jam 也使用了这个问题。

希望算法能帮到你。

感谢维基百科。

于 2014-11-14T08:41:24.280 回答
0

您可以尝试应用http://en.wikipedia.org/wiki/Elo_rating_system,主要是基于其他人使用它来锻炼优势。然而,任何这样的系统实际上都是基于某种真实情况的概率模型,您最好尝试为您的特定游戏想出一个模型。例如,对于足球,一种方法是将球队的进球数建模为泊松过程,这取决于他们的进攻强度和对方的防守。一旦你有了一个模型,你就可以将它拟合到数据中,例如通过最大似然。

作为模型产生影响的示例,请查看http://en.wikipedia.org/wiki/Nontransitive_dice。这是一个简单的例子,A​​ 通常击败 B,B 通常击败 C,C 通常击败 A,这不是您所期望的简单一维强度系统。

于 2014-11-06T05:42:44.840 回答
0

===第一步===

假设 A 和 B 两支球队打了 n 场比赛,A 赢了 m 次。通过应用平坦的 beta 分布,A 下次获胜的概率为:(m+1)/(n+2)。

如您所见,如果 m 和 n 是大数,则它大致等于 m/n。

===第2步===

在您的情况下,我建议采用以下策略。

设 m = mp + md + mr 和 n = np + nd + nr

后缀 p 表示先验,d 表示直接,r 表示间接。

您可以将 mp 和 np 分别设置为 1 和 2(假设先验平坦)或以高级方式(在末尾详述)

md 和 nd 是胜利和游戏。

mr 和 nr 是通过某种策略计算的。

最终A获胜的概率为(mp+md+mr)/(np+nd+nr)。

===第三步===

如何计算mr和nr:

您可以使用某种阻尼。例如。如果 A def C 和 C def B,则将其视为 A 对 B 的 p 获胜。对于更长的链,使用指数衰减。

可以使用交叉验证来计算 p 的最佳值,其中您遗漏了数据的某些部分并使用最大化该遗漏数据的概率的 p。对于您的特定问题,我建议忽略一对之间的游戏,估计概率并与实际值进行比较。

您可以使用:k*log^2(s/t) 作为惩罚,其中 k 是左对 A 和 B 之间的游戏次数,s 是预测的,t 是 A 获胜的实际概率。您还可以使用诸如 KL 散度之类的东西。

===第四步===

重新访问设置 mp 和 np。

你需要在同一支球队之间进行多次多次对决才能解决这个问题。

对于每对团队计算获胜的概率并绘制它。如果它看起来平坦,使用 1 和 2 作为 mp 和 np 就可以了。否则通过http://en.wikipedia.org/wiki/Beta_distribution并选择最匹配的分布。

于 2014-11-12T01:36:37.893 回答
0

这个问题可以用有向图来解决。

让所有的队伍都是顶点,team1和team2之间的有向边意味着team1击败了team2。

完成后,您可以将图形划分为强连通分量,并独立处理每个连通分量,因为它们在统计上是独立的。还是他们?眨眼

我们要问的问题是,team1 击败 team2 的机会有多大

这很容易回答,如果您要比较的团队之间有直接匹配。在这种情况下,您只关心直接匹配;例如,team1 击败了 team2 多少次?你回答问题的方式;

(team1WinsAgainstTeam2)/(matchesPlayedBetweenThem)

它是否正确?当我们知道 teamB 与 teamX 打过 100 次并赢得了 100 次,但 teamX 总是击败 teamA 时,teamA 的机会是否应该减少?如果是,请放弃我在这篇文章中所说的一切:-)

最终算法应如下所示:

double getOddsTeam1Winning(int team1, int team2){

    if(!isInSameConnectedComponent(team1, team2)){
        // if two teams are not in the same
        // connected component,

        // we can use heuristic,
        // we'll compare how many matches has team1 won,
        // compared to team2.

        var team1Wins = (team1Wins - team1Loses);
        var team2Wins = (team2Wins - team2Loses);

        return team1Wins / (team1Wins + team2Wins);
    }

    if(isDirectMatchBetween(team1, team2)){
        return team1WinsOverTeam2/
            totalMatchesPlayedBetweenTeam1AndTeam2;
    }

    List<double> odds= new List<double>();

    foreach(var opponentTeam in teamsThatTeam1HasPlayedWith){

        var oddsThatOponentTeamBeatsTeam2 = getOddsTeam1Winning(opponentTeam, team2);
        var oddsThatTeam1BeatsOpponentTeam = getOddsTeam1Winning(team1, opponentTeam);

        // combine them &  push them to odds list
    }

    return odds.Average(); // taking average of odds?!
}

ps,我在几分钟内把它放在一起,不完全确定它在数学上是否正确,但我认为这将解决你列出的原始问题中的问题,至少有一个实例:p。

于 2014-11-17T17:09:21.627 回答