{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from copy import deepcopy\n",
    "from scipy.special import expit\n",
    "from scipy.optimize import minimize\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.linear_model import LogisticRegression as skLogisticRegression\n",
    "from sklearn.multiclass import OneVsOneClassifier as skOneVsOneClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class OneVsOneClassifier():\n",
    "    def __init__(self, estimator):\n",
    "        self.estimator = estimator\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.classes_ = np.unique(y)\n",
    "        self.estimators_ = []\n",
    "        for i in range(len(self.classes_)):\n",
    "            for j in range(i + 1, len(self.classes_)):\n",
    "                cond = np.logical_or(y == i, y == j)\n",
    "                X_train = X[cond]\n",
    "                y_train = np.zeros(len(y[cond]))\n",
    "                y_train[y[cond] == j] = 1\n",
    "                clf = deepcopy(self.estimator)\n",
    "                clf.fit(X_train, y_train)\n",
    "                self.estimators_.append(clf)\n",
    "        return self\n",
    "\n",
    "    def decision_function(self, X):\n",
    "        votes = np.zeros((X.shape[0], len(self.classes_)))\n",
    "        # use decision function to break tie\n",
    "        sum_of_confidences = np.zeros((X.shape[0], len(self.classes_)))\n",
    "        k = 0\n",
    "        for i in range(len(self.classes_)):\n",
    "            for j in range(i + 1, len(self.classes_)):\n",
    "                cur_prediction = self.estimators_[k].predict(X)\n",
    "                cur_confidence = self.estimators_[k].decision_function(X)\n",
    "                votes[cur_prediction == 0, i] += 1\n",
    "                votes[cur_prediction == 1, j] += 1\n",
    "                sum_of_confidences[:, i] -= cur_confidence\n",
    "                sum_of_confidences[:, j] += cur_confidence\n",
    "                k += 1\n",
    "        # decision function should not influence vote\n",
    "        # follow the solution in scikit-learn\n",
    "        transformed_confidences = (sum_of_confidences /\n",
    "                                   (3 * (np.abs(sum_of_confidences) + 1)))\n",
    "        return votes + transformed_confidences\n",
    "\n",
    "    def predict(self, X):\n",
    "        scores = self.decision_function(X)\n",
    "        indices = np.argmax(scores, axis=1)\n",
    "        return self.classes_[indices]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Simplified version of LogisticRegression, only work for binary classification\n",
    "class BinaryLogisticRegression():\n",
    "    def __init__(self, C=1.0):\n",
    "        self.C = C\n",
    "\n",
    "    @staticmethod\n",
    "    def _cost_grad(w, X, y, alpha):\n",
    "        def _log_logistic(x):\n",
    "            if x > 0:\n",
    "                return -np.log(1 + np.exp(-x))\n",
    "            else:\n",
    "                return x - np.log(1 + np.exp(x))\n",
    "        yz = y * (np.dot(X, w[:-1]) + w[-1])\n",
    "        cost = -np.sum(np.vectorize(_log_logistic)(yz)) + 0.5 * alpha * np.dot(w[:-1], w[:-1])\n",
    "        grad = np.zeros(len(w))\n",
    "        t = (expit(yz) - 1) * y\n",
    "        grad[:-1] = np.dot(X.T, t) + alpha * w[:-1]\n",
    "        grad[-1] = np.sum(t)\n",
    "        return cost, grad\n",
    "\n",
    "    def _solve_lbfgs(self, X, y):\n",
    "        y_train = np.full(X.shape[0], -1)\n",
    "        y_train[y == 1] = 1\n",
    "        w0 = np.zeros(X.shape[1] + 1)\n",
    "        res = minimize(fun=self._cost_grad, jac=True, x0=w0,\n",
    "                       args=(X, y_train, 1 / self.C), method='L-BFGS-B')\n",
    "        return res.x[:-1], res.x[-1]\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.coef_, self.intercept_ = self._solve_lbfgs(X, y)\n",
    "        return self\n",
    "\n",
    "    def decision_function(self, X):\n",
    "        scores = np.dot(X, self.coef_) + self.intercept_\n",
    "        return scores\n",
    "\n",
    "    def predict(self, X):\n",
    "        scores = self.decision_function(X)\n",
    "        indices = (scores > 0).astype(int)\n",
    "        return indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "for C in [0.1, 1, 10, np.inf]:\n",
    "    X, y = load_iris(return_X_y=True)\n",
    "    clf1 = OneVsOneClassifier(BinaryLogisticRegression(C=C)).fit(X, y)\n",
    "    clf2 = skOneVsOneClassifier(skLogisticRegression(C=C, multi_class=\"ovr\", solver=\"lbfgs\",\n",
    "                                                     # keep consisent with scipy default\n",
    "                                                     tol=1e-5, max_iter=15000)).fit(X, y)\n",
    "    prob1 = clf1.decision_function(X)\n",
    "    prob2 = clf2.decision_function(X)\n",
    "    pred1 = clf1.predict(X)\n",
    "    pred2 = clf2.predict(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    assert np.array_equal(pred1, pred2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}