MRG Use scores, not p-values, for feature selection
diff --git a/doc/modules/feature_selection.rst b/doc/modules/feature_selection.rst
index 0c7bb54b77ec6..574a7b8ad745f 100644
--- a/doc/modules/feature_selection.rst
+++ b/doc/modules/feature_selection.rst
@@ -17,12 +17,13 @@ Univariate feature selection
 
 Univariate feature selection works by selecting the best features based on
 univariate statistical tests. It can seen as a preprocessing step
-to an estimator. Scikit-Learn exposes feature selection routines
-a objects that implement the `transform` method:
+to an estimator. Scikit-learn exposes feature selection routines
+as objects that implement the `transform` method:
 
- * selecting the k-best features :class:`SelectKBest`
+ * :class:`SelectKBest` removes all but the `k` highest scoring features
 
- * setting a percentile of features to keep :class:`SelectPercentile`
+ * :class:`SelectPercentile` removes all but a user-specified highest scoring
+   percentile of features
 
  * using common univariate statistical tests for each feature:
    false positive rate :class:`SelectFpr`, false discovery rate
diff --git a/doc/whats_new.rst b/doc/whats_new.rst
index 14ce0966c5cfc..2e2f2a5948d77 100644
--- a/doc/whats_new.rst
+++ b/doc/whats_new.rst
@@ -14,6 +14,12 @@ Changelog
    - :class:`feature_selection.SelectPercentile` now breaks ties
      deterministically instead of returning all equally ranked features.
 
+   - :class:`feature_selection.SelectKBest` and
+     :class:`feature_selection.SelectPercentile` are more numerically stable
+     since they use scores, rather than p-values, to rank results. This means
+     that they might sometimes select different features than they did
+     previously.
+
    - Ridge regression and ridge classification fitting with ``sparse_cg`` solver
      no longer has quadratic memory complexity, by `Lars Buitinck`_ and
      `Fabian Pedregosa`_.
diff --git a/sklearn/feature_selection/tests/test_feature_select.py b/sklearn/feature_selection/tests/test_feature_select.py
index 7c66cbe5b3082..3b5707bbd4954 100644
--- a/sklearn/feature_selection/tests/test_feature_select.py
+++ b/sklearn/feature_selection/tests/test_feature_select.py
@@ -2,12 +2,14 @@
 Todo: cross-check the F-value with stats model
 """
 
+import itertools
 import numpy as np
+from scipy import stats, sparse
 import warnings
 
 from nose.tools import assert_equal, assert_raises, assert_true
 from numpy.testing import assert_array_equal, assert_array_almost_equal
-from scipy import stats, sparse
+from sklearn.utils.testing import assert_not_in
 
 from sklearn.datasets.samples_generator import (make_classification,
                                                 make_regression)
@@ -402,7 +404,7 @@ def test_selectkbest_tiebreaking():
 
 
 def test_selectpercentile_tiebreaking():
-    """Test if SelectPercentile actually selects k features in case of ties.
+    """Test if SelectPercentile selects the right n_features in case of ties.
     """
     X = [[1, 0, 0], [0, 1, 1]]
     y = [0, 1]
@@ -413,3 +415,21 @@ def test_selectpercentile_tiebreaking():
 
         X2 = SelectPercentile(chi2, percentile=67).fit_transform(X, y)
         assert_equal(X2.shape[1], 2)
+
+
+def test_tied_pvalues():
+    """Test whether k-best and percentiles work with tied pvalues from chi2."""
+    # chi2 will return the same p-values for the following features, but it
+    # will return different scores.
+    X0 = np.array([[10000, 9999, 9998], [1, 1, 1]])
+    y = [0, 1]
+
+    for perm in itertools.permutations((0, 1, 2)):
+        X = X0[:, perm]
+        Xt = SelectKBest(chi2, k=2).fit_transform(X, y)
+        assert_equal(Xt.shape, (2, 2))
+        assert_not_in(9998, Xt)
+
+        Xt = SelectPercentile(chi2, percentile=67).fit_transform(X, y)
+        assert_equal(Xt.shape, (2, 2))
+        assert_not_in(9998, Xt)
diff --git a/sklearn/feature_selection/univariate_selection.py b/sklearn/feature_selection/univariate_selection.py
index 1c9fa19a35ae6..e5e08c1eb24dc 100644
--- a/sklearn/feature_selection/univariate_selection.py
+++ b/sklearn/feature_selection/univariate_selection.py
@@ -293,7 +293,7 @@ def inverse_transform(self, X):
 ######################################################################
 
 class SelectPercentile(_AbstractUnivariateFilter):
