Machine Learning in C++: Linear and Logistic Regression from Scratch

Machine learning has become an integral part of many software applications we use every day, from recommendation systems to facial recognition to fraud detection. While Python has emerged as the go-to language for machine learning in recent years due to its simplicity and wealth of libraries like scikit-learn and TensorFlow, C++ remains a compelling choice in certain situations.

C++‘s advantages for machine learning include:

• Performance: C++ is much faster than Python, which is important when working with very large datasets or deploying models that need to make predictions in real-time. ML models built in C++ can have an order of magnitude less latency.

• Control: C++ gives developers fine-grained control over system resources and memory usage. Careful optimization of C++ code can further improve performance.

• Legacy codebases: In industries like robotics, defense, healthcare and finance, critical systems are often built in C++. Implementing machine learning in C++ allows integrating with these existing codebases.

In this post, we‘ll dive into two fundamental machine learning algorithms – linear regression and logistic regression – and walk through how to implement them from scratch in C++. In the process, we‘ll develop an intuition for how these techniques work and when to use them.

Linear Regression

Linear regression is a supervised learning algorithm used to predict a continuous quantity. Conceptually, it tries to find a line of best fit through the training data that minimizes the distances (residuals) between the predicted values and actual values.

Mathematically, if x is the input variable and y is the output variable we‘re trying to predict, the equation for the line is:

y = B0 + B1*x

• B0 is the y-intercept (value of y when x=0)
• B1 is the slope of the line (how much y changes for a 1 unit increase in x)

The key question is: how do we find the optimal values of the coefficients B0 and B1? This is where gradient descent comes in.

Gradient Descent

Gradient descent is an iterative optimization algorithm that incrementally tweaks the coefficients to minimize a loss function. For linear regression, a common loss function is mean squared error (MSE):

MSE = 1/N * Σ(y_predicted – y_actual)^2

The gradient is the derivative of the loss function with respect to each coefficient. It tells us the direction to move the coefficient values in order to reduce the loss. The magnitude of movement is controlled by the learning rate hyperparameter.

Here‘s the pseudocode:
Repeat until convergence: {

1. Calculate predicted y using current coefficient values
2. Calculate MSE loss
3. Calculate gradients of loss wrt coefficients
4. Update coefficients in the direction opposite to gradient
   }

By taking many small steps in the direction that minimizes the loss, we‘ll eventually converge to the optimal B0 and B1. We just have to be careful not to set the learning rate too high (causes divergence) or too low (slow convergence).

Implementing Linear Regression in C++

Now let‘s see how to code this up in C++. Full code is available on GitHub, but we‘ll break down the key parts here.

We‘ll start by defining our training data:

// Input data (X)
vector<double> X = {1, 2, 3, 4, 5};

// Output data (Y)  
vector<double> Y = {5, 7, 9, 11, 13};

And initializing the coefficients and hyperparameters:

double B0 = 0.0;      // Bias term  
double B1 = 0.0;      // Weight for input  
double learning_rate = 0.01;
int num_epochs = 1000;

The training loop performs a step of gradient descent for a set number of epochs:

for (int i = 0; i < num_epochs; i++) {
  // Make predictions
  vector<double> Yhat;
  for (int j = 0; j < X.size(); j++) {
    double yhat = B0 + B1 * X[j];
    Yhat.push_back(yhat);
  } 

  // Calculate gradients
  double dB0 = -2.0 * accumulate(Y.begin(), Y.end(), 0.0) + 2.0 * accumulate(Yhat.begin(), Yhat.end(), 0.0);
  double dB1 = -2.0 * inner_product(X.begin(), X.end(), Y.begin(), 0.0) + 2.0 * inner_product(X.begin(), X.end(), Yhat.begin(), 0.0);

  // Update coefficients
  B0 -= learning_rate * dB0;
  B1 -= learning_rate * dB1;
}

After training, we can use the model to make predictions on new data:

double new_x = 6.0;
double yhat = B0 + B1 * new_x;
cout << "Prediction: " << yhat << endl;

This prints out:

Prediction: 14.9842

Which is quite close to the actual value of 15. We‘ve successfully built a linear regression model in C++!

Logistic Regression

While linear regression is used to predict continuous quantities, logistic regression is a classification algorithm used to predict a discrete label (or class). The most common usage is binary classification, where the output is one of two classes, usually denoted as 0 and 1.

Some examples:

• Spam email detection (spam or not spam)
• Churn prediction (customer will churn or not churn)
• Disease diagnosis (has disease or doesn‘t have disease)

Under the hood, logistic regression still computes a weighted sum of the input features, but it then applies the logistic function to squash this value between 0 and 1. This output can be interpreted as the probability of belonging to class 1.

Mathematically, this looks like:

y = 1 / (1 + e^-(B0 + B1*x))

Where:

• y is the predicted probability of class 1 (between 0 and 1)
• e is the natural exponential

