problem description.html

<!DOCTYPE html>
<!-- saved from url=(0082)http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp2.html -->
<html lang="en-us"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <link href="http://gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  

  <!-- Enable responsiveness on mobile devices-->
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">

  <title>
    
      MP2— Text Categorization · CS 6501: Text Mining
    
  </title>

  <!-- CSS -->
  <link rel="stylesheet" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/css/poole.css">
  <link rel="stylesheet" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/css/syntax.css">
  <link rel="stylesheet" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/css/lanyon.css">
  <link rel="stylesheet" href="http://fonts.googleapis.com/css?family=PT+Serif:400,400italic,700%7CPT+Sans:400">

  <!-- Icons -->
  <link rel="apple-touch-icon-precomposed" sizes="144x146" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/UVA_Rotunda_Logo.png">
  <link rel="shortcut icon" sizes="32x32" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/uva_rotunda.jpg">  
<style type="text/css">.MathJax_Hover_Frame {border-radius: .25em; -webkit-border-radius: .25em; -moz-border-radius: .25em; -khtml-border-radius: .25em; box-shadow: 0px 0px 15px #83A; -webkit-box-shadow: 0px 0px 15px #83A; -moz-box-shadow: 0px 0px 15px #83A; -khtml-box-shadow: 0px 0px 15px #83A; border: 1px solid #A6D ! important; display: inline-block; position: absolute}
.MathJax_Hover_Arrow {position: absolute; width: 15px; height: 11px; cursor: pointer}
</style><style type="text/css">#MathJax_About {position: fixed; left: 50%; width: auto; text-align: center; border: 3px outset; padding: 1em 2em; background-color: #DDDDDD; color: black; cursor: default; font-family: message-box; font-size: 120%; font-style: normal; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; z-index: 201; border-radius: 15px; -webkit-border-radius: 15px; -moz-border-radius: 15px; -khtml-border-radius: 15px; box-shadow: 0px 10px 20px #808080; -webkit-box-shadow: 0px 10px 20px #808080; -moz-box-shadow: 0px 10px 20px #808080; -khtml-box-shadow: 0px 10px 20px #808080; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
.MathJax_Menu {position: absolute; background-color: white; color: black; width: auto; padding: 2px; border: 1px solid #CCCCCC; margin: 0; cursor: default; font: menu; text-align: left; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; z-index: 201; box-shadow: 0px 10px 20px #808080; -webkit-box-shadow: 0px 10px 20px #808080; -moz-box-shadow: 0px 10px 20px #808080; -khtml-box-shadow: 0px 10px 20px #808080; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
.MathJax_MenuItem {padding: 2px 2em; background: transparent}
.MathJax_MenuArrow {position: absolute; right: .5em; color: #666666}
.MathJax_MenuActive .MathJax_MenuArrow {color: white}
.MathJax_MenuArrow.RTL {left: .5em; right: auto}
.MathJax_MenuCheck {position: absolute; left: .7em}
.MathJax_MenuCheck.RTL {right: .7em; left: auto}
.MathJax_MenuRadioCheck {position: absolute; left: 1em}
.MathJax_MenuRadioCheck.RTL {right: 1em; left: auto}
.MathJax_MenuLabel {padding: 2px 2em 4px 1.33em; font-style: italic}
.MathJax_MenuRule {border-top: 1px solid #CCCCCC; margin: 4px 1px 0px}
.MathJax_MenuDisabled {color: GrayText}
.MathJax_MenuActive {background-color: Highlight; color: HighlightText}
.MathJax_Menu_Close {position: absolute; width: 31px; height: 31px; top: -15px; left: -15px}
</style><style type="text/css">.MathJax_Preview .MJXc-math {color: inherit!important}
</style><style type="text/css">#MathJax_Zoom {position: absolute; background-color: #F0F0F0; overflow: auto; display: block; z-index: 301; padding: .5em; border: 1px solid black; margin: 0; font-weight: normal; font-style: normal; text-align: left; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; box-shadow: 5px 5px 15px #AAAAAA; -webkit-box-shadow: 5px 5px 15px #AAAAAA; -moz-box-shadow: 5px 5px 15px #AAAAAA; -khtml-box-shadow: 5px 5px 15px #AAAAAA; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
#MathJax_ZoomOverlay {position: absolute; left: 0; top: 0; z-index: 300; display: inline-block; width: 100%; height: 100%; border: 0; padding: 0; margin: 0; background-color: white; opacity: 0; filter: alpha(opacity=0)}
#MathJax_ZoomFrame {position: relative; display: inline-block; height: 0; width: 0}
#MathJax_ZoomEventTrap {position: absolute; left: 0; top: 0; z-index: 302; display: inline-block; border: 0; padding: 0; margin: 0; background-color: white; opacity: 0; filter: alpha(opacity=0)}
</style><style type="text/css">.MathJax_Preview {color: #888}
#MathJax_Message {position: fixed; left: 1em; bottom: 1.5em; background-color: #E6E6E6; border: 1px solid #959595; margin: 0px; padding: 2px 8px; z-index: 102; color: black; font-size: 80%; width: auto; white-space: nowrap}
#MathJax_MSIE_Frame {position: absolute; top: 0; left: 0; width: 0px; z-index: 101; border: 0px; margin: 0px; padding: 0px}
.MathJax_Error {color: #CC0000; font-style: italic}
</style><style type="text/css">.MathJax_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}
.MathJax .merror {background-color: #FFFF88; color: #CC0000; border: 1px solid #CC0000; padding: 1px 3px; font-style: normal; font-size: 90%}
.MathJax .MJX-monospace {font-family: monospace}
.MathJax .MJX-sans-serif {font-family: sans-serif}
#MathJax_Tooltip {background-color: InfoBackground; color: InfoText; border: 1px solid black; box-shadow: 2px 2px 5px #AAAAAA; -webkit-box-shadow: 2px 2px 5px #AAAAAA; -moz-box-shadow: 2px 2px 5px #AAAAAA; -khtml-box-shadow: 2px 2px 5px #AAAAAA; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true'); padding: 3px 4px; z-index: 401; position: absolute; left: 0; top: 0; width: auto; height: auto; display: none}
.MathJax {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}
.MathJax img, .MathJax nobr, .MathJax a {border: 0; padding: 0; margin: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; vertical-align: 0; line-height: normal; text-decoration: none}
img.MathJax_strut {border: 0!important; padding: 0!important; margin: 0!important; vertical-align: 0!important}
.MathJax span {display: inline; position: static; border: 0; padding: 0; margin: 0; vertical-align: 0; line-height: normal; text-decoration: none}
.MathJax nobr {white-space: nowrap!important}
.MathJax img {display: inline!important; float: none!important}
.MathJax * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}
.MathJax_Processing {visibility: hidden; position: fixed; width: 0; height: 0; overflow: hidden}
.MathJax_Processed {display: none!important}
.MathJax_ExBox {display: block!important; overflow: hidden; width: 1px; height: 60ex; min-height: 0; max-height: none}
.MathJax .MathJax_EmBox {display: block!important; overflow: hidden; width: 1px; height: 60em; min-height: 0; max-height: none}
.MathJax .MathJax_HitBox {cursor: text; background: white; opacity: 0; filter: alpha(opacity=0)}
.MathJax .MathJax_HitBox * {filter: none; opacity: 1; background: transparent}
#MathJax_Tooltip * {filter: none; opacity: 1; background: transparent}
@font-face {font-family: MathJax_Main; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Main-Regular.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Main-Regular.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Main-bold; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Main-Bold.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Main-Bold.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Main-italic; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Main-Italic.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Main-Italic.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Math-italic; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Math-Italic.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Math-Italic.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Caligraphic; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Caligraphic-Regular.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Caligraphic-Regular.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Size1; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Size1-Regular.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Size1-Regular.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Size2; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Size2-Regular.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Size2-Regular.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Size3; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Size3-Regular.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Size3-Regular.otf?rev=2.5.3') format('opentype')}
@font-face {font-family: MathJax_Size4; src: url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/woff/MathJax_Size4-Regular.woff?rev=2.5.3') format('woff'), url('http://cdn.mathjax.org/mathjax/latest/fonts/HTML-CSS/TeX/otf/MathJax_Size4-Regular.otf?rev=2.5.3') format('opentype')}
.MathJax .noError {vertical-align: ; font-size: 90%; text-align: left; color: black; padding: 1px 3px; border: 1px solid}
</style><style type="text/css">.MJXc-script {font-size: .8em}
.MJXc-right {-webkit-transform-origin: right; -moz-transform-origin: right; -ms-transform-origin: right; -o-transform-origin: right; transform-origin: right}
.MJXc-bold {font-weight: bold}
.MJXc-italic {font-style: italic}
.MJXc-scr {font-family: MathJax_Script,'Times New Roman',Times,STIXGeneral,serif}
.MJXc-frak {font-family: MathJax_Fraktur,'Times New Roman',Times,STIXGeneral,serif}
.MJXc-sf {font-family: MathJax_SansSerif,'Times New Roman',Times,STIXGeneral,serif}
.MJXc-cal {font-family: MathJax_Caligraphic,'Times New Roman',Times,STIXGeneral,serif}
.MJXc-mono {font-family: MathJax_Typewriter,'Times New Roman',Times,STIXGeneral,serif}
.MJXc-largeop {font-size: 150%}
.MJXc-largeop.MJXc-int {vertical-align: -.2em}
.MJXc-math {display: inline-block; line-height: 1.2; text-indent: 0; font-family: 'Times New Roman',Times,STIXGeneral,serif; white-space: nowrap; border-collapse: collapse}
.MJXc-display {display: block; text-align: center; margin: 1em 0}
.MJXc-math span {display: inline-block}
.MJXc-box {display: block!important; text-align: center}
.MJXc-box:after {content: " "}
.MJXc-rule {display: block!important; margin-top: .1em}
.MJXc-char {display: block!important}
.MJXc-mo {margin: 0 .15em}
.MJXc-mfrac {margin: 0 .125em; vertical-align: .25em}
.MJXc-denom {display: inline-table!important; width: 100%}
.MJXc-denom > * {display: table-row!important}
.MJXc-surd {vertical-align: top}
.MJXc-surd > * {display: block!important}
.MJXc-script-box > *  {display: table!important; height: 50%}
.MJXc-script-box > * > * {display: table-cell!important; vertical-align: top}
.MJXc-script-box > *:last-child > * {vertical-align: bottom}
.MJXc-script-box > * > * > * {display: block!important}
.MJXc-mphantom {visibility: hidden}
.MJXc-munderover {display: inline-table!important}
.MJXc-over {display: inline-block!important; text-align: center}
.MJXc-over > * {display: block!important}
.MJXc-munderover > * {display: table-row!important}
.MJXc-mtable {vertical-align: .25em; margin: 0 .125em}
.MJXc-mtable > * {display: inline-table!important; vertical-align: middle}
.MJXc-mtr {display: table-row!important}
.MJXc-mtd {display: table-cell!important; text-align: center; padding: .5em 0 0 .5em}
.MJXc-mtr > .MJXc-mtd:first-child {padding-left: 0}
.MJXc-mtr:first-child > .MJXc-mtd {padding-top: 0}
.MJXc-mlabeledtr {display: table-row!important}
.MJXc-mlabeledtr > .MJXc-mtd:first-child {padding-left: 0}
.MJXc-mlabeledtr:first-child > .MJXc-mtd {padding-top: 0}
.MJXc-merror {background-color: #FFFF88; color: #CC0000; border: 1px solid #CC0000; padding: 1px 3px; font-style: normal; font-size: 90%}
.MJXc-scale0 {-webkit-transform: scaleX(.0); -moz-transform: scaleX(.0); -ms-transform: scaleX(.0); -o-transform: scaleX(.0); transform: scaleX(.0)}
.MJXc-scale1 {-webkit-transform: scaleX(.1); -moz-transform: scaleX(.1); -ms-transform: scaleX(.1); -o-transform: scaleX(.1); transform: scaleX(.1)}
.MJXc-scale2 {-webkit-transform: scaleX(.2); -moz-transform: scaleX(.2); -ms-transform: scaleX(.2); -o-transform: scaleX(.2); transform: scaleX(.2)}
.MJXc-scale3 {-webkit-transform: scaleX(.3); -moz-transform: scaleX(.3); -ms-transform: scaleX(.3); -o-transform: scaleX(.3); transform: scaleX(.3)}
.MJXc-scale4 {-webkit-transform: scaleX(.4); -moz-transform: scaleX(.4); -ms-transform: scaleX(.4); -o-transform: scaleX(.4); transform: scaleX(.4)}
.MJXc-scale5 {-webkit-transform: scaleX(.5); -moz-transform: scaleX(.5); -ms-transform: scaleX(.5); -o-transform: scaleX(.5); transform: scaleX(.5)}
.MJXc-scale6 {-webkit-transform: scaleX(.6); -moz-transform: scaleX(.6); -ms-transform: scaleX(.6); -o-transform: scaleX(.6); transform: scaleX(.6)}
.MJXc-scale7 {-webkit-transform: scaleX(.7); -moz-transform: scaleX(.7); -ms-transform: scaleX(.7); -o-transform: scaleX(.7); transform: scaleX(.7)}
.MJXc-scale8 {-webkit-transform: scaleX(.8); -moz-transform: scaleX(.8); -ms-transform: scaleX(.8); -o-transform: scaleX(.8); transform: scaleX(.8)}
.MJXc-scale9 {-webkit-transform: scaleX(.9); -moz-transform: scaleX(.9); -ms-transform: scaleX(.9); -o-transform: scaleX(.9); transform: scaleX(.9)}
.MathJax_CHTML .noError {vertical-align: ; font-size: 90%; text-align: left; color: black; padding: 1px 3px; border: 1px solid}
</style></head>


  <body><div id="MathJax_Message" style="display: none;"></div><div style="visibility: hidden; overflow: hidden; position: absolute; top: 0px; height: 1px; width: auto; padding: 0px; border: 0px; margin: 0px; text-align: left; text-indent: 0px; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal;"><div id="MathJax_Hidden"></div></div>

    <script type="text/javascript" src="./problem description_files/MathJax.js">
    </script> 
    
    <script type="text/x-mathjax-config;executed=true">
      MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']],
                         displayMath: [['\\[','\\]'], ['$$','$$']]}});
    </script>

    <!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Formula for this course: <br><b>Text Mining = Data Mining + Text Data</b></p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site">Home</a>

    
          <a class="sidebar-nav-item" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/assignments/">Homework</a>
        
      
          <a class="sidebar-nav-item" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/lectures/">Lectures</a>
        
      
          <a class="sidebar-nav-item" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/presentation/">Paper Presentation</a>
        
      
          <a class="sidebar-nav-item" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/project/">Course Project</a>
        
      
          <a class="sidebar-nav-item" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/quizzes/">Quizzes</a>
        
      
          <a class="sidebar-nav-item" href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/resources/">Resources</a>
        
      
  </nav>

  <div class="sidebar-item">
  	<p>
  		Currently v1.0.0
  	</p>
    <p>
      © 2015. All rights reserved. <a href="http://www.cs.virginia.edu/">CS@UVa</a>
    </p>
  </div>
</div>


    <!-- Wrap is the content to shift when toggling the sidebar. We wrap the
         content to avoid any CSS collisions with our real content. -->
    <div class="wrap">
      <div class="masthead">
        <div class="container">
          <h3 class="masthead-title">
            <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site" title="Home">CS 6501: Text Mining</a>
            <small>Spring 2015 · <a href="http://www.cs.virginia.edu/">CS@UVa</a></small>
          </h3>
        </div>
      </div>

      <div class="container content">
        <p>This assignment is designed to help you practice with general steps in building a text categorization system. It  consists of four tasks and a bonus task, including feature selection, building Naive Bayes classifier, kNN classifier, and classification performance evaluation, totaling 100 points (with additional 15 points as bonus).</p>

<!--snippet-->

<ul>
<li><strong>Task 1: <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp2.html#fv">Feature selection</a></strong> <em>(30 points)</em>: implement two basic feature selection methods, i.e., Information Gain and Chi Square, for selecting high-quality text features;<br></li>
<li><strong>Task 2: <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp2.html#nb">Naive Bayes</a></strong> <em>(20 points)</em>: build a Naive Bayes classifier for text document classification;</li>
<li><strong>Task 3: <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp2.html#knn">k Nearest Neighbor</a></strong> <em>(25 points)</em>: build a k Nearest Neighbor classifier with random projection for text document classification;</li>
<li><strong>Task 4: <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp2.html#eval">Classification performance evaluation</a></strong> <em>(25 points)</em>: evaluate the constructed classifiers with standard classification performance metrics, including precision, recall and F-measure.<br></li>
<li><strong>Bonus Task: <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp2.html#bonus">Explore the best configuration of kNN</a></strong> <em>(15 points)</em>: use cross-validation to find the best hyper-parameter setting in kNN classifier with random projection.<br></li>
</ul>

<p>The deadline and submission guidance are explicitly described <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp2.html#time">here</a>.</p>

<h1>Data Set</h1>

<p>We will use the same small Yelp review data set as we used in MP1 on the CS lab servers (e.g., <em>labunix01.cs.virginia.edu</em>, <em>labunix02.cs.virginia.edu</em>, <em>labunix03.cs.virginia.edu</em>):</p>
<div class="highlight"><pre><code class="language-text" data-lang="text">"/home/hw5x/TextMining/MP1/data/Yelp_Small" 
</code></pre></div>
<p>More details of this review data set can be found in our previous <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp1.html">MP1 description</a>.</p>

<p>Please reuse your implementation for MP1 as much as possible. Based that, you should be able to finish this assignment without too much effort. </p>

<p><em>HINT: since we have posted a sample solution provided by Mohammad Al Boni, you can refer to it to solve the following MP2 tasks.</em> </p>

<h1><a name="preparation"></a>Preparation: Creating a classification task</h1>

<h2>Terminologies</h2>

<p>We will keep using the same terminologies as we used in MP1. </p>

<ul>
<li><strong>Document</strong>: it refers to each individual Yelp review document contained in the json file. Therefore, one json file might contain multiple review documents.<br></li>
<li><strong>Restaurant</strong>: it refers to a specific restaurant entity contained in the given review data set. It is uniquely identified by the corresponding Yelp ID; and one json for one restaurant.<br></li>
<li><strong>DF/IDF/TF/TTF/Cosine similarity</strong>: the definitions for those metrics strictly follow those on our lecture slides, unless specifically defined below.</li>
</ul>

<h2>Basic text processing techniques</h2>

<p>We will use the same text processing techniques as we have explored in MP1, including tokenization, stemming, normalization and stopword removal (please use the standard <a href="http://jmlr.org/papers/volume5/lewis04a/a11-smart-stop-list/english.stop">Smart system's stopword list</a>). More action details can be found in our previous <a href="http://www.cs.virginia.edu/~hw5x/Course/Text-Mining-2015-Spring/_site/mps/mp1.html">description of MP1</a>. Note, in all the following tasks, we will only use <strong>unigram as our feature</strong> and <strong>json files in the train folder</strong>.   </p>

<h2>Defining the classes</h2>

<p>For each review document in this data set, it is associated with a numeric overall rating in the range of 1 to 5. We will treat the review documents with overall rating <strong>below 4 as negative (labeled as 0)</strong> and <strong>the rest as positive (labeled as 1)</strong>. As a result, we have created a binary text classification problem. </p>

<h1><a name="fv"></a>Task 1: Feature Selection (30pts)</h1>

<p>Based on the basic text processing steps we have taken in MP1, we have created a vector representation for every review document in our collection. Next we will implement two most effective text feature selection methods, i.e., Information Gain and Chi Square, to further refine this representation.</p>

<p>The definitions of Information Gain and Chi Square feature selector are as follows (please also refer to our lecture slides),</p>

<p><span class="MathJax_Preview" style="color: inherit;"></span><div class="MathJax_Display" style="text-align: center;"><span class="MathJax" id="MathJax-Element-1-Frame"><nobr><span class="math" id="MathJax-Span-1" role="math" style="width: 41.166em; display: inline-block;"><span style="display: inline-block; position: relative; width: 35.476em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.64em 1000.002em 4.183em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-2"><span class="mi" id="MathJax-Span-3" style="font-family: MathJax_Math-italic;">I<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mi" id="MathJax-Span-4" style="font-family: MathJax_Math-italic;">G</span><span class="mo" id="MathJax-Span-5" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-6" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-7" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-8" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mo" id="MathJax-Span-9" style="font-family: MathJax_Main; padding-left: 0.261em;">−</span><span class="munderover" id="MathJax-Span-10" style="padding-left: 0.175em;"><span style="display: inline-block; position: relative; width: 1.813em; height: 0px;"><span style="position: absolute; clip: rect(2.933em 1000.002em 4.571em -999.998em); top: -4.006em; left: 0.175em;"><span class="mo" id="MathJax-Span-11" style="font-family: MathJax_Size2; vertical-align: 0.002em;">∑</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.399em -999.998em); top: -2.929em; left: 0.002em;"><span class="texatom" id="MathJax-Span-12"><span class="mrow" id="MathJax-Span-13"><span class="mi" id="MathJax-Span-14" style="font-size: 70.7%; font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-15" style="font-size: 70.7%; font-family: MathJax_Main;">=</span><span class="texatom" id="MathJax-Span-16"><span class="mrow" id="MathJax-Span-17"><span class="mn" id="MathJax-Span-18" style="font-size: 70.7%; font-family: MathJax_Main;">0</span><span class="mo" id="MathJax-Span-19" style="font-size: 70.7%; font-family: MathJax_Main;">,</span><span class="mn" id="MathJax-Span-20" style="font-size: 70.7%; font-family: MathJax_Main;">1</span></span></span></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mi" id="MathJax-Span-21" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-22" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-23" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-24" style="font-family: MathJax_Main;">)</span><span class="mi" id="MathJax-Span-25" style="font-family: MathJax_Main; padding-left: 0.175em;">log</span><span class="mo" id="MathJax-Span-26"></span><span class="mi" id="MathJax-Span-27" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-28" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-29" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-30" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-31" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-32" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">p</span><span class="mo" id="MathJax-Span-33" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-34" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-35" style="font-family: MathJax_Main;">)</span><span class="munderover" id="MathJax-Span-36" style="padding-left: 0.175em;"><span style="display: inline-block; position: relative; width: 1.813em; height: 0px;"><span style="position: absolute; clip: rect(2.933em 1000.002em 4.571em -999.998em); top: -4.006em; left: 0.175em;"><span class="mo" id="MathJax-Span-37" style="font-family: MathJax_Size2; vertical-align: 0.002em;">∑</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.399em -999.998em); top: -2.929em; left: 0.002em;"><span class="texatom" id="MathJax-Span-38"><span class="mrow" id="MathJax-Span-39"><span class="mi" id="MathJax-Span-40" style="font-size: 70.7%; font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-41" style="font-size: 70.7%; font-family: MathJax_Main;">=</span><span class="texatom" id="MathJax-Span-42"><span class="mrow" id="MathJax-Span-43"><span class="mn" id="MathJax-Span-44" style="font-size: 70.7%; font-family: MathJax_Main;">0</span><span class="mo" id="MathJax-Span-45" style="font-size: 70.7%; font-family: MathJax_Main;">,</span><span class="mn" id="MathJax-Span-46" style="font-size: 70.7%; font-family: MathJax_Main;">1</span></span></span></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mi" id="MathJax-Span-47" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-48" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-49" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="texatom" id="MathJax-Span-50"><span class="mrow" id="MathJax-Span-51"><span class="mo" id="MathJax-Span-52" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-53" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-54" style="font-family: MathJax_Main;">)</span><span class="mi" id="MathJax-Span-55" style="font-family: MathJax_Main; padding-left: 0.175em;">log</span><span class="mo" id="MathJax-Span-56"></span><span class="mi" id="MathJax-Span-57" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-58" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-59" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="texatom" id="MathJax-Span-60"><span class="mrow" id="MathJax-Span-61"><span class="mo" id="MathJax-Span-62" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-63" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-64" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-65" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-66" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">p</span><span class="mo" id="MathJax-Span-67" style="font-family: MathJax_Main;">(</span><span class="texatom" id="MathJax-Span-68"><span class="mrow" id="MathJax-Span-69"><span class="munderover" id="MathJax-Span-70"><span style="display: inline-block; position: relative; width: 0.606em; height: 0px;"><span style="position: absolute; clip: rect(3.235em 1000.002em 4.14em -999.998em); top: -4.006em; left: 0.088em;"><span class="mi" id="MathJax-Span-71" style="font-family: MathJax_Math-italic;">t</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.278em 1000.002em 3.58em -999.998em); top: -4.179em; left: 0.088em;"><span class="mo" id="MathJax-Span-72" style="font-family: MathJax_Main;">¯</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span></span></span><span class="mo" id="MathJax-Span-73" style="font-family: MathJax_Main;">)</span><span class="munderover" id="MathJax-Span-74" style="padding-left: 0.175em;"><span style="display: inline-block; position: relative; width: 1.813em; height: 0px;"><span style="position: absolute; clip: rect(2.933em 1000.002em 4.571em -999.998em); top: -4.006em; left: 0.175em;"><span class="mo" id="MathJax-Span-75" style="font-family: MathJax_Size2; vertical-align: 0.002em;">∑</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.399em -999.998em); top: -2.929em; left: 0.002em;"><span class="texatom" id="MathJax-Span-76"><span class="mrow" id="MathJax-Span-77"><span class="mi" id="MathJax-Span-78" style="font-size: 70.7%; font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-79" style="font-size: 70.7%; font-family: MathJax_Main;">=</span><span class="texatom" id="MathJax-Span-80"><span class="mrow" id="MathJax-Span-81"><span class="mn" id="MathJax-Span-82" style="font-size: 70.7%; font-family: MathJax_Main;">0</span><span class="mo" id="MathJax-Span-83" style="font-size: 70.7%; font-family: MathJax_Main;">,</span><span class="mn" id="MathJax-Span-84" style="font-size: 70.7%; font-family: MathJax_Main;">1</span></span></span></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mi" id="MathJax-Span-85" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-86" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-87" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="texatom" id="MathJax-Span-88"><span class="mrow" id="MathJax-Span-89"><span class="mo" id="MathJax-Span-90" style="font-family: MathJax_Main;">|</span></span></span><span class="texatom" id="MathJax-Span-91"><span class="mrow" id="MathJax-Span-92"><span class="munderover" id="MathJax-Span-93"><span style="display: inline-block; position: relative; width: 0.606em; height: 0px;"><span style="position: absolute; clip: rect(3.235em 1000.002em 4.14em -999.998em); top: -4.006em; left: 0.088em;"><span class="mi" id="MathJax-Span-94" style="font-family: MathJax_Math-italic;">t</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.278em 1000.002em 3.58em -999.998em); top: -4.179em; left: 0.088em;"><span class="mo" id="MathJax-Span-95" style="font-family: MathJax_Main;">¯</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span></span></span><span class="mo" id="MathJax-Span-96" style="font-family: MathJax_Main;">)</span><span class="mi" id="MathJax-Span-97" style="font-family: MathJax_Main; padding-left: 0.175em;">log</span><span class="mo" id="MathJax-Span-98"></span><span class="mi" id="MathJax-Span-99" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-100" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-101" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="texatom" id="MathJax-Span-102"><span class="mrow" id="MathJax-Span-103"><span class="mo" id="MathJax-Span-104" style="font-family: MathJax_Main;">|</span></span></span><span class="texatom" id="MathJax-Span-105"><span class="mrow" id="MathJax-Span-106"><span class="munderover" id="MathJax-Span-107"><span style="display: inline-block; position: relative; width: 0.606em; height: 0px;"><span style="position: absolute; clip: rect(3.235em 1000.002em 4.14em -999.998em); top: -4.006em; left: 0.088em;"><span class="mi" id="MathJax-Span-108" style="font-family: MathJax_Math-italic;">t</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.278em 1000.002em 3.58em -999.998em); top: -4.179em; left: 0.088em;"><span class="mo" id="MathJax-Span-109" style="font-family: MathJax_Main;">¯</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span></span></span><span class="mo" id="MathJax-Span-110" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 2.752em; vertical-align: -1.597em;"></span></span></nobr></span></div><script type="math/tex; mode=display" id="MathJax-Element-1"> IG(t) = -\sum_{y={0,1}} p(y)\log p(y) + p(t)\sum_{y={0,1}} p(y|t)\log p(y|t) + p(\bar t)\sum_{y={0,1}} p(y|\bar t)\log p(y|\bar t) </script>
where <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-2-Frame"><nobr><span class="math" id="MathJax-Span-111" role="math" style="width: 4.916em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.226em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-112"><span class="mi" id="MathJax-Span-113" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-114" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-115" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-116" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-117" style="font-family: MathJax_Main; padding-left: 0.261em;">1</span><span class="texatom" id="MathJax-Span-118"><span class="mrow" id="MathJax-Span-119"><span class="mo" id="MathJax-Span-120" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-121" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-122" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-2">p(y=1|t)</script> is the probability that we get a positive document where we observe the term t, and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-3-Frame"><nobr><span class="math" id="MathJax-Span-123" role="math" style="width: 5.218em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.485em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.813em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-124"><span class="mi" id="MathJax-Span-125" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-126" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-127" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-128" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-129" style="font-family: MathJax_Main; padding-left: 0.261em;">1</span><span class="texatom" id="MathJax-Span-130"><span class="mrow" id="MathJax-Span-131"><span class="mo" id="MathJax-Span-132" style="font-family: MathJax_Main;">|</span></span></span><span class="texatom" id="MathJax-Span-133"><span class="mrow" id="MathJax-Span-134"><span class="munderover" id="MathJax-Span-135"><span style="display: inline-block; position: relative; width: 0.606em; height: 0px;"><span style="position: absolute; clip: rect(3.235em 1000.002em 4.14em -999.998em); top: -4.006em; left: 0.088em;"><span class="mi" id="MathJax-Span-136" style="font-family: MathJax_Math-italic;">t</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.278em 1000.002em 3.58em -999.998em); top: -4.179em; left: 0.088em;"><span class="mo" id="MathJax-Span-137" style="font-family: MathJax_Main;">¯</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span></span></span><span class="mo" id="MathJax-Span-138" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.302em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-3">p(y=1|\bar t)</script> is the probability that we get a positive document where we do not observe the term t.</p>

