Chapter 6

Perceptron and Support Vector Methods (SVM)

This chapter examines the fundamental aspects of object classification using machine-learning techniques, in particular the perceptron and support vector methods (SVM, Support Vector Machine). All code presented in this textbook, and in this chapter in particular, can be found at https://sohoware.ru/SohoBook/. In the study and application of computer science and artificial intelligence, a key element is understanding and processing different types of data, which may range from physical objects to abstract...

106min 20,129Words 24Materials

Key ideas

Fundamentals of Classifying Objects and Concepts
Pattern
Proximity Function
Classification
Classifiers
Nearest Neighbor Classifier (KNN)

Practice assignment

Create ten two-dimensional points from two classes and compare a KNN decision with a simple decision-tree boundary. Connect the result with "Perceptron and Support Vector Methods (SVM)".

Open lab

Perceptron and Support Vector Methods (SVM)

Theme

Open lab

6.1 Fundamentals of Classifying Objects and Concepts

6.1.1 Pattern

In the study and application of computer science and artificial intelligence, a key element is understanding and processing different types of data, which may range from physical objects to abstract concepts. These data, or information elements, are often called “patterns,” a term that covers a wide range of possibilities. For example, in everyday life and in scientific research, we encounter the task of recognizing and classifying many different objects, such as people and pieces of furniture, as well as subtler and less tangible aspects, such as writing or speech styles.

When these elements are processed and analyzed in computer systems, the question arises of how they should be represented in a form that a machine can understand. Since it is impossible to store physical objects or abstract concepts directly in a computer, a process is needed to transform these elements into data that a machine can work with. This process is called “representation.” It involves creating simplified yet sufficiently accurate models of objects or concepts that can be stored and processed by a computer.

There are several ways to represent such elements. One of the most common approaches is to use a vector space, where each element is modeled as a point or vector in a multidimensional space described by a set of numerical values. These values may reflect various characteristics of an object or concept, for example the size or weight of physical objects, or the frequency of use of certain words in texts. An alternative approach is to use linguistic or structural models, where elements are represented by a formal language that describes their properties and relationships.

The choice of representation method is important because it affects the system’s ability to process and classify data effectively. Vector models, for example, are widely used in machine learning and artificial intelligence because they allow accurate classification and analysis of similarity or difference between objects using metrics such as Euclidean distance or cosine similarity.

It is important to note that, although an object or concept and its computer representation are technically different things, in the context of data processing they are often treated as interchangeable. This means that the term used to denote a physical object or an abstract concept can also be applied to its data representation. For example, when speaking about “object classification,” we often mean the classification of their representations in a computer system. Despite this distinction, the term “pattern” is commonly used, and its exact meaning is clarified by context. A collection of $n$ patterns is represented as $\{X_1, X_2, \ldots, X_n\}$ , where each pattern is a $p$ -dimensional vector:

X_i = \{X_{i1}, X_{i2}, \ldots, X_{ip}\} \in \mathbb{X}^p.

6.1.2 Proximity Function

A proximity function plays a key role in classification tasks because it makes it possible to evaluate the degree of similarity or difference between objects. This evaluation can be performed through two main approaches: by using a distance function or by using a similarity function.

A distance function determines how far objects are from one another in feature space. The most common method is Euclidean distance, which is calculated as the square root of the sum of the squared differences between the corresponding features of two objects. The distance between objects $X_i$ and $X_j$ is denoted by $d(X_i, X_j)$ and is given by

d(X_i, X_j)=\left(\sum_{k=1}^{p}(x_{ik}-x_{jk})^2\right)^{1/2}.

This distance satisfies three basic properties for any three objects $X_i$ , $X_j$ , and $X_k$ :

Non-negativity: $d(X_i, X_j) \ge 0$ ; distance cannot be less than zero.

Symmetry: $d(X_i, X_j)=d(X_j, X_i)$ ; the distance from one object to another is equal to the distance from the second object to the first.

Triangle inequality: $d(X_i, X_j)+d(X_j, X_k)\ge d(X_i, X_k)$ ; the sum of the distances between two pairs of objects cannot be less than the distance between the most distant pair. This property is useful for reducing computation time and establishing useful bounds that simplify the analysis of several algorithms.

These properties make Euclidean distance a convenient tool for many classification tasks, although in some cases, for example when working with vectors of different lengths, it may be preferable to use other metrics.

A metric is a way to measure and quantify differences between objects or data points. For example, the square of the Euclidean distance is not a metric; however, it works just as well as Euclidean distance for ranking and classification.

Consider the following example:

import numpy as np
import matplotlib.pyplot as plt

# Initial data
X = np.array([2, 2])
X1 = np.array([2, 5])
X2 = np.array([5, 5])
X3 = np.array([3, 2])
X4 = np.array([4, 4])
X5 = np.array([6, 6])

# Compute Euclidean distances
d_X_X3 = np.linalg.norm(X - X3)
d_X_X1 = np.linalg.norm(X - X1)
d_X_X2 = np.linalg.norm(X - X2)

# Compute squared Euclidean distances
d_X_X3_squared = np.linalg.norm(X - X3) ** 2
d_X_X1_squared = np.linalg.norm(X - X1) ** 2
d_X_X2_squared = np.linalg.norm(X - X2) ** 2
d_X_X4_squared = np.linalg.norm(X - X4) ** 2
d_X_X5_squared = np.linalg.norm(X - X5) ** 2

# Output results
print(f"Euclidean distance d(X, X3) = {d_X_X3} < d(X, X1) = {d_X_X1} < d(X, X2) = {d_X_X2}")
print(f"Squared Euclidean distances d(X, X3)^2 = {d_X_X3_squared} < d(X, X1)^2 = {d_X_X1_squared} < d(X, X2)^2 = {d_X_X2_squared}")
print(f"Squared Euclidean distance d(X, X4)^2 = {d_X_X4_squared}, d(X, X5)^2 = {d_X_X5_squared}")
print(
    f"Comparison of squared distances and checking the triangle inequality:\n"
    f"d(X, X5)^2 = {d_X_X5_squared} > d(X, X4)^2 + d(X4, X5)^2 = "
    f"{d_X_X4_squared + np.linalg.norm(X4 - X5) ** 2}"
)

points = [X, X1, X2, X3, X4, X5]
labels = ['X', 'X1', 'X2', 'X3', 'X4', 'X5']

plt.figure(figsize=(8, 6))
for point, label in zip(points, labels):
    plt.scatter(point[0], point[1], label=label)

# Connect points with lines to visualize distances
plt.plot([X[0], X3[0]], [X[1], X3[1]], 'r--', lw=1)
plt.plot([X[0], X1[0]], [X[1], X1[1]], 'g--', lw=1)
plt.plot([X[0], X2[0]], [X[1], X2[1]], 'b--', lw=1)
plt.plot([X[0], X4[0]], [X[1], X4[1]], 'y--', lw=1)
plt.plot([X[0], X5[0]], [X[1], X5[1]], 'm--', lw=1)

# Add legend and axis labels
plt.legend()
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Euclidean Distances Between Points')
plt.grid(True)
plt.show()

Output:

Euclidean distance d(X, X3) = 1.0 < d(X, X1) = 3.0 < d(X, X2) = 4.242640687119285
Squared Euclidean distances d(X, X3)^2 = 1.0 < d(X, X1)^2 = 9.0 < d(X, X2)^2 = 17.999999999999996
Squared Euclidean distance d(X, X4)^2 = 8.000000000000002, d(X, X5)^2 = 32.00000000000001
Comparison of squared distances and checking the triangle inequality:
d(X, X5)^2 = 32.00000000000001 > d(X, X4)^2 + d(X4, X5)^2 = 16.000000000000004

Textbook illustration: Perceptron and Support Vector Methods (SVM) — 6.1.2 Proximity Function

Thus, the triangle inequality is not satisfied for squared Euclidean distances.

A similarity function reflects the degree of resemblance between objects. One of the most frequently used methods in this context is cosine similarity. It is defined as follows:

\cos(X_i,X_j)=\frac{X_i^T X_j}{\|X_i\|\,\|X_j\|}.

If we consider the objects $X$ , $X_1$ , $X_2$ , and $X_3$ from the previous example, we obtain $\cos(X, X_2) > \cos(X, X_3) > \cos(X, X_1)$ . Thus, the first three neighbors of $X$ in order of similarity are $X_2$ , $X_3$ , and $X_1$ . Notice that $X$ and $X_2$ are very similar according to cosine similarity because the angle between these two objects is 0 degrees, even though their magnitudes differ.

This method evaluates the cosine of the angle between the feature vectors of objects, making it possible to determine their directional similarity regardless of the magnitude, or length, of the vectors. Cosine similarity is especially useful in tasks involving texts and other high-dimensional data, where comparing the directions of vectors is more important than comparing their absolute values.

The relationship between the dot product and cosine similarity is that, if vectors have unit norm, their dot product equals the cosine of the angle between them. This property makes the dot product and cosine similarity interchangeable when the data are normalized. Thus, the dot product can be used to compute the degree of similarity between normalized vectors, providing an efficient mechanism for comparing objects in multidimensional spaces.

It is important to understand that the choice between a distance function and a similarity function depends on the specific task and the characteristics of the data. While Euclidean distance may be an ideal choice for spaces with a small number of dimensions, cosine similarity is often preferable in high-dimensional spaces such as text data, where it is more important to evaluate the general direction of feature vectors than their absolute distances.

6.1.3 Classification

In machine learning, classification refers to the process of determining which class or category each object or pattern under consideration belongs to. Each class is a set of objects that have common characteristics or properties expressed through their class labels. In binary-classification tasks, we often encounter two groups: positive ( $C+$ ), associated with the presence of a certain feature, and negative ( $C-$ ), indicating its absence. Membership of an object in one class or the other can be determined using a function $g$ , which maps a multidimensional object, or pattern, $X$ , to a real number:

g: \mathbb{R}^p \to \mathbb{R}.

The two classes can then be written as

C^- = \{X \mid g(X) < 0\}, \qquad C^+ = \{X \mid g(X) > 0\}.

If the value of $g$ for an object $X$ is less than zero, the object belongs to the negative class $C^-$ . If it is greater than zero, the object belongs to the positive class $C^+$ . This allows us to interpret classification as a process of dividing objects into two groups on the basis of their characteristics.

The function $g$ can be defined in different ways depending on the task and the nature of the data, which provides a flexible approach to a wide variety of classification problems.

Example:

import numpy as np
import matplotlib.pyplot as plt

# Define points for two classes
class_negative = np.array([(0, 0), (2, 2)])
class_positive = np.array([(3, -3), (4, -2), (3, -1)])

# Visualize the points on a plot
plt.figure(figsize=(8, 6))
plt.scatter(class_negative[:, 0], class_negative[:, 1], color='red', label='C-')
plt.scatter(class_positive[:, 0], class_positive[:, 1], color='blue', label='C+')

# Define and visualize a separating line
# For this example, use the linear function g(x) = x - 3.5
x_values = np.linspace(0, 8, 100)
y_values = x_values - 3.5
plt.plot(x_values, y_values, 'g--', label='g(x) = x - 3.5')

plt.xlabel('X')
plt.ylabel('Y')
plt.title('Example of Classification with Two Classes')
plt.legend()
plt.grid(True)
plt.show()

The plot shows points for two classes in two-dimensional space: class $C-$ and class $C+$ . The plot also shows a dashed line, which represents the assumed boundary separating these two classes, defined by the function $g(X)=X_1-3.5$ . This illustrates how the function $g(x)$ can be used to determine whether points belong to a particular class depending on their position relative to the boundary.

6.2 Classifiers

6.2.1 Nearest Neighbor Classifier (KNN)

The nearest neighbor classifier (KNN) is one of the simplest machine-learning methods used to classify objects on the basis of their nearest neighbors in feature space. The principle of KNN is that, to classify a new object $X$ , the system first identifies the objects from the training dataset that are closest to it and then assigns $X$ to the class most frequently represented among its nearest neighbors.

To determine the class of an object $X$ , a special function is used:

g(X)=g^-(X)-g^+(X), \qquad X\in\mathbb{R}^p,

where

g^-(X)=\min_{X_j\in C^-} d(X,X_j), \qquad g^+(X)=\min_{X_j\in C^+} d(X,X_j).

This function computes the difference between the minimum distance from $X$ to any object in the negative class $C-$ and the minimum distance from $X$ to any object in the positive class $C+$ . In other words, $g^-(X)$ is the distance from $X$ to its nearest neighbor in class $C-$ , and $g^+(X)$ is the distance to the nearest neighbor in class $C+$ .

Any metric can be used to calculate the distances, but in this example the squared Euclidean distance is used. This choice is due to the fact that squared Euclidean distance is often used in machine-learning tasks because it is simple and computationally efficient.

import numpy as np
import matplotlib.pyplot as plt

# Define classes and points
class_negative = np.array([(0, 0), (2, 2)])
class_positive = np.array([(3, -3), (4, -2), (3, -1)])
X = np.array([1, 2])
X_prime = np.array([4, 0])

# Distance function: squared Euclidean distance
def squared_euclidean_distance(x1, x2):
    return np.sum((x1 - x2) ** 2)

# Compute g-(X) and g+(X)
g_minus_X = np.min([squared_euclidean_distance(X, x) for x in class_negative])
g_plus_X = np.min([squared_euclidean_distance(X, x) for x in class_positive])
g_X = g_minus_X - g_plus_X

g_minus_X_prime = np.min([squared_euclidean_distance(X_prime, x) for x in class_negative])
g_plus_X_prime = np.min([squared_euclidean_distance(X_prime, x) for x in class_positive])
g_X_prime = g_minus_X_prime - g_plus_X_prime