To make a final classification, we choose a decision threshold, typically 0.5. If y >= 0.5, we classify the example as class 1, else class 0.

Implementing Logistic Regression in C++

The code for logistic regression looks very similar to linear regression, with a few key differences.

First, our data consists of two input features and a class label:

// Input data (X1 and X2)
vector<double> X1 = {2.7810836,1.465489372,3.396561688,1.38807019,3.06407232,7.627531214,5.332441248,6.922596716,8.675418651,7.673756466};
vector<double> X2 = {2.550537003,2.362125076,4.400293529,1.850220317,3.005305973,2.759262235,2.088626775,1.77106367,2.230851207,3.508563011};

// Output data (Y)
vector<double> Y = {0,0,0,0,0,1,1,1,1,1};

We also have an additional coefficient/weight for the second input feature:

double B0 = 0.0;
double B1 = 0.0;
double B2 = 0.0;

In the prediction step, we apply the logistic function:

vector<double> Yhat;
for (int j = 0; j < X1.size(); j++) {
  double z = B0 + B1 * X1[j] + B2 * X2[j];
  double yhat = 1.0 / (1.0 + exp(-z));
  Yhat.push_back(yhat);
}

The loss function is now log loss instead of mean squared error, but gradient descent still works the same way conceptually.

To make a final class prediction, we compare the predicted probability to 0.5:

double new_x1 = 7.673756466;
double new_x2 = 3.508563011;
double z = B0 + B1*new_x1 + B2*new_x2;
double prob = 1.0 / (1.0 + exp(-z));

int pred_class;
if (prob >= 0.5) {
  pred_class = 1;
} else {
  pred_class = 0;  
}
cout << "Predicted class: " << pred_class << endl;

Running this gives:

Predicted class: 1

Confirming that we‘ve built a working logistic regression classifier in C++!

Tips for Optimizing Machine Learning in C++

While C++ is known for its performance, there are still some best practices to keep in mind when implementing machine learning algorithms:

• Use vectors instead of arrays for dynamic resizing
• Pass large objects and vectors by reference to avoid copying
• Prefer pre-increment (++i) to post-increment (i++)
• Use initialization lists for constructors
• Avoid creating unnecessary variables
• Disable synchronization for I/O streams if not needed

Many of these are general C++ performance tips, but they definitely still apply in a machine learning context. Optimizing the linear algebra operations is especially important as most ML algorithms involve a large amount of matrix math.

C++ vs Python for Machine Learning

You may be wondering, why bother with C++ when Python has such a rich ecosystem for machine learning? While Python and scikit-learn are great for prototyping and experimentation, there are several reasons why you might want to use C++ for certain machine learning tasks:

• Performance: C++ is much faster than Python, particularly for computationally intensive tasks. This is important when working with huge datasets or deploying low-latency models in production.

• Control: C++ gives you fine-grained control over system resources and memory usage. You can optimize your code to run efficiently on embedded devices or custom hardware.

• Existing codebases: If you‘re working on a system that is primarily built in C++, it often makes sense to implement machine learning in the same language to avoid the overhead of bindings between languages.

That said, Python is still the lingua franca of machine learning, and it‘s hard to beat the ease of use of scikit-learn and the deep learning frameworks. My recommendation would be to prototype in Python, and then port performance-critical portions to C++ as needed.

Importance of Machine Learning Fundamentals

Regardless of which programming language you use, what‘s most important is to develop a strong understanding of the underlying machine learning concepts and algorithms.

Implementing algorithms from scratch, like we did in this post, is a great way to build intuition for how they work under the hood. But you don‘t have to do this every time – once you understand the fundamentals, you can leverage libraries like Torch, Shark and mlpack to be more productive.

In addition to linear and logistic regression, some other important machine learning concepts to learn are:

• Regularization (L1/L2)
• Support vector machines
• Decision trees and random forests
• K-means clustering
• Dimensionality reduction (PCA)
• Neural networks

I‘d recommend checking out classic texts like Pattern Recognition and Machine Learning by Bishop and machine learning courses on Coursera or Udemy.

Wrapping Up

In this post, we covered how to implement two fundamental machine learning algorithms – linear and logistic regression – from scratch in C++. In the process, we saw:

• How linear regression makes continuous predictions by minimizing the residuals between predicted and actual values
• How logistic regression estimates the probability of a binary outcome
• How gradient descent iteratively optimizes model coefficients
• Tips for writing performant C++ code for machine learning
• How C++ compares to Python for machine learning tasks

I hope this post inspires you to dive deeper into machine learning and gives you the foundation to implement more advanced algorithms in C++. While we focused on regression here, the same concepts extend to other supervised and unsupervised learning techniques.

To learn more, I recommend checking out:

• Hands-On Machine Learning with C++ by Kirill Kolodiazhnyi
• mlpack C++ machine learning library
• Shark C++ machine learning library
• Dlib C++ library
• Torch C++ deep learning framework

Happy machine learning in C++!