{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy.special import expit, logsumexp\n",
    "from scipy.optimize import minimize\n",
    "from sklearn.datasets import load_iris, load_breast_cancer\n",
    "from sklearn.linear_model import LogisticRegression as skLogisticRegression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation 1\n",
    "- convert multiclass classification problem to binary classification problem in a one-vs-all fashion\n",
    "- based on gradient decent\n",
    "- similar to sklearn multi_class='ovr' & solver='lbfgs'\n",
    "- reference: http://fa.bianp.net/blog/2013/numerical-optimizers-for-logistic-regression/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LogisticRegression():\n",
    "    def __init__(self, C=1.0):\n",
    "        self.C = C\n",
    "\n",
    "    def _encode(self, y):\n",
    "        classes = np.unique(y)\n",
    "        y_train = np.full((y.shape[0], len(classes)), -1)\n",
    "        for i, c in enumerate(classes):\n",
    "            y_train[y == c, i] = 1\n",
    "        if len(classes) == 2:\n",
    "            y_train = y_train[:, 1].reshape(-1, 1)\n",
    "        return classes, y_train\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",
    "        result = np.zeros((y.shape[1], X.shape[1] + 1))\n",
    "        for i in range(y.shape[1]):\n",
    "            cur_y = y[:, i]\n",
    "            w0 = np.zeros(X.shape[1] + 1)\n",
    "            res = minimize(fun=self._cost_grad, jac=True, x0=w0,\n",
    "                           args=(X, cur_y, 1 / self.C), method='L-BFGS-B')\n",
    "            result[i] = res.x\n",
    "        return result[:, :-1], result[:, -1]\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.classes_, y_train = self._encode(y)\n",
    "        self.coef_, self.intercept_ = self._solve_lbfgs(X, y_train)\n",
    "        return self\n",
    "\n",
    "    def decision_function(self, X):\n",
    "        scores = np.dot(X, self.coef_.T) + self.intercept_\n",
    "        if scores.shape[1] == 1:\n",
    "            return scores.ravel()\n",
    "        else:\n",
    "            return scores\n",
    "\n",
    "    def predict(self, X):\n",
    "        scores = self.decision_function(X)\n",
    "        if len(scores.shape) == 1:\n",
    "            indices = (scores > 0).astype(int)\n",
    "        else:\n",
    "            indices = np.argmax(scores, axis=1)\n",
    "        return self.classes_[indices]\n",
    "\n",
    "    def predict_proba(self, X):\n",
    "        scores = self.decision_function(X)\n",
    "        prob = expit(scores)\n",
    "        if len(scores.shape) == 1:\n",
    "            prob = np.vstack((1 - prob, prob)).T\n",
    "        else:\n",
    "            prob /= np.sum(prob, axis=1)[:, np.newaxis]\n",
    "        return prob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# binary classification\n",
    "for C in [0.1, 1, 10]:\n",
    "    X, y = load_breast_cancer(return_X_y = True)\n",
    "    clf1 = LogisticRegression(C=C).fit(X, y)\n",
    "    clf2 = 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",
    "    assert clf1.coef_.shape == (1, X.shape[1])\n",
    "    assert np.allclose(clf1.coef_, clf2.coef_)\n",
    "    assert np.allclose(clf1.intercept_, clf2.intercept_)\n",
    "    prob1 = clf1.decision_function(X)\n",
    "    prob2 = clf2.decision_function(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    prob1 = clf1.predict_proba(X)\n",
    "    prob2 = clf2.predict_proba(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    pred1 = clf1.predict(X)\n",
    "    pred2 = clf2.predict(X)\n",
    "    assert np.array_equal(pred1, pred2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# multiclass classification\n",
    "for C in [0.1, 1, 10]:\n",
    "    X, y = load_iris(return_X_y=True)\n",
    "    clf1 = LogisticRegression(C=C).fit(X, y)\n",
    "    clf2 = 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",
    "    assert clf1.coef_.shape == (len(np.unique(y)), X.shape[1])\n",
    "    assert np.allclose(clf1.coef_, clf2.coef_)\n",
    "    assert np.allclose(clf1.intercept_, clf2.intercept_)\n",
    "    prob1 = clf1.decision_function(X)\n",
    "    prob2 = clf2.decision_function(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    prob1 = clf1.predict_proba(X)\n",
    "    prob2 = clf2.predict_proba(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    pred1 = clf1.predict(X)\n",
    "    pred2 = clf2.predict(X)\n",
    "    assert np.array_equal(pred1, pred2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# penalty = 'none'\n",
    "X, y = load_iris(return_X_y=True)\n",
    "clf1 = LogisticRegression(C=np.inf).fit(X, y)\n",
    "clf2 = skLogisticRegression(penalty='none', multi_class=\"ovr\", solver=\"lbfgs\",\n",
    "                            # keep consisent with scipy default\n",
    "                            tol=1e-5, max_iter=15000).fit(X, y)\n",
    "assert clf1.coef_.shape == (len(np.unique(y)), X.shape[1])\n",
    "assert np.allclose(clf1.coef_, clf2.coef_)\n",
    "assert np.allclose(clf1.intercept_, clf2.intercept_)\n",
    "prob1 = clf1.decision_function(X)\n",
    "prob2 = clf2.decision_function(X)\n",
    "assert np.allclose(prob1, prob2)\n",
    "prob1 = clf1.predict_proba(X)\n",
    "prob2 = clf2.predict_proba(X)\n",
    "assert np.allclose(prob1, prob2)\n",
    "pred1 = clf1.predict(X)\n",
    "pred2 = clf2.predict(X)\n",
    "assert np.array_equal(pred1, pred2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation 2\n",
    "- support multiclass classification problem directly\n",
    "- based on gradient decent\n",
    "- similar to sklearn multi_class='multinomial' & solver='lbfgs'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LogisticRegression():\n",
    "    def __init__(self, C=1.0):\n",
    "        self.C = C\n",
    "\n",
    "    def _encode(self, y):\n",
    "        classes = np.unique(y)\n",
    "        y_train = np.zeros((y.shape[0], len(classes)))\n",
    "        for i, c in enumerate(classes):\n",
    "            y_train[y == c, i] = 1\n",
    "        return classes, y_train\n",
    "\n",
    "    @staticmethod\n",
    "    def _cost_grad(w, X, y, alpha):\n",
    "        w = w.reshape(y.shape[1], -1)\n",
    "        p = np.dot(X, w[:, :-1].T) + w[:, -1]\n",
    "        p -= logsumexp(p, axis=1)[:, np.newaxis]\n",
    "        cost = -np.sum(y * p) + 0.5 * alpha * np.dot(w[:, :-1].ravel(), w[:, :-1].ravel())\n",
    "        grad = np.zeros_like(w)\n",
    "        diff = np.exp(p) - y\n",
    "        grad[:, :-1] = np.dot(diff.T, X) + alpha * w[:, :-1]\n",
    "        grad[:, -1] = np.sum(diff, axis=0)\n",
    "        return cost, grad.ravel()\n",
    "\n",
    "    def _solve_lbfgs(self, X, y):\n",
    "        w0 = np.zeros(y.shape[1] * (X.shape[1] + 1))\n",
    "        res = minimize(fun=self._cost_grad, jac=True, x0=w0,\n",
    "                       args=(X, y, 1 / self.C), method='L-BFGS-B')\n",
    "        result = res.x.reshape(y.shape[1], -1)\n",
    "        if y.shape[1] == 2:\n",
    "            result = result[1][np.newaxis, :]\n",
    "        return result[:, :-1], result[:, -1]\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.classes_, y_train = self._encode(y)\n",
    "        self.coef_, self.intercept_ = self._solve_lbfgs(X, y_train)\n",
    "        return self\n",
    "\n",
    "    def decision_function(self, X):\n",
    "        scores = np.dot(X, self.coef_.T) + self.intercept_\n",
    "        if scores.shape[1] == 1:\n",
    "            return scores.ravel()\n",
    "        else:\n",
    "            return scores\n",
    "\n",
    "    def predict(self, X):\n",
    "        scores = self.decision_function(X)\n",
    "        if len(scores.shape) == 1:\n",
    "            indices = (scores > 0).astype(int)\n",
    "        else:\n",
    "            indices = np.argmax(scores, axis=1)\n",
    "        return self.classes_[indices]\n",
    "\n",
    "    def predict_proba(self, X):\n",
    "        scores = self.decision_function(X)\n",
    "        if len(scores.shape) == 1:\n",
    "            scores = np.c_[-scores, scores]\n",
    "        scores -= np.max(scores, axis=1)[:, np.newaxis]\n",
    "        prob = np.exp(scores)\n",
    "        prob /= np.sum(prob, axis=1)[:, np.newaxis]\n",
    "        return prob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# binary classification\n",
    "for C in [0.1, 1, 10]:\n",
    "    X, y = load_breast_cancer(return_X_y = True)\n",
    "    clf1 = LogisticRegression(C=C).fit(X, y)\n",
    "    clf2 = skLogisticRegression(C=C, multi_class=\"multinomial\", solver=\"lbfgs\",\n",
    "                                # keep consisent with scipy default\n",
    "                                tol=1e-5, max_iter=15000).fit(X, y)\n",
    "    assert clf1.coef_.shape == (1, X.shape[1])\n",
    "    assert np.allclose(clf1.coef_, clf2.coef_)\n",
    "    assert np.allclose(clf1.intercept_, clf2.intercept_)\n",
    "    prob1 = clf1.decision_function(X)\n",
    "    prob2 = clf2.decision_function(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    prob1 = clf1.predict_proba(X)\n",
    "    prob2 = clf2.predict_proba(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    pred1 = clf1.predict(X)\n",
    "    pred2 = clf2.predict(X)\n",
    "    assert np.array_equal(pred1, pred2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# multiclass classification\n",
    "for C in [0.1, 1, 10]:\n",
    "    X, y = load_iris(return_X_y=True)\n",
    "    clf1 = LogisticRegression(C=C).fit(X, y)\n",
    "    clf2 = skLogisticRegression(C=C, multi_class=\"multinomial\", solver=\"lbfgs\",\n",
    "                                # keep consisent with scipy default\n",
    "                                tol=1e-5, max_iter=15000).fit(X, y)\n",
    "    assert clf1.coef_.shape == (len(np.unique(y)), X.shape[1])\n",
    "    assert np.allclose(clf1.coef_, clf2.coef_)\n",
    "    assert np.allclose(clf1.intercept_, clf2.intercept_)\n",
    "    prob1 = clf1.decision_function(X)\n",
    "    prob2 = clf2.decision_function(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    prob1 = clf1.predict_proba(X)\n",
    "    prob2 = clf2.predict_proba(X)\n",
    "    assert np.allclose(prob1, prob2)\n",
    "    pred1 = clf1.predict(X)\n",
    "    pred2 = clf2.predict(X)\n",
    "    assert np.array_equal(pred1, pred2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# penalty = 'none'\n",
    "X, y = load_iris(return_X_y=True)\n",
    "clf1 = LogisticRegression(C=np.inf).fit(X, y)\n",
    "clf2 = skLogisticRegression(penalty='none', multi_class=\"multinomial\", solver=\"lbfgs\",\n",
    "                            # keep consisent with scipy default\n",
    "                            tol=1e-5, max_iter=15000).fit(X, y)\n",
    "assert clf1.coef_.shape == (len(np.unique(y)), X.shape[1])\n",
    "assert np.allclose(clf1.coef_, clf2.coef_)\n",
    "assert np.allclose(clf1.intercept_, clf2.intercept_)\n",
    "prob1 = clf1.decision_function(X)\n",
    "prob2 = clf2.decision_function(X)\n",
    "assert np.allclose(prob1, prob2)\n",
    "prob1 = clf1.predict_proba(X)\n",
    "prob2 = clf2.predict_proba(X)\n",
    "assert np.allclose(prob1, prob2)\n",
    "pred1 = clf1.predict(X)\n",
    "pred2 = clf2.predict(X)\n",
    "assert np.array_equal(pred1, pred2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "dev",
   "language": "python",
   "name": "dev"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}