# Visualization
plt.figure(figsize=(8, 6))
plt.scatter(class_negative[:, 0], class_negative[:, 1], color='red', label='C-')
plt.scatter(class_positive[:, 0], class_positive[:, 1], color='blue', label='C+')
plt.scatter(X[0], X[1], color='green', label='X (1, 2)', edgecolors='k', s=100, zorder=5)
plt.scatter(X_prime[0], X_prime[1], color='purple', label="X' (4, 0)", edgecolors='k', s=100, zorder=5)
plt.legend()
plt.xlabel('X1')
plt.ylabel('X2')
plt.title('KNN Classification Example')
plt.grid(True)

# Output results
print(f"g-(X) = {g_minus_X}, g+(X) = {g_plus_X}; therefore g(X) = {g_X}, assigning X to C-")
print(f"g-(X') = {g_minus_X_prime}, g+(X') = {g_plus_X_prime}; therefore g(X') = {g_X_prime}, assigning X' to C+")

plt.show()

Output:

g-(X) = 1, g+(X) = 13; therefore g(X) = -12, assigning X to C-
g-(X') = 8, g+(X') = 2; therefore g(X') = 6, assigning X' to C+

In this example, we calculated the squared Euclidean distances from the point $X=(1,2)$ to classes $C-$ and $C+$ and obtained the values $g^-(X)=1$ and $g^+(X)=13$ . Thus, $g(X)=-12<0$ , which means that $X$ is closer to class $C-$ and is assigned to that class. For the point $X'=(4,0)$ , analogous calculations give $g(X')=6$ , which leads to assigning $X'$ to class $C+$ .

If the value of the function $g(X)$ is negative, this means that the nearest neighbor of $X$ lies in class $C-$ , and therefore $X$ is assigned to that class. Similarly, a positive value of $g(X)$ indicates that $X$ is closer to objects of class $C+$ , and $X$ is assigned to $C+$ .

This approach allows the KNN classifier to adapt flexibly to different data distributions in feature space and to separate objects into classes effectively on the basis of their proximity to known examples from the training set. This makes KNN useful in applications where relationships between features and object classes may be complex and nonlinear.

6.2.2 k-Nearest Neighbors Classifier (KNNC)

The k-nearest neighbors classifier (KNNC) extends the basic nearest-neighbor classification principle by allowing not one but $k$ nearest neighbors of a test object $X$ to be considered when determining its class. Instead of relying exclusively on the single closest neighbor, KNNC examines a group of $k$ neighbors and assigns object $X$ to the class whose representatives dominate among these $k$ neighbors.

The function $g(X)$ is computed as the difference between the number of neighbors from the positive class $g^+(X)$ and the number of neighbors from the negative class $g^-(X)$ , where $g^-(X)=K^-$ and $g^+(X)=K^+=K-K^-$ . This means that, if most of the $k$ nearest neighbors belong to class $C-$ , then $g(X)$ will be negative and $X$ will be assigned to class $C-$ . If most of the neighbors belong to class $C+$ , then $g(X)$ will be positive and $X$ will be assigned to $C+$ .

Consider an example:

import numpy as np
import matplotlib.pyplot as plt

# Function for computing squared Euclidean distance
def squared_distance(x1, x2):
    return np.sum((x1 - x2) ** 2)

# Function for finding k nearest neighbors
def find_k_nearest_neighbors(data, labels, x, k):
    distances = np.array([squared_distance(x, point) for point in data])
    indices = np.argsort(distances)[:k]
    return labels[indices]

# Function for determining the class by majority vote
def classify_point(k_neighbors):
    counts = np.bincount(k_neighbors)
    return np.argmax(counts)

# Function for visualizing k nearest neighbors
def plot_k_nearest_neighbors(data, labels, test_point, k):
    distances = np.array([squared_distance(test_point, point) for point in data])
    indices = np.argsort(distances)[:k]
    nearest_neighbors = data[indices]

    # Visualize neighbors
    for neighbor in nearest_neighbors:
        plt.plot([test_point[0], neighbor[0]], [test_point[1], neighbor[1]], 'k--', lw=1)

# Source data
class_negative = np.array([(0, 0), (2, 2)])
class_positive = np.array([(3, -3), (4, -2), (3, -1)])
data = np.vstack((class_negative, class_positive))
labels = np.array([0] * len(class_negative) + [1] * len(class_positive))  # 0 - C-, 1 - C+

test_points = np.array([[1, 2], [5, 2]])

# Visualize and classify test points
plt.figure(figsize=(8, 6))
plt.scatter(class_negative[:, 0], class_negative[:, 1], color='red', label='C-')
plt.scatter(class_positive[:, 0], class_positive[:, 1], color='blue', label='C+')

for test_point in test_points:
    plt.scatter(test_point[0], test_point[1], color='green', edgecolors='k', s=100, zorder=5)
    k_neighbors_labels = find_k_nearest_neighbors(data, labels, test_point, 3)
    classification = classify_point(k_neighbors_labels)
    print(f"Point {test_point} is classified as {'C-' if classification == 0 else 'C+'}")
    plot_k_nearest_neighbors(data, labels, test_point, 3)

plt.legend()
plt.xlabel('X1')
plt.ylabel('X2')
plt.title('3-Nearest Neighbors Classifier (KNNC)')
plt.grid(True)
plt.show()

Output:

Point [1 2] is classified as C-
Point [5 2] is classified as C+

The plot shows classes $C-$ and $C+$ , as well as two test points, $[1,2]$ and $[5,2]$ . For each test point, dashed lines show connections to its three nearest neighbors found by the KNN algorithm with parameter $k=3$ .

The point $[1,2]$ was classified as belonging to class $C-$ , demonstrating that most of its nearest neighbors are in the negative class.

The point $[5,2]$ was classified as belonging to class $C+$ , indicating that neighbors from the positive class predominate among its nearest neighbors.

This plot clearly demonstrates how the KNN algorithm determines the class of a test point on the basis of the classes of its nearest neighbors and shows the relationship of the test points to those neighbors.

6.2.3 Minimum Distance Classifier (MDC)

The minimum distance classifier (MDC) is a classification method that uses the concept of distance to determine whether a test object belongs to one of two classes on the basis of its proximity to the mean values, or centroids, of these classes. Let us examine how the MDC works in more detail.

Defining class means: First, the mean values, or centroids, for each class are computed. This is done by finding the arithmetic mean of all points belonging to a given class. In our example, $m^-$ is the mean of the points of class $C-$ , and $m^+$ is the mean of the points of class $C+$ :

m^- = \frac{\sum_{X_j\in C^-} X_j}{|C^-|}, \qquad m^+ = \frac{\sum_{X_j\in C^+} X_j}{|C^+|}.

These mean values represent the “central” points of each class in the multidimensional feature space.

Computing distances to centroids: To classify a test object $X$ , distances from $X$ to each class centroid are first computed using a distance function. Thus, $g^-(X)$ is the distance from $X$ to the centroid of class $C-$ :

g^-(X)=d(X,m^-),

and $g^+(X)$ is the distance from $X$ to the centroid of class $C+$ :

g^+(X)=d(X,m^+).

Classification based on distances: A test object $X$ is classified by comparing distances to centroids: if the distance to the centroid of class $C-$ is smaller than the distance to the centroid of class $C+$ , then $X$ is assigned to class $C-$ . Otherwise, if the distance to the centroid of class $C+$ is smaller, $X$ is assigned to class $C+$ .

Consider an example:

import numpy as np
import matplotlib.pyplot as plt

# Function for computing squared Euclidean distances
def squared_euclidean_distance(x1, x2):
    return np.sum((x1 - x2) ** 2)

# Define classes and their centroids
class_negative = np.array([[1, 1], [2, 2]])
class_positive = np.array([[6, 2], [7, 2], [7, 3]])
m_negative = np.mean(class_negative, axis=0)
m_positive = np.mean(class_positive, axis=0)

# Test points
X = np.array([1, 2])
X_prime = np.array([5, 2])

# Compute distances from test points to centroids
g_minus_X = squared_euclidean_distance(X, m_negative)
g_plus_X = squared_euclidean_distance(X, m_positive)
g_X = g_minus_X - g_plus_X

g_minus_X_prime = squared_euclidean_distance(X_prime, m_negative)
g_plus_X_prime = squared_euclidean_distance(X_prime, m_positive)
g_X_prime = g_minus_X_prime - g_plus_X_prime

# Visualization
plt.figure(figsize=(8, 6))
plt.scatter(class_negative[:, 0], class_negative[:, 1], color='red', label='C-')
plt.scatter(class_positive[:, 0], class_positive[:, 1], color='blue', label='C+')
plt.scatter(X[0], X[1], color='green', label='X (1, 2)', edgecolors='k', s=100, zorder=5)
plt.scatter(X_prime[0], X_prime[1], color='purple', label="X' (5, 2)", edgecolors='k', s=100, zorder=5)
plt.scatter(m_negative[0], m_negative[1], color='red', marker='x', s=200, label='m-')
plt.scatter(m_positive[0], m_positive[1], color='blue', marker='x', s=200, label='m+')
plt.legend()
plt.xlabel('X1')
plt.ylabel('X2')
plt.title('Minimum Distance Classifier (MDC)')
plt.grid(True)
plt.show()

# Output results
print(f"g-(X) = {g_minus_X}, g+(X) = {g_plus_X}; hence g(X) = {g_X}, assigning X to {'C-' if g_X < 0 else 'C+'}")
print(f"g-(X') = {g_minus_X_prime}, g+(X') = {g_plus_X_prime}; hence g(X') = {g_X_prime}, assigning X' to {'C-' if g_X_prime < 0 else 'C+'}")

Output:

g-(X) = 0.5, g+(X) = 32.22222222222223; hence g(X) = -31.72222222222223, assigning X to C-
g-(X') = 12.5, g+(X') = 2.8888888888888897; hence g(X') = 9.61111111111111, assigning X' to C+

The plot shows two classes, $C-$ and $C+$ , as well as two test points, $X=(1,2)$ and $X'=(5,2)$ . The centroids of each class are indicated by crosses of the corresponding colors.

For the point $X$ , the calculation showed that the squared Euclidean distance to the centroid of class $C-$ , $g^-(X)$ , is 0.5, while the distance to the centroid of class $C+$ , $g^+(X)$ , is 32.2. Thus, the difference $g(X)=-31.7$ indicates that the point $X$ is closer to the centroid of class $C-$ and is assigned to that class.

For the point $X'$ , the calculation showed that the squared Euclidean distance to the centroid of class $C-$ , $g^-(X')$ , is 12.5, while the distance to the centroid of class $C+$ , $g^+(X')$ , is 2.9. Therefore, the difference $g(X')=9.6$ indicates that the point $X'$ is closer to the centroid of class $C+$ and is assigned to class $C+$ .

This example illustrates how the minimum distance classifier (MDC) uses distances to class means to determine the class of test points.

6.2.4 Mahalanobis Minimum Distance Classifier

This classification method uses the Mahalanobis distance to determine whether an object belongs to one of two classes. It is especially effective when data are normally distributed and when it is necessary to account for covariance, that is, the measure of dependence between two or more random variables, in order to determine the “distance” between data points.

Basic concepts:

The Mahalanobis distance differs from Euclidean distance in that it accounts for correlations between variables. In the context of classification, this means that the distance between a data point and the center, or mean, of a class is measured not simply as a straight line, but with consideration of the overall structure of the data.

**Class center ( $\mu$ )** is the mean value of all points in a class. For each class $C-$ and $C+$ , its own centers $\mu^-$ and $\mu^+$ are computed, respectively.

**Covariance matrix ( $\Sigma$ )** describes how the data variables are related to one another and distributed in space.

How the classifier works:

Computing Mahalanobis distances:

For a test point $X$ , distances $g^-(X)$ and $g^+(X)$ to class centers $\mu^-$ and $\mu^+$ are computed as follows:

Subtracting the mean: First, the corresponding class mean is subtracted from $X$ ( $\mu^-$ for class $C-$ and $\mu^+$ for class $C+$ ). This produces a difference vector directed from the class center to the point $X$ .

Applying the inverse covariance matrix: This difference vector is then multiplied by the inverse covariance matrix $\Sigma^{-1}$ . The inverse covariance matrix accounts for relationships between variables and “normalizes” the distance while taking these correlations into account. If the data have a large variance in one direction, the distance in that direction is treated as smaller.

Computing the squared Mahalanobis distance: The result of the multiplication is then multiplied, as a dot product, by the difference vector again. The resulting value is the squared Mahalanobis distance from $X$ to the class center. The formula for class $C-$ has the form

g^-(X)=(X-\mu^-)^T\Sigma^{-1}(X-\mu^-),

and for class $C+$ :

g^+(X)=(X-\mu^+)^T\Sigma^{-1}(X-\mu^+).

Classification: The test point $X$ is classified as belonging to the class whose center has the smaller Mahalanobis distance. If $g^-(X)<g^+(X)$ , then $X$ is assigned to class $C-$ , and vice versa.

6.2.5 Decision Tree Classifier (DTC)

A decision tree (DecisionTreeClassifier, DTC) is a machine-learning algorithm that builds a predictive model in the form of a tree. The splitting process in a decision tree is based on selecting features that make it possible to separate data into classes as well as possible. The goal is to create “pure” nodes, where each node contains patterns, or data points, that are as homogeneous as possible in terms of class membership.

The key point in building a decision tree is selecting the feature for splitting that maximizes the “purity” of the nodes after the split. Purity means that the patterns in a node belong to the same class. Thus, an ideal split completely separates patterns of different classes into different tree branches.

