Alternating decision tree

Motivation

Original boosting algorithms typically used either decision stumps or decision trees as weak hypotheses. As an example, boosting decision stumps creates a set of ${\displaystyle T}$ weighted decision stumps (where ${\displaystyle T}$ is the number of boosting iterations), which then vote on the final classification according to their weights. Individual decision stumps are weighted according to their ability to classify the data.

Boosting a simple learner results in an unstructured set of ${\displaystyle T}$ hypotheses, making it difficult to infer correlations between attributes. Alternating decision trees introduce structure to the set of hypotheses by requiring that they build off a hypothesis that was produced in an earlier iteration. The resulting set of hypotheses can be visualized in a tree based on the relationship between a hypothesis and its "parent."

Another important feature of boosted algorithms is that the data is given a different distribution at each iteration. Instances that are misclassified are given a larger weight while accurately classified instances are given reduced weight.

Alternating decision tree structure

An alternating decision tree consists of decision nodes and prediction nodes. Decision nodes specify a predicate condition. Prediction nodes contain a single number. ADTrees always have prediction nodes as both root and leaves. An instance is classified by an ADTree by following all paths for which all decision nodes are true and summing any prediction nodes that are traversed. This is different from binary classification trees such as CART (Classification and regression tree) or C4.5 in which an instance follows only one path through the tree.

Example

The following tree was constructed using JBoost on the spambase dataset (available from the UCI Machine Learning Repository). In this example, spam is coded as 1 and regular email is coded as −1.

The following table contains part of the information for a single instance.

The instance is scored by summing all of the prediction nodes through which it passes. In the case of the instance above, the score is calculated as

The final score of 0.657 is positive, so the instance is classified as spam. The magnitude of the value is a measure of confidence in the prediction. The original authors list three potential levels of interpretation for the set of attributes identified by an ADTree:

• Individual nodes can be evaluated for their own predictive ability.
• Sets of nodes on the same path may be interpreted as having a joint effect
• The tree can be interpreted as a whole.

Care must be taken when interpreting individual nodes as the scores reflect a re weighting of the data in each iteration.

Description of the algorithm

The inputs to the alternating decision tree algorithm are:

• A set of inputs ${\displaystyle (x_1,y_1),\dots ,(x_m,y_m)}$ where ${\displaystyle x_i}$ is a vector of attributes and ${\displaystyle y_i}$ is either -1 or 1. Inputs are also called instances.
• A set of weights ${\displaystyle w_i}$ corresponding to each instance.

The fundamental element of the ADTree algorithm is the rule. A single rule consists of a precondition, a condition, and two scores. A condition is a predicate of the form "attribute <comparison> value." A precondition is simply a logical conjunction of conditions. Evaluation of a rule involves a pair of nested if statements:

1 <b id="mwjg">if</b> (precondition) 2 <b id="mwjw">if</b> (condition) 3 <b id="mwkA">return</b> score_one 4 <b id="mwkQ">else</b> 5 <b id="mwkg">return</b> score_two 6 <b id="mwkw">end if</b> 7 <b id="mwlA">else</b> 8 <b id="mwlQ">return</b> 0 9 <b id="mwlg">end if</b>

Several auxiliary functions are also required by the algorithm:

• ${\displaystyle W_{+}(c)}$ returns the sum of the weights of all positively labeled examples that satisfy predicate ${\displaystyle c}$
• ${\displaystyle W_{-}(c)}$ returns the sum of the weights of all negatively labeled examples that satisfy predicate ${\displaystyle c}$
• ${\displaystyle W(c)=W_{+}(c)+W_{-}(c)}$ returns the sum of the weights of all examples that satisfy predicate ${\displaystyle c}$

The algorithm is as follows:

