I have implemented the discriminant function and was able to classify the 2D patterns (via Python), but I have troubles thinking about an approach to plot the decision boundaries. Hope anyone has an idea how I can achieve this.
More specifically, I am wondering if I need to derive the separate decision boundaries via g1(x) = g2(x), g1(x) = g3(x), g2(x) = g3(x) from an analytical solution or if there is a way around that in matplotlib that would allow me to use the equation of the discriminant function (which I use to classify the patterns below) directly to plot the decision boundaries and or decision regions.
The discriminant function would be defined as: $ g_i(\pmb{x}) = \pmb{x}^{\,t} \bigg( - \frac{1}{2} \Sigma_i^{-1} \bigg) \pmb{x} + \bigg( \Sigma_i^{-1} \pmb{\mu}_{i}\bigg)^t \pmb x + \bigg( -\frac{1}{2} \pmb{\mu}_{i}^{\,t} \Sigma_{i}^{-1} \pmb{\mu}_{i} -\frac{1}{2} ln(|\Sigma_i|)\bigg)$
So that I ended up with the 3 discriminant functions $\quad g_1(\pmb{x}) = \pmb{x}^{\,t} \bigg( - \frac{1}{2} \Sigma_1^{-1} \bigg) \pmb{x} + \bigg( \Sigma_1^{-1} \pmb{\mu}_{\,1}\bigg)^t \pmb x + \bigg( -\frac{1}{2} \pmb{\mu}_{\,1}^{\,t} \Sigma_{1}^{-1} \pmb{\mu}_{\,1} -\frac{1}{2} ln(|\Sigma_1|)\bigg) \\ \quad g_2(\pmb{x}) = \pmb{x}^{\,t} \bigg( - \frac{1}{2} \Sigma_2^{-1} \bigg) \pmb{x} + \bigg( \Sigma_2^{-1} \pmb{\mu}_{\,2}\bigg)^t \pmb x + \bigg( -\frac{1}{2} \pmb{\mu}_{\,2}^{\,t} \Sigma_{2}^{-1} \pmb{\mu}_{\,2} -\frac{1}{2} ln(|\Sigma_2|)\bigg) \\ \quad g_3(\pmb{x}) = \pmb{x}^{\,t} \bigg( - \frac{1}{2} \Sigma_3^{-1} \bigg) \pmb{x} + \bigg( \Sigma_3^{-1} \pmb{\mu}_{\,3}\bigg)^t \pmb x + \bigg( -\frac{1}{2} \pmb{\mu}_{\,3}^{\,t} \Sigma_{3}^{-1} \pmb{\mu}_{\,3} -\frac{1}{2} ln(|\Sigma_3|)\bigg)$
And the following parameters are known:
$p([x_1, x_2]^t |\omega_1) ∼ N([0,0]^t,4I), \\ p([x_1, x_2]^t |\omega_2) ∼ N([10,0]^t,4I), \\ p([x_1, x_2]^t |\omega_3) ∼ N([5,5]^t,5I),$
I tried to solve the discriminant functions analytically, but I may have made some mistakes, because g1(x) - g2(x) = 0 would lead to weird solutions. So here is what I got so far:
Let:
$\pmb{W}_{i} = - \frac{1}{2} \Sigma_i^{-1}\\ \pmb{w}_i = \Sigma_i^{-1} \pmb{\mu}_{\,i}\\ \omega_{i0} = \bigg( -\frac{1}{2} \pmb{\mu}_{\,i}^{\,t}\; \Sigma_{i}^{-1} \pmb{\mu}_{\,i} -\frac{1}{2} ln(|\Sigma_i|)\bigg)$
$ \pmb{W}_{1} = \bigg[ \begin{array}{cc} -(1/8) & 0\\ 0 & -(1/8) \\ \end{array} \bigg] $
$ \pmb{w}_{1} = \bigg[ \begin{array}{cc} (1/4) & 0\\ 0 & (1/4) \\ \end{array} \bigg] \cdot \bigg[ \begin{array}{c} 0 \\ 0 \\ \end{array} \bigg] = \bigg[ \begin{array}{c} 0 \\ 0 \\ \end{array} \bigg]$
$ \omega_{10} = -\frac{1}{2} [0 \quad 0 ] \bigg[ \begin{array}{cc} (1/4) & 0\\ 0 & (1/4) \\ \end{array} \bigg] \cdot \bigg[ \begin{array}{c} 0 \\ 0 \\ \end{array} \bigg] - ln(4) = -ln(4)$
with $ \quad g_1(\pmb{x}) = \pmb{x}^{\,t} \bigg( - \frac{1}{2} \Sigma_1^{-1} \bigg) \pmb{x} + \bigg( \Sigma_1^{-1} \pmb{\mu}_{\,1}\bigg)^t \pmb x + \bigg( -\frac{1}{2} \pmb{\mu}_{\,1}^{\,t} \Sigma_{1}^{-1} \pmb{\mu}_{\,1} -\frac{1}{2} ln(|\Sigma_1|)\bigg) $
$ \Rightarrow g_1(\pmb{x}) = \pmb{x}^{t} \bigg[ \begin{array}{cc} -(1/8) & 0\\ 0 & -(1/8) \\ \end{array} \bigg] \pmb{x} + [0 \quad 0 ] \; \pmb x - ln(4) = \pmb{x}^{t} (-(1/8) \; \pmb{x}) - ln(4) $
$ \pmb{W}_{2} = \bigg[ \begin{array}{cc} -(1/8) & 0\\ 0 & -(1/8) \\ \end{array} \bigg] $
$ \pmb{w}_{2} = \bigg[ \begin{array}{cc} (1/4) & 0\\ 0 & (1/4) \\ \end{array} \bigg] \cdot \bigg[ \begin{array}{c} 10 \\ 0 \\ \end{array} \bigg] = \bigg[ \begin{array}{c} 2.5 \\ 0 \\ \end{array} \bigg]$
$ \omega_{20} = -\frac{1}{2} [10 \quad 0 ] \bigg[ \begin{array}{cc} (1/4) & 0\\ 0 & (1/4) \\ \end{array} \bigg] \cdot \bigg[ \begin{array}{c} 10 \\ 0 \\ \end{array} \bigg] - ln(4) = -12.5-ln(4)$
$ \Rightarrow g_2(\pmb{x}) = \pmb{x}^{t} \bigg[ \begin{array}{cc} -(1/8) & 0\\ 0 & -(1/8) \\ \end{array} \bigg] \pmb{x} + [2.5 \quad 0 ]\;\pmb x - ln(4) = \pmb{x}^{t} \cdot( -(1/8) \; \pmb{x}) + 2.5 x_1 - ln(4) $
$ \pmb{W}_{3} = \bigg[ \begin{array}{cc} -(1/10) & 0\\ 0 & -(1/10) \\ \end{array} \bigg] $
$ \pmb{w}_{3} = \bigg[ \begin{array}{cc} (1/5) & 0\\ 0 & (1/5) \\ \end{array} \bigg] \cdot \bigg[ \begin{array}{c} 5 \\ 5 \\ \end{array} \bigg] = \bigg[ \begin{array}{c} 1 \\ 1 \\ \end{array} \bigg]$
$ \omega_{30} = -\frac{1}{2} [5 \quad 5 ] \bigg[ \begin{array}{cc} (1/5) & 0\\ 0 & (1/5) \\ \end{array} \bigg] \cdot \bigg[ \begin{array}{c} 5 \\ 5 \\ \end{array} \bigg] - ln(5) = 5 -ln(5)$
$ \Rightarrow g_3(\pmb{x}) = \pmb{x}^{t} \bigg[ \begin{array}{cc} -(1/10) & 0\\ 0 & -(1/10) \\ \end{array} \bigg] \pmb{x} + [1 \quad 1 ]\; \pmb x - ln(4) = \pmb{x}^{t} \cdot ( -(1/10)\; \pmb x )+ \; {x_1} + {x_2} + 5 - ln(5) $
As I mentioned above, the results may not be correct :(
I would really appreciate it if someone has so time to check whether this is correct!
So what I have done so far: I was given a dataset of 2D patterns that can stem from 3 classes, 1, 2, or 3. The model is Gaussian and the parameters are known:
When I plot the training data set (with class labels known) it would look like this:
# Training Dataset
f, ax = plt.subplots(figsize=(7, 7))
ax.scatter(train_set[train_set[:,2] == 1][:,0], train_set[train_set[:,2] == 1][:,1], \
marker='o', color='green', s=40, alpha=0.5, label='$\omega_1$')
ax.scatter(train_set[train_set[:,2] == 2][:,0], train_set[train_set[:,2] == 2][:,1], \
marker='^', color='red', s=40, alpha=0.5, label='$\omega_2$')
ax.scatter(train_set[train_set[:,2] == 3][:,0], train_set[train_set[:,2] == 3][:,1], \
marker='s', color='blue', s=40, alpha=0.5, label='$\omega_3$')
plt.legend(loc='upper right')
plt.title('Training Dataset', size=20)
plt.ylabel('$x_2$', size=20)
plt.xlabel('$x_1$', size=20)
plt.show()
So I came up with the discriminant functions (based on Bayes' rule for statistical pattern classification):
then I implemented the discriminant function to classify the patterns (pretending I don't know the labels). The equation is $ g_i(\pmb{x}) = \pmb{x}^{\,t} \bigg( - \frac{1}{2} \Sigma_i^{-1} \bigg) \pmb{x} + \bigg( \Sigma_i^{-1} \pmb{\mu}_{i}\bigg)^t \pmb x + \bigg( -\frac{1}{2} \pmb{\mu}_{i}^{\,t} \Sigma_{i}^{-1} \pmb{\mu}_{i} -\frac{1}{2} ln(|\Sigma_i|)\bigg)$
def discriminant_function(x_vec, cov_mat, mu_vec):
"""
Calculates the value of the discriminant function for a dx1 dimensional
sample given the covariance matrix and mean vector.
Keyword arguments:
x_vec: A dx1 dimensional numpy array representing the sample.
cov_mat: numpy array of the covariance matrix.
mu_vec: dx1 dimensional numpy array of the sample mean.
Returns a float value as result of the discriminant function.
"""
W_i = (-1/2) * np.linalg.inv(cov_mat)
assert(W_i.shape[0] > 1 and W_i.shape[1] > 1), 'W_i must be a matrix'
w_i = np.linalg.inv(cov_mat).dot(mu_vec)
assert(w_i.shape[0] > 1 and w_i.shape[1] == 1), 'w_i must be a column vector'
omega_i_p1 = (((-1/2) * (mu_vec).T).dot(np.linalg.inv(cov_mat))).dot(mu_vec)
omega_i_p2 = (-1/2) * np.log(np.linalg.det(cov_mat))
omega_i = omega_i_p1 - omega_i_p2
assert(omega_i.shape == (1, 1)), 'omega_i must be a scalar'
g = ((x_vec.T).dot(W_i)).dot(x_vec) + (w_i.T).dot(x_vec) + omega_i
return float(g)
import operator
def classify_data(x_vec, g, mu_vecs, cov_mats):
"""
Classifies an input sample into 1 out of 3 classes determined by
maximizing the discriminant function g_i().
Keyword arguments:
x_vec: A dx1 dimensional numpy array representing the sample.
g: The discriminant function.
mu_vecs: A list of mean vectors as input for g.
cov_mats: A list of covariance matrices as input for g.
Returns a tuple (g_i()_value, class label).
"""
assert(len(mu_vecs) == len(cov_mats)), 'Number of mu_vecs and cov_mats must be equal.'
g_vals = []
for m,c in zip(mu_vecs, cov_mats):
g_vals.append(g(x_vec, mu_vec=m, cov_mat=c))
max_index, max_value = max(enumerate(g_vals), key=operator.itemgetter(1))
return (max_value, max_index + 1)
And then I classified the data to calculate the error:
# Empirical Error of the training set
import prettytable
class1_as_1 = 0
class1_as_2 = 0
class1_as_3 = 0
for row in train_set[train_set[:,2] == 1]:
g = classify_data(
row[0:2],
discriminant_function,
[mu_vec_1, mu_vec_2, mu_vec_3],
[cov_mat_1, cov_mat_2, cov_mat_3]
)
if g == 2:
class1_as_2 += 1
elif g == 3:
class1_as_3 += 1
else:
class1_as_1 += 1
class2_as_1 = 0
class2_as_2 = 0
class2_as_3 = 0
for row in train_set[train_set[:,2] == 2]:
g = classify_data(
row[0:2],
discriminant_function,
[mu_vec_1, mu_vec_2, mu_vec_3],
[cov_mat_1, cov_mat_2, cov_mat_3]
)
if g == 2:
class2_as_2 += 1
elif g == 3:
class2_as_3 += 1
else:
class2_as_1 += 1
class3_as_1 = 0
class3_as_2 = 0
class3_as_3 = 0
for row in train_set[train_set[:,2] == 3]:
g = classify_data(
row[0:2],
discriminant_function,
[mu_vec_1, mu_vec_2, mu_vec_3],
[cov_mat_1, cov_mat_2, cov_mat_3]
)
if g == 2:
class3_as_2 += 1
elif g == 3:
class3_as_3 += 1
else:
class3_as_1 += 1
Which yielded:
+--------------+----------------+----------------+----------------+
| test dataset | w1 (predicted) | w2 (predicted) | w3 (predicted) |
+--------------+----------------+----------------+----------------+
| w1 (actual) | 327 | 3 | 20 |
| w2 (actual) | 0 | 323 | 27 |
| w3 (actual) | 7 | 10 | 333 |
+--------------+----------------+----------------+----------------+
Empirical Error: 0.06 (6.38%)