Imagine that we have a dataset divided into two classes and are considering two features, $X_1$ and $X_2$ , for splitting. Splitting by feature $X_1$ may result in one branch of the tree containing only patterns of class $C+$ , while the other branch contains mostly patterns of class $C-$ , but with some patterns of class $C+$ as well; this is called impurity. Splitting by feature $X_2$ may lead to greater impurity in both branches.

In the context of a decision tree,

g(X)=g^+(X)-g^-(X),

where $g^+(X)$ and $g^-(X)$ are Boolean functions that return 1 or 0 depending on whether pattern $X$ should be directed to class $C+$ or class $C-$ on the basis of the splitting conditions in the tree. These conditions are determined by moving from the root of the tree to its leaves, where each leaf is associated with a class label.

Each leaf node of the tree is associated with one of the classes, and the classification decision for an object is made on the basis of the path the object follows from the root of the tree to a leaf. If the tree has $m$ leaf nodes, and $m^-$ of them are associated with class $C-$ , then $g^-(X)$ is a disjunction, a logical “OR,” of $m^-$ conjunctions, logical “ANDs,” where each conjunction corresponds to a unique path from the root to a leaf associated with $C-$ . Similarly, $g^+(X)$ is the disjunction of the remaining paths leading to leaves associated with $C+$ .

To understand this classifier, consider an example.

The dataset contains six patterns, and their class labels are as follows:

Negative class: $(1,1)$ and $(2,2)$ .

Positive class: $(2,3)$ , $(6,2)$ , $(7,2)$ , and $(7,3)$ .

There is also a decision tree consisting of three leaf nodes: one negative and two positive.

Thus, the corresponding functions $g^-(X)$ and $g^+(X)$ are as follows:

g^-(X)=(X_1\le 4)\land(X_2\le 2.5),

and

g^+(X)=(X_1>4)\lor\bigl((X_1\le 4)\land(X_2>2.5)\bigr).

If $X=(1,2)$ , then $g^-(X)=1$ and $g^+(X)=0$ , assuming that a Boolean function returns 0 when it is false and 1 when it is true. Thus, $g(X)=g^+(X)-g^-(X)=0-1=-1<0$ , and therefore $X$ is assigned to $C-$ .

If $X=(5,2)$ , then $g^-(X)=0$ and $g^+(X)=1$ . Thus, $g(X)=1$ , and therefore $X$ is assigned to $C+$ .

6.2.6 Classification Based on a Linear Discriminant Function

Classification based on a linear discriminant function is a method used in machine learning and statistics to determine whether objects belong to specific classes. The linear discriminant function is the basis of this method. It is an equation that linearly combines an object’s features in order to make a classification decision.

The function has the form

g(X)=W^T X+w_0,

where:

$X$ is the feature vector of the object that we want to classify. Features are the characteristics or attributes of the object that can be measured or evaluated.

$W$ is the weight vector, representing the importance or influence of each feature on the final classification. Each element in vector $W$ corresponds to the weight of a feature in $X$ .

$w_0$ is a scalar value known as the bias or threshold, which adjusts the level at which the function is activated in order to make a classification decision.

The classification process using this function consists of substituting the object’s feature vector into the equation, producing a numerical result. This result is then interpreted as follows: if the value of the function is positive, the object belongs to one class; if it is negative, the object belongs to another class. Thus, a linear decision boundary is created in feature space, separating objects into two groups according to their classification.

It is important to note that selecting the weight vector $W$ and the bias $w_0$ is an important stage in classifier training. These parameters are usually determined from training data, a set of objects with known classification. The purpose of training is to tune $W$ and $w_0$ so that the linear discriminant function separates objects of different classes as accurately as possible.

This method is widely used because of its simplicity and efficiency in many classification tasks, especially when the relationships between features and classes are approximately linear. However, its effectiveness may decrease when the data are difficult to separate linearly, requiring the use of more complex nonlinear methods.

Consider an example:

import numpy as np
import matplotlib.pyplot as plt

# Generate a dataset
np.random.seed(0)
class1 = np.random.randn(100, 2) + np.array([2, 2])
class2 = np.random.randn(100, 2) + np.array([-2, -2])

# Visualize the dataset
plt.scatter(class1[:, 0], class1[:, 1], color='red', label='class 1')
plt.scatter(class2[:, 0], class2[:, 1], color='blue', label='class 2')

# Define weight vector and bias
W = np.array([1, 1])
w0 = 0.5

# Function for drawing the decision boundary
def draw_decision_boundary(W, w0):
    # Select two points to define the line
    x_values = np.array(plt.xlim())
    y_values = -(W[0] / W[1]) * x_values - (w0 / W[1])
    plt.plot(x_values, y_values, 'k--', label='decision boundary')

# Classification function
def classify(X, W, w0):
    return np.dot(X, W) + w0

# Test point (green point)
test_point = np.array([0.5, -0.5])
result = classify(test_point, W, w0)

# Visualize the test point and the decision boundary
draw_decision_boundary(W, w0)
plt.scatter(test_point[0], test_point[1], color='green', label='test point')
plt.text(
    test_point[0],
    test_point[1],
    f" Classified as {'class 1' if result > 0 else 'class 2'}",
    color='green'
)

plt.legend()
plt.show()

6.2.7 Nonlinear Discriminant Function (NDF)

A nonlinear discriminant function is an extension of the linear discriminant function for situations in which data cannot be effectively separated by a linear boundary. Unlike the linear discriminant function, which defines the boundary separating classes using a straight line, or a hyperplane in multidimensional space, a nonlinear function makes it possible to form more complex curvilinear boundaries.

The main idea is to use nonlinear combinations of features to classify objects. This may include quadratic, cubic, or other power terms, as well as trigonometric functions or exponentials, allowing more complex separation shapes between classes to be created in feature space.

For example, the function

g(X)=x_1^2+x_2+c

is nonlinear because of the quadratic term $x_1^2$ . This means that the separating boundary between classes will be curvilinear in the two-dimensional feature space $(X_1, X_2)$ .

Using an NDF is relevant when the relationship between features and classes is complex and cannot be adequately described by linear models. This makes it possible to improve classification accuracy in difficult tasks where the data have a complex structure or where classes overlap in feature space.

Consider an example:

import numpy as np
import matplotlib.pyplot as plt

# Generate a dataset
np.random.seed(0)
N = 100  # Number of points in each class
r_inner = 2
r_outer = 4

# Inner circle
inner_circle = r_inner * np.random.rand(N, 2)
theta = 2 * np.pi * np.random.rand(N)
inner_circle[:, 0] = r_inner * np.cos(theta)
inner_circle[:, 1] = r_inner * np.sin(theta)

# Outer circle
outer_circle = r_outer * np.random.rand(N, 2)
theta = 2 * np.pi * np.random.rand(N)
outer_circle[:, 0] = r_outer * np.cos(theta)
outer_circle[:, 1] = r_outer * np.sin(theta)

# Visualize the dataset
plt.figure(figsize=(8, 8))
plt.scatter(inner_circle[:, 0], inner_circle[:, 1], color='red', label='Class 1')
plt.scatter(outer_circle[:, 0], outer_circle[:, 1], color='blue', label='Class 2')

# Test point (green)
test_point = np.array([3, 1])
plt.scatter(test_point[0], test_point[1], color='green', label='Test Point')

# Nonlinear separating boundary (average radius)
average_radius = (r_inner + r_outer) / 2
circle = plt.Circle((0, 0), average_radius, color='black', fill=False, linestyle='--', label='Decision Boundary')
plt.gca().add_artist(circle)

# Classification using a nonlinear function
def classify_nonlinear(point):
    distance = np.sqrt(point[0] ** 2 + point[1] ** 2)
    if distance < average_radius:  # Simple condition based on distance
        return 'Class 1'
    else:
        return 'Class 2'

# Classify the test point
test_point_class = classify_nonlinear(test_point)
print(f"The test point is classified as: {test_point_class}")

plt.legend()
plt.show()

Output:

The test point is classified as: Class 2

This code illustrates the classification of linearly inseparable data using a nonlinear boundary. Two classes of points are generated so that one is inside a circle and the other is outside it, creating concentric circles. The classification boundary, represented by a dashed circle, is defined by the average radius between the inner and outer circles. The green test point is classified on the basis of its distance from the center: if it is inside the boundary, it belongs to the inner class; if it is outside, it belongs to the outer class.

6.2.8 Naive Bayes Classifier (NBC)

The naive Bayes classifier (NBC) is a simple probabilistic classifier based on the application of Bayes’ theorem under the assumption that the features are independent of one another within a class.

The operation of NBC consists of determining whether an object $X$ belongs to one of the classes $C-$ or $C+$ on the basis of probabilities.

The classifier compares the posterior probabilities $P(C^-\mid X)$ and $P(C^+\mid X)$ , that is, the probabilities that object $X$ belongs to class $C-$ or class $C+$ , respectively, after observing $X$ . The object is classified into class $C-$ if $P(C^-\mid X)>P(C^+\mid X)$ and into class $C+$ otherwise.

The discrimination function $g(X)$ for NBC is defined as the difference between the posterior probabilities for the two classes:

g(X)=g^-(X)-g^+(X),

where

g^-(X)=P(C^-\mid X), \qquad g^+(X)=P(C^+\mid X).

A posterior probability is a conditional probability conditioned on randomly observed data.

According to Bayes’ theorem, the posterior probability $P(C^-\mid X)$ can be expressed through the probability of observing $X$ given class $C-$ , $P(X\mid C^-)$ , the prior probability of class $C-$ , $P(C^-)$ , and the total probability of observing $X$ , $P(X)$ :

P(C^-\mid X)=\frac{P(X\mid C^-)P(C^-)}{P(X)}.

An analogous expression applies to $P(C^+\mid X)$ .

In the context of NBC, where conditional independence of features is assumed, the probability $P(X\mid C^-)$ is decomposed into the product of the probabilities of each feature $x_i$ given class $C-$ :

P(C^-\mid X) \propto \prod_{i=1}^{p} P(x_i\mid C^-)P(C^-),

and, correspondingly,

P(C^+\mid X) \propto \prod_{i=1}^{p} P(x_i\mid C^+)P(C^+).

6.3 Linear Discriminant Functions

6.3.1 Decision Boundary, $C+$, and $C-$

As we saw earlier in this chapter, the linear discriminant function has the form

g(X)=W^T X+b,

where $W$ is a column vector of size $p$ , and $b$ is a scalar. The function $g(X)$ divides the vector space into three parts. They are as follows.

Decision boundary DB (Decision Boundary)

In the case of linear discriminant functions,

g(X)=W^T X+b=0

characterizes a hyperplane, or a line in the two-dimensional case, called the decision boundary. The decision boundary corresponding to $g(X)$ , denoted $DB_g$ , can also be represented as

DB_g=\{X\mid g(X)=0\}.

Negative half-space NHS (Negative Half Space)

This can be regarded as the set of all samples belonging to class $C-$ . Accordingly, the negative half-space corresponding to $g(X)$ , denoted $NHS_g$ , is the set

NHS_g=\{X\mid g(X)<0\}=C^-.

Positive half-space PHS (Positive Half Space)

This is the set of all samples belonging to class $C+$ . Accordingly, the positive half-space corresponding to $g(X)$ , denoted $PHS_g$ , is given by

PHS_g=\{X\mid g(X)>0\}=C^+.

Notice that each of these parts is a potentially infinite set. However, the training dataset and the collection of test samples encountered in practice are finite.

6.3.2 Linear Separability

Linear separability is a concept in machine learning that refers to the ability of a classification algorithm to separate a dataset into classes using a linear function.

Suppose that we have a set of labeled samples $X$ consisting of “object–class label” pairs $(X_i, C_i)$ , where $i$ indexes the samples in the set.

A dataset $X$ is said to be linearly separable if one can find parameters of a linear function, namely a weight vector $W$ and a scalar bias $b$ , such that for all samples from one class, for example $C+$ , the value of the linear function $W^T X_i+b$ is greater than zero, and for all samples from the other class, for example $C-$ , it is less than zero. This means that there exists a hyperplane, or a line in two-dimensional space, defined by the equation $W^T X+b=0$ , that perfectly separates the samples of the two classes in feature space.

Using linear classifiers becomes relevant when the data are linearly separable, because in such a case the classifier can perfectly separate samples into classes without errors on the training set. An example of linearly separable data is two-dimensional samples that can be separated by a straight line.

If data are linearly separable, there is not just one but infinitely many linear discriminant functions (LDFs) that can perfectly separate these classes, because any line, or hyperplane in higher-dimensional spaces, that passes between the two nearest points of different classes without crossing them can serve as a decision boundary. This fact is illustrated by figures showing different possible separating lines, or hyperplanes, for a linearly separable dataset.

For clarity, let us consider two examples: one with linearly separable data and another with linearly inseparable data. To do this, we create two sets of points on a plane: one that can be separated into two classes by a straight line, and another for which such separation is impossible.

Linearly separable data

Suppose that we have two classes of points on a two-dimensional plane: one class in the upper-left and lower-right corners, and another in the upper-right and lower-left corners. These points can be separated by a straight line.

Linearly inseparable data

Now imagine another set of points in which points of one class surround points of another class, for example in the form of a circle. In this case, it is impossible to draw a single straight line that separates the points of the two classes.

Let us visualize both examples using Python.

import matplotlib.pyplot as plt
import numpy as np

# Generate linearly separable data
np.random.seed(0)
x1 = np.random.randn(100, 2) + np.array([-3, 3])  # Class 1
x2 = np.random.randn(100, 2) + np.array([3, -3])  # Class 2