<p><strong>Note</strong>: here we need to define <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-4-Frame"><nobr><span class="math" id="MathJax-Span-139" role="math" style="width: 5.175em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.442em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.899em 1000.002em 3.063em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-140"><span class="mn" id="MathJax-Span-141" style="font-family: MathJax_Main;">0</span><span class="mi" id="MathJax-Span-142" style="font-family: MathJax_Main; padding-left: 0.175em;">log</span><span class="mo" id="MathJax-Span-143"></span><span class="mn" id="MathJax-Span-144" style="font-family: MathJax_Main; padding-left: 0.175em;">0</span><span class="mo" id="MathJax-Span-145" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-146" style="font-family: MathJax_Main; padding-left: 0.261em;">0</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.153em; vertical-align: -0.297em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-4">0\log 0=0</script> to avoid zero probabilities in entropy computation.  </p>

<p><span class="MathJax_Preview" style="color: inherit;"></span><div class="MathJax_Display" style="text-align: center;"><span class="MathJax" id="MathJax-Element-5-Frame"><nobr><span class="math" id="MathJax-Span-147" role="math" style="width: 20.907em; display: inline-block;"><span style="display: inline-block; position: relative; width: 18.019em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.037em 1000.002em 3.795em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-148"><span class="msubsup" id="MathJax-Span-149"><span style="display: inline-block; position: relative; width: 1.037em; height: 0px;"><span style="position: absolute; clip: rect(3.45em 1000.002em 4.356em -999.998em); top: -4.006em; left: 0.002em;"><span class="mi" id="MathJax-Span-150" style="font-family: MathJax_Math-italic;">χ</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; top: -4.438em; left: 0.649em;"><span class="mn" id="MathJax-Span-151" style="font-size: 70.7%; font-family: MathJax_Main;">2</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mo" id="MathJax-Span-152" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-153" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-154" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-155" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mfrac" id="MathJax-Span-156" style="padding-left: 0.261em;"><span style="display: inline-block; position: relative; width: 14.269em; height: 0px; margin-right: 0.131em; margin-left: 0.131em;"><span style="position: absolute; clip: rect(3.063em 1000.002em 4.399em -999.998em); top: -4.696em; left: 50%; margin-left: -6.506em;"><span class="mrow" id="MathJax-Span-157"><span class="mo" id="MathJax-Span-158" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-159" style="font-family: MathJax_Math-italic;">A</span><span class="mo" id="MathJax-Span-160" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-161" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">B</span><span class="mo" id="MathJax-Span-162" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-163" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-164" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-165" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">D</span><span class="mo" id="MathJax-Span-166" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-167" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-168" style="font-family: MathJax_Math-italic;">A</span><span class="mi" id="MathJax-Span-169" style="font-family: MathJax_Math-italic;">D</span><span class="mo" id="MathJax-Span-170" style="font-family: MathJax_Main; padding-left: 0.218em;">−</span><span class="mi" id="MathJax-Span-171" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">B</span><span class="mi" id="MathJax-Span-172" style="font-family: MathJax_Math-italic;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="msubsup" id="MathJax-Span-173"><span style="display: inline-block; position: relative; width: 0.821em; height: 0px;"><span style="position: absolute; clip: rect(3.149em 1000.002em 4.399em -999.998em); top: -4.006em; left: 0.002em;"><span class="mo" id="MathJax-Span-174" style="font-family: MathJax_Main;">)</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; top: -4.351em; left: 0.39em;"><span class="mn" id="MathJax-Span-175" style="font-size: 70.7%; font-family: MathJax_Main;">2</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.149em 1000.002em 4.399em -999.998em); top: -3.317em; left: 50%; margin-left: -7.067em;"><span class="mrow" id="MathJax-Span-176"><span class="mo" id="MathJax-Span-177" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-178" style="font-family: MathJax_Math-italic;">A</span><span class="mo" id="MathJax-Span-179" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-180" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-181" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-182" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-183" style="font-family: MathJax_Math-italic;">B</span><span class="mo" id="MathJax-Span-184" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-185" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">D</span><span class="mo" id="MathJax-Span-186" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-187" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-188" style="font-family: MathJax_Math-italic;">A</span><span class="mo" id="MathJax-Span-189" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-190" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">B</span><span class="mo" id="MathJax-Span-191" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-192" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-193" style="font-family: MathJax_Math-italic;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-194" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="mi" id="MathJax-Span-195" style="font-family: MathJax_Math-italic; padding-left: 0.218em;">D</span><span class="mo" id="MathJax-Span-196" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(0.907em 1000.002em 1.209em -999.998em); top: -1.291em; left: 0.002em;"><span style="border-left-width: 14.269em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.045em; vertical-align: 0.002em;"></span><span style="display: inline-block; width: 0px; height: 1.08em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 3.002em; vertical-align: -1.147em;"></span></span></nobr></span></div><script type="math/tex; mode=display" id="MathJax-Element-5">\chi^2(t) = \frac{(A+B+C+D)(AD-BC)^2}{(A+C)(B+D)(A+B)(C+D)} </script> 
where A is the number of positive documents containing term t, B is the number of positive documents not containing term t, C is the number of negative documents containing term t, and D is the number of negative documents not containing term t.</p>

