scikit-learn/scikit-learn — pull request #1386 by coreylynch (2012-11-20 22:49:10+00:00)
Title: WIP: Implement ROC-SVM linear pairwise ranking loss with SGD 

see #1061 [] (https://github.com/scikit-learn/scikit-learn/issues/1061)

I'm taking a stab at porting SophiaML's ranking sgd svm to sklearn.

#### Summary of Additions

##### sgd_fast.pyx
* Added a ranking_sgd function. Similar to plain_sgd, but implements the outer loop found in sophia-ml-methods.cc's StochasticRocLoop & SingleSgdSvmRankStep [Sophia source] (https://code.google.com/p/sofia-ml/)

##### utils.seq_dataset.pyx:
* Added a PairwiseDataset class
* In the init, I create an index of positives and negatives for fast sampling of disagreeing pairs similar to the StochasticRocLoop in sophia-ml-methods.cc
* The .next() returns a random pair of examples with disagreeing labels. See the 'Indexed Sampling' section of http://www.eecs.tufts.edu/~dsculley/papers/large-scale-rank.pdf; they point out that indexing gave faster sampling when D ﬁt in memory.

##### weight_vector.pyx
* Added "dot_on_difference" method, following the example of Sophia ML's SingleSgdSvmRankStep and sf-weight-vector.cc implementation.

##### stochastic_gradient.py
* Added a 'roc_pairwise_ranking' loss option to the SGDClassifier class
* Added a 'ranking' parameter to _make_dataset that defaults to False, but is set to True when the loss function is 'roc_pairwise_ranking'. Used to create a pairwise dataset in seq_dataset.pyx

##### Problems
* I tried running the current code on an unbalanced dataset (using [this example] (http://scikit-learn.org/stable/auto_examples/svm/plot_separating_hyperplane_unbalanced.html#example-svm-plot-separating-hyperplane-unbalanced-py)'s data) and I'm not getting the performance I had hoped for.

Here is the code I ran:
```python
import numpy as np
import pylab as pl
from sklearn.linear_model import SGDClassifier
from sklearn.metrics import confusion_matrix

if __name__=="__main__":
n_samples_1 = 10000
n_samples_2 = 100
X = np.r_[1.5 * np.random.randn(n_samples_1, 2),
0.5 * np.random.randn(n_samples_2, 2) + [2, 2]]
y = np.array([0] * (n_samples_1) + [1] * (n_samples_2), dtype=np.float64)
idx = np.arange(y.shape[0])
np.random.shuffle(idx)
X = X[idx]
y = y[idx]
mean = X.mean(axis=0)
std = X.std(axis=0)
X = (X - mean) / std

for clf, name in ((SGDClassifier(n_iter=100, alpha=0.01), "plain sgd"),
(SGDClassifier(n_iter=100, alpha=0.01, class_weight={1: 10}),("weighted sgd")),
(SGDClassifier(n_iter=100, alpha=0.01, loss='roc_pairwise_ranking'), ("pairwise sgd"))):
clf.fit(X,y)
print clf
print "SCORE: " + str(clf.score(X,y))
print "CONFUSION MATRIX: "
print confusion_matrix(y,clf.predict(X))
print 80*'='
```
... which outputs
```python
SGDClassifier(alpha=0.01, class_weight=None, epsilon=0.1, eta0=0.0,
fit_intercept=True, l1_ratio=0.15, learning_rate=optimal,
loss=hinge, n_iter=100, n_jobs=1, penalty=l2, power_t=0.5, rho=None,
seed=0, shuffle=False, verbose=0, warm_start=False)
SCORE: 0.990099009901
CONFUSION MATRIX:
[[10000 0]
[ 100 0]]
================================================================================
SGDClassifier(alpha=0.01, class_weight={1: 10}, epsilon=0.1, eta0=0.0,
fit_intercept=True, l1_ratio=0.15, learning_rate=optimal,
loss=hinge, n_iter=100, n_jobs=1, penalty=l2, power_t=0.5, rho=None,
seed=0, shuffle=False, verbose=0, warm_start=False)
SCORE: 0.968415841584
CONFUSION MATRIX:
[[9731 269]
[ 50 50]]
================================================================================
SGDClassifier(alpha=0.01, class_weight=None, epsilon=0.1, eta0=0.0,
fit_intercept=True, l1_ratio=0.15, learning_rate=optimal,
loss=roc_pairwise_ranking, n_iter=100, n_jobs=1, penalty=l2,
power_t=0.5, rho=None, seed=0, shuffle=False, verbose=0,
warm_start=False)
SCORE: 0.514257425743
CONFUSION MATRIX:
[[5094 4906]
[ 0 100]]
================================================================================
```

Any suggestions for code cleanup would be greatly appreciated!