riix.models.melo

  1"""Multidimensional Elo"""
  2import math
  3import numpy as np
  4from riix.core.base import OnlineRatingSystem
  5from riix.models.elo import Elo
  6from riix.utils.math_utils import sigmoid
  7
  8
  9def generate_orthogonal_matrix(d, k):
 10    # Constraint check
 11    if d > k + 1:
 12        raise ValueError('d must be less than or equal to k + 1')
 13
 14    # Initialize the matrix with zeros
 15    matrix = np.zeros((d, k))
 16
 17    # Generate a base pattern
 18    base_pattern = np.array([1.0, -1.0] * (k // 2) + [1.0] * (k % 2))
 19
 20    # Fill the first d-1 rows
 21    for i in range(d - 1):
 22        shift = i % k  # Calculate the shift for the pattern
 23        matrix[i] = np.roll(base_pattern, shift)
 24
 25    # Fill the d-th row
 26    matrix[-1] = -np.sum(matrix[:-1], axis=0)
 27    return matrix
 28
 29
 30class Melo(Elo):
 31    """Multidimensional Elo rating system, (good for rock paper scissors problems)"""
 32
 33    rating_dim = 1
 34
 35    def __init__(
 36        self,
 37        competitors: list,
 38        initial_rating: float = 1500.0,
 39        dimension: int = 1,  # this is the k in melo_2k, not sure why they had to use that letter when it's already used in Elo smh
 40        eta_r: float = 32.0,  # this is the normal elo k factor
 41        eta_c: float = 0.125,  # 1 is bad: https://dclaz.github.io/mELO/articles/03_noise.html#simulations-1
 42        alpha: float = math.log(10.0) / 400.0,
 43        update_method: str = 'online',
 44        dtype=np.float64,
 45    ):
 46        OnlineRatingSystem.__init__(self, competitors)
 47        self.eta_r = eta_r
 48        self.eta_c = eta_c
 49        self.alpha = alpha
 50        self.ratings = np.zeros(shape=self.num_competitors, dtype=dtype) + initial_rating
 51        two_k = 2 * dimension
 52        self.c = generate_orthogonal_matrix(d=two_k, k=self.num_competitors).T # / 10.0
 53
 54        # rng = np.random.default_rng(42)
 55        # self.c = rng.uniform(low=-1.0, high=1.0, size=(num_competitors, two_k))
 56
 57        self.omega = np.zeros((two_k, two_k), dtype=np.int32)
 58        # Set every other off-diagonal element to 1 or -1
 59        self.omega[np.arange(0, two_k - 1, 2), np.arange(1, two_k, 2)] = 1  # Upper off diagonal
 60        self.omega[np.arange(1, two_k, 2), np.arange(0, two_k - 1, 2)] = -1  # Lower off diagonal
 61
 62        if update_method == 'batched':
 63            self.update = self.batched_update
 64        if update_method == 'online':
 65            self.update = self.online_update
 66
 67        self.cache = {'probs': None, 'c_1_times_omega': None}
 68
 69    def get_pre_match_ratings(self, matchups, **kwargs):
 70        return self.ratings[matchups]
 71
 72    def predict(self, matchups: np.ndarray, set_cache: bool = False, **kwargs):
 73        """generate predictions"""
 74        ratings_1 = self.ratings[matchups[:, 0]]
 75        ratings_2 = self.ratings[matchups[:, 1]]
 76        c_1 = self.c[matchups[:, 0], None, :]  # [bs, 1, 2k]
 77        c_2 = self.c[matchups[:, 1], :, None]  # [bs, 2k, 1]
 78        elo_diff = ratings_1 - ratings_2
 79        c_1_times_omega = np.matmul(c_1, self.omega)
 80        melo_diff = np.matmul(c_1_times_omega, c_2)[:, 0, 0]
 81        probs = sigmoid(self.alpha * (elo_diff + melo_diff))
 82        if set_cache:
 83            self.cache['probs'] = probs
 84            self.cache['c_1_times_omega'] = c_1_times_omega.squeeze(axis=1)
 85
 86        return probs
 87
 88    def batched_update(self, matchups, outcomes, time_step=None, use_cache=False):
 89        """apply one update based on all of the results of the rating period"""
 90        active_in_period = np.unique(matchups)
 91        masks = np.equal(matchups[:, :, None], active_in_period[None, :])  # N x 2 x active
 92
 93        c_1 = self.c[matchups[:, 0], :]  # [bs, 2k]
 94        c_2 = self.c[matchups[:, 1], :]  # [bs, 2k]
 95
 96        if use_cache:
 97            probs = self.cache['probs']
 98            dp_dc_2 = self.cache['c_1_times_omega']
 99        else:
100            probs = self.predict(time_step=None, matchups=matchups, set_cache=False)
101            dp_dc_2 = np.matmul(c_1, self.omega)
102
103        per_match_diff = (outcomes - probs)[:, None]
104        per_match_diff = np.hstack([per_match_diff, -per_match_diff])
105        per_competitor_diff = (per_match_diff[:, :, None] * masks).sum(axis=(0, 1))
106
107        dp_dc_1 = np.matmul(c_2, self.omega)
108        dp_dc = np.stack([dp_dc_1, -1.0 * dp_dc_2], axis=1)
109        c_updates = self.eta_c * per_match_diff[:, :, None] * dp_dc
110        c_updates_pooled = (c_updates[:, :, None] * masks[:, :, :, None]).sum(axis=(0, 1))
111
112        self.ratings[active_in_period] += self.eta_r * per_competitor_diff
113        self.c[active_in_period] += c_updates_pooled
114
115    def online_update(self, matchups, outcomes, use_cache=False, **kwargs):
116        """treat the matchups in the rating period as if they were sequential"""
117        for idx in range(matchups.shape[0]):
118            comp_1, comp_2 = matchups[idx]
119            elo_diff = self.ratings[comp_1] - self.ratings[comp_2]
120            c_1 = self.c[comp_1]
121            c_2 = self.c[comp_2]
122
123            melo_diff = np.dot(c_1, np.dot(self.omega, c_2)).item()
124            prob = sigmoid(self.alpha * (elo_diff + melo_diff))
125            delta = outcomes[idx] - prob
126
127            rating_update = self.eta_r * delta
128
129            self.ratings[comp_1] += rating_update
130            self.ratings[comp_2] -= rating_update
131
132            dp_dc_1 = np.dot(self.omega, c_2).flatten()
133            dp_dc_2 = np.dot(self.omega, c_1).flatten()
134
135            self.c[comp_1] += self.eta_c * delta * dp_dc_1
136            self.c[comp_2] -= self.eta_c * delta * dp_dc_2