<p>Before we apply these two feature selection methods, we need to filter the features by DF first. We will use the same threshold <strong>50</strong> as in MP1, i.e., removing the terms with DF smaller than 50. </p>

<p>As required in Chi Square, we will use the threshold <strong>3.841</strong> to filter out insignificant terms, i.e., removing the terms whose <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-6-Frame"><nobr><span class="math" id="MathJax-Span-197" role="math" style="width: 6.726em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.778em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.769em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-198"><span class="msubsup" id="MathJax-Span-199"><span style="display: inline-block; position: relative; width: 1.037em; height: 0px;"><span style="position: absolute; clip: rect(3.45em 1000.002em 4.356em -999.998em); top: -4.006em; left: 0.002em;"><span class="mi" id="MathJax-Span-200" style="font-family: MathJax_Math-italic;">χ</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; top: -4.351em; left: 0.649em;"><span class="mn" id="MathJax-Span-201" style="font-size: 70.7%; font-family: MathJax_Main;">2</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mo" id="MathJax-Span-202" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-203" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-204" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-205" style="font-family: MathJax_Main; padding-left: 0.261em;">&lt;</span><span class="mn" id="MathJax-Span-206" style="font-family: MathJax_Main; padding-left: 0.261em;">3.841</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.353em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-6">\chi^2(t)<3.841</script>.</p>