1 <b id="mwpA">function</b> ad_tree 2 <b id="mwpQ">input</b> Set of <span class="texhtml mvar" style="font-style:italic;" about="#mwt40" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"mvar","href":"./Template:Mvar"},"params":{"1":{"wt":"m"}},"i":0}}]}' id="mwpg">m</span> training instances 3 4 <span class="texhtml " about="#mwt41" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"math","href":"./Template:Math"},"params":{"1":{"wt":"''w<sub>i</sub>'' = 1/''m''"}},"i":0}}]}' id="mwpw"><i>w<sub>i</sub></i> = 1/<i>m</i></span> for all <span class="texhtml mvar" style="font-style:italic;" about="#mwt42" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"mvar","href":"./Template:Mvar"},"params":{"1":{"wt":"i"}},"i":0}}]}' id="mwqA">i</span> 5 <span class="nowrap" about="#mwt43" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>a = \\frac 1 2 \\textrm{ln}\\frac{W_+(true)}{W_-(true)}</math>"}},"i":0}}]}' id="mwqQ"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt44" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"a = \\frac 1 2 \\textrm{ln}\\frac{W_+(true)}{W_-(true)}"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(true)}{W_{-}(true)}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext>ln</mtext> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mi>r</mi> <mi>u</mi> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−<!-- − --></mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mi>r</mi> <mi>u</mi> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(true)}{W_{-}(true)}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb96f9955809b0294e1bd4f73813cdd9837aefbe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:18.918ex; height:6.509ex;" alt="{\displaystyle a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(true)}{W_{-}(true)}}}"/></span></span> 6 <span class="texhtml " about="#mwt45" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"math","href":"./Template:Math"},"params":{"1":{"wt":"''R''<sub>0</sub> ="}},"i":0}}]}' id="mwqg"><i>R</i><sub>0</sub> =</span> a rule with scores <span class="texhtml mvar" style="font-style:italic;" about="#mwt46" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"mvar","href":"./Template:Mvar"},"params":{"1":{"wt":"a"}},"i":0}}]}' id="mwqw">a</span> and <span class="texhtml " about="#mwt47" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"math","href":"./Template:Math"},"params":{"1":{"wt":"0"}},"i":0}}]}' id="mwrA">0</span>, precondition "true" and condition "true." 7 <span class="nowrap" about="#mwt48" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>\\mathcal{P} = \\{true\\}</math>"}},"i":0}}]}' id="mwrQ"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt49" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\mathcal{P} = \\{true\\}"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\mathcal {P}}=\{true\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>t</mi> <mi>r</mi> <mi>u</mi> <mi>e</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}=\{true\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/67bc4b5199a361668268075361f184788d09f38d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.428ex; height:2.843ex;" alt="{\displaystyle {\mathcal {P}}=\{true\}}"/></span></span> 8 <span class="nowrap" about="#mwt50" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>\\mathcal{C} = </math> the set of all possible conditions"}},"i":0}}]}' id="mwrg"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt51" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\mathcal{C} = "}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\mathcal {C}}=}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">C</mi> </mrow> </mrow> <mo>=</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}=}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/82b7bcca93bed7fd2bb4e1c0ea3e7c702d227c2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.692ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}=}"/></span> the set of all possible conditions</span> 9 <span class="nowrap" about="#mwt52" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"'''for''' <math>j = 1 \\dots T</math>"}},"i":0}}]}' id="mwrw"><b>for</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt53" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"j = 1 \\dots T"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle j=1\dots T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>=</mo> <mn>1</mn> <mo>…<!-- … --></mo> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j=1\dots T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b84cfa3159281dd86952a26b2c3f5806871472d8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:10.379ex; height:2.509ex;" alt="{\displaystyle j=1\dots T}"/></span></span> 10 <span class="nowrap" about="#mwt54" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>p \\in \\mathcal{P}, c \\in \\mathcal{C} </math> get values"}},"i":0}}]}' id="mwsA"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt55" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"p \\in \\mathcal{P}, c \\in \\mathcal{C} "}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle p\in {\mathcal {P}},c\in {\mathcal {C}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>∈<!-- ∈ --></mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mo>,</mo> <mi>c</mi> <mo>∈<!-- ∈ --></mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p\in {\mathcal {P}},c\in {\mathcal {C}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0000acfaf8b73ee23ecd622d960cc03f2557357f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:11.924ex; height:2.509ex;" alt="{\displaystyle p\in {\mathcal {P}},c\in {\mathcal {C}}}"/></span> get values</span> <span class="nowrap" about="#mwt56" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"that minimize <math> z = 2 \\left( \\sqrt{W_+(p \\wedge c) W_-(p \\wedge c)} + \\sqrt{W_+(p \\wedge \\neg c) W_-(p \\wedge \\neg c)} \\right) +W(\\neg p) </math>"}},"i":0}}]}' id="mwsQ">that minimize <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt57" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" z = 2 \\left( \\sqrt{W_+(p \\wedge c) W_-(p \\wedge c)} + \\sqrt{W_+(p \\wedge \\neg c) W_-(p \\wedge \\neg c)} \\right) +W(\\neg p) "}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle z=2\left({\sqrt {W_{+}(p\wedge c)W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)W_{-}(p\wedge \neg c)}}\right)+W(\neg p)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>z</mi> <mo>=</mo> <mn>2</mn> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi>c</mi> <mo stretchy="false">)</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−<!-- − --></mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi>c</mi> <mo stretchy="false">)</mo> </msqrt> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi mathvariant="normal">¬<!-- ¬ --></mi> <mi>c</mi> <mo stretchy="false">)</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−<!-- − --></mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi mathvariant="normal">¬<!-- ¬ --></mi> <mi>c</mi> <mo stretchy="false">)</mo> </msqrt> </mrow> </mrow> <mo>)</mo> </mrow> <mo>+</mo> <mi>W</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">¬<!-- ¬ --></mi> <mi>p</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle z=2\left({\sqrt {W_{+}(p\wedge c)W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)W_{-}(p\wedge \neg c)}}\right)+W(\neg p)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/50c8da613301197c565e4d8c5b85a95b24c32eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:69.995ex; height:4.843ex;" alt="{\displaystyle z=2\left({\sqrt {W_{+}(p\wedge c)W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)W_{-}(p\wedge \neg c)}}\right)+W(\neg p)}"/></span></span> 11 <span class="nowrap" about="#mwt58" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>\\mathcal{P} += p \\wedge c + p \\wedge \\neg c</math>"}},"i":0}}]}' id="mwsg"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt59" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\mathcal{P} += p \\wedge c + p \\wedge \\neg c"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\mathcal {P}}+=p\wedge c+p\wedge \neg c}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mo>+</mo> <mo>=</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi>c</mi> <mo>+</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi mathvariant="normal">¬<!-- ¬ --></mi> <mi>c</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}+=p\wedge c+p\wedge \neg c}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ebf5f59657ae3016c8425ed463886f0e8f198111" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.519ex; height:2.509ex;" alt="{\displaystyle {\mathcal {P}}+=p\wedge c+p\wedge \neg c}"/></span></span> 12 <span class="nowrap" about="#mwt60" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>a_1=\\frac{1}{2}\\textrm{ln}\\frac{W_+(p\\wedge c)+1}{W_-(p \\wedge c)+1}</math>"}},"i":0}}]}' id="mwsw"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt61" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"a_1=\\frac{1}{2}\\textrm{ln}\\frac{W_+(p\\wedge c)+1}{W_-(p \\wedge c)+1}"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext>ln</mtext> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi>c</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> <mrow> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−<!-- − --></mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi>c</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6de62a7b0e5dbe8ed749a43735367c03e0780489" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:24.432ex; height:6.509ex;" alt="{\displaystyle a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}}"/></span></span> 13 <span class="nowrap" about="#mwt62" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>a_2=\\frac{1}{2}\\textrm{ln}\\frac{W_+(p\\wedge \\neg c)+1}{W_-(p \\wedge \\neg c)+1}</math>"}},"i":0}}]}' id="mwtA"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt63" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"a_2=\\frac{1}{2}\\textrm{ln}\\frac{W_+(p\\wedge \\neg c)+1}{W_-(p \\wedge \\neg c)+1}"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext>ln</mtext> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi mathvariant="normal">¬<!-- ¬ --></mi> <mi>c</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> <mrow> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−<!-- − --></mo> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>∧<!-- ∧ --></mo> <mi mathvariant="normal">¬<!-- ¬ --></mi> <mi>c</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2d9fd2a86e01f4ecb86c165ee2f98ff443c413f9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:25.982ex; height:6.509ex;" alt="{\displaystyle a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}}"/></span></span> 14 <span class="texhtml " about="#mwt64" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"math","href":"./Template:Math"},"params":{"1":{"wt":"''R<sub>j</sub>'' ="}},"i":0}}]}' id="mwtQ"><i>R<sub>j</sub></i> =</span> new rule with precondition <span class="texhtml mvar" style="font-style:italic;" about="#mwt65" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"mvar","href":"./Template:Mvar"},"params":{"1":{"wt":"p"}},"i":0}}]}' id="mwtg">p</span>, condition <span class="texhtml mvar" style="font-style:italic;" about="#mwt66" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"mvar","href":"./Template:Mvar"},"params":{"1":{"wt":"c"}},"i":0}}]}' id="mwtw">c</span>, and weights <span class="texhtml " about="#mwt67" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"math","href":"./Template:Math"},"params":{"1":{"wt":"''a''<sub>1</sub>"}},"i":0}}]}' id="mwuA"><i>a</i><sub>1</sub></span> and <span class="texhtml " about="#mwt68" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"math","href":"./Template:Math"},"params":{"1":{"wt":"''a''<sub>2</sub>"}},"i":0}}]}' id="mwuQ"><i>a</i><sub>2</sub></span> 15 <span class="nowrap" about="#mwt69" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"nowrap","href":"./Template:Nowrap"},"params":{"1":{"wt":"<math>w_i = w_i e^{ -y_i R_j(x_i) }</math>"}},"i":0}}]}' id="mwug"><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt70" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"w_i = w_i e^{ -y_i R_j(x_i) }"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−<!-- − --></mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f9b5d6fa0690250f745c603471e0c864a6314ab6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.857ex; height:3.176ex;" alt="{\displaystyle w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}}"/></span></span> 16 <b id="mwuw">end for</b> 17 <b id="mwvA">return</b> set of <span class="texhtml " about="#mwt71" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"math","href":"./Template:Math"},"params":{"1":{"wt":"''R<sub>j</sub>''"}},"i":0}}]}' id="mwvQ"><i>R<sub>j</sub></i></span>

The set ${\displaystyle \mathcal{P}}$ grows by two preconditions in each iteration, and it is possible to derive the tree structure of a set of rules by making note of the precondition that is used in each successive rule.

Empirical results

Figure 6 in the original paper demonstrates that ADTrees are typically as robust as boosted decision trees and boosted decision stumps. Typically, equivalent accuracy can be achieved with a much simpler tree structure than recursive partitioning algorithms.