SGDClassifier: Online Learning/partial_fit with a previously unknown label

Question

My training set contains about 50k entries with which I do an initial learning. On a weekly basis, ~ 5k entries are added; but the same amount "disappears" (as it is user data which has to be deleted after some time).

Therefore I use online learning because I do not have access to the full dataset at a later time. Currently I'm using an SGDClassifier which works, but my big problem: new categories are appearing and now I can't use my model any more as they were not in the initial fit.

Is there a way with SGDClassifier or some other model? Deep learning?

It doesn't matter if I have to start from scratch NOW (i.e. use something other than SGDClassifier), but I need something which enables online learning with new labels.

Answer 1

It sounds like you don't want to start retraining the model every time a new label category appears. The easiest way to retain maximal information of past data would be train one classifier per category.

This way you can continue to train each classifier incrementally ("online") with something like SGDClassifier without having to retrain them. Whenever a new category appears you add a new binary classifier for just that category. You then select the class with the highest probability/score among the set of classifiers.

This is also not much different from what you are doing today, because scikit's SDGClassifier already handles the multiclass-scenario by fitting multiple "One vs All" classifiers under the hood.

If a lot of new categories keep coming up, of course, this approach might become a little tricky to manage.

Answer 2

If new categories are arriving very rarely, I myself prefer the "one vs all" solution provided by @oW_. For each new category, you train a new model on X number of samples from new category (class 1), and X number of samples from the rest of categories (class 0).

However, if new categories are arriving frequently and you want to use a single shared model, there is a way to accomplish this using neural networks.

In summary, upon the arrival of a new category, we add a corresponding new node to softmax layer with zero (or random) weights, and keep the old weights intact, then we train the extended model with the new data. Here is a visual sketch for the idea (drawn by myself):

Here is an implementation for the complete scenario:

1. Model is trained on two categories,

2. A new category arrives,

3. Model and target formats are updated accordingly,

4. Model is trained on new data.

Code:

from keras import Model
from keras.models import Sequential
from keras.layers import Dense
from keras.optimizers import Adam
from sklearn.metrics import f1_score
import numpy as np


# Add a new node to the last place in Softmax layer
def add_category(model, pre_soft_layer, soft_layer, new_layer_name, random_seed=None):
    weights = model.get_layer(soft_layer).get_weights()
    category_count = len(weights)
    # set 0 weight and negative bias for new category
    # to let softmax output a low value for new category before any training
    # kernel (old + new)
    weights[0] = np.concatenate((weights[0], np.zeros((weights[0].shape[0], 1))), axis=1)
    # bias (old + new)
    weights[1] = np.concatenate((weights[1], [-1]), axis=0)
    # New softmax layer
    softmax_input = model.get_layer(pre_soft_layer).output
    sotfmax = Dense(category_count + 1, activation='softmax', name=new_layer_name)(softmax_input)
    model = Model(inputs=model.input, outputs=sotfmax)
    # Set the weights for the new softmax layer
    model.get_layer(new_layer_name).set_weights(weights)
    return model


# Generate data for the given category sizes and centers
def generate_data(sizes, centers, label_noise=0.01):
    Xs = []
    Ys = []
    category_count = len(sizes)
    indices = range(0, category_count)
    for category_index, size, center in zip(indices, sizes, centers):
        X = np.random.multivariate_normal(center, np.identity(len(center)), size)
        # Smooth [1.0, 0.0, 0.0] to [0.99, 0.005, 0.005]
        y = np.full((size, category_count), fill_value=label_noise/(category_count - 1))
        y[:, category_index] = 1 - label_noise
        Xs.append(X)
        Ys.append(y)
    Xs = np.vstack(Xs)
    Ys = np.vstack(Ys)
    # shuffle data points
    p = np.random.permutation(len(Xs))
    Xs = Xs[p]
    Ys = Ys[p]
    return Xs, Ys


def f1(model, X, y):
    y_true = y.argmax(1)
    y_pred = model.predict(X).argmax(1)
    return f1_score(y_true, y_pred, average='micro')


seed = 12345
verbose = 0
np.random.seed(seed)

model = Sequential()
model.add(Dense(5, input_shape=(2,), activation='tanh', name='pre_soft_layer'))
model.add(Dense(2, input_shape=(2,), activation='softmax', name='soft_layer'))
model.compile(loss='categorical_crossentropy', optimizer=Adam())