<p>After these filtering steps, rank the resulting features by their <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-7-Frame"><nobr><span class="math" id="MathJax-Span-207" role="math" style="width: 2.804em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.416em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-208"><span class="mi" id="MathJax-Span-209" style="font-family: MathJax_Math-italic;">I<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mi" id="MathJax-Span-210" style="font-family: MathJax_Math-italic;">G</span><span class="mo" id="MathJax-Span-211" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-212" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-213" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-7">IG(t)</script> and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-8-Frame"><nobr><span class="math" id="MathJax-Span-214" role="math" style="width: 2.545em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.2em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.769em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-215"><span class="msubsup" id="MathJax-Span-216"><span style="display: inline-block; position: relative; width: 1.037em; height: 0px;"><span style="position: absolute; clip: rect(3.45em 1000.002em 4.356em -999.998em); top: -4.006em; left: 0.002em;"><span class="mi" id="MathJax-Span-217" style="font-family: MathJax_Math-italic;">χ</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; top: -4.351em; left: 0.649em;"><span class="mn" id="MathJax-Span-218" style="font-size: 70.7%; font-family: MathJax_Main;">2</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mo" id="MathJax-Span-219" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-220" style="font-family: MathJax_Math-italic;">t</span><span class="mo" id="MathJax-Span-221" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.353em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-8">\chi^2(t)</script> value in descending order accordingly. We will choose the top 5000 words from each of these two ordered lists as our candidate features. If we don't have 5000 features left in Chi Square selection, return whatever you got after filtering.</p>

