I am looking for a machine-learning (classification) model that can adapt to new data. By that, I don’t mean completely new samples in the online-learning sense, but rather additional details about an existing sample. Over time, for an existing sample, I learn an additional feature value that was missing before. (Once it is learned it doesn't change.) When I run an updated sample through the model, I would like to get a "more accurate" prediction.
The time and order at which new data becomes available are not consistent and features can still be missing at the end. In my training data, I only know the data that is available at the end and not when which feature value became available.
Most of the features are categorical and I am wondering if it would be enough to train a model by creating many synthetic samples where I randomly replace some of the categories with a “missing category” value. It seems to me though that this approach would not make sure that additional data would lead to a more confident prediction. The model would just see it as a new and different sample. How can I make sure that an update leads to a better prediction? Any hints are appreciated.