# In 2D feature space,
# first category is clustered around (-2, 0),
# second category around (0, 2), and third category around (2, 0)
X, y = generate_data([1000, 1000], [[-2, 0], [0, 2]])
print('y shape:', y.shape)

# Train the model
model.fit(X, y, epochs=10, verbose=verbose)

# Test the model
X_test, y_test = generate_data([200, 200], [[-2, 0], [0, 2]])
print('model f1 on 2 categories:', f1(model, X_test, y_test))

# New (third) category arrives
X, y = generate_data([1000, 1000, 1000], [[-2, 0], [0, 2], [2, 0]])
print('y shape:', y.shape)

# Extend the softmax layer to accommodate the new category
model = add_category(model, 'pre_soft_layer', 'soft_layer', new_layer_name='soft_layer2')
model.compile(loss='categorical_crossentropy', optimizer=Adam())

# Test the extended model before training
X_test, y_test = generate_data([200, 200, 0], [[-2, 0], [0, 2], [2, 0]])
print('extended model f1 on 2 categories before training:', f1(model, X_test, y_test))

# Train the extended model
model.fit(X, y, epochs=10, verbose=verbose)

# Test the extended model on old and new categories separately
X_old, y_old = generate_data([200, 200, 0], [[-2, 0], [0, 2], [2, 0]])
X_new, y_new = generate_data([0, 0, 200], [[-2, 0], [0, 2], [2, 0]])
print('extended model f1 on two (old) categories:', f1(model, X_old, y_old))
print('extended model f1 on new category:', f1(model, X_new, y_new))

which outputs:

y shape: (2000, 2)
model f1 on 2 categories: 0.9275
y shape: (3000, 3)
extended model f1 on 2 categories before training: 0.8925
extended model f1 on two (old) categories: 0.88
extended model f1 on new category: 0.91

I should explain two points regarding this output:

1. Model performance is decreased from 0.9275 to 0.8925 by merely adding a new node. This is because the output of new node is also included for category selection. In practice, the output of new node should be included only after model is trained on a sizable sample. For example, we should peak the largest of first two entries in [0.15, 0.30, 0.55], i.e. 2nd class, at this stage.

2. Performance of extended model on two (old) categories 0.88 is less than the old model 0.9275. This is normal, because now the extended model wants to assign an input to one of three categories instead of two. This decrease is also expected when we select from three binary classifiers compared to two binary classifiers in "one vs all" approach.

Answer 3

I got to say that I haven't found any literature regarding this topic. As far as I know, what you ask is impossible. You should be aware of this, and the product owner should be too. The reason is that any loss function relies on known labels, so there is no way you can predict a label which is not in the training data. Also, is science-fiction that a machine learning algorithm can predict something which It hasn't been trained for

Having said so, I think there can be a workaround (let me point out that this is an opinion not based on formal literature). If the classifier is probabilistic, the output is the probability for each class to be true and the decission is the higher prob. Maybe you can set a threshold for that probability, such that the model predicts "unknown" if all probabilities are below that threshold. Let me give you an example.

Let $M(x)$ be a model such that: given an $x$, decides if $x$ belongs to one out of three categories $c_1, c_2, c_3$. The output of $M$ is a vector of probabilities $p$. The decision is made by taking the highest prob in $p$. So an output of $M(x) = p(x) = (0.2,0.76,0.5)$ would correspond to the decision $x$ belongs to $c_2$. You can modify this decision by setting a $\tau$ such if none of $p_i \geq \tau$ then the decision is $x$ belongs to unknown class

What do you do with those unknown's depends on bussines logic. If they are important, you can create a pool of them and re-train the model using available data. I think you can do sort of "transfer learning" from the trained model by changing the dimension of the output. But this is something I haven't faced, so I am just saying

Take on count that SGDClassifier uses SVM underneath, which is not a probabilistic algorithm. Following SGDClassifier documentation you can modify the loss argument to modified_huber or log in order to get probabilistic outputs.

Answer 4

There are two options:

1. Predict the chance of a datapoint belonging to an unknown or unk category. Any new categories that appear in the stream should be predicted as unk. This is common in Natural Language Processing (NLP) because there are always new word tokens appearing in word streams.

2. Retrain the model every time a new category appears.

Since you mention SGDClassifier, I assume you using scikit-learn. Scikit-learn does not support online learning very well. It would be better to switch a framework that better supports streaming and online learning, such as Spark.