{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/dbamman/anlp25/blob/main/6.tests/Bootstrap.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RQvC3yGQdLJi"
   },
   "source": [
    "This notebook explores the use of the bootstrap to create confidence intervals for any statistic of interest that is estimated from data.  \n",
    "\n",
    "For the classification model that you developed, use the bootstrap to put 95% confidence intervals around your measure of validity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "XAJFQkL4dLJj"
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "from collections import Counter\n",
    "from math import sqrt\n",
    "from random import choices\n",
    "\n",
    "import nltk\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from nltk import word_tokenize\n",
    "from scipy import sparse\n",
    "from scipy.stats import norm\n",
    "from sklearn import linear_model, preprocessing\n",
    "\n",
    "nltk.download(\"punkt\")\n",
    "nltk.download(\"punkttab\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "_lqy7jCXdN1a"
   },
   "outputs": [],
   "source": [
    "# get LMRD data\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/lmrd/train.tsv -O lmrd_train.tsv\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/lmrd/dev.tsv -O lmrd_dev.tsv\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/lmrd/test.tsv -O lmrd_test.tsv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "PL5mixK-dOXY"
   },
   "outputs": [],
   "source": [
    "# get Convote data\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/convote/train.tsv -O convote_train.tsv\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/convote/dev.tsv -O convote_dev.tsv\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/convote/test.tsv -O convote_test.tsv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "BQzthGc9dOnT"
   },
   "outputs": [],
   "source": [
    "# get LoC data\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/loc/train.tsv -O loc_train.tsv\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/loc/dev.tsv -O loc_dev.tsv\n",
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/refs/heads/main/data/loc/test.tsv -O loc_test.tsv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zfJaKQ8odLJk"
   },
   "outputs": [],
   "source": [
    "def read_data(filename):\n",
    "    df = pd.read_csv(filename, names=[\"label\", \"text\"], sep=\"\\t\")\n",
    "    return df.text.to_list(), df.label.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "7ddkB0jXdLJl"
   },
   "outputs": [],
   "source": [
    "# Change this to the directory with the data you will be using.\n",
    "# The directory should contain train.tsv, dev.tsv and test.tsv\n",
    "data = \"convote\"\n",
    "\n",
    "x_train, y_train = read_data(\"%s_train.tsv\" % data)\n",
    "x_dev, y_dev = read_data(\"%s_dev.tsv\" % data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "bnpOAACGdLJl"
   },
   "outputs": [],
   "source": [
    "## HELPER FUNCTIONS ##\n",
    "\n",
    "def build_features(x_train, feature_functions):\n",
    "    data = []\n",
    "    for doc in x_train:\n",
    "        feats = {}\n",
    "        tokens = doc.split(\" \")\n",
    "\n",
    "        for function in feature_functions:\n",
    "            feats.update(function(tokens))\n",
    "\n",
    "        data.append(feats)\n",
    "    return data\n",
    "\n",
    "# This helper function converts a dictionary of feature names to unique numerical ids\n",
    "def create_vocab(data):\n",
    "    feature_vocab = {}\n",
    "    idx = 0\n",
    "    for doc in data:\n",
    "        for feat in doc:\n",
    "            if feat not in feature_vocab:\n",
    "                feature_vocab[feat] = idx\n",
    "                idx += 1\n",
    "\n",
    "    return feature_vocab\n",
    "\n",
    "# This helper function converts a dictionary of feature names to a sparse representation\n",
    "# that we can fit in a scikit-learn model.  This is important because almost all feature\n",
    "# values will be 0 for most documents (note: why?), and we don't want to save them all in\n",
    "# memory.\n",
    "\n",
    "def features_to_ids(data, feature_vocab):\n",
    "    new_data = sparse.lil_matrix((len(data), len(feature_vocab)))\n",
    "    for idx,doc in enumerate(data):\n",
    "        for f in doc:\n",
    "            if f in feature_vocab:\n",
    "                new_data[idx, feature_vocab[f]] = doc[f]\n",
    "    return new_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "lxx3wyf5dLJn"
   },
   "outputs": [],
   "source": [
    "# This function trains a model and returns the predicted and true labels for test data\n",
    "def evaluate(x_train, x_dev, y_train, y_dev, feature_functions):\n",
    "    x_train_feat = build_features(x_train, feature_functions)\n",
    "    x_dev_feat = build_features(x_dev, feature_functions)\n",
    "\n",
    "    # just create vocabulary from features in *training* data\n",
    "    feature_vocab = create_vocab(x_train_feat)\n",
    "\n",
    "    x_train_ids = features_to_ids(x_train_feat, feature_vocab)\n",
    "    x_dev_ids = features_to_ids(x_dev_feat, feature_vocab)\n",
    "\n",
    "    label_encoder = preprocessing.LabelEncoder()\n",
    "    label_encoder.fit(y_train)\n",
    "\n",
    "    y_train = label_encoder.transform(y_train)\n",
    "    y_dev = label_encoder.transform(y_dev)\n",
    "\n",
    "    logreg = linear_model.LogisticRegression(C=1.0, solver='lbfgs', penalty='l2', max_iter=10000)\n",
    "    logreg.fit(x_train_ids, y_train)\n",
    "    predictions = logreg.predict(x_dev_ids)\n",
    "    return (predictions, y_dev)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Metrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "baFlMaGOdLJn"
   },
   "outputs": [],
   "source": [
    "def accuracy(targets, predictions):\n",
    "    correct = [\n",
    "        int(pred == target) for pred, target in zip(predictions, targets)\n",
    "    ]\n",
    "    \n",
    "    return sum(correct) / len(correct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "x9V63ujidLJo"
   },
   "outputs": [],
   "source": [
    "def F1(targets, predictions):\n",
    "\n",
    "    true_positives = 0\n",
    "    pred_positives = 0\n",
    "    relevant = 0\n",
    "    \n",
    "    for pred, target in zip(predictions, targets):\n",
    "        if pred == 1 and pred == target:\n",
    "            true_positives += 1\n",
    "        if target == 1:\n",
    "            relevant += 1\n",
    "        if pred == 1:\n",
    "            pred_positives += 1\n",
    "\n",
    "    precision = true_positives / pred_positives if pred_positives > 0 else 0\n",
    "    recall = true_positives / relevant if relevant > 0 else 0\n",
    "    f = (2 * precision * recall) / (precision + recall) if (precision + recall) > 0 else 0\n",
    "    return f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "PObtCqvpdLJo"
   },
   "source": [
    "Specify features for model and train logistic regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here's a sample dictionary we can create by inspecting the output of the Mann-Whitney test (in 2.compare/)\n",
    "\n",
    "# EDIT TO FIT YOUR DATASET\n",
    "dem_dictionary = set([\"republican\",\"cut\", \"opposition\"])\n",
    "repub_dictionary = set([\"growth\",\"economy\"])\n",
    "\n",
    "def political_dictionary_feature(tokens):\n",
    "    feats = {}\n",
    "    for word in tokens:\n",
    "        if word in dem_dictionary:\n",
    "            feats[\"word_in_dem_dictionary\"] = 1\n",
    "        if word in repub_dictionary:\n",
    "            feats[\"word_in_repub_dictionary\"] = 1\n",
    "    return feats\n",
    "\n",
    "def unigram_feature(tokens):\n",
    "    feats = {}\n",
    "    for word in tokens:\n",
    "        feats[\"UNIGRAM_%s\" % word] = 1\n",
    "    return feats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "9EQ8fHVqdLJo"
   },
   "outputs": [],
   "source": [
    "features = [political_dictionary_feature]\n",
    "predictions, targets = evaluate(x_train, x_dev, y_train, y_dev, features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "yVT5EBLCdLJo"
   },
   "source": [
    "First, let's just see what parametric confidence intervals are for accuracy (for which the underlying assumptions of normality are justified by the CLT)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ShiKUFgldLJn"
   },
   "outputs": [],
   "source": [
    "def binomial_cis(predictions, targets, confidence_level=0.95):\n",
    "    correct = [int(prediction == target) for prediction, target in zip(predictions, targets)]\n",
    "\n",
    "    success_rate = np.mean(correct)\n",
    "\n",
    "    # two-tailed test\n",
    "    critical_value = (1 - confidence_level) / 2\n",
    "    # ppf finds z such that p(X < z) = critical_value\n",
    "    z_alpha = -1 * norm.ppf(critical_value)\n",
    "    print(\"Critical value: %.3f\\tz_alpha: %.3f\" % (critical_value, z_alpha))\n",
    "\n",
    "    # the standard error is the square root of (the variance/sample size)\n",
    "    # the variance for a binomial test is p*(1-p)\n",
    "    standard_error = sqrt((success_rate * (1-success_rate)) / len(correct))\n",
    "\n",
    "    lower = success_rate - z_alpha * standard_error\n",
    "    upper = success_rate + z_alpha * standard_error\n",
    "\n",
    "    return lower, upper\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "AgY0tjRndLJp"
   },
   "outputs": [],
   "source": [
    "binomial_cis(predictions, targets, confidence_level=0.95)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "JVXrqOACdLJp"
   },
   "source": [
    "Here we'll use the bootstrap to create confidence intervals at a specified confidence level for any function `metric(truth, predictions)` where *truth* is an array of true labels for a set of data points, and *predictions* is an array of predicted labels for those same points.  This `bootstrap` function returns a tuple of (lower, median, upper), where *lower* is the lower confidence bound, *upper* is the upper confidence bound, and *median* is the median value of the metric among the bootstrap resamples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "aAwyCsLPdLJp"
   },
   "outputs": [],
   "source": [
    "def bootstrap(predictions, targets, metric, B=10000, confidence_level=0.95):\n",
    "    critical_value = (1 - confidence_level) / 2\n",
    "    lower_sig = 100 * critical_value\n",
    "    upper_sig = 100 * (1 - critical_value)\n",
    "    data = []\n",
    "    for g, p in zip(targets, predictions):\n",
    "        data.append([g, p])\n",
    "\n",
    "    values = []\n",
    "\n",
    "    for b in range(B):\n",
    "        choice = choices(data, k=len(data))\n",
    "        choice = np.array(choice)\n",
    "        value = metric(choice[:,0], choice[:,1])\n",
    "\n",
    "        values.append(value)\n",
    "\n",
    "    percentiles = np.percentile(values, [lower_sig, 50, upper_sig])\n",
    "\n",
    "    lower = percentiles[0]\n",
    "    median = percentiles[1]\n",
    "    upper = percentiles[2]\n",
    "\n",
    "    return lower, median, upper\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "s7-2ZEA2dLJp"
   },
   "source": [
    "We can use that bootstrap implementation to generate confidence intervals for accuracy and F1 score for the predictions made above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "i3Z1-TXDdLJp"
   },
   "outputs": [],
   "source": [
    "confidence_level = 0.95\n",
    "lower, median, upper = bootstrap(targets, predictions, accuracy, B=10000, confidence_level=confidence_level)\n",
    "print(\"%.3f, %s%% Bootstrap confidence interval: [%.3f, %.3f]\" % (median, confidence_level*100, lower, upper))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "l7u49S6qdLJp"
   },
   "outputs": [],
   "source": [
    "confidence_level=0.95\n",
    "lower, median,upper = bootstrap(targets, predictions, F1, B=10000,confidence_level=confidence_level)\n",
    "print(\"%.3f, %s%% Bootstrap confidence interval: [%.3f, %.3f]\" % (median, confidence_level*100, lower, upper))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "79xi0lqldLJq"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}