<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@non_parametric_methods_notes" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Notes – Chapter 14: Non-parametric methods</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_methods_notes_top">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_methods_notes_top" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>
You can sequence through the Non-parametric methods lecture video and note segments (go to Next page). </p><p>
You can also (or alternatively) download the <a href="/assets/courseware/v1/2ea3ce073a6c2ff4d5ead87a661e7e41/asset-v1:MITx+6.036+1T2019+type@asset+block/notes_chapter_Non-parametric_methods.pdf" target="_blank">Chapter 14: Non-parametric methods</a> notes as a PDF file. </p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12a_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Introduction to non-parametric models</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12a">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12a" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Introduction to non-parametric models</h3>
<div
id="video_MIT6036L12a"
class="video closed"
data-metadata='{"streams": "1.00:wJ63CNfgSDY", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12a/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12a/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12a/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12a/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12a"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@non_parametric_intro_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Introduction to non-parametric methods</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_intro">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_intro" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>
We will continue to broaden the class of models that we can fit to our data. Neural networks have adaptable complexity, in the sense that we can try different structural models and use cross validation to find one that works well on our data. </p><p>
We now turn to models that automatically adapt their complexity to the training data. The name <em>non-parametric methods</em> is misleading: it is really a class of methods that does not have a fixed parameterization in advance. Some non-parametric models, such as decision trees, which we might call <em>semi-parametric methods</em>, can be seen as dynamically constructing something that ends up looking like a more traditional parametric model, but where the actual training data affects exactly what the form of the model will be. Other non-parametric methods, such as nearest-neighbor, rely directly on the data to make predictions and do not compute a model that summarizes the data. </p><p>
The semi-parametric methods tend to have the form of a composition of simple models. We'll look at: </p><ul class="itemize"><li><p><em>Tree models</em>: partition the input space and use different simple predictions on different regions of the space; this increases the hypothesis space. </p></li><li><p><em>Additive models</em>: train several different classifiers on the whole space and average the answers; this decreases the estimation error. </p></li></ul><p><em>Boosting</em> is a way to construct an additive model that decreases both estimation and structural error, but we won't address it in this class. </p><p>
Why are we studying these methods, in the heyday of neural networks? </p><ul class="itemize"><li><p>
They are fast to implement and have few or no hyper-parameters to tune. </p></li><li><p>
They often work as well or better than more complicated methods. </p></li><li><p>
Both can be easier to explain to a human user: decision-trees are fairly directly human-interpretable and nearest neighbor methods can justify their decision to some extend by showing a few training examples that the prediction was based on. </p></li></ul><p>
<br/></p><p>
<br/></p><p><a href="/assets/courseware/v1/2ea3ce073a6c2ff4d5ead87a661e7e41/asset-v1:MITx+6.036+1T2019+type@asset+block/notes_chapter_Non-parametric_methods.pdf" target="_blank">Download this chapter as a PDF file</a></p><span><br/><span style="color:gray;font-size:10pt"><center>This page was last updated on Friday May 24, 2019; 02:29:59 PM (revision 4f166135)</center></span></span>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12b_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Decision trees</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12b">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12b" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Decision trees</h3>
<div
id="video_MIT6036L12b"
class="video closed"
data-metadata='{"streams": "1.00:hDNFt7-Gvlc", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12b/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12b/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12b/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12b/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12b"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12c_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Regression trees - problem statement</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12c">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12c" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Regression trees - problem statement</h3>
<div
id="video_MIT6036L12c"
class="video closed"
data-metadata='{"streams": "1.00:0kpbar28_h8", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12c/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12c/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12c/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12c/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12c"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12d_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Building a tree - greedy algorithm</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12d">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12d" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Building a tree - greedy algorithm</h3>
<div
id="video_MIT6036L12d"
class="video closed"
data-metadata='{"streams": "1.00:b81imrBlVKE", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12d/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12d/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12d/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12d/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12d"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12e_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Building a tree - minimum error splits</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12e">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12e" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Building a tree - minimum error splits</h3>
<div
id="video_MIT6036L12e"
class="video closed"
data-metadata='{"streams": "1.00:e5l1Ycfc9p8", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12e/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12e/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12e/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12e/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12e"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12f_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Building a tree - pruning</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12f">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12f" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Building a tree - pruning</h3>
<div
id="video_MIT6036L12f"
class="video closed"
data-metadata='{"streams": "1.00:qGUFy_h8cZw", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12f/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12f/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12f/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12f/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12f"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12g_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Classification trees</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12g">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12g" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Classification trees</h3>
<div
id="video_MIT6036L12g"
class="video closed"
data-metadata='{"streams": "1.00:DV2YYIhFNwM", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12g/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12g/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12g/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12g/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12g"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12h_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Classification trees - impurity measures - gini index</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12h">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12h" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Classification trees - impurity measures - gini index</h3>
<div
id="video_MIT6036L12h"
class="video closed"
data-metadata='{"streams": "1.00:iKEtdZUHmJ0", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12h/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12h/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12h/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12h/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12h"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12j_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Classification trees - impurity measures - entropy</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12j">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12j" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Classification trees - impurity measures - entropy</h3>
<div
id="video_MIT6036L12j"
class="video closed"
data-metadata='{"streams": "1.00:F80O7uBkgPg", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12j/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12j/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12j/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12j/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12j"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12k_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Decision trees - the good and the bad</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12k">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12k" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Decision trees - the good and the bad</h3>
<div
id="video_MIT6036L12k"
class="video closed"
data-metadata='{"streams": "1.00:cHdgFU5blCE", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12k/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12k/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12k/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12k/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12k"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@non_parametric_trees_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Trees</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_trees">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_trees" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>
The idea here is that we would like to find a partition of the input space and then fit very simple models to predict the output in each piece. The partition is described using a (typically binary) “decision tree," which recursively splits the space. </p><p>
These methods differ by: </p><ul class="itemize"><li><p>
The class of possible ways to split the space at each node; these are generally linear splits, either aligned with the axes of the space, or sometimes more general classifiers. </p></li><li><p>
The class of predictors within the partitions; these are often simply constants, but may be more general classification or regression models. </p></li><li><p>
The way in which we control the complexity of the hypothesis: it would be within the capacity of these methods to have a separate partition for each individual training example. </p></li><li><p>
The algorithm for making the partitions and fitting the models. </p></li></ul><p>
The primary advantage of tree models is that they are easily interpretable by humans. This is important in application domains, such as medicine, where there are human experts who often ultimately make critical decisions and who need to feel confident in their understanding of recommendations made by an algorithm. </p><p>
These methods are most appropriate for domains where the input space is not very high-dimensional and where the individual input features have some substantially useful information individually or in small groups. They would not be good for image input, but might be good in cases with, for example, a set of meaningful measurements of the condition of a patient in the hospital. </p><p>
We'll concentrate on the CART/ID3 family of algorithms, which were invented independently in the statistics and the artificial intelligence communities. They work by greedily constructing a partition, where the splits are <em>axis aligned</em> and by fitting a <em>constant</em> model in the leaves. The interesting questions are how to select the splits and and how to control capacity. The regression and classification versions are very similar. </p><p><h3>Regression</h3></p><p>
The predictor is made up of </p><ul class="itemize"><li><p>
a partition function, [mathjaxinline]\pi[/mathjaxinline], mapping elements of the input space into exactly one of [mathjaxinline]M[/mathjaxinline] regions, [mathjaxinline]R_1, \ldots , R_ M[/mathjaxinline], and </p></li><li><p>
a collection of [mathjaxinline]M[/mathjaxinline] output values, [mathjaxinline]O_ m[/mathjaxinline], one for each region. </p></li></ul><p>
If we already knew a division of the space into regions, we would set [mathjaxinline]\hat{y}_ m[/mathjaxinline], the constant output for region [mathjaxinline]R_ m[/mathjaxinline], to be the average of the training output values in that region; that is: </p><table id="a0000000002" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]O_ m = {\rm average}_{\{ i \mid x^{(i)} \in R_ m\} }y^{(i)}\; \; .[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
Define the error in a region as </p><table id="a0000000003" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]E_ m = \sum _{\{ i \mid x^{(i)} \in R_ m\} }(y^{(i)} - O_ m)^2\; \; .[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
Ideally, we would select the partition to minimize </p><table id="a0000000004" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]\lambda M + \sum _{m=1}^ M E_ m\; \; ,[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
for some regularization constant [mathjaxinline]\lambda[/mathjaxinline]. It is enough to search over all partitions of the training data (not all partitions of the input space!) to optimize this, but the problem is NP-complete. <br/> <br/><span style="color:#FF0000"><b class="bf">Study Question:</b></span> <span style="color:#0000FF">Be sure you understand why it's enough to consider all partitions of the training data, if this is your objective.</span> <br/></p><p><h4>Building a tree</h4> So, we'll be greedy. We establish a criterion, given a set of data, for finding the best single split of that data, and then apply it recursively to partition the space. We will select the partition of the data that <em>minimizes the sum of the mean squared errors of each partition.</em> </p><p>
Given a data set [mathjaxinline]D[/mathjaxinline], let </p><ul class="itemize"><li><p>
[mathjaxinline]R^+_{j,s}(D) = \{ x \in D \mid x_ j \geq s\}[/mathjaxinline] be the set of examples in data set [mathjaxinline]D[/mathjaxinline] whose value in dimension [mathjaxinline]j[/mathjaxinline] is greater than or equal to [mathjaxinline]s[/mathjaxinline]; </p></li><li><p>
[mathjaxinline]R^-_{j,s}(D) = \{ x \in D \mid x_ j < s\}[/mathjaxinline] by the set of examples in [mathjaxinline]D[/mathjaxinline] whose value in dimension [mathjaxinline]j[/mathjaxinline] is less than [mathjaxinline]s[/mathjaxinline]; </p></li><li><p>
[mathjaxinline]\hat{y}^+_{j,s} = {\rm average}_{\{ i \mid x^{(i)} \in R^+_{j,s}(D)\} }y^{(i)}[/mathjaxinline] be the average [mathjaxinline]y[/mathjaxinline] value of the data points in set [mathjaxinline]R^+_{j,s}(D)[/mathjaxinline]; and </p></li><li><p>
[mathjaxinline]\hat{y}^-_{j,s} = {\rm average}_{\{ i \mid x^{(i)} \in R^-_{j,s}(D)\} }y^{(i)}[/mathjaxinline] be the average [mathjaxinline]y[/mathjaxinline] value of the data points in set [mathjaxinline]R^-_{j,s}(D)[/mathjaxinline]. </p></li></ul><p>
Now, here is the pseudocode. [mathjaxinline]{\bf BuildTree}(D)[/mathjaxinline]: </p><ul class="itemize"><li><p>
If [mathjaxinline]|D| \leq k[/mathjaxinline]: return [mathjaxinline]{\rm Leaf}(D)[/mathjaxinline] </p></li><li><p>
Find the variable [mathjaxinline]j[/mathjaxinline] and split point [mathjaxinline]s[/mathjaxinline] that minimizes: </p><table id="a0000000005" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]E_{R^+_{j,s}(D)} + E_{R^+_{j,s}(D)}\; \; .[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table></li><li><p>
Return [mathjaxinline]{\bf Node}(j, s, {\bf BuildTree}(R^+_{j,s}(D)), {\bf BuildTree}(R^-_{j,s}(D))[/mathjaxinline] </p></li></ul><p>
Each call to <b class="bf">BuildTree</b> considers [mathjaxinline]O(d n)[/mathjaxinline] splits (for [mathjaxinline]d[/mathjaxinline] dimensions, since we only need to split between each data point in each dimension); each requires [mathjaxinline]O(n)[/mathjaxinline] work. <br/> <br/><span style="color:#FF0000"><b class="bf">Study Question:</b></span> <span style="color:#0000FF">Concretely, what would be a good set of split-points to consider for dimension [mathjaxinline]j[/mathjaxinline] of a dataset [mathjaxinline]D[/mathjaxinline]?</span> <br/></p><p><h4>Pruning</h4> It might be tempting to regularize by using a somewhat large value of [mathjaxinline]k[/mathjaxinline], or by stopping when splitting a node does not significantly decrease the error. One problem with short-sighted stopping criteria is that they might not see the value of a split that will require one more split before it seems useful. <br/> <br/><span style="color:#FF0000"><b class="bf">Study Question:</b></span> <span style="color:#0000FF">Apply the decision-tree algorithm to the XOR problem in two dimensions. What is the training-set error of all possible hypothesis based on a single split?</span> <br/>So, we will tend to build a tree that is too large, and then prune it back. </p><p>
Define <em>cost complexity</em> of a tree [mathjaxinline]T[/mathjaxinline], where [mathjaxinline]m[/mathjaxinline] ranges over its leaves as </p><table id="a0000000006" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]C_\alpha (T) = \sum _{m = 1}^{|T|} E_ m(T) + \alpha |T|\; \; .[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
For a fixed [mathjaxinline]\alpha[/mathjaxinline], we can find a [mathjaxinline]T[/mathjaxinline] that (approximately) minimizes [mathjaxinline]C_\alpha (T)[/mathjaxinline] by “weakest-link" pruning: </p><ul class="itemize"><li><p>
Create a sequence of trees by successively removing the bottom-level split that minimizes the increase in overall error, until the root is reached. </p></li><li><p>
Return the [mathjaxinline]T[/mathjaxinline] in the sequence that minimizes the criterion. </p></li></ul><p>
We can choose an appropriate [mathjaxinline]\alpha[/mathjaxinline] using cross validation. </p><p><h3>Classification</h3></p><p>
The strategy for building and pruning classification trees is very similar to the strategy for regression trees. </p><p>
Given a region [mathjaxinline]R_ m[/mathjaxinline] corresponding to a leaf of the tree, we would pick the output class [mathjaxinline]y[/mathjaxinline] to be the value that exists most frequently (the <em>majority value</em>) in the data points whose [mathjaxinline]x[/mathjaxinline] values are in that region: </p><table id="a0000000007" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]O_ m = {\rm majority}_{\{ i \mid x^{(i)} \in R_ m\} }y^{(i)}\; \; .[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
Define the error in a region as the number of data points that do not have the value [mathjaxinline]O_ m[/mathjaxinline]: </p><table id="a0000000008" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]E_ m = \left|\{ i \mid x^{(i)} \in R_ m \; \text {and}\; y^{(i)} \not= O_ m\} \right|\; \; .[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
Define the <em>empirical probability</em> of an item from class [mathjaxinline]k[/mathjaxinline] occurring in region [mathjaxinline]m[/mathjaxinline] as: </p><table id="a0000000009" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]\hat{P}_{mk} = \hat{P}(R_ m)(k) = \frac{\left|\{ i \mid x^{(i)} \in R_ m \; \text {and}\; y^{(i)} = k\} \right|}{N_ m}\; \; ,[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
where [mathjaxinline]N_ m[/mathjaxinline] is the number of training points in region [mathjaxinline]m[/mathjaxinline]. We'll define the empirical probabilities of split values, as well, for later use. </p><table id="a0000000010" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]\hat{P}_{mjv} = \hat{P}(R_{mj})(v) = \frac{\left|\{ i \mid x^{(i)} \in R_ m \; \text {and}\; x^{(i)}_ j \geq v\} \right|}{N_ m}[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p><span style="color:ForestGreen"><b class="bf">Splitting criteria</b></span></p><p>
In our greedy algorithm, we need a way to decide which split to make next. There are many criteria that express some measure of the “impurity" in child nodes. Some measures include: </p><ul class="itemize"><li><p><em>Misclassification error</em>: </p><table id="a0000000011" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]Q_ m(T) = \frac{E_ m}{N_ m} = 1 - \hat{P}_{mO_ m}[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table></li><li><p><em>Gini index</em>: </p><table id="a0000000012" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]Q_ m(T) = \sum _ k \hat{P}_{mk}(1 - \hat{P}_{mk})[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table></li><li><p><em>Entropy</em>: </p><table id="a0000000013" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]Q_ m(T) = H(R_ m) = - \sum _ k \hat{P}_{mk} \log _2 \hat{P}_{mk}[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
So that this is well-defined when [mathjaxinline]\hat{P} = 0[/mathjaxinline], we will stipulate that [mathjaxinline]0 \log _2 0 = 0[/mathjaxinline]. </p></li></ul><p>
They are very similar, and it's not entirely obvious which one is better. We will focus on entropy, just to be concrete. </p><p>
Choosing the split that minimizes the entropy of the children is equivalent to maximize the <em>information gain</em> of the test [mathjaxinline]X_ j = v[/mathjaxinline], defined by </p><table id="a0000000014" cellpadding="7" width="100%" cellspacing="0" class="eqnarray" style="table-layout:auto"><tr id="a0000000015"><td style="width:40%; border:none"> </td><td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle {\rm infoGain}(X_ j = v, R_ m)[/mathjaxinline]
</td><td style="vertical-align:middle; text-align:center; border:none">
[mathjaxinline]\displaystyle =[/mathjaxinline]
</td><td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle H(R_ m) - \left(\hat{P}_{mjv}H(R^+_{j, v}) + (1 - \hat{P}_{mjv})H(R^-_{j, v})\right)[/mathjaxinline]
</td><td style="width:40%; border:none"> </td><td style="width:20%; border:none" class="eqnnum"> </td></tr></table><p>
In the two-class case, all the criteria have the values </p><table id="a0000000016" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]\begin{cases} 0.0 & \text {when $\hat{P}_{m0} = 0.0$}\\ 0.0 & \text {when $\hat{P}_{m0} = 1.0$} \end{cases}[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
The respective impurity curves are shown below, where [mathjaxinline]p = \hat{p }_{m0}[/mathjaxinline]: </p><center><img src="/assets/courseware/v1/3eb9db03ec84b67afe6ca924d26df677/asset-v1:MITx+6.036+1T2019+type@asset+block/images_impurity.png" width="400" style="scale:0.5"/></center><p>
There used to be endless haggling about which one to use. It seems to be traditional to use: </p><ul class="itemize"><li><p>
Entropy to select which node to split while growing the tree </p></li><li><p>
Misclassification error in the pruning criterion </p></li></ul><p>
As a concerete example, consider the following images: </p><center><img src="/assets/courseware/v1/055ac80fd30b1fcbe6444dd806b4212a/asset-v1:MITx+6.036+1T2019+type@asset+block/images_dt_points.png" width="400" style="scale:0.756"/><img src="/assets/courseware/v1/4c7780dd73b316087d8b4318c067c53b/asset-v1:MITx+6.036+1T2019+type@asset+block/images_dt_soln.png" width="400" style="scale:0.6"/></center><p>
The left image depicts a set of labeled data points and the right shows a partition into regions by a decision tree. </p><p><span style="color:ForestGreen"><b class="bf">Points about trees</b></span></p><p>
There are many variations on this theme: </p><ul class="itemize"><li><p>
Linear regression or other regression or classification method in each leaf </p></li><li><p>
Non-axis-parallel splits: e.g., run a perceptron for a while to get a split. </p></li></ul><p>
What's good about trees: </p><ul class="itemize"><li><p>
Easily interpretable </p></li><li><p>
Fast to train! </p></li><li><p>
Easy to handle multi-class classification </p></li><li><p>
Easy to handle different loss functions (just change predictor in the leaves) </p></li></ul><p>
What's bad about trees: </p><ul class="itemize"><li><p>
High estimation error: small changes in the data can result in very big changes in the hypothesis. </p></li><li><p>
Often not the best predictions </p></li></ul><p><span style="color:ForestGreen"><b class="bf">Hierarchical mixture of experts</b></span></p><p>
Make a “soft" version of trees, in which the splits are probabilistic (so every point has some degree of membership in every leaf). Can be trained with a form of gradient descent. </p><p>
<br/></p><p>
<br/></p><p><a href="/assets/courseware/v1/2ea3ce073a6c2ff4d5ead87a661e7e41/asset-v1:MITx+6.036+1T2019+type@asset+block/notes_chapter_Non-parametric_methods.pdf" target="_blank">Download this chapter as a PDF file</a></p><span><br/><span style="color:gray;font-size:10pt"><center>This page was last updated on Friday May 24, 2019; 02:29:59 PM (revision 4f166135)</center></span></span>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12m_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Bagging - bootstrap aggregation of models</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12m">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12m" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Bagging - bootstrap aggregation of models</h3>
<div
id="video_MIT6036L12m"
class="video closed"
data-metadata='{"streams": "1.00:2XFoq1NRiIg", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12m/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12m/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12m/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12m/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12m"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@non_parametric_bagging_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Bagging</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_bagging">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_bagging" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><em>Bootstrap aggregation</em> is a technique for reducing the estimation error of a non-linear predictor, or one that is adaptive to the data. </p><ul class="itemize"><li><p>
Construct [mathjaxinline]B[/mathjaxinline] new data sets of size [mathjaxinline]n[/mathjaxinline] by sampling them with replacement from [mathjaxinline]{\cal D}[/mathjaxinline] </p></li><li><p>
Train a predictor on each one: [mathjaxinline]\hat{f}^ b[/mathjaxinline] </p></li><li><p><em>Regression case</em>: bagged predictor is </p><table id="a0000000017" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]\hat{f}_{\rm bag}(x) = \frac{1}{B} \sum _{b=1}^ B \hat{f}^ b(x)[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table></li><li><p><em>Classification case</em>: majority bagged predictor: let [mathjaxinline]\hat{f}^ b(x)[/mathjaxinline] be a “one-hot" vector with a single 1 and [mathjaxinline]K-1[/mathjaxinline] zeros, so that [mathjaxinline]\hat{y}^ b(x) = {\rm arg}\max _{k} \hat{f}^ b(x)_ k[/mathjaxinline]. Then </p><table id="a0000000018" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]\hat{f}_{\rm bag}(x) = \frac{1}{B} \sum _{b=1}^ B \hat{f}^ b(x),[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
which is a vector containing the proportion of classifiers that predicted each class [mathjaxinline]k[/mathjaxinline] for input [mathjaxinline]x[/mathjaxinline]; and the predicted output is </p><table id="a0000000019" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]\hat{y}_{\rm bag}(x) = {\rm arg}\max _{k} \hat{f}_{\rm bag}(x)_ k\; \; .[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table></li></ul><p>
There are theoretical arguments showing that bagging does, in fact, reduce estimation error. </p><p>
However, when we bag a model, any simple predictability is lost. </p><p><h3>Random Forests</h3></p><p>
Random forests are collections of trees that are constructed to be de-correlated, so that using them to vote gives maximal advantage. In competitions, they often have the best classification performance among large collections of much fancier methods. </p><p>
For [mathjaxinline]b = 1 .. B[/mathjaxinline] </p><ul class="itemize"><li><p>
Draw a bootstrap sample [mathjaxinline]{\cal D}_ b[/mathjaxinline] of size [mathjaxinline]n[/mathjaxinline] from [mathjaxinline]{\cal D}[/mathjaxinline] </p></li><li><p>
Grow a tree on data [mathjaxinline]{\cal D}_ b[/mathjaxinline] by recursively repeating these steps: </p><ul class="itemize"><li><p>
Select [mathjaxinline]m[/mathjaxinline] variables at random from the [mathjaxinline]d[/mathjaxinline] variables </p></li><li><p>
Pick the best variable and split point among them </p></li><li><p>
Split the node </p></li></ul></li><li><p>
return tree [mathjaxinline]T_ b[/mathjaxinline] </p></li></ul><p>
Given the ensemble of trees, vote to make a prediction on a new [mathjaxinline]x[/mathjaxinline]. </p><p>
<br/></p><p>
<br/></p><p><a href="/assets/courseware/v1/2ea3ce073a6c2ff4d5ead87a661e7e41/asset-v1:MITx+6.036+1T2019+type@asset+block/notes_chapter_Non-parametric_methods.pdf" target="_blank">Download this chapter as a PDF file</a></p><span><br/><span style="color:gray;font-size:10pt"><center>This page was last updated on Friday May 24, 2019; 02:29:59 PM (revision 4f166135)</center></span></span>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12n_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Random forests models</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12n">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12n" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Random forests models</h3>
<div
id="video_MIT6036L12n"
class="video closed"
data-metadata='{"streams": "1.00:p5PTeED4fFY", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12n/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12n/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12n/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12n/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12n"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@MIT6036L12o_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Lecture: Nearest neighbor models</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12o">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12o" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Lecture: Nearest neighbor models</h3>
<div
id="video_MIT6036L12o"
class="video closed"
data-metadata='{"streams": "1.00:7B2eHRSt284", "savedVideoPosition": 0.0, "poster": null, "captionDataDir": null, "transcriptTranslationUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12o/handler/transcript/translation/__lang__", "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12o/handler/xmodule_handler/save_user_state", "ytTestTimeout": 1500, "autoplay": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionEnabled": false, "showCaptions": "true", "transcriptLanguages": {"en": "English"}, "end": 0.0, "start": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "generalSpeed": 1.0, "recordedYoutubeIsAvailable": true, "sources": [], "publishCompletionUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12o/handler/publish_completion", "speed": null, "duration": 0.0, "transcriptLanguage": "en", "ytMetadataEndpoint": "", "autoAdvance": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.036+1T2019/xblock/block-v1:MITx+6.036+1T2019+type@video+block@MIT6036L12o/handler/transcript/available_translations", "autohideHtml5": false, "completionPercentage": 0.95}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="MIT6036L12o"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-graded="False" data-init="VerticalStudentView" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@vertical+block@non_parametric_nearest_neighbor_vert" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Nearest Neighbor</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_nearest_neighbor">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-graded="False" data-init="XBlockToXModuleShim" data-runtime-version="1" data-has-score="False" data-usage-id="block-v1:MITx+6.036+1T2019+type@html+block@non_parametric_nearest_neighbor" data-course-id="course-v1:MITx+6.036+1T2019" data-request-token="178036d405d411f095120e84ffb47eb3" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>
In nearest-neighbor models, we don't do any processing of the data at training time–we just remember it! All the work is done at prediction time. </p><p>
Input values [mathjaxinline]x[/mathjaxinline] can be from any domain [mathjaxinline]\mathcal X[/mathjaxinline] ([mathjaxinline]\mathbb {R}^ d[/mathjaxinline], documents, tree-structured objects, etc.). We just need a distance metric, [mathjaxinline]d: \mathcal X \times \mathcal X \rightarrow \mathbb {R}^+[/mathjaxinline], which satisfies the following, for all [mathjaxinline]x, x', x" \in \mathcal X[/mathjaxinline]: </p><table id="a0000000020" cellpadding="7" width="100%" cellspacing="0" class="eqnarray" style="table-layout:auto"><tr id="a0000000021"><td style="width:40%; border:none"> </td><td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle d(x, x)[/mathjaxinline]
</td><td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle = 0[/mathjaxinline]
</td><td style="width:40%; border:none"> </td><td style="width:20%; border:none" class="eqnnum"> </td></tr><tr id="a0000000022"><td style="width:40%; border:none"> </td><td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle d(x, x')[/mathjaxinline]
</td><td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle = d(x', x)[/mathjaxinline]
</td><td style="width:40%; border:none"> </td><td style="width:20%; border:none" class="eqnnum"> </td></tr><tr id="a0000000023"><td style="width:40%; border:none"> </td><td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle d(x, x")[/mathjaxinline]
</td><td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle \leq d(x, x') + d(x', x")[/mathjaxinline]
</td><td style="width:40%; border:none"> </td><td style="width:20%; border:none" class="eqnnum"> </td></tr></table><p>
Given a data-set [mathjaxinline]\mathcal D = \{ (x^{(i)},y^{(i)})\} _{i=1}^ n[/mathjaxinline], our predictor for a new [mathjaxinline]x \in \mathcal X[/mathjaxinline] is </p><table id="a0000000024" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]h(x) = y^{(i)} \; \; \; \text {where}\; \; \; i = {\rm arg}\min _{i} d(x, x^{(i)})\; \; ,[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
that is, the predicted output associated with the training point that is closest to the query point [mathjaxinline]x[/mathjaxinline]. </p><p>
This same algorithm works for regression <em>and</em> <span options="" class="marginote"><span class="marginote_desc" style="display:none">It's a floor wax <em>and</em> a dessert topping!</span><span>classification! </span></span> </p><p>
The nearest neighbor prediction function can be described by a Voronoi partition (dividing the space up into regions whose closest point is each individual training point) as shown below: </p><center><img src="/assets/courseware/v1/8d13816de7fcbf1be3d685ff038e68ee/asset-v1:MITx+6.036+1T2019+type@asset+block/images_voronoi.png" width="400" style="scale:0.6"/></center><p>
In each region, we predict the associated [mathjaxinline]y[/mathjaxinline] value. <br/> <br/><span style="color:#FF0000"><b class="bf">Study Question:</b></span> <span style="color:#0000FF">Convince yourself that these boundaries do represent the nearest-neighbor classifier derived from these 6 data points.</span> <br/></p><p>
There are several useful variations on this method. In <em>[mathjaxinline]k[/mathjaxinline]-nearest-neighbors</em>, we find the [mathjaxinline]k[/mathjaxinline] training points nearest to the query point [mathjaxinline]x[/mathjaxinline] and output the majority [mathjaxinline]y[/mathjaxinline] value for classification or the average for regression. We can also do <em>locally weighted regression</em> in which we fit locally linear regression models to the [mathjaxinline]k[/mathjaxinline] nearest points, possibly giving less weight to those that are farther away. In large data-sets, it is important to use good data structures (e.g., ball trees) to perform the nearest-neighbor look-ups efficiently (without looking at all the data points each time). </p><p>
<br/></p><p>
<br/></p><p><a href="/assets/courseware/v1/2ea3ce073a6c2ff4d5ead87a661e7e41/asset-v1:MITx+6.036+1T2019+type@asset+block/notes_chapter_Non-parametric_methods.pdf" target="_blank">Download this chapter as a PDF file</a></p><script src="/assets/courseware/v1/1ab2c06aefab58693cfc9c10394b7503/asset-v1:MITx+6.036+1T2019+type@asset+block/marginotes.js" type="text/javascript"/><span><br/><span style="color:gray;font-size:10pt"><center>This page was last updated on Friday May 24, 2019; 02:29:59 PM (revision 4f166135)</center></span></span>
</div>
</div>
</div>
</div>
© All Rights Reserved