Training a regression algorithm with a variable number of features I need to train a regression algorithm with multiple features and a single label (predicted value). The problem is that this algorithm has to be able to do on-line learning and the number of features it will receive will vary. Let me give a clear example:

The algorithm is trained on a dataset of shape:

[--------Features-----------------] [Label]
[-- context11 -- | -- context12 --] [label1]


Then, for the next training example, one of the contexts might be missing, so the training example might either be:

[--------Features-----------------] [Label]
[-- context21 -- ]                  [label2]


or 

[--------Features-----------------] [Label]
                  [-- context22 --] [label2]


How can I deal with this situation? So far, I thought about two possibilities:


Replace the missing part of the features with zeros. I am not sure how this will affect the algorithm though.
Use a decision tree or random forest? Do these have a more natural way of dealing with a variable number of features?


Any other ideas?
I think in the specific case that you have given as an example, you can use approach 1 which you have mentioned above i.e. 

either replace the missing features with a zero value 

or otherwise you can also 

implement your algorithm in a sparse manner so that it doesn't need to always have all the features for an instance. 

Using a sparse format will not affect the runtime (or any other aspect) of your algorithm. Whereas, if you use the zeroing features approach, then your algorithm will have to do the unnecessary multiply by zero operations and this will increase your runtime ( How much? that depends on how sparse is your actual data).

Hope that helps.