There are several ways to prune an ensemble of decision trees, but one very simple algorithm worth trying (based on a paper, but i can't seem to find it...)
| Subject | Repo | Branch | Lines +/- | |
|---|---|---|---|---|
| [WIP] Prune trees out of ensemble | search/MjoLniR | master | +475 -0 |
| Status | Subtype | Assigned | Task | ||
|---|---|---|---|---|---|
| Invalid | None | T174064 [FY 2017-18 Objective] Implement advanced search methodologies | |||
| Resolved | EBernhardson | T161632 [Epic] Improve search by researching and deploying machine learning to re-rank search results | |||
| Resolved | EBernhardson | T162053 backend data engineering and plumbing for LTRank | |||
| Resolved | EBernhardson | T172589 Evaluate ensemble pruning algorithms |
I implemented a hackish version of this and ran it against a 100 tree model that was trained against 32M observations. Removing trees changes the score as follows.
Not NDCG@10 started at 0.85267 before any pruning occured. Removing trees towards the beginning actually improves the quality of the model, to a max of 0.85452.
after removing 18 trees from the ensemble. We can actually remove 57 trees to get a score of 0.85262, which is basically where we started. I still need to verify this doesn't have any bugs, and it takes a pretty long time to run, but it has the possibility to improve both the prediction speed and quality.
| original | 0.8526755752893869 |
| tree_2 | 0.8534814588322 |
| tree_0 | 0.8538909954020505 |
| tree_11 | 0.8541095838822635 |
| tree_21 | 0.8542634118538496 |
| tree_6 | 0.8543745280649098 |
| tree_29 | 0.8544050371020617 |
| tree_45 | 0.8544274826847199 |
| tree_10 | 0.8544255519937989 |
| tree_37 | 0.8544375869530494 |
| tree_18 | 0.8544408309599962 |
| tree_34 | 0.8544474561717582 |
| tree_15 | 0.8544725794302217 |
| tree_36 | 0.8544827545143275 |
| tree_42 | 0.8544928642262134 |
| tree_89 | 0.8544738462653381 |
| tree_24 | 0.8544644147082961 |
| tree_9 | 0.854504026449298 |
| tree_53 | 0.8545170510360092 |
| tree_93 | 0.8545117159368455 |
| tree_27 | 0.8545035215863562 |
| tree_95 | 0.8544685327050491 |
| tree_32 | 0.8544535422863354 |
| tree_64 | 0.8544287328329437 |
| tree_55 | 0.854395964408186 |
| tree_96 | 0.854369822301337 |
| tree_77 | 0.8543500151487167 |
| tree_91 | 0.854305863199338 |
| tree_14 | 0.8542666708971052 |
| tree_41 | 0.8542712990849507 |
| tree_70 | 0.8542299714553042 |
| tree_7 | 0.8542042444488114 |
| tree_58 | 0.8541939735330666 |
| tree_49 | 0.8541717035392439 |
| tree_13 | 0.8541356953790398 |
| tree_51 | 0.8541207964722727 |
| tree_97 | 0.8540598286533062 |
| tree_99 | 0.854015412606587 |
| tree_71 | 0.8539626581870964 |
| tree_30 | 0.8539199821911418 |
| tree_81 | 0.8538999867708735 |
| tree_80 | 0.8538461584212078 |
| tree_83 | 0.853780443966831 |
| tree_75 | 0.853716799079589 |
| tree_12 | 0.8536494807128545 |
| tree_46 | 0.8535996969085202 |
| tree_44 | 0.8535830877257539 |
| tree_65 | 0.853513803103564 |
| tree_76 | 0.8534410623727549 |
| tree_98 | 0.8533755446461535 |
| tree_25 | 0.8533070197802961 |
| tree_94 | 0.853235075005165 |
| tree_60 | 0.8531295188375054 |
| tree_72 | 0.8530457529937424 |
| tree_17 | 0.8529358390428995 |
| tree_31 | 0.8528620763247267 |
| tree_86 | 0.8527532003555717 |
| tree_78 | 0.8526213412058438 |
| tree_3 | 0.8525442344947167 |
| tree_84 | 0.852476666779801 |
| tree_92 | 0.8523797543642866 |
| tree_90 | 0.8522665609566459 |
| tree_59 | 0.8521575076764754 |
| tree_74 | 0.8520365278367638 |
| tree_48 | 0.8519237583555358 |
| tree_88 | 0.8517729362227421 |
| tree_79 | 0.8515837661945378 |
| tree_56 | 0.8513936028459914 |
| tree_57 | 0.8511900407064946 |
| tree_23 | 0.8509923770767224 |
| tree_20 | 0.8508161664007255 |
| tree_1 | 0.8508919775646772 |
| tree_50 | 0.8508476731761839 |
| tree_85 | 0.8506608807573397 |
| tree_82 | 0.850436665692155 |
| tree_26 | 0.8502532154684804 |
| tree_63 | 0.850058777380352 |
| tree_69 | 0.849829952828476 |
| tree_68 | 0.8495063133023955 |
| tree_87 | 0.8491783598531001 |
| tree_19 | 0.8488870821504623 |
| tree_61 | 0.8485117174089658 |
| tree_66 | 0.8480505048222637 |
| tree_4 | 0.8477295548028438 |
| tree_38 | 0.8477711347061445 |
| tree_39 | 0.8477079286163248 |
| tree_73 | 0.847305095349432 |
| tree_62 | 0.8467135711435149 |
| tree_47 | 0.845966782660598 |
| tree_67 | 0.8450037023029577 |
| tree_28 | 0.8440031773679915 |
| tree_54 | 0.842850920442764 |
| tree_52 | 0.84124295635184 |
| tree_8 | 0.8395389344769163 |
| tree_40 | 0.8368481908112617 |
| tree_43 | 0.8333844979916419 |
| tree_35 | 0.829054869132139 |
| tree_22 | 0.8221793380482011 |
| tree_33 | 0.811557090832345 |
| tree_16 | 0.7735804255678047 |
| tree_5 | 0.34272244027773546 |
Change 376099 had a related patch set uploaded (by EBernhardson; owner: EBernhardson):
[search/MjoLniR@master] [WIP] Prune trees out of ensemble
We'll need to decide if this is just interesting or actually useful. We'll need to look at this further, moving to backlog board.
This was investigated. The final decision was that while interesting, it didn't provide enough benefit over the cost of both maintenance and model build time increases.
Change 376099 abandoned by EBernhardson:
[WIP] Prune trees out of ensemble
Reason:
interesting, but was too expensive to really use