# Generate linearly inseparable data
theta = np.linspace(0, 2 * np.pi, 100)
r = 2 + np.cos(5 * theta)  # Radial function for the "inner" class
x_inner = np.c_[r * np.cos(theta), r * np.sin(theta)]
x_outer = np.random.randn(100, 2) * 3  # "Outer" class

# Visualization
fig, axs = plt.subplots(1, 2, figsize=(12, 6))

# Linearly separable data
axs[0].scatter(x1[:, 0], x1[:, 1], label='Class 1')
axs[0].scatter(x2[:, 0], x2[:, 1], label='Class 2')
axs[0].set_title('Linearly Separable Data')
axs[0].legend()

# Linearly inseparable data
axs[1].scatter(x_inner[:, 0], x_inner[:, 1], label='Class 1')
axs[1].scatter(x_outer[:, 0], x_outer[:, 1], label='Class 2')
axs[1].set_title('Linearly Inseparable Data')
axs[1].legend()

plt.show()

The visualization presents two datasets:

Linearly separable data (left): Here, the point classes are arranged so that they can be clearly separated by a straight line. One class is located in the upper-left and lower-right corners, and the other is located in the upper-right and lower-left corners.

Linearly inseparable data (right): In this example, points of one class, the inner class, are surrounded by points of another class, the outer class. It is impossible to draw one straight line that separates the points of the two classes, which makes the data linearly inseparable.

6.3.3 Linear Classification Based on a Linear Discriminant Function

A linear classifier is described by the corresponding linear discriminant function

g(X)=W^T X+b.

The quantities $W^T$ , $X$ , and $b$ play important roles in understanding how the classifier works. Let us consider them in more detail.

The decision boundary, or hyperplane, in the context of a linear classifier is the set of points in feature space where the classifier cannot unambiguously determine whether the given points should be assigned to the positive class ( $C+$ ) or the negative class ( $C-$ ). Mathematically, this boundary is defined by the equation

g(X)=W^T X+b=0,

where $W$ is the weight vector, $X$ is the feature vector, and $b$ is the bias. Points that satisfy this equation lie on the hyperplane, which divides the feature space into two parts, each associated with one of the classes.

When we consider two different points $X_1$ and $X_2$ lying on this hyperplane, we see that both points satisfy

W^T X_1+b = W^T X_2+b=0.

Subtracting one equation from the other, we obtain

W^T(X_1-X_2)=0.

This indicates that vector $W$ is perpendicular to the vector connecting points $X_1$ and $X_2$ and therefore perpendicular to the decision-boundary hyperplane itself. This property is important because it determines the direction in which the transition from one class to the other occurs.

The orthogonality, or perpendicularity, of the weight vector $W$ to the decision boundary implies that the direction of the maximum change in the value of the function $g(X)$ , that is, the direction in which the classifier is most “confident” about a change in class membership, coincides with the direction of vector $W$ . Thus, vector $W$ not only determines the orientation of the decision boundary but also indicates which side of that boundary corresponds to the positive class. This connects the direction of vector $W$ with the distribution of classes in feature space.

The positive half-space is defined as the region of feature space where any sample $X$ satisfies

g(X)=W^T X+b>0.

This condition indicates that the sample belongs to the positive class in the context of a linear classifier. Let us examine this in more detail.

Role of the bias: The parameter $b$ in the linear discriminant function determines the position of the hyperplane relative to the origin. If we consider the value of $g(X)$ at the origin and assume that $b>0$ , then even for $X=0$ , that is, at the origin, we have $g(0)=b>0$ , which places the origin in the positive half-space. This means that when $b$ is positive, even the absence of features, represented by the zero vector $X$ , leads to classifying the sample as belonging to the positive class.

If $b=0$ , then the hyperplane passes through the origin, and the value of $g(X)$ for any point $X$ lying on the hyperplane is equal to zero. In this case, the origin lies directly on the decision boundary.

Role of the weights: The weight vector $W$ determines the orientation of the decision-boundary hyperplane in feature space. If we consider the linear discriminant function $g(X)$ with $b=0$ , then $g(X)=W^T X$ . For samples $X$ located in the positive half-space, $g(X)>0$ , which indicates that $W$ is oriented in the direction of increasing features corresponding to the positive class.

The fact that $W^T X>0$ can be interpreted through the cosine of the angle between vectors $W$ and $X$ . Since the cosine of the angle is positive when the angle between the vectors is less than 90 degrees, this means that vector $W$ is directed toward the positive half-space, supporting the classification of samples in this half-space as belonging to the positive class.

The negative half-space is defined as the region in feature space where every point $X$ is classified as belonging to the negative class; that is, for these points the condition

g(X)<0

is satisfied. This means that the value of the linear discriminant function $g(X)=W^T X+b$ for these points is less than zero.

If the bias parameter $b$ is equal to zero and we consider a point $X$ from the negative class, then the condition $W^T X<0$ indicates that the feature vector $X$ is oriented relative to the weight vector $W$ in such a way that the angle $\theta$ between them is greater than 90 degrees and less than 270 degrees. This confirms that the weight vector $W$ points toward the positive half-space, because vectors located in the negative half-space form an angle with $W$ that extends beyond a right angle.

When the bias parameter $b$ is less than zero, any point $X$ in the negative half-space satisfies

g(X)=W^T X+b<0.

In this case, even at the origin, $X=0$ , the value $g(0)=b<0$ , which places the origin in the negative half-space.

Thus, the parameters $W$ and $b$ in the linear discriminant function $g(X)=W^T X+b$ play the following roles.

The value of $b$ determines the position of the origin. The origin lies in the positive half-space ( $PHS_g$ ) if $b>0$ , in the negative half-space ( $NHS_g$ ) if $b<0$ , and on the decision boundary if $b=0$ .

The weight vector $W$ is orthogonal to the decision boundary and points toward the positive half-space. This means that regardless of the value of $b$ , the orientation of $W$ remains constant, and all decision boundaries corresponding to different values of $b$ are parallel to one another.

6.4 Perceptron

A perceptron is one of the machine-learning algorithms used for binary classification, that is, for tasks in which it is necessary to determine whether an object belongs to one of two possible classes. It is based on a linear discriminant function, which takes input data and weights them in order to make a prediction about class membership.

At the beginning of the development of artificial intelligence, the perceptron was one of the algorithms being studied, because it became the basis for many more complex classification methods, including support vector machines (SVM).

A linear discriminant function is a function that helps separate or classify input data, such as images or text, into two groups, or classes, using a line in 2D, a plane in 3D, or a hyperplane in higher dimensions.

g(X)=W^{T}X+b

is the mathematical representation of a linear discriminant function, where $g(X)$ is the value of the function for the input vector $X$ , $W$ is the weight vector, $b$ is the bias, or threshold, and $W^T$ is the transposed weight vector. The idea is that, depending on the value of $g(X)$ , we can determine which class the input vector $X$ belongs to.

Training a perceptron consists of finding optimal values for the weights $W$ and the bias $b$ so that the two classes are separated as accurately as possible.

Augmented vectors ( $X_a$ and $W_a$ ) are a trick used to simplify mathematical operations: an additional dimension is added to the original feature vector $X$ and to the weight vector $W$ in order to account for the bias $b$ . This makes it possible to integrate $b$ into the weight vector and simplify the computations.

Classification with a perceptron is performed by computing $g(X)$ and assigning $X$ to class $C-$ if $g(X)<0$ , and to class $C+$ if $g(X)>0$ . This means that if the function value is negative, the object belongs to one class, and if it is positive, it belongs to the other.

Linear separability is the assumption required for successful use of the perceptron: there must exist a line, plane, or hyperplane that can separate all input data into two classes without errors.

The class label ( $y$ ) is the actual class designation for each sample in the data. In the context of the perceptron, $y$ takes the value $-1$ or $+1$ , corresponding to the two classes ( $C-$ and $C+$ ).

Consider a table illustrating the classification process using the perceptron algorithm. The table lists six different samples, or patterns, each of which has a class label (+ or -) and two attributes ( $x_1$ and $x_2$ ). The table also gives the result of multiplying the weight vector $W_a^T$ by the attribute vector $x_a$ for each sample.

The transposed weight vector $W_a^T$ is the weight vector turned so that rows become columns, or vice versa. In this case it is represented as $W_a^T=(-14,1,5)^T$ , where the superscript $T$ denotes transposition. This means that the weight vector is converted from a horizontal position to a vertical one. In the context of the perceptron, the weight vector represents the coefficients that determine the importance of each attribute in the classification process.

The attribute vector $x_a$ is the augmented attribute vector of each sample. It includes the bias, or threshold, as the first element, and the attributes $x_1$ and $x_2$ as the second and third elements, respectively.

The dot product, denoted as $W_a^T x_a$ , is computed by multiplying the corresponding elements of two vectors and then summing the resulting products. Mathematically, this can be written as

W_a^T x_a=(-14\cdot \text{bias})+(1\cdot x_1)+(5\cdot x_2),

where the “bias” is usually equal to 1 in order to account for the activation threshold of the neuron.

W_a^T yx_a=\left((-14\cdot \text{bias})+(1\cdot x_1)+(5\cdot x_2)\right)\cdot (y\text{, the class label, takes the value }-1\text{ or }+1).

The result of the dot product is used to determine which class should be assigned to each sample. If the result is positive, the sample is classified as belonging to class $C+$ ; if it is negative, it is classified as belonging to class $C-$ .

y=-1\quad \text{if } X\in C-

y=+1\quad \text{if } X\in C+

The “1” column in the table is a constant feature that is added to each input-data vector. This is done to include the bias in the model. The bias allows the algorithm not only to perform linear classification through the origin, but also to shift the separating boundary away from zero. Thus, instead of a classification function defined only by the two features $x_1$ and $x_2$ , a constant feature, equal to 1 in this case, is added so that the model can compute and use the bias.

Sample number | Class label | 1 | $x_1$ | $x_2$ | $W_a^T yx_a$
1 | - | -1 | -1 | -1 | 8
2 | - | -1 | -1 | -2 | 2
3 | + | 1 | 1 | 2 | 3
4 | + | 1 | 1 | 6 | 2
5 | + | 1 | 1 | 7 | 3
6 | + | 1 | 1 | 7 | 8

The function $g(yX)$ is described as the multiplication of the vector $W_a$ by the attribute vector $X_a$ , multiplied by the class label $y$ .

If a sample belongs to class $C-$ , then $g(X)=W_a^T x_a<0$ , which corresponds to the class label $y=-1$ . If a sample belongs to class $C+$ , then $g(X)=W_a^T x_a>0$ , which corresponds to the class label $y=+1$ .

Thus, the function $g(yX)$ will be positive regardless of whether $X$ belongs to class $C-$ or class $C+$ , which simplifies the learning algorithm. The table shows that the weight vector $(-14,1,5)^T$ correctly classifies all values of $yX_a$ .

For the remaining part of this chapter, we use the following notation for brevity and simplicity:

$W$ is used to denote $W_a$ , assuming that $b$ is the first element in $W$ . - $X$ is used to denote $yX_a$ , assuming that $X$ is augmented by adding 1 as the first component and that the vector $X_a$ is multiplied by $y$ ; the resulting vector is denoted by $X$ . - $W$ is learned from the training data. - The perceptron learning algorithm is used to learn $W$ .

6.4.1 Perceptron Learning Algorithm

Initialization: The algorithm starts by initializing the iteration counter $i$ to zero and the weight vector $W_i$ to the zero vector. A zero vector means that all its components are equal to zero. The weight vector is used to determine the decision boundary in feature space.

Iteration over samples: Next, the algorithm iteratively checks each sample of the training set ( $X_k$ for $k$ from 1 to $n$ , where $n$ is the number of samples). If the current weight vector $W_i$ incorrectly classifies the sample $X_k$ , that is, if the product of the weight vector and the feature vector of the sample is less than or equal to zero, the weight vector is updated by adding the feature vector of the current sample to it. This update is intended to move the decision boundary closer to the current sample so that it is classified correctly. The iteration counter $i$ is increased by one every time an update occurs.

Repeat until convergence: Step 2 is repeated for the entire set of samples until the iteration counter $i$ no longer changes during a full pass, or epoch, through all samples. This means that the algorithm has reached convergence and all samples are classified correctly with the current weight vector; in other words, the algorithm has found a decision boundary that correctly separates the two classes in feature space.

import numpy as np
import matplotlib.pyplot as plt


def perceptron_learning_algorithm(X, Y, max_epochs=1000):
    n_samples, n_features = X.shape
    W = np.zeros(n_features)  # Initialize the weights as a zero vector
    i = 0  # Initialize the iteration counter
    epoch = 0  # Count epochs to prevent an infinite loop if the data are not linearly separable

    while epoch < max_epochs:
        i_old = i  # Store the previous value of the iteration counter to check convergence

        for k in range(n_samples):
            if (np.dot(W, X[k]) * Y[k]) <= 0:  # Check the misclassification condition
                W = W + X[k] * Y[k]  # Update the weights
                i += 1  # Increase the iteration counter

        if i_old == i:  # Check convergence
            break  # Leave the loop if the iteration counter did not change during the epoch

        epoch += 1

    return W


# Generate an artificial dataset
np.random.seed(42)  # Set the seed for reproducibility
n_samples = 20  # Number of samples in each of the two classes

# Generate positive samples:
# np.random.randn(n_samples, 2) creates a two-dimensional array (matrix)
# with n_samples rows and 2 columns, filled with random numbers from the
# standard normal distribution (mean = 0, standard deviation = 1).
# Adding [2, 3] shifts the distribution so that the mean values in the
# two dimensions are 2 and 3, respectively, so the samples cluster around
# the point (2, 3) in two-dimensional space.
X_positive = np.random.randn(n_samples, 2) + [2, 3]