<p>Before moving onto the next task, merge the feature lists you have got from Information Gain and Chi Square, i.e., take the union of these two sets of selected features, and use the resulting list as the finalized features (i.e., controlled vocabulary) for the following tasks. Then use this controlled vocabulary to construct vector representation for all the review documents in the train folder, and <strong>ignore</strong> the documents with less or equal to five non-zero features (i.e., length of the resulting sparse vector is less or equal to 5). We will refer to the resulting document collection as <strong>corpus</strong> in our following descriptions.</p>

<p><strong>What to submit</strong>:</p>

<ol>
<li>List the top 20 words selected by Information Gain and Chi Square accordingly. What is the size of your finalized controlled vocabulary after merging? How many review documents are there in the resulting corpus after feature selection? (10 pts).</li>
<li>Paste your code for Information Gain and Chi Square computation (2<span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-9-Frame"><nobr><span class="math" id="MathJax-Span-222" role="math" style="width: 0.95em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.821em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(2.114em 1000.002em 2.847em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-223"><span class="mo" id="MathJax-Span-224" style="font-family: MathJax_Main;">×</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.653em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-9">\times</script>10 pts).</li>
</ol>

<h1><a name="nb"></a>Task 2: Naive Bayes (20pts)</h1>

<h3>2.1 Training Naive Bayes with Maximum a Posterior estimator (10pts)</h3>

<p>As we discussed in the course lecture, a Naive Bayes classifier for text categorization problem can be considered as consisting of independent N-gram language models for each class. In this assignment, we will use unigram language models with additive smoothing (set <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-10-Frame"><nobr><span class="math" id="MathJax-Span-225" role="math" style="width: 3.58em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.063em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 2.89em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-226"><span class="mi" id="MathJax-Span-227" style="font-family: MathJax_Math-italic;">δ<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-228" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-229" style="font-family: MathJax_Main; padding-left: 0.261em;">0.1</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.953em; vertical-align: -0.098em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-10">\delta=0.1</script>) to estimate parameters in a Naive Bayes text classifier.</p>

<p>You are suggested to reuse your implementation in MP1 for unigram language models in this task. </p>

<p><em>HINT: you only need to estimate two unigram language models for positive and negative classes accordingly, and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-11-Frame"><nobr><span class="math" id="MathJax-Span-230" role="math" style="width: 2.096em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.797em; height: 0px; font-size: 117%;"><span style="position: absolute; clip: rect(1.797em 1000.002em 3.079em -999.998em); top: -2.69em; left: 0.002em;"><span class="mrow" id="MathJax-Span-231"><span class="mi" id="MathJax-Span-232" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-233" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-234" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-235" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.694em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-11">p(y)</script> is simply the ratio of the two classes in the corpus.</em> </p>

<p><strong>What to submit</strong>:</p>

<ol>
<li>Use the whole corpus to estimate a Naive Bayes classifier. Compute the log ratio between <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-12-Frame"><nobr><span class="math" id="MathJax-Span-236" role="math" style="width: 5.304em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.571em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-237"><span class="mi" id="MathJax-Span-238" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-239" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-240" style="font-family: MathJax_Math-italic;">w</span><span class="texatom" id="MathJax-Span-241"><span class="mrow" id="MathJax-Span-242"><span class="mo" id="MathJax-Span-243" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-244" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-245" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-246" style="font-family: MathJax_Main; padding-left: 0.261em;">1</span><span class="mo" id="MathJax-Span-247" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-12">p(w|y=1)</script> and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-13-Frame"><nobr><span class="math" id="MathJax-Span-248" role="math" style="width: 5.304em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.571em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-249"><span class="mi" id="MathJax-Span-250" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-251" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-252" style="font-family: MathJax_Math-italic;">w</span><span class="texatom" id="MathJax-Span-253"><span class="mrow" id="MathJax-Span-254"><span class="mo" id="MathJax-Span-255" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-256" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-257" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-258" style="font-family: MathJax_Main; padding-left: 0.261em;">0</span><span class="mo" id="MathJax-Span-259" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-13">p(w|y=0)</script>, i.e., <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-14-Frame"><nobr><span class="math" id="MathJax-Span-260" role="math" style="width: 5.476em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.7em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.511em 1000.002em 3.45em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-261"><span class="mi" id="MathJax-Span-262" style="font-family: MathJax_Main;">log</span><span class="mo" id="MathJax-Span-263"></span><span class="mfrac" id="MathJax-Span-264" style="padding-left: 0.175em;"><span style="display: inline-block; position: relative; width: 2.976em; height: 0px; margin-right: 0.131em; margin-left: 0.131em;"><span style="position: absolute; clip: rect(3.364em 1000.002em 4.313em -999.998em); top: -4.567em; left: 50%; margin-left: -1.42em;"><span class="mrow" id="MathJax-Span-265"><span class="mi" id="MathJax-Span-266" style="font-size: 70.7%; font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-267" style="font-size: 70.7%; font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-268" style="font-size: 70.7%; font-family: MathJax_Math-italic;">w</span><span class="texatom" id="MathJax-Span-269"><span class="mrow" id="MathJax-Span-270"><span class="mo" id="MathJax-Span-271" style="font-size: 70.7%; font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-272" style="font-size: 70.7%; font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-273" style="font-size: 70.7%; font-family: MathJax_Main;">=</span><span class="mn" id="MathJax-Span-274" style="font-size: 70.7%; font-family: MathJax_Main;">1</span><span class="mo" id="MathJax-Span-275" style="font-size: 70.7%; font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.364em 1000.002em 4.313em -999.998em); top: -3.575em; left: 50%; margin-left: -1.42em;"><span class="mrow" id="MathJax-Span-276"><span class="mi" id="MathJax-Span-277" style="font-size: 70.7%; font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-278" style="font-size: 70.7%; font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-279" style="font-size: 70.7%; font-family: MathJax_Math-italic;">w</span><span class="texatom" id="MathJax-Span-280"><span class="mrow" id="MathJax-Span-281"><span class="mo" id="MathJax-Span-282" style="font-size: 70.7%; font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-283" style="font-size: 70.7%; font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-284" style="font-size: 70.7%; font-family: MathJax_Main;">=</span><span class="mn" id="MathJax-Span-285" style="font-size: 70.7%; font-family: MathJax_Main;">0</span><span class="mo" id="MathJax-Span-286" style="font-size: 70.7%; font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(0.907em 1000.002em 1.209em -999.998em); top: -1.291em; left: 0.002em;"><span style="border-left-width: 2.976em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.045em; vertical-align: 0.002em;"></span><span style="display: inline-block; width: 0px; height: 1.08em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 2.052em; vertical-align: -0.747em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-14">\log\frac{p(w|y=1)}{p(w|y=0)}</script>, and rank the features in a descending order with respect to this  log ratio. List the top 20 and bottom 20 words from this ranked list. Do they make sense to you in terms of distinguishing the positive opinion from negative opinion? (10 pts).</li>
</ol>

