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 from new category. 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 is less than the old model. 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.

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.

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, and X number of samples from the rest of categories.

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.

from keras import Model
from keras.models import Sequential
from keras.layers import Dense
from keras.optimizers import Nadam
import numpy as np


# Adds a new node at 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)
    # 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], np.zeros(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(input=model.input, output=sotfmax)
    # Set the weights for the new softmax layer
    model.get_layer(new_layer_name).set_weights(weights)
    return model


# return 2D data for given category sizes and centers
def generate_data(sizes, centers):
    Xs = []
    Ys = []
    category_count = len(sizes)
    indices = range(0, category_count)
    for category_index, size, center in zip(indices, sizes, centers):
        feature1 = np.random.normal(center[0], size=size)
        feature2 = np.random.normal(center[1], size=size)
        X = np.vstack((feature1, feature2)).T
        y = np.zeros((size, category_count))
        y[:, category_index] = 1
        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


seed = 12345
np.random.seed(seed)

model = Sequential()
model.add(Dense(10, 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=Nadam(), metrics=['accuracy'])

# In 2D feature space,
# first category is clustered around (0, 0),
# second category around (0, 2), and third category around (2, 0)
X, y = generate_data([1000, 1000], [[0, 0], [0, 2]])
# Train the model
model.fit(X, y, epochs=10)

# New (third) category arrives
X, y = generate_data([200, 200, 200], [[0, 0], [0, 2], [2, 0]])
# 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=Nadam(), metrics=['accuracy'])
# Train the extended model
model.fit(X, y, epochs=10)

If you test the code with zero number of samples from new (third) category, i.e.

X, y = generate_data([200, 200, 0], [[0, 0], [0, 2], [2, 0]])

you will see that the start accuracy of second fit is the continuation of the first fit, meaning that the model is extended and the old weights are kept intact.

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.

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 from new category. 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 is less than the old model. 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.