-    """Filter: Select the best percentile of the p-values.
+    """Select features according to a percentile of the highest scores.
 
     Parameters
     ----------
@@ -331,24 +331,24 @@ def _get_support_mask(self):
         if percentile > 100:
             raise ValueError("percentile should be between 0 and 100"
                              " (%f given)" % (percentile))
-        # Cater for Nans
+        # Cater for NaNs
         if percentile == 100:
-            return np.ones(len(self.pvalues_), dtype=np.bool)
+            return np.ones(len(self.scores_), dtype=np.bool)
         elif percentile == 0:
-            return np.zeros(len(self.pvalues_), dtype=np.bool)
-        alpha = stats.scoreatpercentile(self.pvalues_, percentile)
+            return np.zeros(len(self.scores_), dtype=np.bool)
+        alpha = stats.scoreatpercentile(self.scores_, 100 - percentile)
         # XXX refactor the indices -> mask -> indices -> mask thing
-        inds = np.where(self.pvalues_ <= alpha)[0]
-        # if we selected to many because of equal p-values,
+        inds = np.where(self.scores_ >= alpha)[0]
+        # if we selected too many features because of equal scores,
         # we throw them away now
-        inds = inds[:len(self.pvalues_) * percentile // 100]
-        mask = np.zeros(self.pvalues_.shape, dtype=np.bool)
+        inds = inds[:len(self.scores_) * percentile // 100]
+        mask = np.zeros(self.scores_.shape, dtype=np.bool)
         mask[inds] = True
         return mask
 
 
 class SelectKBest(_AbstractUnivariateFilter):
-    """Filter: Select the k lowest p-values.
+    """Select features according to the k highest scores.
 
     Parameters
     ----------
@@ -369,7 +369,7 @@ class SelectKBest(_AbstractUnivariateFilter):
 
     Notes
     -----
-    Ties between features with equal p-values will be broken in an unspecified
+    Ties between features with equal scores will be broken in an unspecified
     way.
 
     """
@@ -380,15 +380,15 @@ def __init__(self, score_func=f_classif, k=10):
 
     def _get_support_mask(self):
         k = self.k
-        if k > len(self.pvalues_):
+        if k > len(self.scores_):
             raise ValueError("cannot select %d features among %d"
-                             % (k, len(self.pvalues_)))
+                             % (k, len(self.scores_)))
 
         # XXX This should be refactored; we're getting an array of indices
         # from argsort, which we transform to a mask, which we probably
         # transform back to indices later.
-        mask = np.zeros(self.pvalues_.shape, dtype=bool)
-        mask[np.argsort(self.pvalues_)[:k]] = 1
+        mask = np.zeros(self.scores_.shape, dtype=bool)
+        mask[np.argsort(self.scores_)[-k:]] = 1
         return mask
 
 
@@ -527,9 +527,13 @@ class GenericUnivariateSelect(_AbstractUnivariateFilter):
                         }
 
     def __init__(self, score_func=f_classif, mode='percentile', param=1e-5):
+        if not callable(score_func):
+            raise TypeError(
+                "The score function should be a callable, %r (type %s) "
+                "was passed." % (score_func, type(score_func)))
         if mode not in self._selection_modes:
             raise ValueError(
-                "The mode passed should be one of %s, %r "
+                "The mode passed should be one of %s, %r, (type %s) "
                 "was passed." % (
                         self._selection_modes.keys(),
                         mode, type(mode)))

This solves the numerical stability issue that @amueller encountered some time ago: p-values, at least those returned by `chi2`, may contain ties even when the scores don't.

This also paves the way for score functions that are not based on significance tests, such as mutual information and infogain (whence the name of this branch, but I won't be pushing those in this PR).