# Generate negative samples in the same way, but centered at (1, -2).
X_negative = np.random.randn(n_samples, 2) + [1, -2]

# Combine positive and negative samples into one dataset:
# np.vstack((X_positive, X_negative)) stacks arrays vertically (by rows),
# producing an array in which all positive samples come first, followed by all negative samples.
X = np.vstack((X_positive, X_negative))

# Create class labels for the samples:
# np.ones(n_samples) creates an array of n_samples elements, all equal to 1,
# corresponding to positive samples.
# -np.ones(n_samples) creates a similar array with values -1,
# corresponding to negative samples.
# np.hstack((...)) joins arrays horizontally, forming a vector of class labels for all samples.
Y = np.hstack((np.ones(n_samples), -np.ones(n_samples)))

# Add a column of ones for the bias:
# np.ones((2*n_samples, 1)) creates a vertical array (column) of ones
# of size 2*n_samples rows by 1 column.
# This column is then added to the beginning of X using np.hstack(...),
# which allows the model to account for the bias, i.e. the intercept in the linear equation.
X = np.hstack((np.ones((2 * n_samples, 1)), X))

# Train the perceptron
weights = perceptron_learning_algorithm(X, Y)

print("Trained weights:", weights)

# Visualize the results
plt.scatter(X_positive[:, 0], X_positive[:, 1], color='blue', marker='o', label='Class +1')
plt.scatter(X_negative[:, 0], X_negative[:, 1], color='red', marker='x', label='Class -1')

# Separating line
x_values = np.linspace(np.min(X[:, 1]), np.max(X[:, 1]), 100)
y_values = -(weights[1] / weights[2]) * x_values - (weights[0] / weights[2])

plt.plot(x_values, y_values, label='Separating line')
plt.xlabel('X1')
plt.ylabel('X2')
plt.legend()
plt.grid(True)
plt.show()

Output:

Trained weights: [0.         0.75824757 4.69036742]

6.4.1.1 Learning Boolean Functions

For clarity in presenting the algorithm, let us use the example of a Boolean function, specifically the “OR” function. The corresponding truth table is shown below.

Truth table for the logical OR operation:

$x_1$ | $x_2$ | $x_1 \vee x_2$
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1

Classification using vectors of the form $yX_a$ :

Sample number | Class label | 1 | $x_1$ | $x_2$
1 | -1 | -1 | 0 | 0
2 | 1 | 1 | 0 | 1
3 | 1 | 1 | 1 | 0
4 | 1 | 1 | 1 | 1

We treat this as a two-class problem, where output 0 is interpreted as indicating the negative class, and output 1 as indicating the positive class. After augmentation and multiplication by the class label $y=-1$ or $+1$ , respectively, for the negative or positive classes, we obtain the data shown in “Classification using vectors of the form $yX_a$ .”

We start with $W_0=(0,0,0)^T$ . The successive updates of $W$ are as follows:

$W_0$ incorrectly classifies the first vector $(-1,0,0)^T$ , since their dot product is 0. Thus,

W_1=W_0+(-1,0,0)^T=(-1,0,0)^T.

$W_1$ incorrectly classifies the second pattern $(1,0,1)^T$ , because the dot product is $-1<0$ . Thus,

W_2=W_1+(1,0,1)^T=(0,0,1)^T.

$W_2$ incorrectly classifies the third pattern $(1,1,0)^T$ ; the dot product is 0. Therefore,

W_3=W_2+(1,1,0)^T=(1,1,1)^T.

Notice that $W_3$ correctly classifies the fourth pattern $(1,1,1)^T$ ; the dot product is greater than $3>0$ . Now we again pass through the patterns starting from the first. The weight $W_3$ fails to classify the first pattern $(-1,0,0)^T$ , since the dot product is $-1$ . Thus,

W_4=W_3+(-1,0,0)^T=(0,1,1)^T.

Notice that $W_4$ still fails to classify the first pattern correctly, even though it classifies patterns 2, 3, and 4. Thus,

W_5=W_4+(-1,0,0)^T=(-1,1,1)^T.

$W_5$ incorrectly classifies the second pattern, and therefore

W_6=W_5+(1,0,1)^T=(0,1,2)^T.

$W_6$ incorrectly classifies the first pattern after correctly classifying patterns 3 and 4, so

W_7=W_6+(-1,0,0)^T=(-1,1,2)^T.

$W_7$ incorrectly classifies the third pattern; therefore,

W_8=W_7+(1,1,0)^T=(0,2,2)^T.

$W_8$ incorrectly classifies the first pattern. Thus,

W_9=W_8+(-1,0,0)^T=(-1,2,2)^T.

Notice that $W_9$ classifies all four patterns correctly. Thus, the discriminant function $g(X)$ has the form

g(X)=(-1,2,2)(1,x_1,x_2)^T.

Therefore, the decision rule has the form

2x_1+2x_2=1.

6.4.1.2 Non-Uniqueness of the Weight Vector in the Perceptron

The weight vector $W$ used by the perceptron for classification is not unique. This means that there may be several different weight vectors that correctly classify the data. Which exact weight vector is found depends on the order in which the algorithm processes the data points.

There are two different ways to use the patterns to update the initial weight vector $W_0=(0,0,0)^T$ . As soon as we obtain a $W$ that classifies all patterns correctly, we stop the iterations.

Consider the figure above.

There are four patterns. They belong to two classes, as shown below:

Negative class: $(1,1)^T$ , $(2,2)^T$

Positive class: $(6,1)^T$ , $(7,1)^T$

The augmented, or improved, patterns after multiplication by $y$ are:

Negative class: $X_1=(-1,-1,-1)^T$ , $X_2=(-1,-2,-2)^T$

Positive class: $X_3=(1,6,1)^T$ , $X_4=(1,7,1)^T$

When the patterns are used in the sequence $X_1,X_2,X_3,X_4$ , the initial value of the weight vector $W_0$ is taken as $(0,0,0)^T$ , and the algorithm terminates at $W_4=(-2,2,-3)^T$ . As a result, we obtain a decision boundary in the form of the function $g(x)=2x_1-3x_2=2$ , which is shown in the graph as the dashed line ( $g(x)=2x_1-3x_2=2$ ).

If the patterns are used in the reverse order $X_4,X_3,X_2,X_1$ , starting from the same initial weight vector $W_0=(0,0,0)^T$ , we find $W_4=(-2,3,-3)^T$ , which correctly classifies all four patterns. Here, the decision boundary is described by the function $g(x)=3x_1-3x_2=2$ and is shown in the graph as the solid line ( $g(x)=3x_1-3x_2=2$ ).

6.4.1.3 How the Learning Algorithm Works

Algebraic approach

If the weight vector $W_i$ incorrectly classifies the vector $X_k$ , then the dot product $W_i^T X_k$ is not greater than 0. The updated vector $W_{i+1}$ is computed as $W_i+X_k$ , so that

W_{i+1}^T X_k=(W_i+X_k)^T X_k=W_i^T X_k+X_k^T X_k.

Since $X_k^T X_k=\|X_k\|^2$ is always positive, because it is the square of the Euclidean norm, $W_{i+1}^T X_k$ increases relative to the previous value. This means that $W_{i+1}$ is better suited for classifying $X_k$ than $W_i$ , and the dot product $W_{i+1}^T X_k$ may become positive even if $W_i^T X_k$ was not.

In other words, the algebraic approach is that if a data point is misclassified, the weights can be adjusted so as to increase the chance of correctly classifying that point at the next iteration.

Classification check: For each data point, the algorithm computes the dot product of the weight vector $W$ and the feature vector of the point $X$ . If the result of the dot product does not correspond to the expected class label, the point is considered misclassified.

Weight update: In the case of misclassification, the weights are adjusted by adding the feature vector of the misclassified point to them if the point should be positive, or by subtracting this vector if the point should be negative. This update makes the next check of this point more likely to be classified correctly.

Iterations: The process is repeated until a stopping criterion is reached, for example a certain number of iterations or the absence of misclassified points.

import numpy as np


# Function for updating weights
def update_weights(W, X, y):
    """
    Updates the weights for a misclassified vector X.

    Parameters:
    - W: current weight vector.
    - X: feature vector that was misclassified.
    - y: true class label for X, +1 or -1.

    Returns:
    - updated weight vector.
    """
    W_new = W + y * X
    return W_new


# Initial weight vector
W = np.array([0, 0, 0])

# Example feature vectors and their class labels
X_samples = np.array([
    [-1, 0, 0],  # Example 1
    [1, 0, 1],   # Example 2
    [1, 1, 0]    # Example 3
])

y_labels = np.array([-1, 1, 1])  # Class labels

# Simulate the learning process
# zip in Python is a built-in function used to iterate jointly over elements
# of two or more iterable objects (for example, lists, tuples, dictionaries, etc.),
# creating pairs or groups of elements from these objects. The elements are
# combined in order from each iterable object.
# Here, X_samples and y_labels are assumed to be two lists (or iterable objects)
# of the same length, where X_samples contains samples, such as feature data for
# machine learning, and y_labels contains the corresponding labels or answers.
# On each iteration, zip takes one element from X_samples and one element from
# y_labels, combines them into the pair (X, y), and this pair is used in the body
# of the loop. This continues until one of the iterable objects is exhausted. If
# X_samples and y_labels have different lengths, zip stops at the shortest one,
# and the remaining elements in the longer object are ignored.
for X, y in zip(X_samples, y_labels):
    # Class prediction
    prediction = np.dot(W, X)

    # Check for misclassification
    if (prediction <= 0 and y == 1) or (prediction > 0 and y == -1):
        # Update weights in the case of misclassification
        W = update_weights(W, X, y)

print(f"Updated weight vector: {W}")

Output:

Updated weight vector: [1 0 1]

Geometric approach

The geometric approach gives a visual understanding of how updating the weights changes the decision boundary in order to classify samples correctly.

Misclassification: Imagine that we have a weight vector $W_i$ that incorrectly classifies the point $P_3$ . The decision boundary corresponding to $W_i$ , denoted by $DB_i$ , does not separate the classes properly.

Weight update: When we add $P_3$ to $W_i$ , we effectively shift the weight vector so that it classifies $P_3$ better. This can be visualized as completing a parallelogram, where $W_{i+1}$ is the diagonal of the parallelogram formed by the vectors $W_i$ and $P_3$ .

Change in the decision boundary: The new weight vector $W_{i+1}$ now correctly classifies $P_3$ , and the corresponding decision boundary, denoted by $DB_{i+1}$ , is now orthogonal to $W_{i+1}$ , providing better class separation.

These approaches explain how the perceptron algorithm consistently corrects the weight vector at each misclassification, gradually improving the separation of classes until all samples are classified correctly or until a specified number of iterations is reached.

6.4.1.4 Convergence of the Perceptron Algorithm

Convergence of the perceptron algorithm refers to the property of the perceptron algorithm that guarantees that if some separation of the data exists, the algorithm can find a separating hyperplane for those data in a finite number of steps.

The perceptron convergence theorem was proved by Frank Rosenblatt in 1957. It states that if the data are linearly separable, then the algorithm will converge to an optimal separating hyperplane after a finite number of weight-update iterations. This means that the algorithm is guaranteed to find a set of weights for which all samples are classified correctly if such a solution is possible.

The perceptron convergence theorem states that if there exist some weights that can correctly classify the training data, the perceptron will converge to those weights in a finite number of steps.

Let us analyze the algorithm:

Initialization

Before training begins, the perceptron is initialized with specified learning-rate and iteration-count parameters. The weights and bias are initialized to zeros. These parameters are adapted during training in order to minimize prediction errors.

Training

The training process consists of repeated passes through the training dataset, where each data element is processed individually. For each example, the weighted sum of its features and bias is computed, after which the activation function is applied to obtain a prediction. The difference between the predicted value and the true value is used to update the weights and bias, taking the learning rate into account.

Activation

The activation function in the perceptron is a step function that returns 1 if the weighted sum of the inputs and the bias is greater than zero, and 0 otherwise. This allows the model to make clear binary predictions.

Prediction

After training, the perceptron can be used to predict the classes of new data. The prediction process is similar to the training process, but without updating the weights and bias.

Visualization of the decision boundary

For clarity in the training process and its results, one can visualize the decision boundary that separates the classes in feature space. This is done by creating a grid of values and applying the model to each grid point.

Iterative training and visualization

Using the FuncAnimation class from the Matplotlib library, we can create an animation that shows the perceptron training process as training data are added iteratively and the decision boundary changes.

# Import NumPy for working with arrays
import numpy as np

# Import Matplotlib for creating plots
import matplotlib.pyplot as plt

# Import FuncAnimation for creating animations
from matplotlib.animation import FuncAnimation


