title: Fast Information Gain computation
body: <p>I need to compute <strong>Information Gain</strong> scores for >100k features in >10k documents for <strong>text classification</strong>. Code below works fine but <strong>for the full dataset is very slow</strong> - takes more than an hour on a laptop. Dataset is 20newsgroup and I am using scikit-learn, <strong><a href="http://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.chi2.html" rel="noreferrer">chi2</a></strong> function which is provided in scikit works extremely fast.</p>
  
  <p>Any idea how to compute Information Gain faster for such dataset?</p>
  
  <pre><code>def information_gain(x, y):
  
      def _entropy(values):
          counts = np.bincount(values)
          probs = counts[np.nonzero(counts)] / float(len(values))
          return - np.sum(probs * np.log(probs))
  
      def _information_gain(feature, y):
          feature_set_indices = np.nonzero(feature)[1]
          feature_not_set_indices = [i for i in feature_range if i not in feature_set_indices]
          entropy_x_set = _entropy(y[feature_set_indices])
          entropy_x_not_set = _entropy(y[feature_not_set_indices])
  
          return entropy_before - (((len(feature_set_indices) / float(feature_size)) * entropy_x_set)
                                   + ((len(feature_not_set_indices) / float(feature_size)) * entropy_x_not_set))
  
      feature_size = x.shape[0]
      feature_range = range(0, feature_size)
      entropy_before = _entropy(y)
      information_gain_scores = []
  
      for feature in x.T:
          information_gain_scores.append(_information_gain(feature, y))
      return information_gain_scores, []
  </code></pre>
  
  <p><strong>EDIT:</strong></p>
  
  <p>I merged the internal functions and ran <code>cProfiler</code> as below (on a dataset limited to ~15k features and ~1k documents):</p>
  
  <pre><code>cProfile.runctx(
      """for feature in x.T:
      feature_set_indices = np.nonzero(feature)[1]
      feature_not_set_indices = [i for i in feature_range if i not in feature_set_indices]
  
      values = y[feature_set_indices]
      counts = np.bincount(values)
      probs = counts[np.nonzero(counts)] / float(len(values))
      entropy_x_set = - np.sum(probs * np.log(probs))
  
      values = y[feature_not_set_indices]
      counts = np.bincount(values)
      probs = counts[np.nonzero(counts)] / float(len(values))
      entropy_x_not_set = - np.sum(probs * np.log(probs))
  
      result = entropy_before - (((len(feature_set_indices) / float(feature_size)) * entropy_x_set)
                               + ((len(feature_not_set_indices) / float(feature_size)) * entropy_x_not_set))
      information_gain_scores.append(result)""",
      globals(), locals())
  </code></pre>
  
  <p>Result top 20 by <code>tottime</code>:</p>
  
  <pre><code>ncalls  tottime percall cumtime percall filename:lineno(function)
  1       60.27   60.27   65.48   65.48   &lt;string&gt;:1(&lt;module&gt;)
  16171   1.362   0   2.801   0   csr.py:313(_get_row_slice)
  16171   0.523   0   0.892   0   coo.py:201(_check)
  16173   0.394   0   0.89    0   compressed.py:101(check_format)
  210235  0.297   0   0.297   0   {numpy.core.multiarray.array}
  16173   0.287   0   0.331   0   compressed.py:631(prune)
  16171   0.197   0   1.529   0   compressed.py:534(tocoo)
  16173   0.165   0   1.263   0   compressed.py:20(__init__)
  16171   0.139   0   1.669   0   base.py:415(nonzero)
  16171   0.124   0   1.201   0   coo.py:111(__init__)
  32342   0.123   0   0.123   0   {method 'max' of 'numpy.ndarray' objects}
  48513   0.117   0   0.218   0   sputils.py:93(isintlike)
  32342   0.114   0   0.114   0   {method 'sum' of 'numpy.ndarray' objects}
  16171   0.106   0   3.081   0   csr.py:186(__getitem__)
  32342   0.105   0   0.105   0   {numpy.lib._compiled_base.bincount}
  32344   0.09    0   0.094   0   base.py:59(set_shape)
  210227  0.088   0   0.088   0   {isinstance}
  48513   0.081   0   1.777   0   fromnumeric.py:1129(nonzero)
  32342   0.078   0   0.078   0   {method 'min' of 'numpy.ndarray' objects}
  97032   0.066   0   0.153   0   numeric.py:167(asarray)
  </code></pre>
  
  <p>Looks that most of the time is spent in <code>_get_row_slice</code>. I am not entirely sure about the first row, looks it covers the whole block I provided to <code>cProfile.runctx</code>, though I don't know why there is such a big gap between first line <code>totime=60.27</code> and second one <code>tottime=1.362</code>. Where was the difference spent in? Is it possible to check it in <code>cProfile</code>?</p>
  
  <p>Basically, looks the problem is with sparse matrix operations (slicing, getting elements) -- the solution probably would be to calculate <strong>Information Gain</strong> using matrix algebra (like <strong><a href="https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/feature_selection/univariate_selection.py#L154" rel="noreferrer">chi2 is implemented in scikit</a></strong>). But I have no idea how to express this calculation in terms of matrices operations... Anyone has an idea??</p>