<h3>2.2 Naive Bayes as a linear classifier (10pts)</h3>

<p>As discussed in our lecture, a Naive Bayes classifier for binary classification boils turns out to be a linear classification model:</p>

<p><span class="MathJax_Preview" style="color: inherit;"></span><div class="MathJax_Display" style="text-align: center;"><span class="MathJax" id="MathJax-Element-15-Frame"><nobr><span class="math" id="MathJax-Span-287" role="math" style="width: 38.45em; display: inline-block;"><span style="display: inline-block; position: relative; width: 33.149em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.123em 1000.002em 4.011em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-288"><span class="mi" id="MathJax-Span-289" style="font-family: MathJax_Math-italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-290" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-291" style="font-family: MathJax_Math-italic;">X<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-292" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-293" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mi" id="MathJax-Span-294" style="font-family: MathJax_Main; padding-left: 0.261em;">log</span><span class="mo" id="MathJax-Span-295"></span><span class="mfrac" id="MathJax-Span-296" style="padding-left: 0.175em;"><span style="display: inline-block; position: relative; width: 4.83em; height: 0px; margin-right: 0.131em; margin-left: 0.131em;"><span style="position: absolute; clip: rect(3.149em 1000.002em 4.399em -999.998em); top: -4.696em; left: 50%; margin-left: -2.369em;"><span class="mrow" id="MathJax-Span-297"><span class="mi" id="MathJax-Span-298" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-299" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-300" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-301" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-302" style="font-family: MathJax_Main; padding-left: 0.261em;">1</span><span class="texatom" id="MathJax-Span-303"><span class="mrow" id="MathJax-Span-304"><span class="mo" id="MathJax-Span-305" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-306" style="font-family: MathJax_Math-italic;">X<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-307" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.149em 1000.002em 4.399em -999.998em); top: -3.317em; left: 50%; margin-left: -2.369em;"><span class="mrow" id="MathJax-Span-308"><span class="mi" id="MathJax-Span-309" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-310" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-311" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-312" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-313" style="font-family: MathJax_Main; padding-left: 0.261em;">0</span><span class="texatom" id="MathJax-Span-314"><span class="mrow" id="MathJax-Span-315"><span class="mo" id="MathJax-Span-316" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-317" style="font-family: MathJax_Math-italic;">X<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-318" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(0.907em 1000.002em 1.209em -999.998em); top: -1.291em; left: 0.002em;"><span style="border-left-width: 4.83em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.045em; vertical-align: 0.002em;"></span><span style="display: inline-block; width: 0px; height: 1.08em;"></span></span></span></span><span class="mo" id="MathJax-Span-319" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mi" id="MathJax-Span-320" style="font-family: MathJax_Main; padding-left: 0.261em;">log</span><span class="mo" id="MathJax-Span-321"></span><span class="mfrac" id="MathJax-Span-322" style="padding-left: 0.175em;"><span style="display: inline-block; position: relative; width: 3.709em; height: 0px; margin-right: 0.131em; margin-left: 0.131em;"><span style="position: absolute; clip: rect(3.149em 1000.002em 4.399em -999.998em); top: -4.696em; left: 50%; margin-left: -1.765em;"><span class="mrow" id="MathJax-Span-323"><span class="mi" id="MathJax-Span-324" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-325" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-326" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-327" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-328" style="font-family: MathJax_Main; padding-left: 0.261em;">1</span><span class="mo" id="MathJax-Span-329" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.149em 1000.002em 4.399em -999.998em); top: -3.317em; left: 50%; margin-left: -1.765em;"><span class="mrow" id="MathJax-Span-330"><span class="mi" id="MathJax-Span-331" style="font-family: MathJax_Math-italic;">p</span><span class="mo" id="MathJax-Span-332" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-333" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-334" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-335" style="font-family: MathJax_Main; padding-left: 0.261em;">0</span><span class="mo" id="MathJax-Span-336" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(0.907em 1000.002em 1.209em -999.998em); top: -1.291em; left: 0.002em;"><span style="border-left-width: 3.709em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.045em; vertical-align: 0.002em;"></span><span style="display: inline-block; width: 0px; height: 1.08em;"></span></span></span></span><span class="mo" id="MathJax-Span-337" style="font-family: MathJax_Main; padding-left: 0.218em;">+</span><span class="munderover" id="MathJax-Span-338" style="padding-left: 0.218em;"><span style="display: inline-block; position: relative; width: 1.468em; height: 0px;"><span style="position: absolute; clip: rect(2.933em 1000.002em 4.571em -999.998em); top: -4.006em; left: 0.002em;"><span class="mo" id="MathJax-Span-339" style="font-family: MathJax_Size2; vertical-align: 0.002em;">∑</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.58em 1000.002em 4.269em -999.998em); top: -2.972em; left: 0.519em;"><span class="mi" id="MathJax-Span-340" style="font-size: 70.7%; font-family: MathJax_Math-italic;">x</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mo" id="MathJax-Span-341" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-342" style="font-family: MathJax_Main;">log</span><span class="mo" id="MathJax-Span-343"></span><span class="mi" id="MathJax-Span-344" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-345" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-346" style="font-family: MathJax_Math-italic;">x</span><span class="texatom" id="MathJax-Span-347"><span class="mrow" id="MathJax-Span-348"><span class="mo" id="MathJax-Span-349" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-350" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-351" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-352" style="font-family: MathJax_Main; padding-left: 0.261em;">1</span><span class="mo" id="MathJax-Span-353" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-354" style="font-family: MathJax_Main; padding-left: 0.218em;">−</span><span class="mi" id="MathJax-Span-355" style="font-family: MathJax_Main; padding-left: 0.218em;">log</span><span class="mo" id="MathJax-Span-356"></span><span class="mi" id="MathJax-Span-357" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">p</span><span class="mo" id="MathJax-Span-358" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-359" style="font-family: MathJax_Math-italic;">x</span><span class="texatom" id="MathJax-Span-360"><span class="mrow" id="MathJax-Span-361"><span class="mo" id="MathJax-Span-362" style="font-family: MathJax_Main;">|</span></span></span><span class="mi" id="MathJax-Span-363" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-364" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-365" style="font-family: MathJax_Main; padding-left: 0.261em;">0</span><span class="mo" id="MathJax-Span-366" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-367" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 3.103em; vertical-align: -1.397em;"></span></span></nobr></span></div><script type="math/tex; mode=display" id="MathJax-Element-15">f(X)=\log\frac{p(y=1|X)}{p(y=0|X)}=\log\frac{p(y=1)}{p(y=0)} + \sum_x(\log p(x|y=1) - \log p(x|y=0))</script>, and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-16-Frame"><nobr><span class="math" id="MathJax-Span-368" role="math" style="width: 7.459em; display: inline-block;"><span style="display: inline-block; position: relative; width: 6.425em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-369"><span class="texatom" id="MathJax-Span-370"><span class="mrow" id="MathJax-Span-371"><span class="munderover" id="MathJax-Span-372"><span style="display: inline-block; position: relative; width: 0.606em; height: 0px;"><span style="position: absolute; clip: rect(3.45em 1000.002em 4.356em -999.998em); top: -4.006em; left: 0.002em;"><span class="mi" id="MathJax-Span-373" style="font-family: MathJax_Math-italic;">y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.278em 1000.002em 3.58em -999.998em); top: -4.006em; left: 0.088em;"><span class="mo" id="MathJax-Span-374" style="font-family: MathJax_Main;">¯</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span></span></span><span class="mo" id="MathJax-Span-375" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mi" id="MathJax-Span-376" style="font-family: MathJax_Math-italic; padding-left: 0.261em;">s</span><span class="mi" id="MathJax-Span-377" style="font-family: MathJax_Math-italic;">g<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mi" id="MathJax-Span-378" style="font-family: MathJax_Math-italic;">n</span><span class="mo" id="MathJax-Span-379" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-380" style="font-family: MathJax_Math-italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-381" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-382" style="font-family: MathJax_Math-italic;">X<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-383" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-384" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-16">\bar y=sgn(f(X))</script>
where <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-17-Frame"><nobr><span class="math" id="MathJax-Span-385" role="math" style="width: 5.476em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.7em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-386"><span class="mi" id="MathJax-Span-387" style="font-family: MathJax_Math-italic;">s</span><span class="mi" id="MathJax-Span-388" style="font-family: MathJax_Math-italic;">g<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mi" id="MathJax-Span-389" style="font-family: MathJax_Math-italic;">n</span><span class="mo" id="MathJax-Span-390" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-391" style="font-family: MathJax_Math-italic;">x</span><span class="mo" id="MathJax-Span-392" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-393" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-394" style="font-family: MathJax_Main; padding-left: 0.261em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-17">sgn(x)=1</script> if <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-18-Frame"><nobr><span class="math" id="MathJax-Span-395" role="math" style="width: 2.761em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.373em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.942em 1000.002em 2.976em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-396"><span class="mi" id="MathJax-Span-397" style="font-family: MathJax_Math-italic;">x</span><span class="mo" id="MathJax-Span-398" style="font-family: MathJax_Main; padding-left: 0.261em;">≥</span><span class="mn" id="MathJax-Span-399" style="font-family: MathJax_Main; padding-left: 0.261em;">0</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.052em; vertical-align: -0.198em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-18">x\ge0</script>, otherwise 0. </p>