# Define the Perceptron class
# In the Perceptron class constructor, initial parameters are set, including
# the learning rate (learning_rate) and the number of iterations (n_iters).
# Variables for the weights (self.weights) and bias (self.bias) are also
# initialized; they will be defined in the fit method.
class Perceptron:
    def __init__(self, learning_rate=0.01, n_iters=1000):
        # Initialize the perceptron with the specified learning-rate and iteration parameters
        self.lr = learning_rate
        self.n_iters = n_iters
        self.activation_func = self._unit_step_func  # The activation function transforms the weighted sum of input signals and bias into the predicted output value. It returns 1 if the weighted sum is greater than 0 and 0 otherwise, allowing the model to make clear binary predictions.
        self.weights = None  # Weights are initialized in the fit method
        self.bias = None  # Bias is initialized in the fit method
        self.weights_history = []  # Store the history of weights

    # The fit method is responsible for training the model. The weights are
    # initialized with zeros; then, in a loop, predictions are computed for each
    # example from the training dataset and the weights and bias are updated.
    def fit(self, X, y):
        # Train the model on X and y
        n_samples, n_features = X.shape

        # Initialize weights and bias with zeros
        self.weights = np.zeros(n_features)
        self.bias = 0

        # Add the initial state of the weights and bias to the history
        self.weights_history.append((self.weights.copy(), self.bias))

        # Transform class labels
        y_ = np.array([1 if i > 0 else 0 for i in y])

        # Main training loop
        for _ in range(self.n_iters):
            for idx, x_i in enumerate(X):
                # Compute the linear transformation and apply the activation function
                linear_output = np.dot(x_i, self.weights) + self.bias
                y_predicted = self.activation_func(linear_output)

                # Update weights and bias
                update = self.lr * (y_[idx] - y_predicted)
                self.weights += update * x_i
                self.bias += update

                # Record the history
                self.weights_history.append((self.weights.copy(), self.bias))

    # The _unit_step_func function is a step activation function used to
    # transform the weighted sum of inputs into a binary prediction.
    def _unit_step_func(self, x):
        return np.where(x > 0, 1, 0)

    # The predict method is used to compute predictions for new data. It applies
    # the trained weights and bias to the data and returns the predicted classes.
    def predict(self, X):
        # Predict classes for new data
        linear_output = np.dot(X, self.weights) + self.bias
        y_predicted = self.activation_func(linear_output)
        return y_predicted


# The plot_decision_boundary function visualizes the decision boundary by
# creating a grid of possible values and using the model to predict the class
# at each grid point.
def plot_decision_boundary(X, y, classifier, ax):
    # Determine axis ranges
    x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1

    # Create a grid for visualization
    xx1, xx2 = np.meshgrid(np.arange(x1_min, x1_max, 0.1),
                           np.arange(x2_min, x2_max, 0.1))

    # Predict classes for each grid point
    Z = classifier.predict(np.array([xx1.ravel(), xx2.ravel()]).T).reshape(xx1.shape)

    # Visualize the decision boundary and data
    ax.contourf(xx1, xx2, Z, alpha=0.4)
    ax.scatter(X[:, 0], X[:, 1], c=y, s=10, edgecolor='k')

    # Display weights and bias
    weights, bias = classifier.weights_history[-1]
    ax.set_xlabel(f'Weights: {weights}, Bias: {bias}')


# Set the seed for the random-number generator
np.random.seed(1)

# Generate random data
X = np.random.randn(100, 2)
y = np.array([1 if x[0] + x[1] > 0 else 0 for x in X])

# Create a perceptron instance
p = Perceptron(learning_rate=0.1, n_iters=10)

# Prepare visualization objects
fig, ax = plt.subplots()


# Update function for the animation
def update(frame):
    ax.clear()  # Clear the previous state
    p.fit(X[:frame + 1], y[:frame + 1])  # Train on part of the data
    plot_decision_boundary(X[:frame + 1], y[:frame + 1], p, ax)  # Visualize
    ax.set_title(f'Iterations: {frame + 1}')  # Display the iteration number


# Using FuncAnimation from Matplotlib makes it possible to create an animation
# demonstrating the training process and the changing decision boundary. The
# update function, called for each animation frame, trains the model on a subset
# of the data and updates the visualization.
ani = FuncAnimation(fig, update, frames=range(1, X.shape[0]), interval=100)

plt.show()  # Display the animation

It is important to note that convergence of the algorithm is guaranteed only for linearly separable data. For data that cannot be separated linearly, the perceptron algorithm may not converge to a stable solution, which means that the weights will continue to update indefinitely while trying to find a solution that does not exist.

6.4.2 Gradient Descent

Gradient descent is an iterative optimization algorithm whose goal is to find the minimum value of a loss, or error, function. The loss function evaluates how well the model works at a given stage of training by expressing the difference between predicted and actual values. Gradient descent seeks to minimize this function by adjusting the perceptron weights so as to achieve the smallest possible error.

The method is based on the concept of the gradient of a function, which is a vector of the partial derivatives of the loss function with respect to each of the weights. The gradient points in the direction of the greatest increase in the function value. Therefore, by moving in the direction opposite to the gradient, that is, by performing gradient descent, one can find the minimum of the function.

There are several variants of gradient descent, differing in the way the gradient is computed:

Batch Gradient Descent: The gradient is computed over the entire dataset, which provides stability in the descent direction, but can be computationally expensive for large amounts of data.

Stochastic Gradient Descent (SGD): The gradient is computed for each training example separately, making the process more random but substantially accelerating the computations.

Mini-batch Gradient Descent: A compromise variant in which the gradient is computed on small groups, or batches, of training examples, combining the advantages of the previous two methods.

Consider stochastic gradient descent with a Python code example. For this, we need to modify the fit method so that it updates the weights after each training example, rather than after a pass through the entire dataset.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation


class Perceptron:
    def __init__(self, learning_rate=0.01, n_iters=1000):
        self.lr = learning_rate  # Learning rate
        self.n_iters = n_iters  # Number of iterations
        self.activation_func = self._unit_step_func
        self.weights = None  # Weights
        self.bias = None  # Bias
        self.weights_history = []  # Store the history of weights

    def fit(self, X, y):
        n_samples, n_features = X.shape

        # Initialize weights and bias with zeros
        self.weights = np.zeros(n_features)
        self.bias = 0

        # Add the initial state of the weights and bias to the history
        self.weights_history.append((self.weights.copy(), self.bias))

        y_ = np.array([1 if i > 0 else 0 for i in y])

        # Main training loop
        for _ in range(self.n_iters):
            for idx, x_i in enumerate(X):
                # Compute the weighted sum of inputs and bias
                linear_output = np.dot(x_i, self.weights) + self.bias

                # Apply the activation function
                y_predicted = self.activation_func(linear_output)

                # Compute the error
                error = y_[idx] - y_predicted

                # Gradient descent: update weights and bias
                # Weights are updated in the direction opposite to the gradient of the loss function.
                # The magnitude of the update is determined by the learning rate and the gradient.
                self.weights += self.lr * error * x_i
                self.bias += self.lr * error

                # Record the history
                self.weights_history.append((self.weights.copy(), self.bias))

    def _unit_step_func(self, x):
        # Activation function: step function
        return np.where(x > 0, 1, 0)

    def predict(self, X):
        # Compute predictions on new data
        linear_output = np.dot(X, self.weights) + self.bias
        y_predicted = self.activation_func(linear_output)
        return y_predicted


# The plot_decision_boundary function visualizes the decision boundary by
# creating a grid of possible values and using the model to predict the class
# at each grid point.
def plot_decision_boundary(X, y, classifier, ax):
    # Determine axis ranges
    x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1

    # Create a grid for visualization
    xx1, xx2 = np.meshgrid(np.arange(x1_min, x1_max, 0.1),
                           np.arange(x2_min, x2_max, 0.1))

    # Predict classes for each grid point
    Z = classifier.predict(np.array([xx1.ravel(), xx2.ravel()]).T).reshape(xx1.shape)

    # Visualize the decision boundary and data
    ax.contourf(xx1, xx2, Z, alpha=0.4)
    ax.scatter(X[:, 0], X[:, 1], c=y, s=10, edgecolor='k')

    # Display weights and bias
    weights, bias = classifier.weights_history[-1]
    ax.set_xlabel(f'Weights: {weights}, Bias: {bias}')


# Set the seed for the random-number generator
np.random.seed(1)

# Generate random data
X = np.random.randn(100, 2)
y = np.array([1 if x[0] + x[1] > 0 else 0 for x in X])

# Create a perceptron instance
p = Perceptron(learning_rate=0.1, n_iters=10)

# Prepare visualization objects
fig, ax = plt.subplots()


# Update function for the animation
def update(frame):
    ax.clear()
    p.fit(X[:frame + 1], y[:frame + 1])
    plot_decision_boundary(X[:frame + 1], y[:frame + 1], p, ax)
    ax.set_title(f'Iterations: {frame + 1}')
    weights, bias = p.weights_history[-1]
    ax.set_xlabel(f'Weights: {weights}, Bias: {bias}')


ani = FuncAnimation(fig, update, frames=range(1, X.shape[0]), interval=100)

plt.show()  # Display the animation

The weights and bias are updated inside the nested loop over each data sample, in the lines with for idx, xi in enumerate(X):: In stochastic gradient descent, weights are updated for each training example rather than after a pass through the entire dataset, as in batch gradient descent. > > *The magnitude of the weight update depends on the error of the specific sample, the learning rate, and the feature value (self.weights += self.lr error xi): In stochastic gradient descent, the gradient of the loss function is estimated on the basis of one sample, and the weights are updated in the direction opposite to the gradient, which allows the algorithm to take steps toward minimizing the overall loss function. > > Use of the learning rate (learning_rate, or self.lr in the code):* This parameter controls the step size when updating the weights. In stochastic gradient descent, the learning rate is a hyperparameter that helps balance convergence speed against the risk of overfitting or getting stuck in local minima.

6.4.3 Nonlinearly Separable Data

In its basic form, the perceptron learns to find a linear boundary separating two classes. However, if we know or can assume the form of a nonlinear boundary separating the classes, the perceptron learning algorithm can be adapted to learn a nonlinear discriminant.

The first step is to transform the input data so that they match the expected form of nonlinearity. This can be achieved by applying functions that introduce nonlinearity into the original data, such as polynomial functions, logarithmic transformations, or trigonometric functions. The choice of a specific function, or combination of functions, depends on the nature of the data and the assumed form of the nonlinear boundary.

After the data are transformed, the perceptron learning algorithm is applied to the modified data. In this context, instead of searching for a linear boundary, the perceptron will learn to find a boundary that corresponds to the applied transformation. This allows the perceptron to effectively separate data that cannot be separated linearly in the original feature space.

Suppose the data are separated by a second-order curve, a parabola. We can transform each input vector by adding a new feature that is the square of the original feature, or features if there are several. Such a transformation changes the original data space so that the perceptron can find a linear boundary in the new space that corresponds to a nonlinear boundary in the original space.

Consider this with a Python code example:

import numpy as np  # Import NumPy for working with arrays
import matplotlib.pyplot as plt  # Import Matplotlib for data visualization
from matplotlib.animation import FuncAnimation  # Import a class for creating animation


class Perceptron:
    def __init__(self, learning_rate=0.01, n_iters=1000):
        self.lr = learning_rate  # Set the learning rate
        self.n_iters = n_iters  # Set the number of training iterations
        self.activation_func = self._unit_step_func  # Set the activation function (unit step function)
        self.weights = None  # Initialize weights
        self.bias = None  # Initialize bias
        self.weights_history = []  # List for storing the history of weight changes

    def fit(self, X, y):  # Method for training the model
        n_samples, n_features = X.shape  # Get the number of samples and features
        self.weights = np.zeros(n_features)  # Initialize weights with zeros
        self.bias = 0  # Initialize the bias with zero
        self.weights_history.append((self.weights.copy(), self.bias))  # Record initial weights and bias

        y_ = np.array([1 if i > 0 else 0 for i in y])  # Transform class labels

        for _ in range(self.n_iters):  # Main training loop
            for idx, x_i in enumerate(X):  # Iterate over all samples
                linear_output = np.dot(x_i, self.weights) + self.bias  # Compute linear output
                y_predicted = self.activation_func(linear_output)  # Obtain model prediction
                update = self.lr * (y_[idx] - y_predicted)  # Compute update for weights
                self.weights += update * x_i  # Update weights
                self.bias += update  # Update bias
                self.weights_history.append((self.weights.copy(), self.bias))  # Record updated weights and bias

    def _unit_step_func(self, x):  # Define the unit step function
        return np.where(x > 0, 1, 0)  # Return 1 if x > 0, otherwise 0

    def predict(self, X):  # Method for predicting classes of new samples
        linear_output = np.dot(X, self.weights) + self.bias  # Compute linear output
        y_predicted = self.activation_func(linear_output)  # Obtain prediction
        return y_predicted  # Return predicted class labels


def add_nonlinear_features(X):  # Function for adding nonlinear features
    X_nonlinear = np.zeros((X.shape[0], X.shape[1] * 3))  # Create an array for nonlinear features
    X_nonlinear[:, :2] = X  # Copy the original features
    X_nonlinear[:, 2] = X[:, 0] ** 2  # Add the square of the first feature
    X_nonlinear[:, 3] = X[:, 1] ** 2  # Add the square of the second feature
    X_nonlinear[:, 4] = X[:, 0] * X[:, 1]  # Add the interaction between features
    return X_nonlinear  # Return the expanded feature set


# The add_nonlinear_features function adds nonlinear features to the original data,
# such as squares and products of the original features, allowing the perceptron
# to find nonlinear decision boundaries.
def plot_decision_boundary(X, y, classifier, ax):  # Function for drawing the decision boundary
    x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1  # Determine limits for the X1 axis
    x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1  # Determine limits for the X2 axis

    xx1, xx2 = np.meshgrid(np.arange(x1_min, x1_max, 0.1),
                           np.arange(x2_min, x2_max, 0.1))  # Create a grid for plotting

    # Apply the model to each grid point
    Z = classifier.predict(add_nonlinear_features(np.array([xx1.ravel(), xx2.ravel()]).T)).reshape(xx1.shape)

    ax.contourf(xx1, xx2, Z, alpha=0.4)  # Fill areas with different colors depending on model predictions
    ax.scatter(X[:, 0], X[:, 1], c=y, s=10, edgecolor='k')  # Mark the original data points

    weights, bias = classifier.weights_history[-1]  # Get the latest weights and bias
    ax.set_xlabel(f'Weights: {weights}, Bias: {bias}')  # Display information about weights and bias on the plot


