I've been implementing Random Forest from scratch as a learning exercise.
While most algorithms for decision trees seem to deal exclusively in binary yes/no questions, leading to binary trees, research has pointed me towards this question that asks about non binary trees, and algorithms such as CHAID that enable their creation.
This has left me wondering how these algorithms that create a node per possible value of a categorical value in the training set deal with possible new values of that same categorical feature in the testing set, or in production.
In my mind, it should be possible for a value of a categorical feature to be filtered out by previous splits on a tree (especially when there's many different possible values), due to the inherent and wanted randomness in bagging, creating a situation where a split for a specific value is "missing". Then, if this specific previously filtered value were to arrive to that same node in testing or production, it would have nowhere to go, since the splits would all be of the "is exactly this value" kind rather than a "is this value" "isn't this value" yes or no question like a binary tree would have.
I'm wondering how the algorithms deal with this possibility, if they do at all. Is it just assumed this will never happen? Do they use some special way of picking and bagging their data, with less randomness and more controlled sampling? Do they predict at a non terminal node if there's simply no next node the sample can go into? Do they select a next node randomly? None of these solutions sound optimal in my mind, but maybe I'm missing something.
