(this might be a 2 parter because way too much math lol)↵
↵
**How do you design a good rating system?** (focusing on 2-player games here, not CF)↵
↵
Conditional probability primer↵
------------------↵
↵
Suppose I have access to two coins.↵
↵
- Coin A: is a fair coin, lands heads or tails with 50% probability↵
- Coin B: is heads on both sides coin, lands heads or heads with 50% probability↵
↵
I choose one of them uniformly at random, flip it, and tell you I got heads. What's the chance I picked coin A and coin B, given that I got heads?↵
↵
You can imagine 4 possible worlds, all with 25% chance of occurring:↵
↵
- Coin A, lands heads (1)↵
- Coin A, lands tails (2)↵
- Coin B, lands heads (3)↵
- Coin B, lands heads (4)↵
↵
We're told we can be in world (1), (3), or (4), so there's a $\frac{1}{3}$ chance we picked coin A and a $\frac{2}{3}$ chance that we picked coin B.↵
↵
We write the probability of $A$ happening given event $B$ happened as $P(A | B)$.↵
↵
The chance of $A$ happening given event $B$ happened is:↵
↵
- $P(A \wedge B)$ — all the worlds where $A$ happened, but you can only count the ones where $B$ also happened, which is in our case (1) if you're after the first coin, or (3) and (4) if you're after the second coin.↵
- Divided by $P(B)$ — all the worlds where $B$ happened, which is in our case (1), (3), and (4), or 75%.↵
↵
Bayes' Theorem↵
------------------↵
↵
With some simple algebraic manipulation you can get↵
↵
$$P(A | B) = \frac{P(B|A) P(A)}{P(B)}.$$↵
↵
You can use this to do the famous disease testing "paradox". Suppose 1 in 1,000 people are infected with a disease $P(d) = 0.001$. Suppose you have a test that is 99% accurate: $P(+ | d) = 0.99, P(- | nod) = 0.99$.↵
↵
Then we have $P(+) = P(+ | d) P(d) + P(+ | nod) P(nod) = (0.99)(0.001) + (0.01)(0.999) = 0.01098$.↵
↵
And by Bayes' Theorem, if you test positive for the disease, you only actually have a↵
↵
$$P(d | +) = \frac{P(+ | d) P(d)}{P(+)} = \frac{0.99 \cdot 0.001}{0.01098} = 0.05902$$↵
↵
chance of having the disease.↵
↵
Bayesian Likelihood Estimation↵
------------------↵
↵
Consider a scenario where I have picked a coin with probability $p$ of being heads. You're told that $0 \le p \le 1$, and that $p$ is chosen in increments of 10%, so the only possible values are $0, 0.1, 0.2, ..., 0.9, 1$.↵
↵
Initially, I tell you that I have chosen the value of $p$ out of all 11 possible choices with equal probability.↵
↵
Now I flip the coin and it lands **heads**. This gives you more information — now you know it's probably more likely I chose a higher value of $p$. Can we quantify this?↵
↵
_The below illustration is simply an illustration — it's not perfectly rigorous but should hopefully be helpful for building intuition when I give you the formula later._↵
↵
Consider $1{,}100$ worlds:↵
↵
- $100$ worlds where $p=0$↵
- $100$ worlds where $p=0.1$↵
- ...↵
- $100$ worlds where $p=1$↵
↵
Then,↵
↵
- $0$ of $100$ worlds where $p=0$ will land heads↵
- $10$ of $100$ worlds where $p=0.1$ will land heads↵
- ...↵
- $100$ of $100$ worlds where $p=1$ will land heads↵
↵
Therefore, there are $550$ worlds where the coin lands heads. We're told we are in one of these $550$ worlds, so, for example, the chance of $p=0.1$ is $\frac{10}{550}$ and the chance of $p=1$ is $\frac{100}{550}$. You can see how higher values of $p$ are much more likely.↵
↵
_Okay, now let's formalize it._↵
↵
We're trying to estimate an unknown parameter $\theta$. It could be a probability, a mean, etc.↵
↵
Our **prior** is our initial belief about the parameter $\theta$. In our example above, it's a discrete probability distribution with $\frac{1}{11}$ chance for each of $0, 0.1, ..., 1$. The probability distribution could also be continuous.↵
↵
Our **likelihood** is the chance that, given a specific value of $\theta$, we get the outcome that we observed. For example, if we observe heads in the above example, the likelihood of observing heads with $p=0.4$ is 0.4. The likelihood of observing heads with $p=0.8$ is 0.8.↵
↵
Finally, we should end up with the **posterior** — the new, updated probability distribution of our belief about $\theta$. In our case, that was the chance of $p=0.1$ being $\frac{10}{550}$, etc.↵
↵
The formula is:↵
↵
$$\text{Posterior} = \text{Likelihood} \cdot \text{Prior}.$$↵
↵
(You do have to divide by the appropriate normalizing constant to make the integral of the posterior's probability density/mass function equal to 1.) When I write multiplication, I literally mean pointwise multiplication.↵
↵
For instance, in the previous example with $p=0.1$, the prior is $\frac{1}{11}$, the likelihood is $\frac{1}{10}$, so the posterior is proportional to $\frac{1}{110}$. This is a factor of $2$ below the actual value we calculated, but that's because we have to divide by the normalizing constant which is the overall likelihood (it's like dividing by $P(B)$ at the bottom of Bayes' Theorem) (in fact it's literally just Bayes' Theorem, the prior is like $P(A)$, and the likelihood is $P(B | A)$), $\frac{1}{2}$ in this case.↵
↵
As you can see, this method of inference is very powerful — you can continually update your beliefs about a hidden variable as more information comes in. You can use this in chess rating systems, exposing Dream for cheating for the 676767677th time, and also AI (because machine learning is just glorified statistics let's be fr)↵
↵
Anyway I think that's enough math for today and I'll make a post over how to use this to create a rating system later (tomorrow?)
↵
**How do you design a good rating system?** (focusing on 2-player games here, not CF)↵
↵
Conditional probability primer↵
------------------↵
↵
Suppose I have access to two coins.↵
↵
- Coin A: is a fair coin, lands heads or tails with 50% probability↵
- Coin B: is heads on both sides coin, lands heads or heads with 50% probability↵
↵
I choose one of them uniformly at random, flip it, and tell you I got heads. What's the chance I picked coin A and coin B, given that I got heads?↵
↵
You can imagine 4 possible worlds, all with 25% chance of occurring:↵
↵
- Coin A, lands heads (1)↵
- Coin A, lands tails (2)↵
- Coin B, lands heads (3)↵
- Coin B, lands heads (4)↵
↵
We're told we can be in world (1), (3), or (4), so there's a $\frac{1}{3}$ chance we picked coin A and a $\frac{2}{3}$ chance that we picked coin B.↵
↵
We write the probability of $A$ happening given event $B$ happened as $P(A | B)$.↵
↵
The chance of $A$ happening given event $B$ happened is:↵
↵
- $P(A \wedge B)$ — all the worlds where $A$ happened, but you can only count the ones where $B$ also happened, which is in our case (1) if you're after the first coin, or (3) and (4) if you're after the second coin.↵
- Divided by $P(B)$ — all the worlds where $B$ happened, which is in our case (1), (3), and (4), or 75%.↵
↵
Bayes' Theorem↵
------------------↵
↵
With some simple algebraic manipulation you can get↵
↵
$$P(A | B) = \frac{P(B|A) P(A)}{P(B)}.$$↵
↵
You can use this to do the famous disease testing "paradox". Suppose 1 in 1,000 people are infected with a disease $P(d) = 0.001$. Suppose you have a test that is 99% accurate: $P(+ | d) = 0.99, P(- | nod) = 0.99$.↵
↵
Then we have $P(+) = P(+ | d) P(d) + P(+ | nod) P(nod) = (0.99)(0.001) + (0.01)(0.999) = 0.01098$.↵
↵
And by Bayes' Theorem, if you test positive for the disease, you only actually have a↵
↵
$$P(d | +) = \frac{P(+ | d) P(d)}{P(+)} = \frac{0.99 \cdot 0.001}{0.01098} = 0.0
↵
chance of having the disease.↵
↵
Bayesian Likelihood Estimation↵
------------------↵
↵
Consider a scenario where I have picked a coin with probability $p$ of being heads. You're told that $0 \le p \le 1$, and that $p$ is chosen in increments of 10%, so the only possible values are $0, 0.1, 0.2, ..., 0.9, 1$.↵
↵
Initially, I tell you that I have chosen the value of $p$ out of all 11 possible choices with equal probability.↵
↵
Now I flip the coin and it lands **heads**. This gives you more information — now you know it's probably more likely I chose a higher value of $p$. Can we quantify this?↵
↵
_The below illustration is simply an illustration — it's not perfectly rigorous but should hopefully be helpful for building intuition when I give you the formula later._↵
↵
Consider $1{,}100$ worlds:↵
↵
- $100$ worlds where $p=0$↵
- $100$ worlds where $p=0.1$↵
- ...↵
- $100$ worlds where $p=1$↵
↵
Then,↵
↵
- $0$ of $100$ worlds where $p=0$ will land heads↵
- $10$ of $100$ worlds where $p=0.1$ will land heads↵
- ...↵
- $100$ of $100$ worlds where $p=1$ will land heads↵
↵
Therefore, there are $550$ worlds where the coin lands heads. We're told we are in one of these $550$ worlds, so, for example, the chance of $p=0.1$ is $\frac{10}{550}$ and the chance of $p=1$ is $\frac{100}{550}$. You can see how higher values of $p$ are much more likely.↵
↵
_Okay, now let's formalize it._↵
↵
We're trying to estimate an unknown parameter $\theta$. It could be a probability, a mean, etc.↵
↵
Our **prior** is our initial belief about the parameter $\theta$. In our example above, it's a discrete probability distribution with $\frac{1}{11}$ chance for each of $0, 0.1, ..., 1$. The probability distribution could also be continuous.↵
↵
Our **likelihood** is the chance that, given a specific value of $\theta$, we get the outcome that we observed. For example, if we observe heads in the above example, the likelihood of observing heads with $p=0.4$ is 0.4. The likelihood of observing heads with $p=0.8$ is 0.8.↵
↵
Finally, we should end up with the **posterior** — the new, updated probability distribution of our belief about $\theta$. In our case, that was the chance of $p=0.1$ being $\frac{10}{550}$, etc.↵
↵
The formula is:↵
↵
$$\text{Posterior} = \text{Likelihood} \cdot \text{Prior}.$$↵
↵
(You do have to divide by the appropriate normalizing constant to make the integral of the posterior's probability density/mass function equal to 1.) When I write multiplication, I literally mean pointwise multiplication.↵
↵
For instance, in the previous example with $p=0.1$, the prior is $\frac{1}{11}$, the likelihood is $\frac{1}{10}$, so the posterior is proportional to $\frac{1}{110}$. This is a factor of $2$ below the actual value we calculated, but that's because we have to divide by the normalizing constant which is the overall likelihood (it's like dividing by $P(B)$ at the bottom of Bayes' Theorem) (in fact it's literally just Bayes' Theorem, the prior is like $P(A)$, and the likelihood is $P(B | A)$), $\frac{1}{2}$ in this case.↵
↵
As you can see, this method of inference is very powerful — you can continually update your beliefs about a hidden variable as more information comes in. You can use this in chess rating systems, exposing Dream for cheating for the 676767677th time, and also AI (because machine learning is just glorified statistics let's be fr)↵
↵
Anyway I think that's enough math for today and I'll make a post over how to use this to create a rating system later (tomorrow?)