np.random.seed(1)  # Set the seed for the random-number generator
X = np.random.randn(100, 2)  # Generate a random dataset

# Define class labels on the basis of a nonlinear decision boundary
y = np.array([1 if x[0] ** 2 + x[1] ** 2 < 1 else 0 for x in X])

X_nonlinear = add_nonlinear_features(X)  # Add nonlinear features to the data
p = Perceptron(learning_rate=0.1, n_iters=10)  # Create a perceptron instance

fig, ax = plt.subplots()  # Create a figure for the plot


def update(frame):  # Function for updating the animation
    ax.clear()  # Clear the current plot
    p.fit(X_nonlinear[:frame + 1], y[:frame + 1])  # Train the model on a limited dataset
    plot_decision_boundary(X_nonlinear[:frame + 1], y[:frame + 1], p, ax)  # Draw the decision boundary
    ax.set_title(f'Iteration: {frame + 1}')  # Set the plot title


ani = FuncAnimation(fig, update, frames=range(1, X.shape[0]), interval=100)  # Create the animation

plt.show()  # Display the plot

The plotdecisionboundary function is used to visualize the classifier’s decision boundary on a graph. First, the function determines the minimum and maximum values for the two features, $x_1$ and $x_2$ , used in the data. A small margin, -1 and +1, is added to these values so that the decision boundaries do not lie right against the extreme data points. Using np.meshgrid, a coordinate grid is created for the feature space. This grid covers the area defined by the minimum and maximum feature values with a certain step, in this case 0.1.

The grid is used to compute classifier predictions at each point of the feature space. For each grid point, that is, for each combination of $x_1$ and $x_2$ values, a classifier prediction is computed.

Since the grid was created from two coordinate arrays, $x_1$ and $x_2$ , the corresponding values from these arrays are used for prediction. For this purpose, the values of $x_1$ and $x_2$ are “flattened” using the ravel method, combined into a feature array, nonlinear transformations are applied to that array if necessary, and predictions are made for the resulting data points using the classifier’s predict method. After that, the predictions are transformed back into the shape corresponding to the grid using the reshape method. The contourf function from the Matplotlib library creates filled regions on the graph corresponding to different classes determined by the classifier’s predictions on the grid. Different classes are denoted by different colors. The original data points are also plotted using the scatter function, where the color of the points corresponds to their true class labels. At the bottom of the graph, information about the current values of the classifier weights and bias is displayed, allowing their change during training to be observed.

6.4.4 Creative Approaches to Using the Perceptron

In the previous section, we did not consider the perceptron’s ability to solve tasks that go beyond simple linearly separable scenarios. However, let us consider some tricks.

For example, the exclusive “OR” operation, XOR, requires the output signal to be activated when one of two input signals is enabled, but not when they are activated simultaneously. This task is an example of nonlinear classification, which cannot be solved by a single perceptron using standard linear weights and thresholds. However, by reformulating the problem conditions or changing the representation of the input data, one can train a perceptron to solve the XOR problem. This demonstrates the possibility of overcoming the limitations of linear classification through a creative approach to data representation.

Another example that demonstrates a complex task a perceptron can handle is the odd-parity function, where the output signal is activated if an odd number of three input signals is activated. This task also requires a nonstandard approach to perceptron training and input-data representation, but it is also solvable.

In mathematics and computer science, functions are often used that can take different data, called arguments, as input and produce a result depending on them. Sometimes these functions have a property called “permutation invariance.” This means that if we take a function with two or more inputs and swap these inputs, the result of the function does not change. An example of such a function is the exclusive OR operation, XOR, which behaves the same regardless of the order of the input data.

Some image properties, for example the presence of at least one black pixel, also do not change if we rearrange the pixels. This is a property of permutation invariance.

Positive normal form is a special way of writing mathematical functions that uses only the operations “AND” and “NOT” to describe them.

Minterms are simple components of more complex functions that contain all variables of the function. If a function is invariant under permutation, that is, if its result does not depend on the order of the variables, then all these minterms can be expressed very simply, and all of them will have the same “weight,” or coefficient, in the formula of the function. This is useful because it simplifies the analysis of and work with such functions.

Consider a Python demonstration showing that the result of the XOR function does not depend on the order of the input variables and that positive normal form is a valid way to represent such a function.

# Let us use a Python code example to show what permutation invariance is
# and how positive normal form works.

# Exclusive OR (XOR) function of two variables
def xor(x1, x2):
    return (x1 and not x2) or (not x1 and x2)


# Check permutation invariance for the XOR function
a = 0
b = 1
result1 = xor(a, b)
result2 = xor(b, a)


# Positive normal form (PNF) for the XOR function
def xor_pnf(x1, x2):
    return (1 - x1) * (x2) + (x1) * (1 - x2)


# Check how positive normal form works
pnf_result1 = xor_pnf(a, b)
pnf_result2 = xor_pnf(b, a)

print(result1, result2, pnf_result1, pnf_result2)

Output:

1 True 1 1

Incremental computation means that you can add data to calculations that have already been performed without recalculating everything from scratch. This is useful, for example, when analyzing images and wanting to add information about new pixels to an analysis that has already been performed.

For example, if we have an image consisting of $l$ pixels and we want to determine whether there is at least one black pixel, we can use an incremental approach. The function $g(X)$ that determines the presence of a black pixel can be computed as the sum of the values of all pixels, $x_1+x_2+\ldots+x_l$ , where each $x$ is the value of a specific pixel, for example 1 if the pixel is black and 0 otherwise.

If the image becomes larger and new pixels are added, we can simply add their values to the already computed sum without recalculating everything from the beginning. This makes the process faster and more efficient.

By contrast, some other functions, such as functions for determining whether the number of black pixels is odd and the exclusive OR function, XOR, are not suited to incremental computation. This means that when the image size changes, their values need to be computed again, which is a more complex and time-consuming task. These functions require the use of all data elements, all image pixels, and they depend strongly on the order in which the data are fed to the input, which makes their computation difficult to optimize using incremental methods.

6.5 Kernel-Based Support Vector Machine (SVM)

In the 1960s and 1970s, Vladimir Vapnik and Alexey Chervonenkis proposed the support vector machine method, which was a significant improvement over the perceptron due to its use of margin optimization between classes. This allowed SVM to provide better generalization capability on test data. Nevertheless, SVM still remained a linear classifier and likewise could not solve problems with nonlinearly separable data.

A breakthrough in overcoming this limitation came with the introduction of the kernel trick, which made it possible to use a linear SVM in nonlinear tasks. The kernel function used in this method allowed the original data to be mapped into a higher-dimensional space where the data became linearly separable. Thus, the SVM algorithm became capable of finding an optimal solution even for nonlinearly separable data, which was impossible for the perceptron.

This discovery contributed to the widespread adoption of support vector machines in machine learning and became the basis for the development of different kernels, such as polynomial, radial-basis-function (RBF), and sigmoid kernels, each of which has its own advantages under certain conditions.

Support vector machines (SVMs) are useful for nonlinear classification based on a linear discriminant function in a high-dimensional kernel space. Linear SVM is widely used in applications associated with high-dimensional spaces. However, in low-dimensional spaces, kernel-based SVM is a popular nonlinear classifier. It uses the kernel trick, which allows us to work in the input-data space instead of working directly in a potentially high-dimensional, or even theoretically infinite-dimensional, kernel or function space. The kernel trick has also become so popular that it is used in various other pattern-recognition and machine-learning algorithms.

6.5.1 Nonlinearly Separable Data

Consider the case in which data are not linearly separable. This means that the data cannot be separated by a straight line into two classes so that each class lies only on one side of the line. In machine learning, and in particular in support vector machines (SVMs), this is the situation in which it is impossible to find a hyperplane that fully separates the data into two classes without errors.

Let us describe what to do when data cannot be linearly separated:

It is impossible to find weights $W$ and a bias $b$ such that $W^T X+b=-1$ if $X$ belongs to the negative class and $W^T X+b=1$ if $X$ belongs to the positive class.

There is no margin that could be maximized, so margin maximization has no meaning. Many practical problems fall into this category, where the data are not separated by a clear boundary.

It is impossible to find an optimal hyperplane, as discussed in the previous chapter, for cases in which the data are not linearly separable.

Instead, a margin is created and optimized, which implies ignoring some data points in order to create that margin.

Consider the two-dimensional data points shown in the figure.

A positive pattern is misclassified if the error $e_1$ is greater than 1. A negative pattern is associated with an error $e_2<1$ , as shown in the figure. Here there is no misclassification.

We would like to minimize such errors. Therefore, we include a term corresponding to the sum of these errors in the criterion function. Thus, the optimization problem reduces to

\min_W\left(\frac{1}{2}\lVert W\rVert^2 + C\sum_{i=1}^{n} e_i\right).

If there is no error in the classification of $X_i$ , then $e_i=0$ . Also, $e_i$ cannot be negative, so $e_i\geq 0$ for all $i$ .

Similarly, the constraints can now be relaxed as

W^T X_i+b\leq -1+e_i, \quad \text{if } y_i=-1,

and

W^T X_i+b\geq 1-e_i, \quad \text{if } y_i=1.

Note that introducing error $e_i$ for pattern $X_i$ from $C+$ ensures that the corresponding constraint is satisfied. There are three possibilities:

The error is $e_i=0$ . In this case, $X_i$ lies on the support plane, $W^T X_i+b=1$ , and is therefore classified correctly.

If $e_i<1$ , then $W^T X_i+b>1-e_i>0$ . Thus, $X_i$ will be classified correctly, although $X_i$ is on the margin boundary.

If $e_i\geq 1$ , then $W^T X_i+b\leq 0$ . Thus, $X_i$ will be classified incorrectly.

An analogous analysis can be carried out for patterns in $C-$ .

Note that regardless of whether $X_i$ is in $C_+\,(y_i=1)$ or $X_i$ is in $C_-\,(y_i=-1)$ , we have

y_i\left(W^T X_i+b\right)\geq 1-e_i

and also $e_i\geq 0$ for all $i$ .

The optimization problem involves minimizing the norm of the weight vector $W$ and the penalty for classification errors, weighted by parameter $C$ . The constraints are modeled in such a way as to provide a certain robustness to errors; that is, some data points may lie on the wrong side of the boundary, but this is allowed within the error margin.

6.5.2 Soft-Margin Formulation

In the context of perceptron training, the concept of “soft fields,” or a “soft margin,” is needed to create more flexible and adaptive models. This concept allows the perceptron to handle data that cannot be perfectly separated by a linear boundary. In this chapter, we will examine in detail how the soft-margin formulation is applied in perceptron training in order to provide improved handling of overlapping data and noise.

Let us consider what the “soft-margin formulation” is using code that creates and visualizes a machine-learning classifier separating two classes of data.

As the first step, we define a sample dataset in the form of two-dimensional points, where each point belongs to one of two classes. For example, the points $X=[[3,3],[3,4],[2,3],[1,1],[1,3],[2,2]]$ represent coordinates, and the array $y=[1,1,1,-1,-1,-1]$ indicates the class of each point. Here we have two classes: 1 and -1.

Next, we create a classifier using a support vector machine (SVM) with a linear kernel, setting parameter C=1.0. This parameter C is the key to understanding the “soft-margin formulation.” It determines how flexibly our classifier treats errors: a smaller value makes the model more tolerant of errors, that is, of margin violations, whereas a larger value requires a stricter separation between classes without errors.

After training the classifier on our data, we visualize the results. In the graph, points from different classes are marked with different colors, and you can see how the classifier constructs a separating line, or boundary, between the classes. The graph also shows the “soft margins” around this boundary, represented by dashed lines. These margins show where the model can allow classification errors in order to achieve better overall accuracy.

Support vectors are those data points that lie closest to the separating boundary. They play a key role in determining the position of this boundary, and in the graph they are highlighted with black circles.

from sklearn import svm  # Import the svm module from sklearn to work with support vector machines
import numpy as np       # Import NumPy to work with arrays
import matplotlib.pyplot as plt  # Import pyplot from matplotlib to visualize data

# Sample data: two-dimensional points and their class labels
X = np.array([  # Create an array of points in two-dimensional space, where each point is represented by a pair of values (x, y)
    [3, 3],
    [3, 4],
    [2, 3],
    [1, 1],
    [1, 3],
    [2, 2]
])

y = np.array([1, 1, 1, -1, -1, -1])  # Create an array of class labels for each point, where 1 and -1 represent different classes

# Create an SVM classifier with a linear kernel and a soft margin
clf = svm.SVC(kernel='linear', C=1.0)  # Initialize the SVM classifier with a linear kernel; parameter C controls the softness of the margin

# Train the classifier
clf.fit(X, y)  # Train the SVM on our data, allowing it to find the optimal decision boundary between the classes

# Visualization
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')  # Visualize the data points, coloring them according to class labels

ax = plt.gca()       # Get the current axes of the graph for further adjustment
xlim = ax.get_xlim() # Get the current range along the X axis
ylim = ax.get_ylim() # Get the current range along the Y axis

# Create a grid for evaluating the model
xx = np.linspace(xlim[0], xlim[1], 30)  # Generate sequential values along the X axis to create the grid
yy = np.linspace(ylim[0], ylim[1], 30)  # Generate sequential values along the Y axis to create the grid
YY, XX = np.meshgrid(yy, xx)            # Create a two-dimensional coordinate grid
xy = np.vstack([XX.ravel(), YY.ravel()]).T  # Transform the grid into a list of coordinate pairs for evaluation

Z = clf.decision_function(xy).reshape(XX.shape)  # Evaluate the SVM decision function at all grid points

