Lesson 6

Programming problem. In the programming task below, you will fit the simplest conditional probabilistic model. Each observation has a context \(x\) and a binary outcome \(y \in \{0,1\}\). For every context \(x\), the model has its own Bernoulli parameter \[\theta_{x}=\Pr[Y=1 \mid X=x].\]

The first line of the input contains three integers \(n\), \(m\), and \(q\). The next \(n\) lines contain observations \(x_{i},y_{i}\), where \(x_{i} \in \{1,\dotsc,m\}\) and \(y_{i} \in \{0,1\}\). The last line contains \(q\) query contexts \(z_{1},\dotsc,z_{q}\). You may assume that \(1 \le m \le 20\), \(m \le n \le 500\), and \(1 \le q \le 3m\). Every query context appears at least once among the observations.

For each query context \(z_{j}\), output the maximum likelihood estimate of \(\Pr[Y=1 \mid X=z_{j}]\). Your answers will be accepted if each number has absolute error at most \(10^{-6}\).

6 3 3
1 1
1 0
1 1
2 0
2 0
3 1
1 2 3

0.6666666667 0.0000000000 1.0000000000