<p>Implement this prediction function with your Naive Bayes classifier. It should take a review document as input and output its predicted class label. </p>

<p><strong>What to submit</strong>:<br>
1. Compute <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-19-Frame"><nobr><span class="math" id="MathJax-Span-400" role="math" style="width: 2.545em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.2em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-401"><span class="mi" id="MathJax-Span-402" style="font-family: MathJax_Math-italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-403" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-404" style="font-family: MathJax_Math-italic;">X<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-405" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-19">f(X)</script> over all documents in the corpus and rank them in a descending order with respect to <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-20-Frame"><nobr><span class="math" id="MathJax-Span-406" role="math" style="width: 2.545em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.2em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.856em 1000.002em 3.106em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-407"><span class="mi" id="MathJax-Span-408" style="font-family: MathJax_Math-italic;">f<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-409" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-410" style="font-family: MathJax_Math-italic;">X<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-411" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.252em; vertical-align: -0.348em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-20">f(X)</script>. Plot the Precision-Recall curve with respect to this ranked list. Please refer to the lecture slides for the instructions of plotting this curve.</p>

<h1><a name="knn"></a>Task 3: k Nearest Neighbor (25pts)</h1>

<p>In our lecture discussion, we have introduced a highly efficient approximation method for retrieving the nearest neighbors to the given input instance, i.e., <a href="http://en.wikipedia.org/wiki/Random_projection">random projection</a>. We will implement this method to speed up our kNN computation.</p>

<p>In our kNN classifier, we will use TF-IDF as feature values in the vector representation and cosine similarity between vectors as distance metric. We will follow the same definition of TF-IDF as we used in MP1, i.e., sub-linear TF scaling. </p>

<p><em>Note in Naive Bayes classifier, we only need raw TF as our feature value.</em> </p>

<p>Denote the size of our final controlled vocabulary as <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-21-Frame"><nobr><span class="math" id="MathJax-Span-412" role="math" style="width: 1.08em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.907em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.985em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-413"><span class="mi" id="MathJax-Span-414" style="font-family: MathJax_Math-italic;">m</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.653em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-21">m</script>, we will create a <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-22-Frame"><nobr><span class="math" id="MathJax-Span-415" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-416"><span class="mi" id="MathJax-Span-417" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-22">l</script>-bits hash code for every review document in the corpus via random projection. The details of how to perform random projection has been discussed in our lecture slides. Briefly, we will create <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-23-Frame"><nobr><span class="math" id="MathJax-Span-418" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-419"><span class="mi" id="MathJax-Span-420" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-23">l</script> different <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-24-Frame"><nobr><span class="math" id="MathJax-Span-421" role="math" style="width: 1.08em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.907em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.985em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-422"><span class="mi" id="MathJax-Span-423" style="font-family: MathJax_Math-italic;">m</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.653em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-24">m</script>-dimensional random vectors, and each dimension of these random vectors falls into the range of [-1,1]. For an input review document, we will compute the inner product of its vector representation with those <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-25-Frame"><nobr><span class="math" id="MathJax-Span-424" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-425"><span class="mi" id="MathJax-Span-426" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-25">l</script> random vectors accordingly; and use the sign function to encode each bit as 0 or 1, i.e., <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-26-Frame"><nobr><span class="math" id="MathJax-Span-427" role="math" style="width: 21.554em; display: inline-block;"><span style="display: inline-block; position: relative; width: 18.58em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.769em 1000.002em 3.192em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-428"><span class="mi" id="MathJax-Span-429" style="font-family: MathJax_Math-italic;">H<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.045em;"></span></span><span class="mo" id="MathJax-Span-430" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-431" style="font-family: MathJax_Math-italic;">x</span><span class="mo" id="MathJax-Span-432" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-433" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mo" id="MathJax-Span-434" style="font-family: MathJax_Main; padding-left: 0.261em;">[</span><span class="mi" id="MathJax-Span-435" style="font-family: MathJax_Math-italic;">s</span><span class="mi" id="MathJax-Span-436" style="font-family: MathJax_Math-italic;">g<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mi" id="MathJax-Span-437" style="font-family: MathJax_Math-italic;">n</span><span class="mo" id="MathJax-Span-438" style="font-family: MathJax_Main;">(</span><span class="msubsup" id="MathJax-Span-439"><span style="display: inline-block; position: relative; width: 1.037em; height: 0px;"><span style="position: absolute; clip: rect(3.45em 1000.002em 4.14em -999.998em); top: -4.006em; left: 0.002em;"><span class="mi" id="MathJax-Span-440" style="font-family: MathJax_Math-italic;">r</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.14em -999.998em); top: -4.351em; left: 0.433em;"><span class="mi" id="MathJax-Span-441" style="font-size: 70.7%; font-family: MathJax_Math-italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.088em;"></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.14em -999.998em); top: -3.705em; left: 0.433em;"><span class="mn" id="MathJax-Span-442" style="font-size: 70.7%; font-family: MathJax_Main;">1</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mi" id="MathJax-Span-443" style="font-family: MathJax_Math-italic;">x</span><span class="mo" id="MathJax-Span-444" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-445" style="font-family: MathJax_Main;">,</span><span class="mi" id="MathJax-Span-446" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">s</span><span class="mi" id="MathJax-Span-447" style="font-family: MathJax_Math-italic;">g<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mi" id="MathJax-Span-448" style="font-family: MathJax_Math-italic;">n</span><span class="mo" id="MathJax-Span-449" style="font-family: MathJax_Main;">(</span><span class="msubsup" id="MathJax-Span-450"><span style="display: inline-block; position: relative; width: 1.037em; height: 0px;"><span style="position: absolute; clip: rect(3.45em 1000.002em 4.14em -999.998em); top: -4.006em; left: 0.002em;"><span class="mi" id="MathJax-Span-451" style="font-family: MathJax_Math-italic;">r</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.14em -999.998em); top: -4.351em; left: 0.433em;"><span class="mi" id="MathJax-Span-452" style="font-size: 70.7%; font-family: MathJax_Math-italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.088em;"></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.14em -999.998em); top: -3.705em; left: 0.433em;"><span class="mn" id="MathJax-Span-453" style="font-size: 70.7%; font-family: MathJax_Main;">2</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mi" id="MathJax-Span-454" style="font-family: MathJax_Math-italic;">x</span><span class="mo" id="MathJax-Span-455" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-456" style="font-family: MathJax_Main;">,</span><span class="mo" id="MathJax-Span-457" style="font-family: MathJax_Main; padding-left: 0.175em;">…</span><span class="mo" id="MathJax-Span-458" style="font-family: MathJax_Main; padding-left: 0.175em;">,</span><span class="mi" id="MathJax-Span-459" style="font-family: MathJax_Math-italic; padding-left: 0.175em;">s</span><span class="mi" id="MathJax-Span-460" style="font-family: MathJax_Math-italic;">g<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.002em;"></span></span><span class="mi" id="MathJax-Span-461" style="font-family: MathJax_Math-italic;">n</span><span class="mo" id="MathJax-Span-462" style="font-family: MathJax_Main;">(</span><span class="msubsup" id="MathJax-Span-463"><span style="display: inline-block; position: relative; width: 1.037em; height: 0px;"><span style="position: absolute; clip: rect(3.45em 1000.002em 4.14em -999.998em); top: -4.006em; left: 0.002em;"><span class="mi" id="MathJax-Span-464" style="font-family: MathJax_Math-italic;">r</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.14em -999.998em); top: -4.351em; left: 0.433em;"><span class="mi" id="MathJax-Span-465" style="font-size: 70.7%; font-family: MathJax_Math-italic;">T<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.088em;"></span></span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span><span style="position: absolute; clip: rect(3.407em 1000.002em 4.14em -999.998em); top: -3.662em; left: 0.433em;"><span class="mi" id="MathJax-Span-466" style="font-size: 70.7%; font-family: MathJax_Math-italic;">l</span><span style="display: inline-block; width: 0px; height: 4.011em;"></span></span></span></span><span class="mi" id="MathJax-Span-467" style="font-family: MathJax_Math-italic;">x</span><span class="mo" id="MathJax-Span-468" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-469" style="font-family: MathJax_Main;">]</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 1.453em; vertical-align: -0.447em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-26">H(x)=[sgn(r_1^Tx),sgn(r_2^Tx),\dots,sgn(r_l^Tx)]</script>.</p>