# Draw the decision boundary and margins
ax.contour(
    XX, YY, Z,
    colors='k',
    levels=[-1, 0, 1],
    alpha=0.5,
    linestyles=['--', '-', '--']
)  # Draw contours at levels -1, 0, and 1, denoting margins and the decision boundary

# Mark the support vectors
ax.scatter(
    clf.support_vectors_[:, 0],
    clf.support_vectors_[:, 1],
    s=100,
    linewidth=1,
    facecolors='none',
    edgecolors='k'
)  # Visualize support vectors as large points with black edges

plt.show()  # Display the graph

This code uses a soft margin, set by parameter C, which allows some data points to violate the margin in order to achieve better generalization when the data are not linearly separable. The decision boundary, the line denoted by -, the margins, the lines denoted by --, and the support vectors, marked by large points, are visualized to illustrate how SVM works.

6.5.3 Classification Using Support Vector Machines with Curves

Support vector machines (SVMs) are traditionally associated with binary-classification tasks, but their principles can also be successfully adapted to solve multiclass-classification tasks. In this chapter we will consider how SVM can be applied to classify data into several classes, identify the strategies and algorithms that make this possible, and provide examples.

To implement multiclass classification using SVM, two main approaches are commonly used: “one-vs-one” (OvO) and “one-vs-all” (OvA).

One-vs-one (OvO): This method involves creating a binary classifier for each pair of classes. If we have $N$ classes, then $N(N-1)/2$ classifiers must be trained. Each classifier is trained using data from only two classes. When a new example is classified, voting is used: the object is assigned to the class most frequently chosen by the classifiers.

One-vs-all (OvA): In this case, a separate classifier is created for each class, distinguishing that class from all the others. Thus, if we have $N$ classes, we must train $N$ classifiers. To classify a new example, the class whose classifier gives the highest confidence score is selected.

Most modern machine-learning libraries, such as scikit-learn, provide built-in support for multiclass classification using SVM, automatically applying one of the above methods. During implementation, it is important to take into account the choice of kernel, regularization parameters, and feature scaling in order to improve model performance.

After considering support vector machines (SVMs) in the context of multiclass classification, it is important to mention a variation of this method known as Nu-SVM, or Nu-SVC for classification tasks. Nu-SVM is an alternative approach to classical SVM that allows the user to control the number of support vectors and errors through the nu parameter, which lies in the range from 0 to 1.

Nu-SVM preserves the basic principles of SVM while adapting them to provide greater flexibility in choosing a trade-off between the number of support vectors and the error margin. This makes Nu-SVM especially useful for tasks that require finer model tuning or when the data contain a great deal of noise.

Moving from traditional SVM to Nu-SVM in the context of multiclass classification allows us to take advantage of all the benefits of Nu-SVM, including its ability to handle both linear and nonlinear classification tasks effectively using different kernels.

The NuSVC classifier is one implementation of the support vector machine (SVM) method in the sklearn library for classification tasks.

NuSVC stands for “Nu-Support Vector Classification.” The nu parameter represents an upper bound on the fraction of misclassified examples and a lower bound on the fraction of support vectors relative to the total number of training examples. This allows the user to control the number of support vectors and errors through a single parameter, nu, which takes values from 0 to 1. The NuSVC class supports kernels and can work with linear and nonlinear data, making it a flexible tool for solving a wide variety of classification tasks.

The sklearn library also contains other SVM variants:

SVC: The main class for classification using support vector machines. It offers flexibility in kernel choice, including linear, polynomial, radial-basis-function, and sigmoid kernels, and is suitable for both linear and nonlinear tasks.

LinearSVC: A simplified version of SVC designed for linear classification. It usually works faster on large datasets and does not support kernels, because class separation is assumed to be linear.

SVR and NuSVR: These classifiers are used for regression tasks. SVR corresponds to the classical support vector method for regression, whereas NuSVR uses parameter nu similarly to NuSVC to control the number of support vectors.

The choice among SVC, NuSVC, and LinearSVC depends on the specific task and dataset. If the data are linearly separable or the dataset is large, it is preferable to use LinearSVC because of its high performance. For nonlinearly separable data, SVC or NuSVC can be used with an appropriate kernel.

To demonstrate multiclass classification using SVM in a practical example, we used the scikit-learn library and its SVC class from the svm module. However, before moving on to the code, it is important to discuss exactly how we can use scikit-learn to solve our task. The scikit-learn library offers a wide range of tools for machine learning, including various algorithms for classification, regression, and clustering. In the context of multiclass SVM classification, the functions and classes provided by the svm module are of particular interest.

The svm module contains not only the SVC class, which we used to create an SVM classifier, but also other useful tools and models, such as LinearSVC, which is intended for linear classification. It is important to understand that depending on the selected kernel type and parameters, the training and classification process can differ significantly, which in turn can affect model performance.

Using a synthetically generated dataset based on the XOR logical operation, we demonstrate the difficulty of the classification task that arises because of the nonlinearity of the class distribution. The NuSVC model, provided by the sklearn library, is selected as the classification tool; it makes it possible to find an optimal nonlinear decision boundary between data classes. The training results are visualized using matplotlib.pyplot, which allows the effectiveness of the SVM method under conditions of nonlinear class separability to be assessed visually. Visualization of the decision surface and the distribution of the original data emphasizes SVM’s ability to adapt to complex data structures and provide high classification accuracy. This study confirms the potential of support vector machines in a wide range of machine-learning tasks requiring efficient processing of nonlinearly separable data.

# Import the necessary libraries
import numpy as np
import matplotlib.pyplot as plt

# Import the svm module from sklearn. svm (Support Vector Machines) is a set of
# machine-learning methods used for classification, regression, and other tasks.
from sklearn import svm

# Create a two-dimensional coordinate grid using the meshgrid function.
# np.linspace(-3, 3, 500) creates uniformly distributed points in the range
# from -3 to 3 inclusive, 500 points in total. xx and yy are matrices of
# X and Y coordinates, respectively, for this grid.
xx, yy = np.meshgrid(np.linspace(-3, 3, 500), np.linspace(-3, 3, 500))

# Set the initial value for the random-number generator so that the results are reproducible.
np.random.seed(0)

# Generate 300 random points (vectors) with two coordinates, following a normal distribution.
X = np.random.randn(300, 2)

# Create an array of class labels using the exclusive OR (XOR) operation.
# If one coordinate of a point is positive and the other is negative, or vice versa,
# then the result is True (1); otherwise it is False (0).
Y = np.logical_xor(X[:, 0] > 0, X[:, 1] > 0)  # Create class labels using XOR

# Create a NuSVC classifier object, which is one implementation of SVM for classification.
clf = svm.NuSVC()

# Train the classifier clf on data X with labels Y.
clf.fit(X, Y)

# Compute the decision-function value for each point on the grid.
# np.c_[xx.ravel(), yy.ravel()] creates an array of grid points.
# ravel() transforms matrices into one-dimensional arrays, and np.c_ combines them into an array of point coordinates.
Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])

# Transform array Z back into a matrix shape corresponding to the shape of grid xx and yy,
# so that the result can be visualized on a graph.
Z = Z.reshape(xx.shape)

# Display matrix Z as an image on the graph. The parameters define the interpolation method,
# axis range, aspect ratio, starting point (lower-left corner), and color map.
plt.imshow(
    Z,
    interpolation='nearest',
    extent=(xx.min(), xx.max(), yy.min(), yy.max()),
    aspect='auto',
    origin='lower',
    cmap=plt.cm.BuGn
)

# Add contour lines to the graph showing the decision boundary.
# levels=[0] means that lines will be drawn where the decision function is equal to 0.
contours = plt.contour(xx, yy, Z, levels=[0], linewidths=2)

# Display data points X on the graph. The point color is specified according to their labels Y,
# using the jet color map.
plt.scatter(X[:, 0], X[:, 1], s=30, c=Y, cmap=plt.cm.jet)

# Remove labels from the X and Y axes.
plt.xticks(())
plt.yticks(())

# Set the boundaries of the displayed area.
plt.axis([-3, 3, -3, 3])

# Show the graph.
plt.show()

6.5.4 Multiclass Classification Using Support Vector Machines

In many machine-learning applications, data divided into multiple categories are common. Support vector machines are also suitable for solving classification tasks with many categories. To work with multiclass classification, methods are used that reduce it to binary classification, including “one-vs-all” and “one-vs-one” strategies. Let us conduct a comparative study on this topic.

Consider how support vector machines are applied to multiclass classification using the example of determining iris species by their form with the Iris dataset. We will evaluate four different types of SVM kernels: linear, polynomial, radial basis function (RBF), and LinearSVC, analyzing the first two parameters of the dataset—petal length and width. We will use familiar methods to create a coordinate grid and visualize the boundaries that separate classes in the models.

We will pay attention to how different SVM kernels divide feature space into classes and how they adapt to the characteristics of the data, which will be demonstrated in graphs for each model. It is also worth comparing the effectiveness of the linear kernel with RBF and polynomial kernels and evaluating the influence of regularization parameter C on the classification results.

import numpy as np  # Import NumPy to work with arrays
import matplotlib.pyplot as plt  # Import pyplot from matplotlib to build graphs
from sklearn import svm, datasets  # Scikit-learn (sklearn) is a Python machine-learning library that offers various tools for modeling and data analysis. The svm module provides tools for working with Support Vector Machines algorithms, and datasets contains standard datasets, including Iris.


def make_meshgrid(x, y, h=.02):
    # This function creates a coordinate grid that will be used to visualize decision boundaries.
    # x and y are arrays of feature values, and h is the grid step.
    # Here the limits for the coordinate grid are defined, expanding the minimum and maximum
    # values of x and y so that the boundaries are slightly beyond the extreme data points.
    x_min, x_max = x.min() - 1, x.max() + 1  # Compute the minimum and maximum values for x
    y_min, y_max = y.min() - 1, y.max() + 1  # Compute the minimum and maximum values for y
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))  # np.meshgrid creates a coordinate grid, which is a two-dimensional array of points. np.arange generates values within the specified limits with step h.
    return xx, yy  # Return the coordinate grid


def plot_contours(ax, clf, xx, yy, **params):
    # The function is intended to draw classifier decision contours on the graph.
    # ax is a matplotlib axes object, clf is the classifier, and xx and yy are coordinate grids.
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])  # np.c_ combines arrays xx and yy along the last axis, and ravel turns them into one-dimensional arrays. clf.predict makes predictions at each grid point.
    Z = Z.reshape(xx.shape)  # Transform prediction results into the grid shape
    out = ax.contourf(xx, yy, Z, **params)  # Draw decision contours
    return out  # Return the drawn contours


# Import some data for experiments
iris = datasets.load_iris()  # Load the Iris dataset
X = iris.data[:, :2]  # Take the first two features from the Iris dataset
y = iris.target  # Take class labels

C = 1.0  # SVM regularization parameter

# Create SVM model instances and train them on the data
models = (
    svm.SVC(kernel='linear', C=C),
    svm.LinearSVC(C=C, max_iter=10000),
    svm.SVC(kernel='rbf', gamma=0.7, C=C),
    svm.SVC(kernel='poly', degree=3, gamma='auto', C=C)
)
models = (clf.fit(X, y) for clf in models)  # Train the models

# Graph titles
titles = (
    'SVC with linear kernel',
    'LinearSVC (linear kernel)',
    'SVC with RBF kernel',
    'SVC with polynomial kernel (degree 3)'
)

fig, sub = plt.subplots(2, 2, figsize=(10, 8))  # Create the figure and subplots
plt.subplots_adjust(wspace=0.2, hspace=0.2)  # Adjust spacing between subplots

X0, X1 = X[:, 0], X[:, 1]  # Take feature values separately
xx, yy = make_meshgrid(X0, X1)  # Create a coordinate grid for drawing

# For each model and corresponding title, draw contours and points
for clf, title, ax in zip(models, titles, sub.flatten()):
    plot_contours(ax, clf, xx, yy, cmap='winter', alpha=0.8)  # Use the "winter" color map for contours (green and blue)
    ax.scatter(X0, X1, c=y, cmap=plt.cm.Greys, s=40, edgecolors='w')  # Draw points in white with black edges
    ax.set_xlim(xx.min(), xx.max())  # Set limits for the X axis
    ax.set_ylim(yy.min(), yy.max())  # Set limits for the Y axis
    ax.set_xlabel('Sepal length')  # Label the X axis
    ax.set_ylabel('Sepal width')  # Label the Y axis
    ax.set_xticks(())  # Remove tick marks on the X axis
    ax.set_yticks(())  # Remove tick marks on the Y axis
    ax.set_title(title)  # Set the subplot title

plt.show()  # Show the graph

Chapter Conclusions

Support vector machines (SVMs) are a powerful machine-learning tool used for classification and regression tasks, including multiclass classification, where they seek to divide data into several classes by maximizing the margin between them using optimal hyperplanes. In multiclass classification, strategies such as one-vs-all and one-vs-one are used to train classifiers that separate classes. To work with nonlinearly separable data, SVM uses the kernel trick, which allows classification to be performed in higher-dimensional spaces without the need to explicitly move into those spaces, using kernel functions such as polynomial, radial-basis-function, and sigmoid kernels. It is also important to choose parameters correctly, including regularization parameter C and kernel-function parameters, to control the balance between maximizing the margin and minimizing classification error, which affects the model’s ability to generalize. Although SVM is effective on data with clear class boundaries and handles high-dimensional data well, it can be sensitive to parameter choice and computationally demanding, especially in multiclass-classification tasks and with large volumes of data.

Check yourself

Which idea best describes the focus of "Perceptron and Support Vector Methods (SVM)"?

In machine learning, theoretical definitions are useful to check with numerical examples and visualizations.

Which actions help reinforce the chapter material?

Take quiz