If new categories are arriving very rarely, I myself prefer the "one vs all" solution provided by [@oW_][1]. 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. 

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

<img src="https://i.sstatic.net/BAdQO.png" width="500" />

Here is an implementation for the complete scenario: 

1. Model is trained on two categories, 

1. A new category arrives, 

1. Model and target formats are updated accordingly, 

1. 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 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.


  [1]: https://datascience.stackexchange.com/a/49341/67328
  [2]: https://i.sstatic.net/BAdQO.png