postprocess_drift_cliques.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "70a2ec6d",
   "metadata": {},
   "source": [
    "# reviewing theorem 3\n",
    "\n",
    "- $C$: number of cases\n",
    "- $\\epsilon$: fraction of cases\n",
    "- $k$: the size of a set of *any* individuals in the population such that there are at least 2 individuals that differ on $\\epsilon C$ cases\n",
    "    - smaller $k$ makes this harder to achieve\n",
    "    - larger $\\epsilon$ makes this harder to achieve\n",
    "\n",
    "empirical question:\n",
    "- what is the smallest $k$, and largest $\\epsilon$, that satisfies these constraints?\n",
    "\n",
    "## approach\n",
    "\n",
    "- load pop error matrix, B\n",
    "- set $\\epsilon$ to some value\n",
    "\n",
    "- make NxN adjacency matrix where i,j indicates whether $n_i$ and $n_j$ differ on less than $\\epsilon$C cases\n",
    "- calculate the maximum clique of this matrix, whose size equals $k$ "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1709bbf0",
   "metadata": {},
   "source": [
    "# todo\n",
    "\n",
    "- compare empirical # evals for these runs to new estimate/bound of running time \n",
    "- look at larger values of epsilon (up to .6?)\n",
    "- look at diversity (via covariance) on filtered error vectors instead of # unique in original matrix\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa9818ce",
   "metadata": {},
   "source": [
    "**done**\n",
    "- compare behavioral diversity to values of k, epsilon\n",
    "    - calculate mean proportion of unique error vectors each gen\n",
    "- calculate best epsilon per generation? \n",
    "    - look at runtime fraction with optimal epsilon?\n",
    "    - what is the best runtime fraction using optimal epsilon, over generations?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56fd25e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import matplotlib\n",
    "matplotlib.rcParams['pdf.fonttype'] = 42\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "sns.set_context('paper', font_scale=1.5)\n",
    "sns.set_style('whitegrid')\n",
    "import os\n",
    "import pypdftk\n",
    "\n",
    "figdir = 'figs/'\n",
    "os.makedirs(figdir, exist_ok=True)\n",
    "\n",
    "def save(h,name, **kwargs):\n",
    "    h.tight_layout()\n",
    "    for ft in ['.png','.pdf']:\n",
    "        h.savefig(figdir+'/'+name+ft, dpi=200, **kwargs)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12b80c23",
   "metadata": {},
   "source": [
    "# load saved data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3235970c",
   "metadata": {},
   "outputs": [],
   "source": [
    "rootdir = 'data/lex-theory-'\n",
    "# popsize = '250'\n",
    "# problem = 'mirror-image'\n",
    "problems = [\n",
    "            ('compare-string-lengths',True,),\n",
    "            ('count-odds',False),\n",
    "            ('double-letters',False),\n",
    "            ('last-index-of-zero',False),\n",
    "            ('mirror-image',True),\n",
    "            ('negative-to-zero',False),\n",
    "                ('x-word-lines', False),\n",
    "            ('vector-average', False)\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41e2f26e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from glob import glob\n",
    "res = []\n",
    "for problem,_ in problems:\n",
    "    print(rootdir+problem)\n",
    "    for f in glob(rootdir+problem+'/runtime_stats-*.csv'):\n",
    "        df = pd.read_csv(f) \n",
    "        if len(df)==0:\n",
    "            print('!!!!',problem,'sucks')\n",
    "            continue\n",
    "        df['problem'] = problem\n",
    "        df['eps'] = df['eps'].round(2)\n",
    "        if len(res)==0:\n",
    "            res = df\n",
    "        else:\n",
    "            res = res.append(df)\n",
    "\n",
    "res.groupby('problem').describe().transpose().iloc[:120]\n",
    "\n",
    "# clean up var names\n",
    "runtime_fraction = 'Running Time Fraction'\n",
    "clean = {\n",
    "    'runtime fraction': runtime_fraction\n",
    "}\n",
    "res = res.rename(columns=clean)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e60eb699",
   "metadata": {},
   "outputs": [],
   "source": [
    "runtime_fraction = 'Running Time Fraction'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c454b79d",
   "metadata": {},
   "outputs": [],
   "source": [
    "res.loc[res.eps==res.best_eps].groupby('problem')[runtime_fraction].mean().mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e855aa0",
   "metadata": {},
   "outputs": [],
   "source": [
    "res.loc[res.eps==res.best_eps].groupby('problem')['best_eps'].mean().mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b37bac0",
   "metadata": {},
   "outputs": [],
   "source": [
    "g =sns.relplot(kind='line',\n",
    "            data=res.loc[res.eps==res.best_eps,:],\n",
    "            x='g',\n",
    "            y=runtime_fraction,\n",
    "#             hue='eps',\n",
    "            col='problem',\n",
    "            col_wrap=4,\n",
    "            facet_kws=dict(sharex=False, legend_out=False),\n",
    "           )\n",
    "sns.set(font_scale=1.7, style='whitegrid')\n",
    "g.set_titles('{col_name}')\n",
    "g.set_xlabels('generations')\n",
    "save(plt.gcf(), 'gens_vs_runtime-fraction_best-eps_by_problem')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0990e2f",
   "metadata": {},
   "source": [
    "## comparison of new diversity metric to mean covariance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e590226c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# smart sample\n",
    "dfplt = pd.DataFrame()\n",
    "i = 0\n",
    "n = 1000\n",
    "for p in res.problem.unique():\n",
    "    sample = res.loc[res.problem==p,:].sample(n)\n",
    "    if i == 0:\n",
    "        dfplt = sample\n",
    "    else:\n",
    "        dfplt = dfplt.append(sample)\n",
    "    i+=1\n",
    "    \n",
    "g=sns.relplot(\n",
    "    kind='scatter',\n",
    "#     data=res.sample(100000),\n",
    "#     data=res.sample(10000),\n",
    "    data=dfplt,\n",
    "    col_order=res.problem.unique(),\n",
    "    y='mean_cov',\n",
    "    x='k%',\n",
    "    hue='eps',\n",
    "    col='problem',\n",
    "    col_wrap=4,\n",
    "    facet_kws=dict(sharey=False)#, legend_out=False),\n",
    "#     legend=False\n",
    ")\n",
    "sns.set(font_scale=1.7, style='whitegrid')\n",
    "g.set_titles('{col_name}')\n",
    "g.set_xlabels('$\\epsilon$-Cluster Similarity (% of N)')\n",
    "g.set_ylabels('Mean Phenotype Covariance')\n",
    "# sns.move_legend(g, \"upper right\")\n",
    "# g.add_legend(facecolor='w')\n",
    "# g.add_legend()\n",
    "# frame = g.legend.get_frame()\n",
    "# frame.set_facecolor('w')\n",
    "\n",
    "save(plt.gcf(), 'k-pct_vs_mean-cov_hue-eps-sampled')\n",
    "# save(plt.gcf(), 'k-pct_vs_mean-cov_hue-eps-sampled', rasterized=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e1ee854",
   "metadata": {},
   "outputs": [],
   "source": [
    "# smart sample\n",
    "dfplt = pd.DataFrame()\n",
    "i = 0\n",
    "n = 1000\n",
    "for p in res.problem.unique():\n",
    "    sample = res.loc[res.problem==p,:].sample(n)\n",
    "    if i == 0:\n",
    "        dfplt = sample\n",
    "    else:\n",
    "        dfplt = dfplt.append(sample)\n",
    "    i+=1\n",
    "        \n",
    "g=sns.displot(\n",
    "#     kind='hist',\n",
    "    kind='hist',\n",
    "    data=dfplt,\n",
    "#     data=res,\n",
    "#     data=res.sample(1000),\n",
    "    col_order=res.problem.unique(),\n",
    "    y='mean_cov',\n",
    "    x='k%',\n",
    "#     hue='eps',\n",
    "    col='problem',\n",
    "    col_wrap=4,\n",
    "    facet_kws=dict(sharey=False, legend_out=False),\n",
    "#     legend=False\n",
    "#     sharey=False,\n",
    "    discrete=(False,False),\n",
    "    bins=20\n",
    ")\n",
    "sns.set(font_scale=1.7, style='whitegrid')\n",
    "g.set_titles('{col_name}')\n",
    "g.set_xlabels('$\\epsilon$-Cluster Similarity (% of N)')\n",
    "g.set_ylabels('Mean Phenotype Covariance')\n",
    "# sns.move_legend(g, \"upper right\")\n",
    "# g.add_legend(facecolor='w')\n",
    "# g.add_legend()\n",
    "# frame = g.legend.get_frame()\n",
    "# frame.set_facecolor('w')\n",
    "\n",
    "# save(plt.gcf(), 'k-pct_vs_mean-cov_hue-eps-lineplot-sampled')\n",
    "# save(plt.gcf(), 'k-pct_vs_mean-cov_hue-eps-sampled', rasterized=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5b2715a",
   "metadata": {},
   "source": [
    "## break down of components of running time bound by value of epsilon"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "398c8c80",
   "metadata": {},
   "source": [
    "- count-odds, double-letters pretty flat but higher epsilon possible\n",
    "\n",
    "TODO:\n",
    "\n",
    "- [x] plot separate runtime bounds terms (epsilon term, k term)\n",
    "- [x] 4n/epsilon + 2kC (divided by worst case)\n",
    "- [x] annotate with which term is dominating"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5addd95",
   "metadata": {},
   "outputs": [],
   "source": [
    "res.columns\n",
    "\n",
    "res['$2k|C|$'] = (2*res['k']*res['N*C']/res['N'])/res['N*C']\n",
    "res['$4N/\\epsilon$'] = (4*res['N']/res['eps'])/res['N*C']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cb269844",
   "metadata": {},
   "outputs": [],
   "source": [
    "df_plt = res.rename(columns={runtime_fraction:'total'})\n",
    "sns.set(font_scale=1, style='whitegrid')\n",
    "\n",
    "g = sns.FacetGrid(\n",
    "    data=df_plt,\n",
    "    col='problem',\n",
    "    col_wrap=4,\n",
    "#     sharey=False,\n",
    "    sharey=True,\n",
    "    sharex=True,\n",
    "    legend_out=True\n",
    ")\n",
    "stride=2\n",
    "xticks = np.arange(res.eps.nunique())[::stride]\n",
    "xticklabels = [str(i) for i in res.eps.unique()[::stride]]\n",
    "np.linspace(0,12,25)\n",
    "\n",
    "lines = [('$2k|C|$','r'),('$4N/\\epsilon$','orange'),('total','b')]\n",
    "\n",
    "for y,c in lines:\n",
    "    (g.map_dataframe(sns.pointplot,\n",
    "                    x='eps',\n",
    "                    y=y,\n",
    "                    color=c,\n",
    "                   )\n",
    "    )\n",
    "    \n",
    "\n",
    "g.add_legend()\n",
    "g.set_titles('{col_name}')\n",
    "# g.set_style('whitegrid')\n",
    "    \n",
    "i=0\n",
    "for ax in g.axes.flat:\n",
    "    print(ax.get_label())\n",
    "    ax.set_xticks(xticks)\n",
    "    ax.set_xticklabels(xticklabels, fontsize=10)\n",
    "    if i>2:\n",
    "        ax.set_xlabel('$\\epsilon$')\n",
    "    if ax.is_first_col():\n",
    "        ax.set_ylabel(runtime_fraction)\n",
    "    ax.set_title(ax.get_title().replace('problem = ',''))\n",
    "#     if i == 0:\n",
    "#         ax.legend(['a','b','c'])\n",
    "    i+=1\n",
    "    \n",
    "from matplotlib.lines import Line2D\n",
    "cmap = plt.cm.coolwarm\n",
    "custom_lines, labels = [],[]\n",
    "for y, c in lines:\n",
    "    custom_lines.append(Line2D([0], [0], color=c, lw=4))\n",
    "    labels.append(y)\n",
    "\n",
    "g.axes[0].legend(custom_lines, labels)\n",
    "\n",
    "save(plt.gcf(), 'eps_running-time-portions')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "061da0fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "sns.relplot(kind='line',\n",
    "            data=res,\n",
    "            x='g',\n",
    "            y='best_eps',\n",
    "            hue='problem',\n",
    "            marker='',\n",
    "            facet_kws=dict(sharey=False, legend_out=False),\n",
    "           )\n",
    "save(plt.gcf(), 'gens_vs_best-eps_hue-problem')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d1abe3b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "sns.relplot(\n",
    "    kind='scatter',\n",
    "    data=res,\n",
    "    y='clique time',\n",
    "    x='eps',\n",
    "    hue='k',\n",
    "    col='problem',\n",
    "    col_wrap=4\n",
    ")\n",
    "g.set_titles('{col_name}')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddaebabc",
   "metadata": {},
   "source": [
    "## load empirical nevals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f5866a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "nevals = pd.read_parquet('data/empirical_num_evals.parquet')\n",
    "nevals['g'] = nevals['generation'].astype(int) \n",
    "nevals = nevals.loc[nevals.N==1000]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3770c7c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "nevals.dtypes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "45af55fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = res[['problem','g','runtime bound','trial']]\n",
    "df['source'] = 'theory'\n",
    "df = df.rename(columns={'runtime bound':'n_evals'})\n",
    "\n",
    "\n",
    "df_worst = res[['problem','g','N*C','trial']]\n",
    "df_worst['source'] = 'worst case'\n",
    "df_worst = df_worst.rename(columns={'N*C':'n_evals'})\n",
    "nevals['source'] = 'data'\n",
    "combo = pd.concat((df, df_worst, nevals[['problem','trial','g','n_evals','source']]))\n",
    "# combo = combo.rename()\n",
    "combo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5093660f",
   "metadata": {},
   "outputs": [],
   "source": [
    "sns.set_style('whitegrid')\n",
    "g = sns.relplot(\n",
    "    kind='line',\n",
    "    data=combo,\n",
    "    x='g',\n",
    "    y='n_evals',\n",
    "    hue='source',\n",
    "    col='problem',\n",
    "    col_wrap=4, \n",
    "    facet_kws=dict(sharex=False, legend_out=False),\n",
    ")\n",
    "g.set_titles('{col_name}')\n",
    "g.set(yscale='log')\n",
    "g.set(ylabel='# of Evals per Selection Event')\n",
    "\n",
    "save(plt.gcf(), 'num_evals_comparison')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b59da45e",
   "metadata": {},
   "source": [
    "## plot k over generations, colored by epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0512c1f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "sns.relplot(kind='line',\n",
    "            data=res,\n",
    "            x='g',\n",
    "            y='k%',\n",
    "            hue='eps',\n",
    "            col='problem',\n",
    "            col_wrap=4,\n",
    "#             share_x=False\n",
    "            facet_kws={'sharex':False}\n",
    "           )\n",
    "plt.ylabel('k (% Population Size)')\n",
    "save(plt.gcf(), 'gens_vs_k-pct_by_problem')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9274e2cd",
   "metadata": {},
   "source": [
    "## plot runtime over generations, colored by epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c27eefe3",
   "metadata": {},
   "outputs": [],
   "source": [
    "sns.relplot(kind='line',\n",
    "            data=res,\n",
    "            x='g',\n",
    "            y=runtime_fraction,\n",
    "            hue='eps',\n",
    "            col='problem',\n",
    "            col_wrap=4,\n",
    "            facet_kws={'sharex':False}\n",
    "           )\n",
    "save(plt.gcf(), 'gens_vs_runtime-fraction_hue-eps_by_problem')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "058acac1",
   "metadata": {},
   "source": [
    "# runtime fraction for different values of epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "233f67de",
   "metadata": {},
   "outputs": [],
   "source": [
    "# plt.plot(res.eps, res['runtime fraction'], '.')\n",
    "sns.pointplot(data=res.round(2),\n",
    "              x='eps',\n",
    "              y=runtime_fraction,\n",
    "              markers=''\n",
    "             )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e374866",
   "metadata": {},
   "source": [
    "# k for different values of epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b89747df",
   "metadata": {},
   "outputs": [],
   "source": [
    "sns.catplot(kind='point',\n",
    "            data=res.round(2),\n",
    "            x='eps',\n",
    "            y='k',\n",
    "            markers='',\n",
    "#             ax=ax,\n",
    "            col='problem',\n",
    "            col_wrap=3\n",
    "            )\n"
   ]
  }
 ],
 "metadata": {
  "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}