examples/map_inference.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ADAG solver\n",
    "\n",
    "MANET comes with implementation of ADAG algorithm which solves the MAP inference of a generix Markov Network. The ADAG algorihm solves a discrete optimization (so called max-sum) problem \n",
    "$$\n",
    "    \\hat{\\mathbf{y}} \\in arg\\max_{\\mathbf{y}\\in\\cal{Y}^{\\cal{V}}}\\left ( \\sum_{v\\in\\cal{V}} q_v(y_v)+ \\sum_{v,v'\\in\\cal{E}} g_{idx(v,v')}(y_v,y_{v'})\\right ) \n",
    "$$\n",
    "where $\\cal{V}=\\{0,\\ldots,n_V-1\\}$ is a set of objects, $\\cal{E}\\subset \\left ( \\cal{V}\\atop 2\\right )$ a set of interacting objects and $\\cal{Y}=\\{0,1,\\ldots,n_Y-1\\}$ a set of labels. The unary scores $q_v\\colon\\cal{Y}\\rightarrow\\Re$ are represented by NP array $Q [n_Y \\times n_V]$. The pair-wise scores $g_i\\colon\\cal{Y}\\times\\cal{Y}\\rightarrow\\Re$, $i=1,\\ldots,n_G$, are represented by NP array $G [n_Y \\times n_Y \\times n_G]$, where $n_G$ is the number of different score functions (e.g. in case of homogeneous MN all edges have the same score and $n_g=0$). The edges are represented by NP array $E [3 \\times |\\cal{E}|]$ where column $E(:,e)=(v,v',idx(e))$ defines edge $e =(v,v')$ conecting objects $v$ and $v'$ and it assignes the $idx(e)$-th pair-wise score function $g_{idx(e)}$ to that edge. The solver returns the maximizing labels $\\hat{\\mathbf{y}}$ and the value of the objective evaluated at $\\hat{\\mathbf{y}}$. The ADAG algorithm allows the undirected graph $(\\cal{V},\\cal{E})$, defining the label interactions, to be arbitrary. \n",
    "\n",
    "The ADAG solver has the following syntax:\n",
    "```\n",
    "labels, energy = adag( Q, G, E )\n",
    "\n",
    "Inputs:\n",
    "    Q [nY x nV] unary functions\n",
    "    G [nY x nY x nG ] pair functions\n",
    "    E [3 x nE] edges between objects\n",
    "Returns:\n",
    "    labels [nV] maximal labelling\n",
    "    energy [float]\n",
    "```\n",
    "\n",
    "In case, the graph $(\\cal{V},\\cal{E})$ is a chain, the MAP inference can be solved efficiently by Viterbi algorihtm which has the following syntax:\n",
    "```\n",
    "label, energy = viterbi( Q, G )\n",
    "\n",
    "Inputs:\n",
    "    Q [nY x nV] unary functions\n",
    "    G [(nV-1) x nK x nK] pair functions\n",
    "Returns:\n",
    "    labels [nV] maximal labelling \n",
    "    energy [float] \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simple example of MAP inference on a chain\n",
    "\n",
    "Assume the following MAP problem on a chain connecting 3 objects:\n",
    "$$\n",
    "   (\\hat{y}_0,\\hat{y_1},\\hat{y_2}) \\in arg\\max_{(y_0,y_1,y_2)\\in\\{0,1\\}^{\\{0,1,2\\}}} \\left ( q_0(y_0) + q_1(y_1) + q_2(y_2)+ g(y_0,y_1) + g(y_1,y_2) \\right )\n",
    "$$\n",
    "where with the unary scores\n",
    "$$\n",
    "q_0(0) = 3, q_0(1)=-1, q_1(0)=2, q_1(1)=2, q_2(0)=2, q_2(1)=0\n",
    "$$\n",
    "and pair-wise score\n",
    "$$\n",
    "   g(0,0) = -1, g(1,0)=2, g(1,1)=4, g(1,1)=-2\n",
    "$$\n",
    "The MAP inference can be solved by Viterbi algorithm or the ADAG solver as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "energy=13.000000100000003\n",
      "[0 1 0]\n",
      "energy=13.0\n",
      "[0 1 0]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from manet.maxsum import adag\n",
    "from manet.maxsum import viterbi\n",
    "\n",
    "Q = np.array([[3, 2, 2], [-1,2,0]])\n",
    "G = np.array( [[-1,4],[2,-2]] )\n",
    "E = np.array( [[0,1],[1,2],[0,0]] )\n",
    "\n",
    "labels, energy = adag( Q, G, E )\n",
    "print(f\"energy={energy}\")\n",
    "print( labels )\n",
    "\n",
    "labels, energy = viterbi( Q, G)\n",
    "print(f\"energy={energy}\")\n",
    "print( labels )\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sudoku solver\n",
    "\n",
    "Solving Sudoku puzzle can be formulated as MAP inference in appropriately constructed Markov Network which looks as follows:\n",
    "$$\n",
    "    \\hat{\\mathbf{y}} \\in arg\\max_{\\mathbf{y}\\in\\cal{Y}^{\\cal{V}}}\\left ( \\sum_{v\\in\\cal{V}} q(x_vy_v)+ \\sum_{v,v'\\in\\cal{E}} g(y_v,y_{v'})\\right )\n",
    "$$\n",
    "where $\\cal{V}=\\{ (i,j)\\in\\cal{N}^2\\mid 1\\leq i \\leq 9, 1\\leq j \\leq 9 \\}$ cells of $9\\times 9$ grid, $\\mathbf{x}=(x_v\\in \\{?,1,\\ldots,9\\} \\mid v\\in\\cal{V})$ is the puzzle assignment, $\\mathbf{y}=(y_v\\in \\{1,\\ldots,9\\} \\mid v\\in\\cal{V})$ the puzzle solution, $\\cal{E}$ are edges connecting all cells in each columns, each row, and each $3\\times 3$ subgrid and the unary scores $q\\colon\\{?,1,\\ldots,9\\}\\rightarrow\\{0,-1\\}$ are\n",
    "$$\n",
    "   q(x,y) = \\left \\{ \\begin{array}{rl} \n",
    "    -1 & if\\; x \\neq ? \\land y\\neq x\\\\\n",
    "    0 & otherwise\n",
    "   \\end{array} \\right .\n",
    "$$\n",
    "and the pair-wise scores $g\\colon\\{1,\\ldots,9\\}\\times\\{1,\\ldots,9\\}\\rightarrow\\{0,-1\\}$ are\n",
    "$$\n",
    "   g(y,y') = \\left \\{ \n",
    "    \\begin{array}{rl}\n",
    "      0 & if\\; y\\neq y' \\\\\n",
    "      -1 & if \\; y = y'\n",
    "    \\end{array}\n",
    "    \\right . \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load Sudoku assignments and solutions from a CSV file. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 4 3 0 0 2 0 9]\n",
      " [0 0 5 0 0 9 0 0 1]\n",
      " [0 7 0 0 6 0 0 4 3]\n",
      " [0 0 6 0 0 2 0 8 7]\n",
      " [1 9 0 0 0 7 4 0 0]\n",
      " [0 5 0 0 8 3 0 0 0]\n",
      " [6 0 0 0 0 0 1 0 5]\n",
      " [0 0 3 5 0 8 6 9 0]\n",
      " [0 4 2 9 1 0 3 0 0]]\n",
      "[[8 6 4 3 7 1 2 5 9]\n",
      " [3 2 5 8 4 9 7 6 1]\n",
      " [9 7 1 2 6 5 8 4 3]\n",
      " [4 3 6 1 9 2 5 8 7]\n",
      " [1 9 8 6 5 7 4 3 2]\n",
      " [2 5 7 4 8 3 9 1 6]\n",
      " [6 8 9 7 3 4 1 2 5]\n",
      " [7 1 3 5 2 8 6 9 4]\n",
      " [5 4 2 9 1 6 3 7 8]]\n"
     ]
    }
   ],
   "source": [
    "import csv\n",
    "import numpy as np\n",
    "\n",
    "with open('ecml2022/data/sudoku10000.csv', newline='') as csvfile:\n",
    "    reader = csv.DictReader(csvfile)\n",
    "    sudoku = []\n",
    "    cnt = 0\n",
    "    for row in reader:\n",
    "        assignment = np.array([char for char in row['quizzes']]).astype(int).reshape(9,9)\n",
    "        solution = np.array([char for char in row['solutions']]).astype(int).reshape(9,9)\n",
    "        sudoku.append( {'assignment': assignment, 'solution': solution} )\n",
    "        if cnt == 10:\n",
    "            break\n",
    "\n",
    "print(sudoku[0]['assignment'])\n",
    "print(sudoku[0]['solution'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translate Sudoku puzzle into MAP inference in Markov Network, i.e. define unary scores, pair-wise scores and edges of the Markov Network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import ceil\n",
    "\n",
    "def sudoku_to_mnet( sudoku ):\n",
    "    K = 1\n",
    "    Q = -K*np.ones([9,9*9] )\n",
    "    obj = 0\n",
    "    for row in range(0,9):\n",
    "        for col in range(0,9):\n",
    "            symbol = sudoku[row,col]\n",
    "            if symbol == 0:\n",
    "                Q[:,obj] = 0\n",
    "            else:\n",
    "                Q[symbol-1,obj] = 0\n",
    "            obj += 1\n",
    "\n",
    "    G = -K*np.identity( 9 )\n",
    "    E = []\n",
    "    for i1 in range(1,10):\n",
    "        for j1 in range(1,10):\n",
    "            for i2 in range(1,10):\n",
    "                for j2 in range(1,10):\n",
    "                    if i1==i2 or j1==j2 or (ceil(i1/3)==ceil(i2/3) and ceil(j1/3)==ceil(j2/3)):\n",
    "                        v0 = i1 + (j1-1)*9 - 1\n",
    "                        v1 = i2 + (j2-1)*9 - 1\n",
    "                        if v0 != v1 and ([v0,v1] not in E) and ([v1,v0] not in E):\n",
    "                            E.append([v0,v1])\n",
    "    E = np.concatenate( (np.array(E).transpose(), np.zeros((1,len(E)),dtype=int)) ,axis=0 )\n",
    "\n",
    "    return Q, G, E"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Call ADAG algorithm on Sudoku puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "energy: 0.0\n",
      "[[0 0 4 3 0 0 2 0 9]\n",
      " [0 0 5 0 0 9 0 0 1]\n",
      " [0 7 0 0 6 0 0 4 3]\n",
      " [0 0 6 0 0 2 0 8 7]\n",
      " [1 9 0 0 0 7 4 0 0]\n",
      " [0 5 0 0 8 3 0 0 0]\n",
      " [6 0 0 0 0 0 1 0 5]\n",
      " [0 0 3 5 0 8 6 9 0]\n",
      " [0 4 2 9 1 0 3 0 0]]\n",
      "[[8 6 4 3 7 1 2 5 9]\n",
      " [3 2 5 8 4 9 7 6 1]\n",
      " [9 7 1 2 6 5 8 4 3]\n",
      " [4 3 6 1 9 2 5 8 7]\n",
      " [1 9 8 6 5 7 4 3 2]\n",
      " [2 5 7 4 8 3 9 1 6]\n",
      " [6 8 9 7 3 4 1 2 5]\n",
      " [7 1 3 5 2 8 6 9 4]\n",
      " [5 4 2 9 1 6 3 7 8]]\n",
      "[[0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0]]\n"
     ]
    }
   ],
   "source": [
    "from manet.maxsum import adag\n",
    "\n",
    "# take i-th puzzle\n",
    "i = 0\n",
    "assignment = sudoku[i]['assignment']\n",
    "correct_solution = sudoku[i]['solution']\n",
    "\n",
    "# call ADAG solver\n",
    "Q, G, E = sudoku_to_mnet( assignment )\n",
    "\n",
    "solution, energy = adag( Q, G, E )\n",
    "solution = solution.reshape(9,9)+1\n",
    "\n",
    "# assignment, solution and (possible) errors\n",
    "print( \"energy:\", energy )\n",
    "print( assignment)\n",
    "print( solution )\n",
    "print( solution - correct_solution )"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.8 ('manet')",
   "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.10.8"
  },
  "vscode": {
   "interpreter": {
    "hash": "34eb675ba1599e41a978d852241fe8b4873ed3c3e59b32810c909d7852b5516c"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}