2
$\begingroup$

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()

enter image description here

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%)
$\endgroup$
2
  • $\begingroup$ Please clarify whether you are looking for help with the Matplotlib code or for statistical advice about computing or visualizing the decision boundaries. $\endgroup$
    – whuber
    Apr 12, 2014 at 19:35
  • 1
    $\begingroup$ I extended the question a little bit, thanks. My initial attempt to plot the decision boundaries would have been to solve the g1(x) = g2(x) (and g2(x) = g3(x) etc.) analytically, and then rearrange the equation to calculate x2 from x1, which I could plot then. But I think I made several mistakes when I tried to simplify g1(x), g2(x) and g3(x). I'd would be great if someone could help me with this. However, if there is away to get around that by plotting the decision boundaries directly from g(x), I would also be happy with that! $\endgroup$
    – user39663
    Apr 12, 2014 at 21:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.