{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Experiments on Real Data #\n", "\n", "For the details of the experimental setup and results please see Section 5.2 of the main text." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "/Users/dennisshasha/anaconda/envs/py36/lib/python3.6/site-packages/numexpr/cpuinfo.py:76: UserWarning: [Errno 2] No such file or directory: 'sysctl': 'sysctl'\n", " stacklevel=stacklevel + 1):\n" ] } ], "source": [ "# IMPORTS\n", "\n", "# BASICS\n", "%matplotlib inline\n", "import numpy as np\n", "import pandas as pd\n", "import matplotlib.pyplot as plt\n", "from random import random\n", "from math import exp, sqrt, log, tanh\n", "from copy import deepcopy\n", "from tqdm import tqdm\n", "import warnings\n", "warnings.filterwarnings('ignore')\n", "\n", "\n", "# STYLE (optional)\n", "np.set_printoptions(formatter={'float': lambda x: \"{0:0.3f}\".format(x)})\n", "plt.rcParams[\"font.family\"] = \"Times New Roman\"\n", "plt.style.use('seaborn-whitegrid')\n", "plt.style.use('seaborn-poster')\n", "plt.style.use('seaborn-dark-palette')\n", "plt.rcParams[\"mathtext.fontset\"] = \"cm\"\n", "\n", "\n", "# SCIKIT-LEARN\n", "from sklearn.model_selection import train_test_split\n", "from sklearn.ensemble import RandomForestClassifier\n", "from sklearn.neighbors import KNeighborsClassifier\n", "from sklearn.linear_model import LogisticRegression\n", "from sklearn import svm\n", "from sklearn import datasets\n", "from sklearn.calibration import CalibratedClassifierCV\n", "from sklearn.utils import shuffle\n", "from sklearn.model_selection import GridSearchCV\n", "from sklearn.preprocessing import StandardScaler\n", "from sklearn.model_selection import KFold\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# CONFIDENCE BASED REFUSAL MECHANISM\n", "\n", "\n", "def calibrate(C,Xcal, ycal, eps):\n", " # Computes and returns the minimum threshold for the classifier C \n", " # that gives the empirical error rate eps on the calibration data (Xcal, ycal).\n", " # Note: Assumes C supports predict.proba() method.\n", " \n", " A = C.predict_proba(Xcal)\n", " pred_cal = C.predict(Xcal)\n", " n_cal, n_features = Xcal.shape\n", " \n", " # Compute potential threshold points\n", " pt = A.max(axis=1)\n", " \n", " # Find the smallest temprorary threshold to satisfy the condition\n", " a = np.argsort(pt)\n", " \n", " errors = sum(pred_cal != ycal) \n", " \n", " predictions = n_cal \n", " threshold = 1\n", " \n", " if errors/predictions > eps:\n", " for i in a: # As we change the threshold, we refuse one more data point each time.\n", " if pred_cal[i] != ycal[i]:\n", " errors = errors - 1 # We got rid of one error\n", " predictions = predictions - 1\n", " if errors/predictions <= eps:\n", " threshold = pt[i]\n", " break\n", " else:\n", " threshold = 0 \n", " return threshold\n", "\n", "\n", "def cv_calibrate(C,X, y, eps, k =3):\n", " # Train C on the data (X,y) and returns the mean of k minimal rejection thresholds\n", " # calibrated on k-fold validation sets using the calibrate() function defined above.\n", " \n", " kf = KFold(n_splits=k, shuffle = False)\n", " th = []\n", " for train_index, test_index in kf.split(X):\n", " X_train, X_test = X[train_index], X[test_index]\n", " y_train, y_test = y[train_index], y[test_index]\n", " C.fit(X_train, y_train)\n", " th.append(calibrate(C,X_test, y_test, eps))\n", " C.fit(X,y)\n", " return np.mean(th)\n", "\n", "def conf_test(C,Xtest, th):\n", " # Predict labels of the points in Xtest using classifier C and rejection threshold th\n", " \n", " test_A = C.predict_proba(Xtest)\n", " pred_test = C.predict(Xtest)\n", " refused = np.sum(test_A>th, axis=1) == 0\n", " return pred_test, refused\n", "\n", "\n", " " ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# ADAPTIVE SAFEPREDICT\n", "\n", "class SafePredict:\n", " def __init__(self, eps = 0.1, w0 = 0.5, alpha = 0, beta = 1, horizon = 1):\n", " # Initialize\n", " self.eps = eps # Target error rate\n", " self.w0 = w0 # Initial weight of Dummy (i.e. 1- w_P)\n", " self.w = [w0, 1-w0]\n", " self.wPs = (1-w0)*w0\n", " self.alpha = alpha # Adaptivity parameter: w_P >= alpha (default value 0)\n", " self.beta = beta # Adaptivity parameter: w_P <= beta (default value 1)\n", " self.T = horizon # Time horizon\n", " self.C = sqrt(-log(w0) - (self.T-1)*log(1-self.alpha)) / (1-self.eps) \n", " self.k = 1 \n", " self.eta = self.C / 2**(self.k/2)\n", " \n", " \n", " def update(self, lP): \n", " # Update the weights, one data point at a time\n", " \n", " # Update the weights\n", " if self.wPs < 2**self.k:\n", " self.w[0] = self.w[0]*exp(-self.eta * self.eps); self.w[1] = self.w[1]*exp(-self.eta * lP); W = sum(self.w)\n", " self.w[0] /= W; self.w[1] /= W\n", " else:\n", " self.w[0] = self.w0; self.w[1] = 1-self.w0\n", " self.k += 1; \n", " self.eta = self.eta / sqrt(2)\n", " self.wPs = (1-self.w0)*self.w0\n", " \n", " # Mix the weights\n", " self.w[0] = self.w[0]*(self.beta-self.alpha) + 1 - self.beta \n", " self.w[1] = self.w[1]*(self.beta-self.alpha) + self.alpha\n", " \n", " \n", " # Update the learning rate \n", " self.wPs += self.w[1]*self.w[0]\n", " \n", " # Return the prediction probability\n", " return self.w[1]\n", " \n", " return self.w[1] " ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# LOAD THE DATA\n", "\n", "### MNIST DATA SET (MULTI-LABEL)\n", "digits = datasets.fetch_mldata('mnist-original')\n", "X, y = digits.data, digits.target\n", "y = y.astype(int)\n", "\n", "\n", "# OTHER DATA-SETS\n", "# MAKE SURE THE LABELS ARE INTEGERS STARTING FROM 0.\n", "\n", "### COD\n", "#cod = datasets.fetch_mldata('cod-rna')\n", "#X, y = cod.data, cod.target\n", "#y = (y + 1)/2\n", "#y = y.astype(int)\n", "\n", "\n", "### COVER\n", "#covtype = datasets.fetch_covtype()\n", "#X, y = covtype.data, covtype.target\n", "\n", "\n", "### LETTER\n", "#letter = datasets.fetch_mldata('letter')\n", "#X, y = letter.data, letter.target\n", "#y = y - 1\n", "#y = y.astype(int)\n", "\n", "\n", "### SENSIT\n", "#sensit = datasets.fetch_mldata('sensit-vehicle-combined')\n", "#X, y = sensit.data, sensit.target\n", "#y = y - 1\n", "#y = y.astype(int)\n", "\n", "\n", "# MAGIC \n", "#df = pd.read_csv('http://archive.ics.uci.edu/ml/machine-learning-databases/magic/magic04.data', sep = ',', header = None)\n", "#X = df[[0,1,2,3,4,5,6,7,8,9]].as_matrix(); y = df[10].as_matrix()\n", "#y = y == 'h'; y = y.astype(int)\n", "\n", "\n", "# SENSORLESS\n", "#df = pd.read_csv('http://archive.ics.uci.edu/ml/machine-learning-databases/00325/Sensorless_drive_diagnosis.txt', sep = '\\s+', header = None)\n", "#y = df[48].as_matrix().astype(int); y = y-1\n", "#X = df.as_matrix(); X = X[:, :-1]\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(array([4, 5, 2, 8, 6, 1, 7, 0, 9, 3]), 10000)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# SCALE AND SPLIT THE DATA\n", "holdout_X, X, holdout_y, y = train_test_split(X, y, train_size=2500/len(y))\n", "scaler = StandardScaler()\n", "holdout_X = scaler.fit_transform(holdout_X)\n", "X = scaler.transform(X)\n", "X, rest_X, y, rest_y = train_test_split(X, y, train_size=10000/len(y))\n", "\n", "T = y.size\n", "\n", "# CHOOSE A TARGET ERROR RATE (Optional, instead one can declare an arbitrary target)\n", "classifier1 = RandomForestClassifier(n_estimators=100, min_samples_leaf=1, oob_score=False, n_jobs=-1)\n", "classifier1.fit(holdout_X,holdout_y)\n", "epsilon = (1 - classifier1.score(rest_X,rest_y))\n", "\n", "\n", "### INTRODUCE A CHANGE POINT (Optional)\n", "permuted_labels = np.random.permutation(max(y)+1)\n", "for t in range(T//2,T):\n", " y[t] = permuted_labels[y[t]] \n", "permuted_labels, len(y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Predict from 100 to 10000\n" ] } ], "source": [ "# EXPERIMENTAL SETUP\n", "\n", "# RETRAIN THE BASE PREDICTOR AT EVERY tau SAMPLES\n", "tau = 100\n", "\n", "# START FROM THE END OF THE FIRST EPOCH\n", "tl = tau\n", "print('Predict from',tl,'to',T)\n", "\n", "\n", "# SET THE BASE PREDICTOR (RANDOM FOREST TRAINED AND REJECTION THRESHOLD IS CALIBRATED USING ONLY THE FIRST EPOCH)\n", "predictor1 = classifier1 \n", "th1 = cv_calibrate(predictor1 ,X[:tl], y[:tl], epsilon, k =3)\n", "\n", "# CREATE A COPY OF THE SAME PREDICTOR FOR THE AMNESIC ADAPTIVITY\n", "predictor2 = deepcopy(classifier1)\n", "th2 = cv_calibrate(predictor1 ,X[:tl], y[:tl], epsilon, k =3)\n", " \n", "# ERROR AND REFUSE FLAGS (BOOK KEEPING)\n", "err1 = np.empty(T-tl)\n", "ref1 = np.empty(T-tl)\n", "err2 = np.empty(T-tl)\n", "ref2 = np.empty(T-tl)\n", "\n", "\n", "# SP\n", "r1 = SafePredict(eps = epsilon, w0 = 0.5, alpha = 10/T, beta = 1, horizon = T)\n", "\n", "# CBR+SP\n", "rcb1 = SafePredict(eps = epsilon, w0 = 0.5, alpha = 10/T, beta = 1, horizon = T)\n", "Wp_cb1 = np.empty(T-tl); \n", "Wp_sp1 = np.empty(T-tl); \n", "Wp_cbsp1 = np.empty(T-tl); \n", "Lp1 = np.empty(T-tl)\n", "\n", "# Amnesic CBR+SP\n", "rcb2 = SafePredict(eps = epsilon, w0 = 0.5, alpha = 10/T, beta = 1, horizon = T)\n", "Wp_cb2 = np.empty(T-tl); \n", "Wp_cbsp2 = np.empty(T-tl); \n", "Lp2 = np.empty(T-tl)\n", "TT = 0 # Last detected change point\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "\r", " 0%| | 0/9900 [00:000] + [0])\n", " \n", " # Update the last detected change point\n", " \n", " if ER < 0.5: # Naive detection, used in the paper\n", " ## More robust detection methods (NOT USED IN THE PAPER)\n", " #if ER < 0.5 and np.sum([1 for x in Wp_cbsp2[t-tl-tau:t-tl+1] if x>0]) > 0.1*tau : \n", " #if ER < 0.5 and t-TT > 3*tau: \n", " TT = t-tau \n", " print(TT)\n", " \n", " \n", " \n", " # COMPUTE THE CONFIDENCE BASED REFUSALS \n", " \n", " pred, ref1[t-tl] = conf_test(predictor1,X[t,:].reshape(1,-1), th1) \n", " Lp1[t-tl] = pred != y[t]\n", " Wp_cb1[t-tl] = 1-ref1[t-tl] # CBR\n", " \n", " pred, ref2[t-tl] = conf_test(predictor2,X[t,:].reshape(1,-1), th2) \n", " Lp2[t-tl] = pred != y[t]\n", " Wp_cb2[t-tl] = 1-ref2[t-tl] # Amnesic CBR+SP \n", " \n", " \n", " \n", " \n", " # COMPUTE THE SAFEPREDICT REFUSALS\n", " \n", " Wp_sp1[t-tl] = r1.update(Lp1[t-tl]) # SP\n", " \n", " \n", " if ref1[t-tl]==0: # CBR+SP\n", " Wp_cbsp1[t-tl] = rcb1.update(Lp1[t-tl])\n", " else:\n", " Wp_cbsp1[t-tl] = 0\n", " \n", " \n", " if ref2[t-tl]==0: # Amnesic CBR+SP\n", " Wp_cbsp2[t-tl] = rcb2.update(Lp2[t-tl])\n", " else:\n", " Wp_cbsp2[t-tl] = 0\n", " \n", "\n", " \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "\n", "WW = 15; HH = 18; \n", "WW = 12; HH = 12; \n", "ll = 3; me = 500; ms = 10\n", "\n", "plt.figure(figsize=(WW,HH))\n", "\n", "\n", "# ERROR PLOT \n", "ax = plt.subplot(2,1,1)\n", "plt.plot(np.cumsum(Lp1)/np.arange(T-tl), linestyle='-.', linewidth=ll)\n", "plt.plot(np.cumsum([i*j for i,j in zip(Wp_cb1,Lp1)])/np.cumsum(Wp_cb1), linestyle='-', linewidth=ll, marker = 'o', markevery=me, markersize = ms)\n", "plt.plot(np.cumsum([i*j for i,j in zip(Wp_sp1,Lp1)])/np.cumsum(Wp_sp1), linestyle='-', linewidth=ll, marker = 'v', markevery=me, markersize = ms)\n", "plt.plot(np.cumsum([i*j for i,j in zip(Wp_cbsp1,Lp1)])/np.cumsum(Wp_cbsp1), linestyle='-', linewidth=ll, marker = 'P', markevery=me, markersize = ms)\n", "plt.plot(np.cumsum([i*j for i,j in zip(Wp_cbsp2,Lp2)])/np.cumsum(Wp_cbsp2),'k', linestyle='--', linewidth=ll, marker = 's', markevery=me, markersize = ms)\n", "plt.plot([0, T-tl],[epsilon, epsilon], label = r'Target ($\\epsilon$)', linestyle = '--', color = 'red', linewidth = ll*1.5)\n", "lg = ax.legend(loc='best')\n", "lg.draw_frame(True)\n", "plt.ylim([0, 0.3]) #4*epsilon])\n", "#plt.legend(loc =0)\n", "plt.ylabel(\"Error Rate\")\n", "# EFFICIENCY PLOT\n", "ax = plt.subplot(2,1,2)\n", "plt.plot( np.ones(T-tl), label = 'Random Forest', linestyle='-.', linewidth=ll)\n", "plt.plot( np.cumsum(Wp_cb1)/np.arange(T-tl), label = 'Conf. Based Ref. (CBR)', linestyle='-', linewidth=ll, marker = 'o', markevery=me, markersize = ms)\n", "plt.plot( np.cumsum(Wp_sp1)/np.arange(T-tl), label = 'SafePredict (SP)', linestyle='-', linewidth=ll, marker = 'v', markevery=me, markersize =ms)\n", "plt.plot( np.cumsum(Wp_cbsp1)/np.arange(T-tl), label = 'CBR + SafePredict', linestyle='-', linewidth=ll, marker = 'P', markevery=me, markersize = ms)\n", "plt.plot( np.cumsum(Wp_cbsp2)/np.arange(T-tl),'k', label = 'Amnesic CBR + SP', linestyle='--', linewidth=ll, marker = 's', markevery=me, markersize =ms)\n", "lg = ax.legend(loc='center left', bbox_to_anchor=(-0.04, -0.25), ncol = 3)\n", "lg.draw_frame(True)\n", "plt.ylim([0, 1.1])\n", "plt.ylabel(\"Efficiency\")\n", "plt.xlabel(\"Time\")\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [conda env:py36]", "language": "python", "name": "conda-env-py36-py" }, "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.3" } }, "nbformat": 4, "nbformat_minor": 2 }