The Bayesian formulation has some limits discussed at the lecture and for certain situation one may need to formulate the problem e.g. as a Neyman-Pearson task, Wald task or minimax task. Out of this spectrum of problem formulations we will examine the minimax task.
To continue with our simple OCR developed in the previous labs, lets consider a situation when we are trying to recognise licence plates. For simplicity we again stick to the simple two-letter alphabet and 10×10 already segmented letters. The situation in the Bayes task then corresponds to a problem of designing a recognition system for a particular crossroad where the a priori probability of the two letters is known or could be measured.
In today's assignment we aim at designing a recognition system which could be deployed anywhere in the Czech republic and we need to take into account that licence plates in different cities use different combination of the letters, so the a priori probabilities differ as well. Further, lets assume it is not practical to find the optimal Bayesian strategy for each used camera.
As you might have already guessed, the situation is ideal for the minimax strategy. Here, the a priori probability exists, but is not known. We will first study the task rather theoretically to demonstrate some principles from the lecture and then we apply the gained knowledge to the real task of recognising the letters on the licence plates.
General information for Python development.
To fulfil this assignment, you need to submit these files (all packed in one .zip
file) into the upload system:
answers.txt
- answers to the Assignment Questions
minimax.ipynb
- a notebook for data initialisation, calling of the implemented functions and plotting of their results (for your convenience, will not be checked).
minimax.py
- file with the following methods implemented:
risk_fix_q_discrete
, risk_fix_q_cont
- functions for computing risk for a fixed strategy but changing a priori probability
worst_risk_discrete
, worst_risk_cont
- worst case risk for a Bayesian strategy trained with a particular a priori probability but evaluated on all a priori probabilities
minmax_strategy_discrete
, minmax_strategy_cont
- functions which find the optimal minmax strategy
plots_discrete.png
, plots_cont.png
, minmax_classif_cont.png
and minmax_classif_discrete.png
- images specified in the tasks
Use template of the assignment. When preparing a zip file for the upload system, do not include any directories, the files have to be in the zip file root.
bayes.py
in BRUTE, please copy all the necessary functions directly into minimax.py
. Sorry for the inconvenience.
As in the last labs, use the discrete and continuous measurements $x$ computed by compute_measurement_lr_discrete
and compute_measurement_lr_cont
.
For the experiments, choose two letters corresponding to your initials and use the distribution parameters given in the following variables (assuming your name is Chuck Norris) for the discrete measurements tasks:
variable | description |
---|---|
discreteC['Prob'] | $p_{X|k}(x|C)$ given as a (21, ) numpy array (the size corresponds to the range of the values of $x$) |
discreteN['Prob'] | $p_{X|k}(x|N)$ given as a (21, ) numpy array (the size corresponds to the range of the values of $x$) |
and the following ones for the cases with continuous measurements:
variable | description |
---|---|
contC['Mean'] | mean value of the normal distribution $p_{X|k}(x|C)$ |
contC['Sigma'] | standard deviation of the normal distribution $p_{X|k}(x|C)$ |
contN['Mean'] | mean value of the normal distribution $p_{X|k}(x|N)$ |
contN['Sigma'] | standard deviation of the normal distribution $p_{X|k}(x|N)$ |
(still assuming you are Chuck Norris)
risk_fix_q_discrete
.worst_risk_discrete
.minmax_strategy_discrete
and minmax_strategy_cont
, so that they find the minmax strategy and its risk for discrete and continuous measurements respectively. Hint: The minimax strategy is the Bayesian strategy with minimal maximal Bayesian risk over all $p_K(C)$.scipy.optimize.fminbound
D1 = discrete['C'] D2 = discrete['N'] q, risk = minmax_strategy_discrete(D1, D2) # q -> array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]) # risk -> 0.02857142873108387 D1 = cont['C'] D2 = cont['N'] q, risk = minmax_strategy_cont(D1, D2) # q['t1'] -> -775.9750275387074 # q['t2'] -> 10080.038857544445 # q['decision'] -> array([0, 1, 0], dtype=int32) # risk -> 0.013218704611063004
create_test_set
.
minmax_classif_cont.png
and minmax_classif_discrete.png
. classification_error_discrete
and classification_error_2normal
functions from the bayes assignment.
error_discrete = classification_error_discrete( images_test_set, labels_test_set, q_minimax_discrete) # error_discrete -> 0.0667 error_cont = classification_error_2normal( images_test_set, labels_test_set, q_minimax_cont) # error_cont -> 0
Fill the correct answers to your answers.txt
file.
This task is not compulsory.
Go through the chapter on non-Bayesian tasks in SH10 book [2], especially the parts discussing solution of the minimax task by linear programming (pages 25, 31, 35-38, 40-41, 46-47). Solve the above classification task using linear programming as described on page 47.
Hints:
scipy.optimize.linprog
.