6
$\begingroup$

So from Algorithm 3 of https://arxiv.org/pdf/1603.02754v3.pdf, it says that an optimum default direction is determined and the missing values will go in that direction. However, or perhaps I have misunderstood/missed the explanation from the article, it doesn't say what exactly is the input.

For example, I have (parent) node A (with 50 inputs) splitting into node B and node C. Now, say of the 50 inputs there are 7 missing values.

The other 43 inputs are split into B and C accordingly. What I seem to be understanding is that, it will allocate the remaining 7 into B and C and determine which one gives a higher gain score; that will be the optimal direction.

However, given the 7 values are missing (Which means I don't know what are these 7 values), how does allocating missing values into any of the child nodes change the gain score, or rather minimize the loss function? This seems to suggest that Xgboost is inputting something for the missing values. I can't seem to find out what is Xgboost inputting for these missing values. I hope this question isn't too vague/general and easy.

Edit: I think "Missing values" may be a vague term. What I meant here is (From wiki) "In statistics, missing data, or missing values, occur when no data value is stored for the variable in an observation."

From the author himself (https://github.com/dmlc/xgboost/issues/21), he said " tqchen commented on Aug 13, 2014 xgboost naturally accepts sparse feature format, you can directly feed data in as sparse matrix, and only contains non-missing value.

i.e. features that are not presented in the sparse feature matrix are treated as 'missing'. XGBoost will handle it internally and you do not need to do anything on it."

And,

" tqchen commented on Aug 13, 2014 Internally, XGBoost will automatically learn what is the best direction to go when a value is missing. Equivalently, this can be viewed as automatically "learn" what is the best imputation value for missing values based on reduction on training loss."

$\endgroup$
9
$\begingroup$

The procedure is described in their paper, section 3.4: Sparsity aware split-finding.

Assume you're at your node with 50 observations and, for the sake of simplicity, that there's only one split point possible.

For example, you have only one binary feature $x$, and your data can be split in three groups:

  • Group $B$: 20 observations such that $x=B$,
  • Group $C$: 20 observations such that $x=C$,
  • Group $M$: 10 observations such that $x=?$

The algorithm will split based on $x$, but does not know where to send the group $M$. It will try both assignments,

$$(B, M), C \qquad \text{and} \qquad B, (C, M),$$

compute the value to be assigned to the prediction at each node using all the data, and chose the assignment that minimizes the loss.

For example, if the split $(B, M), C$ is chosen, the value of the left node will have been computed from all the $B$ and $M$ samples.

This is what is meant by

Automatically "learn" what is the best imputation value for missing values based on reduction on training loss.


Comment question:

how can group M be calculated if I don't know what are the values for them?

The value we compute is not based on the feature $x$, which we don't know, but based on the known label/target of the sample. Let say we are doing a regression and trying to minimize the mean square error, and let say we have the following:

  • For group $B$, the mean of the target is $5$.
  • For group $C$, the mean of the target is $10$.
  • For the missing value group $M$, the mean of the target is $0$.

Note that even if the value of $x$ is missing, we know the value of target of the sample, otherwise we could not use it to train our model.

In this case, the split would be made on $(B,M), C$, the value assigned to the right node containing samples $C$ would be $10$, and the value assigned to the left node containing samples in $(B, M)$ would be the mean of the target for the whole group. In our example, the mean would be

$$\frac{|M|}{|B| + |M|}\text{mean}(M) + \frac{|B|}{|M|+|B|}\text{mean}(B) = \frac{10}{30}0 + \frac{20}{30}5 = 3.\overline{3}$$

$\endgroup$
  • 2
    $\begingroup$ Just to make sure I've understood what you've explained. Following your example, does this mean Xgboost is able to compute all the observations, but the 10 observations of Group M don't "naturally" (poor choice of word) belong to Group B and Group C. So it has to force the group Ms into one of them, which is determined by computing which assignment gives the better value; minimizes the loss. $\endgroup$ – mathnoob Nov 23 '16 at 10:51
  • $\begingroup$ In addition to that, how can group M be calculated if I don't know what are the values for them? Perhaps my initial example was misleading. I hope this clear things up, or if I'm misunderstanding something, please let me know. $\endgroup$ – mathnoob Nov 23 '16 at 11:02
  • 2
    $\begingroup$ @mathnoob Your first comment sounds right. For your second question the value we compute is not based on the feature x but on the value of the target y. I added an example to my answer. $\endgroup$ – Winks Nov 23 '16 at 11:32
  • 1
    $\begingroup$ That was really informative and cleared up everything. Thanks. $\endgroup$ – mathnoob Nov 23 '16 at 11:49
  • 1
    $\begingroup$ But if its using the label to impute, wouldnf then features that have a lot of missing values be more likely to be selected as opposed to features with less missing, as you are artificially adding these best fit values $\endgroup$ – JohnAndrews May 15 '18 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.