<p>Please keep in mind that those <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-27-Frame"><nobr><span class="math" id="MathJax-Span-470" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-471"><span class="mi" id="MathJax-Span-472" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-27">l</script> random vectors should be fixed and shared among all the review documents. In other words, you should first create those <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-28-Frame"><nobr><span class="math" id="MathJax-Span-473" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-474"><span class="mi" id="MathJax-Span-475" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-28">l</script> random vectors, store them, and keep using them for all the incoming documents when computing their hashing values. In addition, random projection only helps you narrow down the search space. Unless there are less than k documents in the resulting hash bucket, you still need to compute cosine similarity between the input document and all the documents in the resulting hash bucket to retrieve the k nearest neighbors for the input document.   </p>

<p><strong>What to submit</strong>:<br>
1. Copy and paste your implementation of random projection. (15pts)<br>
2. Use your implemented random projection (set <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-29-Frame"><nobr><span class="math" id="MathJax-Span-476" role="math" style="width: 3.063em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.631em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.899em 1000.002em 2.89em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-477"><span class="mi" id="MathJax-Span-478" style="font-family: MathJax_Math-italic;">l</span><span class="mo" id="MathJax-Span-479" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-480" style="font-family: MathJax_Main; padding-left: 0.261em;">10</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.953em; vertical-align: -0.098em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-29">l=10</script>) to retrieve the k nearest documents (set <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-30-Frame"><nobr><span class="math" id="MathJax-Span-481" role="math" style="width: 2.718em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.33em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.899em 1000.002em 2.89em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-482"><span class="mi" id="MathJax-Span-483" style="font-family: MathJax_Math-italic;">k</span><span class="mo" id="MathJax-Span-484" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-485" style="font-family: MathJax_Main; padding-left: 0.261em;">5</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.953em; vertical-align: -0.098em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-30">k=5</script>) for those five sample review documents listed in the query json file in MP1. Report the running time for brute-force k nearest neighbor search and approximate k nearest neighbor search by random projection. Can we still find reasonable results with this approximation, i.e., the retrieved documents help us determine the cuisine mentioned in the query document? (10pts)</p>

<h1><a name="eval"></a>Task 4: Classification performance evaluation (25pts)</h1>

<p>In all our previous task descriptions, we used the same corpus for training and testing purposes. Now, we will perform classification evaluation in a more rigorous way, i.e., using cross validation.</p>

<p>We will randomly split the corpus into 10 folds; in each round, we will reserve one fold for testing and the rest for training. Detailed procedures of cross-validation can be found in our lecture slides.</p>

<p>In each round, train and test Naive Bayes and kNN on the same train/test separation. In kNN, set <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-31-Frame"><nobr><span class="math" id="MathJax-Span-486" role="math" style="width: 3.063em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.631em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.899em 1000.002em 2.89em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-487"><span class="mi" id="MathJax-Span-488" style="font-family: MathJax_Math-italic;">l</span><span class="mo" id="MathJax-Span-489" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-490" style="font-family: MathJax_Main; padding-left: 0.261em;">10</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.953em; vertical-align: -0.098em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-31">l=10</script> and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-32-Frame"><nobr><span class="math" id="MathJax-Span-491" role="math" style="width: 2.718em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.33em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.899em 1000.002em 2.89em -999.998em); top: -2.713em; left: 0.002em;"><span class="mrow" id="MathJax-Span-492"><span class="mi" id="MathJax-Span-493" style="font-family: MathJax_Math-italic;">k</span><span class="mo" id="MathJax-Span-494" style="font-family: MathJax_Main; padding-left: 0.261em;">=</span><span class="mn" id="MathJax-Span-495" style="font-family: MathJax_Main; padding-left: 0.261em;">5</span></span><span style="display: inline-block; width: 0px; height: 2.718em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.953em; vertical-align: -0.098em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-32">k=5</script>. </p>

<p><strong>What to submit</strong>:<br>
1. Report the average precision, recall and F1 measure of Naive Bayes and kNN over these 10-fold cross validation. (15pts)<br>
2. Perform paired two sample t-test to verify if one classifier is significantly better than another (set the confidence level to be 95%)? If so, which one is better? (10pts)</p>

<h1><a name="bonus"></a> Bonus Task: Explore the best configuration of <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-33-Frame"><nobr><span class="math" id="MathJax-Span-496" role="math" style="width: 0.367em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.303em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.747em 1000.001em 2.587em -999.999em); top: -2.499em; left: 0.001em;"><span class="mrow" id="MathJax-Span-497"><span class="mi" id="MathJax-Span-498" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.501em;"></span></span></span><span style="border-left-width: 0.001em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.876em; vertical-align: -0.049em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-33">l</script> and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-34-Frame"><nobr><span class="math" id="MathJax-Span-499" role="math" style="width: 0.626em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.54em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.747em 1000.001em 2.587em -999.999em); top: -2.499em; left: 0.001em;"><span class="mrow" id="MathJax-Span-500"><span class="mi" id="MathJax-Span-501" style="font-family: MathJax_Math-italic;">k</span></span><span style="display: inline-block; width: 0px; height: 2.501em;"></span></span></span><span style="border-left-width: 0.001em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.876em; vertical-align: -0.049em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-34">k</script> (15pts)</h1>

<p>In our random projection based kNN implementation, we have two hyper-parameters, i.e., length of projection hash code <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-35-Frame"><nobr><span class="math" id="MathJax-Span-502" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-503"><span class="mi" id="MathJax-Span-504" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-35">l</script> and number of nearest neighbors <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-36-Frame"><nobr><span class="math" id="MathJax-Span-505" role="math" style="width: 0.649em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.563em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-506"><span class="mi" id="MathJax-Span-507" style="font-family: MathJax_Math-italic;">k</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-36">k</script>. We set them arbitrarily. Please use cross-validation as a model selection method to choose the best configuration of <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-37-Frame"><nobr><span class="math" id="MathJax-Span-508" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-509"><span class="mi" id="MathJax-Span-510" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-37">l</script> and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-38-Frame"><nobr><span class="math" id="MathJax-Span-511" role="math" style="width: 0.649em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.563em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-512"><span class="mi" id="MathJax-Span-513" style="font-family: MathJax_Math-italic;">k</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-38">k</script>.</p>

<p><strong>What to submit</strong>:<br>
1. Your experiment design that helps you find the best configuration of <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-39-Frame"><nobr><span class="math" id="MathJax-Span-514" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-515"><span class="mi" id="MathJax-Span-516" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-39">l</script> and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-40-Frame"><nobr><span class="math" id="MathJax-Span-517" role="math" style="width: 0.649em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.563em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-518"><span class="mi" id="MathJax-Span-519" style="font-family: MathJax_Math-italic;">k</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-40">k</script>. And the optimal <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-41-Frame"><nobr><span class="math" id="MathJax-Span-520" role="math" style="width: 0.347em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.304em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-521"><span class="mi" id="MathJax-Span-522" style="font-family: MathJax_Math-italic;">l</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-41">l</script> and <span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax" id="MathJax-Element-42-Frame"><nobr><span class="math" id="MathJax-Span-523" role="math" style="width: 0.649em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.563em; height: 0px; font-size: 116%;"><span style="position: absolute; clip: rect(1.726em 1000.002em 2.675em -999.998em); top: -2.541em; left: 0.002em;"><span class="mrow" id="MathJax-Span-524"><span class="mi" id="MathJax-Span-525" style="font-family: MathJax_Math-italic;">k</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.903em; vertical-align: -0.048em;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-42">k</script> you have found. (15pts) </p>

<h1><a name="time"></a>Deadlines &amp; How to submit</h1>

<p>MP2 is due on <strong>Apr. 17th 11:55pm</strong>. You have in total 9 days to finish this MP. The late policy for all our homework assignments has been carefully discussed in the course syllabus.</p>

<p>Collab assignment page has been created for this MP. Please submit your written report strictly following the requirement specified above. The report <strong>must be in PDF</strong> format.    </p>

      </div>
    </div>

    <label for="sidebar-checkbox" class="sidebar-toggle"></label>

    <script>
      (function(document) {
        var toggle = document.querySelector('.sidebar-toggle');
        var sidebar = document.querySelector('#sidebar');
        var checkbox = document.querySelector('#sidebar-checkbox');

        document.addEventListener('click', function(e) {
          var target = e.target;

          if(!checkbox.checked ||
             sidebar.contains(target) ||
             (target === checkbox || target === toggle)) return;

          checkbox.checked = false;
        }, false);
      })(document);
    </script>
  

<div style="position: absolute; width: 0px; height: 0px; overflow: hidden; padding: 0px; border: 0px; margin: 0px;"><div id="MathJax_Font_Test" style="position: absolute; visibility: hidden; top: 0px; left: 0px; width: auto; padding: 0px; border: 0px; margin: 0px; white-space: nowrap; text-align: left; text-indent: 0px; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; font-size: 40px; font-weight: normal; font-style: normal; font-family: MathJax_Size2, sans-serif;"></div></div></body></html>