Algorithm-Visualizations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a1a84667",
   "metadata": {},
   "source": [
    "## Updater Algorithm Visualization "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d154dfa8",
   "metadata": {},
   "source": [
    "This notebook simulates a series of bounty hunters who come up with different (g,h) pairs to submit as updates to the model. Each group g specified by a bounty hunter is a demographic group, and the h is a simple model trained on that group. For the paper, this was used on the ACS folktables dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2877fff9",
   "metadata": {},
   "source": [
    "First, we load in all of our libraries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbbdb432",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn import metrics\n",
    "\n",
    "import importlib\n",
    "import copy\n",
    "\n",
    "import updater\n",
    "import model\n",
    "import verifier"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b095fff1",
   "metadata": {},
   "source": [
    "Here we define our global parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b085d78d",
   "metadata": {},
   "outputs": [],
   "source": [
    "classifier = \"Decision Tree\" # set to either \"Decision Tree\" or \"Logistic Regression\"\n",
    "test_size = 0.2 #train-test split\n",
    "dt_depth = 10 # setting decision tree training depth globally\n",
    "conjunction = True #setting groups to be conjunctions in random cross-product version; if false runs with disjunctions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf31375e",
   "metadata": {},
   "source": [
    "## Loading Data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d118b9c",
   "metadata": {},
   "source": [
    "Now, we have to load in the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe3d249e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# ACS specific flags\n",
    "\n",
    "acs_task = 'employment' # options: employment, income, public_coverage, mobility, and travel_time.\\\n",
    "acs_year = 2018 # must be between 2014 and 2018\n",
    "acs_states = ['NY'] # can be any list of state abbreviations.\n",
    "acs_horizon='1-Year' # 1-Year or 5-Year\n",
    "acs_survey='person' #'person' or 'household'\n",
    "\n",
    "# for subsampling rows: can specify first and last of data to be pulled. currently pulling everything.\n",
    "row_start = 0 \n",
    "row_end = -1 #set to -1 if you want to pull the whole dataset\n",
    "\n",
    "# for subsampling columns. note: can only subsample consecutive columns with current implementation in folktables\n",
    "col_start=0\n",
    "col_end=-1 #set to -1 if you want to pull the whole dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd6d7f5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import acsData\n",
    "importlib.reload(acsData)\n",
    "\n",
    "[train_x, train_y, test_x, test_y, group_functions, group_indicators, min_age, mid_age] = acsData.get_data(\n",
    "    test_size, acs_task, acs_year, acs_states,acs_horizon=acs_horizon, acs_survey=acs_survey, row_start = row_start,\n",
    "    row_end = row_end, col_start=col_start, col_end=col_end)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3880e37b",
   "metadata": {},
   "source": [
    "To get a sense of what the data loooks like: \n",
    "\n",
    "For the column codes for the ACS data, see appendix B here https://arxiv.org/pdf/2108.04884.pdf. Briefly, the different categories are age (AGEP), education (SCHL), marital status (MAR), relationship (RELP), disability status (DIS), parent employee status (ESP), citizen status (CIT), mobility status (MIG), military service (MIL), ancestry record (ANC), nation of origin (NATIVITY), hearing difficulty (DEAR), visual dificulty (DEYE), learning disability (DREM), sex (SEX), and race (RAC1P).\n",
    "\n",
    "Currently, the group functions generated for the ACS data are the 8 race categories, 2 sex categories, and 3 age groups, one of under 30-year-olds and one of 60+ year olds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80091869",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_group_info(x, groups, group_ind):\n",
    "        indices = [x.apply(g, axis=1)==1 for g in groups]\n",
    "        xs_i = [x[i] for i in indices]\n",
    "        for i in range(len(groups)):\n",
    "            print(\"Number of datapoints in group {}:\".format(group_ind[i], len(xs_i[i])))\n",
    "            \n",
    "\n",
    "def print_all_info_table(x1, x2, groups, group_ind):\n",
    "    indices = [x1.apply(g, axis=1)==1 for g in groups]\n",
    "    x1s = [x1[i] for i in indices]\n",
    "    indices = [x2.apply(g, axis=1)==1 for g in groups]\n",
    "    x2s = [x2[i] for i in indices]\n",
    "    nums = [x1.shape[0] + train_x.shape[0]]\n",
    "    for i in range(len(groups)):\n",
    "        nums.append(len(x1s[i]) + len(x2s[i]))\n",
    "    print(*group_ind, sep= ' & ')\n",
    "    print(*nums, sep=' & ')\n",
    "\n",
    "print_all_info_table(test_x, train_x, group_functions, ['Total'] + group_indicators)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65dcbf18",
   "metadata": {},
   "source": [
    "## Generating our initial model"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e02b3f7",
   "metadata": {},
   "source": [
    "Our initial model will be either logistic regression that's trained over all features or a decision tree over all features with depth 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9dac2815",
   "metadata": {},
   "outputs": [],
   "source": [
    "initial_model = None\n",
    "if classifier == \"Logistic Regression\":\n",
    "    initial_model = LogisticRegression(penalty='none', max_iter = 2000)\n",
    "elif classifier == \"Decision Tree\":\n",
    "    initial_model = DecisionTreeClassifier(max_depth = 1, random_state=0) #setting random state for replicability\n",
    "initial_model.fit(train_x, train_y);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5e98f3a",
   "metadata": {},
   "source": [
    "We now can examine our initial model's loss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa2be289",
   "metadata": {},
   "outputs": [],
   "source": [
    "metrics.zero_one_loss(train_y, initial_model.predict(train_x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23a2b737",
   "metadata": {},
   "source": [
    "## Generating our bounty hunters' inputs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a26c5c22",
   "metadata": {},
   "source": [
    "We want to simulate a series of bounty hunters, each who propose a group function *g* and a model *h* which performs better on that group. Specifically, we first imagine a set of bounty hunters who propose models that are trained only on a specific racial group, then bounty hunters who train groups based on sex, then age categories."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "274bd764",
   "metadata": {},
   "source": [
    "First, we need to define the *g* functions. A given *g_i(x)* should return 1 if *x* is a member of the group that the ith bounty hunter is targeting, and 0 otherwise. We assume that these groups have been predefined, using the features of the dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79eb92b7",
   "metadata": {},
   "source": [
    "Next, we need to generate regression models that are trained just over the portion of the data that each group function applies to. We're going to be reusing this code for later sets of groups, so build a helper function that does it in general."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "862c8a0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bounty_hunter_models(x, y, g_functions):\n",
    "    # learn the indices first\n",
    "    indices = [x.apply(g, axis=1)==1 for g in g_functions]\n",
    "    # then pull the particular rows from the dataframe\n",
    "    training_xs = [x[i] for i in indices]\n",
    "    training_ys = [y[i] for i in indices]\n",
    "\n",
    "    ms = []\n",
    "    for i in range(len(training_xs)):\n",
    "        if classifier == \"Logistic Regression\":\n",
    "            log_reg = LogisticRegression(penalty='none', max_iter = 2000)\n",
    "            log_reg.fit(training_xs[i], training_ys[i])\n",
    "            ms.append(log_reg.predict)\n",
    "        elif classifier == \"Decision Tree\":\n",
    "            dt = DecisionTreeClassifier(max_depth = dt_depth, random_state=0) #setting random state for replicability\n",
    "            dt.fit(training_xs[i], training_ys[i])\n",
    "            ms.append(dt.predict)\n",
    "    return ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4075af49",
   "metadata": {},
   "outputs": [],
   "source": [
    "# now, generate the models using the group functions\n",
    "models = bounty_hunter_models(train_x, train_y, group_functions)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c831d843",
   "metadata": {},
   "source": [
    "# Running the Model Updates"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b8188e8",
   "metadata": {},
   "source": [
    "We now run the updater, which incorporates all of the bounty hunters' updates iteratively, and store the errors of each group at each step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "567051b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "importlib.reload(updater)\n",
    "importlib.reload(model)\n",
    "importlib.reload(verifier)\n",
    "\n",
    "def run_updates(g_functions, models_to_update, g_indicators, file_name):\n",
    "    # stick the gs and hs into a form that the updater accepts\n",
    "    bounty_hunters = [[g_functions[i], models_to_update[i], g_indicators[i]] for i in range(len(g_functions))]\n",
    "\n",
    "    all_groups = [lambda x: 1] + g_functions\n",
    "    print(\"Building initial model\")\n",
    "    # build the initial model \n",
    "    f = model.PointerDecisionList(initial_model.predict, all_groups)\n",
    "\n",
    "    #  recording the errors of the initial model\n",
    "    f.test_errors[0] = updater.measure_all_group_errors(f, all_groups, test_x, test_y)\n",
    "    f.train_errors[0] = updater.measure_all_group_errors(f, all_groups, train_x, train_y)\n",
    "    \n",
    "    # run the updater\n",
    "    updated_pdls = [copy.deepcopy(f)]\n",
    "    print(\"Measuring group errors of initial model on training data\")\n",
    "\n",
    "    i = 0\n",
    "    for b in bounty_hunters:\n",
    "        print(\"Running on group {}/{}\".format(i+1, len(bounty_hunters)))\n",
    "        print(\"Group running on {}\".format(g_indicators[i]))\n",
    "        # check if we want to bother with the update or not\n",
    "        if verifier.is_proposed_group_good(f, test_x, test_y, b[1], b[0]):\n",
    "            # the update step:\n",
    "            updater.iterative_update(f, b[1], b[0], train_x, train_y, test_x, test_y, b[2], all_groups, g_indicators)\n",
    "            # create a copy of the model at this stage for later visualization purposes\n",
    "            updated_pdls.append(copy.deepcopy(f))\n",
    "        # if the update didn't help, just copy the errors and updated_pdls at this round.\n",
    "        else:\n",
    "            print(\"Group {} is rejected\".format(g_indicators[i]))\n",
    "            updated_pdls.append(copy.deepcopy(f))\n",
    "            f.num_rounds += 1\n",
    "            f.track_rejects.append(0)\n",
    "            \n",
    "        i+=1\n",
    "        print(\".....................................................\")\n",
    "    # store our errors for later use\n",
    "    u_test_errors = pd.DataFrame(f.test_errors)\n",
    "    u_test_errors.to_csv(file_name + '.csv')\n",
    "    \n",
    "    u_train_errors = pd.DataFrame(f.train_errors)\n",
    "    \n",
    "    return [u_test_errors, u_train_errors, updated_pdls]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb108d5d",
   "metadata": {},
   "source": [
    "We'd like to shuffle the main groups. The next block does this, and runs the update on the shuffled version. In order to randomize the output, change the value of the random seed in the first line. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0210704f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# change the next line to change the random seed. We use this instead of random.Seed as random.Seed is no longer the\n",
    "# best practice method as the random.seed function affects randomization globally and can mess with imported\n",
    "# packages that use randomness.\n",
    "rng = np.random.default_rng(12345)\n",
    "r_indices = np.arange(len(group_functions))\n",
    "rng.shuffle(r_indices)\n",
    "r_group_functions = [group_functions[i] for i in r_indices]\n",
    "r_models = [models[i] for i in r_indices]\n",
    "r_group_indicators = [group_indicators[i] for i in r_indices]\n",
    "\n",
    "[test_errors, train_errors, pdls] = run_updates(r_group_functions, r_models, r_group_indicators, 'updater-errors-simple')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "372113da",
   "metadata": {},
   "source": [
    "# Visualizing the Group Errors"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a8cbaad",
   "metadata": {},
   "source": [
    "First, we have to clean up our error tables to remove the rows and columns of the updates that were rejected, since we give no monotonicity guarantees for them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "442ab295",
   "metadata": {},
   "outputs": [],
   "source": [
    "# label the dataframe to make easier to read\n",
    "test_errors.columns = ['Total'] + r_group_indicators\n",
    "test_errors.index = ['Total'] + r_group_indicators\n",
    "\n",
    "train_errors.columns = ['Total'] + r_group_indicators\n",
    "train_errors.index = ['Total'] + r_group_indicators\n",
    "\n",
    "test_errors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0464a20e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# identify the rows that have nans\n",
    "row_has_NaN = test_errors.isnull().any(axis=1)\n",
    "\n",
    "ind = []\n",
    "for i in range(len(row_has_NaN)):\n",
    "    if row_has_NaN[i]:\n",
    "        ind.append(i)\n",
    "\n",
    "# drop the columns of updates that correspond to these \n",
    "p_test_errors = test_errors.drop(columns = row_has_NaN.keys()[ind])\n",
    "# drop the rows of updates that correspond to these\n",
    "p_test_errors = p_test_errors.dropna()\n",
    "\n",
    "# identify the rows that have nans\n",
    "row_has_NaN = train_errors.isnull().any(axis=1)\n",
    "\n",
    "ind = []\n",
    "for i in range(len(row_has_NaN)):\n",
    "    if row_has_NaN[i]:\n",
    "        ind.append(i)\n",
    "\n",
    "# drop the columns of updates that correspond to these \n",
    "p_train_errors = train_errors.drop(columns = row_has_NaN.keys()[ind])\n",
    "# drop the rows of updates that correspond to these\n",
    "p_train_errors = p_train_errors.dropna()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18db4a96",
   "metadata": {},
   "source": [
    "## Visualizing the Test Errors\n",
    "\n",
    "These should be monotone, since they are what were used to make the repairs. \n",
    "\n",
    "Since we make no monotonicity guarantees about the updates that were rejected, we remove that data from the data that is to be plotted:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34d2d925",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "fig=plt.figure(figsize=(12,8), dpi= 100, facecolor='w', edgecolor='k') # make plot bigger\n",
    "\n",
    "group_indicators_for_plotting = p_test_errors.columns\n",
    "\n",
    "# plot the errors\n",
    "j=0\n",
    "colors = ['maroon', 'red', 'orange', 'gold', 'yellow',\n",
    "          'chartreuse', 'green', 'blue', 'deepskyblue',\n",
    "          'purple', 'plum',  'pink', 'gray', 'fuchsia', 'black']\n",
    "xs = np.arange(len(group_indicators_for_plotting))\n",
    "for group in group_indicators_for_plotting: #plot all groups\n",
    "    plt.plot(xs[j:],p_test_errors[group][j:].values, label=group, color=colors[j])\n",
    "    plt.plot(xs[:j+1],p_test_errors[group][:j+1].values, linestyle='--', color=colors[j])\n",
    "    j+=1\n",
    "plt.xlabel('Round of update algorithm')\n",
    "plt.ylabel(\"Zero-One Loss on Groups\")\n",
    "plt.legend(prop={'size': 6})\n",
    "plt.title(\"ACS Group Errors Throughout Update Algorithm for Test Data\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45f7b93b",
   "metadata": {},
   "source": [
    "## Visualizing the Training Error"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90c345d4",
   "metadata": {},
   "source": [
    "First we have to determine what the test errors are for each group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b1335f4",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "fig=plt.figure(figsize=(12,8), dpi= 100, facecolor='w', edgecolor='k') # make plot bigger\n",
    "\n",
    "group_indicators_for_plotting = p_train_errors.columns\n",
    "\n",
    "# plot the errors\n",
    "j=0\n",
    "colors = ['maroon', 'red', 'orange', 'gold', 'yellow',\n",
    "          'chartreuse', 'green', 'blue', 'deepskyblue',\n",
    "          'purple', 'plum',  'pink', 'gray', 'fuchsia', 'black']\n",
    "xs = np.arange(len(group_indicators_for_plotting))\n",
    "for group in group_indicators_for_plotting:\n",
    "    plt.plot(xs[j:],p_train_errors[group][j:].values, label=group, color=colors[j])\n",
    "    plt.plot(xs[:j+1],p_train_errors[group][:j+1].values, linestyle='--', color=colors[j])\n",
    "    j+=1\n",
    "plt.xlabel('Round of update algorithm')\n",
    "plt.ylabel(\"Zero-One Loss on Groups\")\n",
    "plt.legend(prop={'size': 6})\n",
    "plt.title(\"AcS Group Errors Throughout Update Algorithm for Training Data\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a843d649",
   "metadata": {},
   "source": [
    "## Visualizing training-test difference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c0abd165",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "fig=plt.figure(figsize=(12,8), dpi= 100, facecolor='w', edgecolor='k') # make plot bigger\n",
    "\n",
    "group_indicators_for_plotting = p_train_errors.columns\n",
    "\n",
    "# plot the errors\n",
    "j=0\n",
    "colors = ['maroon', 'red', 'orange', 'gold', 'yellow',\n",
    "          'chartreuse', 'green', 'blue', 'deepskyblue',\n",
    "          'purple', 'plum',  'pink', 'gray', 'fuchsia', 'black']\n",
    "xs = np.arange(len(group_indicators_for_plotting))\n",
    "for group in group_indicators_for_plotting:\n",
    "    plt.plot(xs[j:],abs(p_test_errors[group][j:].values - p_train_errors[group][j:].values), label=group, color=colors[j])\n",
    "    plt.plot(xs[:j+1],abs(p_test_errors[group][:j+1].values - p_train_errors[group][:j+1].values), linestyle='--', color=colors[j])\n",
    "    j+=1\n",
    "plt.xlabel('Round of update algorithm')\n",
    "plt.ylabel(\"Zero-One Loss on Groups\")\n",
    "plt.legend(prop={'size': 6})\n",
    "plt.title(\"ACS Absolute Difference in Error Between Test and Training Data\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea7f1230",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}