microsoft/AI-For-Beginners
Publicmirrored fromhttps://github.com/microsoft/AI-For-BeginnersAvailable
lessons/2-Symbolic/Animals.ipynb
463lines · modecode
| 1 | { |
| 2 | "cells": [ |
| 3 | { |
| 4 | "cell_type": "markdown", |
| 5 | "metadata": { |
| 6 | "collapsed": true |
| 7 | }, |
| 8 | "source": [ |
| 9 | "# Implementing an Animal Expert System\n", |
| 10 | "\n", |
| 11 | "An example from [AI for Beginners Curriculum](http://github.com/microsoft/ai-for-beginners).\n", |
| 12 | "\n", |
| 13 | "In this sample, we will implement a simple knowledge-based system to determine an animal based on some physical characteristics. The system can be represented by the following AND-OR tree (this is a part of the whole tree, we can easily add some more rules):\n", |
| 14 | "\n", |
| 15 | "" |
| 16 | ] |
| 17 | }, |
| 18 | { |
| 19 | "cell_type": "markdown", |
| 20 | "metadata": {}, |
| 21 | "source": [ |
| 22 | "## Our own expert systems shell with backward inference\n", |
| 23 | "\n", |
| 24 | "Let's try to define a simple language for knowledge representation based on production rules. We will use Python classes as keywords to define rules. There would be essentially 3 types of classes:\n", |
| 25 | "* `Ask` represents a question that needs to be asked to the user. It contains the set of possible answers.\n", |
| 26 | "* `If` represents a rule, and it is just a syntactic sugar to store the content of the rule\n", |
| 27 | "* `AND`/`OR` are classes to represent AND/OR branches of the tree. They just store the list of arguments inside. To simplify code, all functionality is defined in the parent class `Content`" |
| 28 | ] |
| 29 | }, |
| 30 | { |
| 31 | "cell_type": "code", |
| 32 | "execution_count": 11, |
| 33 | "metadata": { |
| 34 | "trusted": true |
| 35 | }, |
| 36 | "outputs": [], |
| 37 | "source": [ |
| 38 | "class Ask():\n", |
| 39 | " def __init__(self,choices=['y','n']):\n", |
| 40 | " self.choices = choices\n", |
| 41 | " def ask(self):\n", |
| 42 | " if max([len(x) for x in self.choices])>1:\n", |
| 43 | " for i,x in enumerate(self.choices):\n", |
| 44 | " print(\"{0}. {1}\".format(i,x),flush=True)\n", |
| 45 | " x = int(input())\n", |
| 46 | " return self.choices[x]\n", |
| 47 | " else:\n", |
| 48 | " print(\"/\".join(self.choices),flush=True)\n", |
| 49 | " return input()\n", |
| 50 | "\n", |
| 51 | "class Content():\n", |
| 52 | " def __init__(self,x):\n", |
| 53 | " self.x=x\n", |
| 54 | " \n", |
| 55 | "class If(Content):\n", |
| 56 | " pass\n", |
| 57 | "\n", |
| 58 | "class AND(Content):\n", |
| 59 | " pass\n", |
| 60 | "\n", |
| 61 | "class OR(Content):\n", |
| 62 | " pass" |
| 63 | ] |
| 64 | }, |
| 65 | { |
| 66 | "cell_type": "markdown", |
| 67 | "metadata": {}, |
| 68 | "source": [ |
| 69 | "In our system, working memory would contain the list of **facts** as **attribute-value pairs**. The knowledgebase can be defined as one big dictionary that maps actions (new facts that should be inserted into working memory) to conditions, expressed as AND-OR expressions. Also, some facts can be `Ask`-ed." |
| 70 | ] |
| 71 | }, |
| 72 | { |
| 73 | "cell_type": "code", |
| 74 | "execution_count": 12, |
| 75 | "metadata": { |
| 76 | "trusted": true |
| 77 | }, |
| 78 | "outputs": [], |
| 79 | "source": [ |
| 80 | "rules = {\n", |
| 81 | " 'default': Ask(['y','n']),\n", |
| 82 | " 'color' : Ask(['red-brown','black and white','other']),\n", |
| 83 | " 'pattern' : Ask(['dark stripes','dark spots']),\n", |
| 84 | " 'mammal': If(OR(['hair','gives milk'])),\n", |
| 85 | " 'carnivor': If(OR([AND(['sharp teeth','claws','forward-looking eyes']),'eats meat'])),\n", |
| 86 | " 'ungulate': If(['mammal',OR(['has hooves','chews cud'])]),\n", |
| 87 | " 'bird': If(OR(['feathers',AND(['flies','lies eggs'])])),\n", |
| 88 | " 'animal:monkey' : If(['mammal','carnivor','color:red-brown','pattern:dark spots']),\n", |
| 89 | " 'animal:tiger' : If(['mammal','carnivor','color:red-brown','pattern:dark stripes']),\n", |
| 90 | " 'animal:giraffe' : If(['ungulate','long neck','long legs','pattern:dark spots']),\n", |
| 91 | " 'animal:zebra' : If(['ungulate','pattern:dark stripes']),\n", |
| 92 | " 'animal:ostrich' : If(['bird','long nech','color:black and white','cannot fly']),\n", |
| 93 | " 'animal:pinguin' : If(['bird','swims','color:black and white','cannot fly']),\n", |
| 94 | " 'animal:albatross' : If(['bird','flies well'])\n", |
| 95 | "}" |
| 96 | ] |
| 97 | }, |
| 98 | { |
| 99 | "cell_type": "markdown", |
| 100 | "metadata": {}, |
| 101 | "source": [ |
| 102 | "To perform the backward inference, we will define `Knowledgebase` class. It will contain:\n", |
| 103 | "* Working `memory` - a dictionary that maps attributes to values\n", |
| 104 | "* Knowledgebase `rules` in the format as defined above\n", |
| 105 | "\n", |
| 106 | "Two main methods are:\n", |
| 107 | "* `get` to obtain the value of an attribute, performing inference if necessary. For example, `get('color')` would get the value of a color slot (it will ask if necessary, and store the value for later usage in the working memory). If we ask `get('color:blue')`, it will ask for a color, and then return `y`/`n` value depending on the color.\n", |
| 108 | "* `eval` performs the actual inference, i.e. traverses AND/OR tree, evaluates sub-goals, etc." |
| 109 | ] |
| 110 | }, |
| 111 | { |
| 112 | "cell_type": "code", |
| 113 | "execution_count": 33, |
| 114 | "metadata": { |
| 115 | "trusted": true |
| 116 | }, |
| 117 | "outputs": [], |
| 118 | "source": [ |
| 119 | "class KnowledgeBase():\n", |
| 120 | " def __init__(self,rules):\n", |
| 121 | " self.rules = rules\n", |
| 122 | " self.memory = {}\n", |
| 123 | " \n", |
| 124 | " def get(self,name):\n", |
| 125 | " if ':' in name:\n", |
| 126 | " k,v = name.split(':')\n", |
| 127 | " vv = self.get(k)\n", |
| 128 | " return 'y' if v==vv else 'n'\n", |
| 129 | " if name in self.memory.keys():\n", |
| 130 | " return self.memory[name]\n", |
| 131 | " for fld in self.rules.keys():\n", |
| 132 | " if fld==name or fld.startswith(name+\":\"):\n", |
| 133 | " # print(\" + proving {}\".format(fld))\n", |
| 134 | " value = 'y' if fld==name else fld.split(':')[1]\n", |
| 135 | " res = self.eval(self.rules[fld],field=name)\n", |
| 136 | " if res!='y' and res!='n' and value=='y':\n", |
| 137 | " self.memory[name] = res\n", |
| 138 | " return res\n", |
| 139 | " if res=='y':\n", |
| 140 | " self.memory[name] = value\n", |
| 141 | " return value\n", |
| 142 | " # field is not found, using default\n", |
| 143 | " res = self.eval(self.rules['default'],field=name)\n", |
| 144 | " self.memory[name]=res\n", |
| 145 | " return res\n", |
| 146 | " \n", |
| 147 | " def eval(self,expr,field=None):\n", |
| 148 | " # print(\" + eval {}\".format(expr))\n", |
| 149 | " if isinstance(expr,Ask):\n", |
| 150 | " print(field)\n", |
| 151 | " return expr.ask()\n", |
| 152 | " elif isinstance(expr,If):\n", |
| 153 | " return self.eval(expr.x)\n", |
| 154 | " elif isinstance(expr,AND) or isinstance(expr,list):\n", |
| 155 | " expr = expr.x if isinstance(expr,AND) else expr\n", |
| 156 | " for x in expr:\n", |
| 157 | " if self.eval(x)=='n':\n", |
| 158 | " return 'n'\n", |
| 159 | " return 'y'\n", |
| 160 | " elif isinstance(expr,OR):\n", |
| 161 | " for x in expr.x:\n", |
| 162 | " if self.eval(x)=='y':\n", |
| 163 | " return 'y'\n", |
| 164 | " return 'n'\n", |
| 165 | " elif isinstance(expr,str):\n", |
| 166 | " return self.get(expr)\n", |
| 167 | " else:\n", |
| 168 | " print(\"Unknown expr: {}\".format(expr))" |
| 169 | ] |
| 170 | }, |
| 171 | { |
| 172 | "cell_type": "markdown", |
| 173 | "metadata": {}, |
| 174 | "source": [ |
| 175 | "Now let's define our animal knowledgebase and perform the consultation. Note that this call will ask you questions. You can answer by typing `y`/`n` for yes-no questions, or by specifying number (0..N) for questions with longer multiple-choice answers." |
| 176 | ] |
| 177 | }, |
| 178 | { |
| 179 | "cell_type": "code", |
| 180 | "execution_count": 34, |
| 181 | "metadata": { |
| 182 | "trusted": true |
| 183 | }, |
| 184 | "outputs": [ |
| 185 | { |
| 186 | "name": "stdout", |
| 187 | "output_type": "stream", |
| 188 | "text": [ |
| 189 | "hair\n", |
| 190 | "y/n\n", |
| 191 | "sharp teeth\n", |
| 192 | "y/n\n", |
| 193 | "claws\n", |
| 194 | "y/n\n", |
| 195 | "eats meat\n", |
| 196 | "y/n\n", |
| 197 | "color\n", |
| 198 | "0. red-brown\n", |
| 199 | "1. black and white\n", |
| 200 | "2. other\n", |
| 201 | "pattern\n", |
| 202 | "0. dark stripes\n", |
| 203 | "1. dark spots\n" |
| 204 | ] |
| 205 | }, |
| 206 | { |
| 207 | "data": { |
| 208 | "text/plain": [ |
| 209 | "'monkey'" |
| 210 | ] |
| 211 | }, |
| 212 | "execution_count": 34, |
| 213 | "metadata": {}, |
| 214 | "output_type": "execute_result" |
| 215 | } |
| 216 | ], |
| 217 | "source": [ |
| 218 | "kb = KnowledgeBase(rules)\n", |
| 219 | "kb.get('animal')" |
| 220 | ] |
| 221 | }, |
| 222 | { |
| 223 | "cell_type": "markdown", |
| 224 | "metadata": {}, |
| 225 | "source": [ |
| 226 | "## Using PyKnow for Forward Inference\n", |
| 227 | "\n", |
| 228 | "In the next example, we will try to implement forward inference using one of the libraries for knowledge representation, [PyKnow](https://github.com/buguroo/pyknow/). **PyKnow** is a library for creating forward inference systems in Python, which is designed to be similar to classical old system [CLIPS](http://www.clipsrules.net/index.html). \n", |
| 229 | "\n", |
| 230 | "We could have also implemented forward chaining ourselves without many problems, but naive implementations are usually not very efficient. For more effective rule matching a special algorithm [Rete](https://en.wikipedia.org/wiki/Rete_algorithm) is used." |
| 231 | ] |
| 232 | }, |
| 233 | { |
| 234 | "cell_type": "code", |
| 235 | "execution_count": 36, |
| 236 | "metadata": { |
| 237 | "trusted": true |
| 238 | }, |
| 239 | "outputs": [ |
| 240 | { |
| 241 | "name": "stdout", |
| 242 | "output_type": "stream", |
| 243 | "text": [ |
| 244 | "Collecting git+https://github.com/buguroo/pyknow/\n", |
| 245 | " Cloning https://github.com/buguroo/pyknow/ to c:\\users\\dmitryso\\appdata\\local\\temp\\pip-req-build-3iv4twpl\n", |
| 246 | "Collecting frozendict==1.2\n", |
| 247 | " Using cached frozendict-1.2.tar.gz (2.6 kB)\n", |
| 248 | "Collecting schema==0.6.7\n", |
| 249 | " Using cached schema-0.6.7-py2.py3-none-any.whl (14 kB)\n", |
| 250 | "Building wheels for collected packages: pyknow, frozendict\n", |
| 251 | " Building wheel for pyknow (setup.py): started\n", |
| 252 | " Building wheel for pyknow (setup.py): finished with status 'done'\n", |
| 253 | " Created wheel for pyknow: filename=pyknow-1.7.0-py3-none-any.whl size=34580 sha256=334cc7a6eb47459f488db594e8537d7d33d2865c2dbcdd44854146c5c27608e3\n", |
| 254 | " Stored in directory: C:\\Users\\dmitryso\\AppData\\Local\\Temp\\pip-ephem-wheel-cache-l_g7bnq7\\wheels\\96\\36\\bd\\ee1de50bbcf2c7a323dead05584cf90db8898524cf7f57f488\n", |
| 255 | " Building wheel for frozendict (setup.py): started\n", |
| 256 | " Building wheel for frozendict (setup.py): finished with status 'done'\n", |
| 257 | " Created wheel for frozendict: filename=frozendict-1.2-py3-none-any.whl size=3146 sha256=71e32ca6c8ad7e0413bdc9a38f5882a36ba0509e562564a69904fcc9c8b66a9b\n", |
| 258 | " Stored in directory: c:\\users\\dmitryso\\appdata\\local\\pip\\cache\\wheels\\5b\\fa\\ab\\0a80360debb57b95f092356ee3a075bbbffc631b9813136599\n", |
| 259 | "Successfully built pyknow frozendict\n", |
| 260 | "Installing collected packages: schema, frozendict, pyknow\n", |
| 261 | "Successfully installed frozendict-1.2 pyknow-1.7.0 schema-0.6.7\n" |
| 262 | ] |
| 263 | }, |
| 264 | { |
| 265 | "name": "stderr", |
| 266 | "output_type": "stream", |
| 267 | "text": [ |
| 268 | " Running command git clone -q https://github.com/buguroo/pyknow/ 'C:\\Users\\dmitryso\\AppData\\Local\\Temp\\pip-req-build-3iv4twpl'\n" |
| 269 | ] |
| 270 | } |
| 271 | ], |
| 272 | "source": [ |
| 273 | "import sys\n", |
| 274 | "!{sys.executable} -m pip install git+https://github.com/buguroo/pyknow/" |
| 275 | ] |
| 276 | }, |
| 277 | { |
| 278 | "cell_type": "code", |
| 279 | "execution_count": 37, |
| 280 | "metadata": { |
| 281 | "trusted": true |
| 282 | }, |
| 283 | "outputs": [], |
| 284 | "source": [ |
| 285 | "from pyknow import *" |
| 286 | ] |
| 287 | }, |
| 288 | { |
| 289 | "cell_type": "markdown", |
| 290 | "metadata": {}, |
| 291 | "source": [ |
| 292 | "We will define our system as a class that subclasses `KnowledgeEngine`. Each rule is defined by a separate function with `@Rule` annotation, which specifies when the rule should fire. Inside the rule, we can add new facts using `declare` function, and adding those facts will result in some more rules being called by forward inference engine. " |
| 293 | ] |
| 294 | }, |
| 295 | { |
| 296 | "cell_type": "code", |
| 297 | "execution_count": 39, |
| 298 | "metadata": { |
| 299 | "trusted": true |
| 300 | }, |
| 301 | "outputs": [], |
| 302 | "source": [ |
| 303 | "class Animals(KnowledgeEngine):\n", |
| 304 | " @Rule(OR(\n", |
| 305 | " AND(Fact('sharp teeth'),Fact('claws'),Fact('forward looking eyes')),\n", |
| 306 | " Fact('eats meat')))\n", |
| 307 | " def cornivor(self):\n", |
| 308 | " self.declare(Fact('carnivor'))\n", |
| 309 | " \n", |
| 310 | " @Rule(OR(Fact('hair'),Fact('gives milk')))\n", |
| 311 | " def mammal(self):\n", |
| 312 | " self.declare(Fact('mammal'))\n", |
| 313 | "\n", |
| 314 | " @Rule(Fact('mammal'),\n", |
| 315 | " OR(Fact('has hooves'),Fact('chews cud')))\n", |
| 316 | " def hooves(self):\n", |
| 317 | " self.declare('ungulate')\n", |
| 318 | " \n", |
| 319 | " @Rule(OR(Fact('feathers'),AND(Fact('flies'),Fact('lays eggs'))))\n", |
| 320 | " def bird(self):\n", |
| 321 | " self.declare('bird')\n", |
| 322 | " \n", |
| 323 | " @Rule(Fact('mammal'),Fact('carnivor'),\n", |
| 324 | " Fact(color='red-brown'),\n", |
| 325 | " Fact(pattern='dark spots'))\n", |
| 326 | " def monkey(self):\n", |
| 327 | " self.declare(Fact(animal='monkey'))\n", |
| 328 | "\n", |
| 329 | " @Rule(Fact('mammal'),Fact('carnivor'),\n", |
| 330 | " Fact(color='red-brown'),\n", |
| 331 | " Fact(pattern='dark stripes'))\n", |
| 332 | " def tiger(self):\n", |
| 333 | " self.declare(Fact(animal='tiger'))\n", |
| 334 | "\n", |
| 335 | " @Rule(Fact('ungulate'),\n", |
| 336 | " Fact('long neck'),\n", |
| 337 | " Fact('long legs'),\n", |
| 338 | " Fact(pattern='dark spots'))\n", |
| 339 | " def giraffe(self):\n", |
| 340 | " self.declare(Fact(animal='giraffe'))\n", |
| 341 | "\n", |
| 342 | " @Rule(Fact('ungulate'),\n", |
| 343 | " Fact(pattern='dark stripes'))\n", |
| 344 | " def zebra(self):\n", |
| 345 | " self.declare(Fact(animal='zebra'))\n", |
| 346 | "\n", |
| 347 | " @Rule(Fact('bird'),\n", |
| 348 | " Fact('long neck'),\n", |
| 349 | " Fact('cannot fly'),\n", |
| 350 | " Fact(color='black and white'))\n", |
| 351 | " def straus(self):\n", |
| 352 | " self.declare(Fact(animal='ostrich'))\n", |
| 353 | "\n", |
| 354 | " @Rule(Fact('bird'),\n", |
| 355 | " Fact('swims'),\n", |
| 356 | " Fact('cannot fly'),\n", |
| 357 | " Fact(color='black and white'))\n", |
| 358 | " def pinguin(self):\n", |
| 359 | " self.declare(Fact(animal='pinguin'))\n", |
| 360 | "\n", |
| 361 | " @Rule(Fact('bird'),\n", |
| 362 | " Fact('flies well'))\n", |
| 363 | " def albatros(self):\n", |
| 364 | " self.declare(Fact(animal='albatross'))\n", |
| 365 | " \n", |
| 366 | " @Rule(Fact(animal=MATCH.a))\n", |
| 367 | " def print_result(self,a):\n", |
| 368 | " print('Animal is {}'.format(a))\n", |
| 369 | " \n", |
| 370 | " def factz(self,l):\n", |
| 371 | " for x in l:\n", |
| 372 | " self.declare(x)" |
| 373 | ] |
| 374 | }, |
| 375 | { |
| 376 | "cell_type": "markdown", |
| 377 | "metadata": {}, |
| 378 | "source": [ |
| 379 | "Once we have defined a knowledgebase, we populate our working memory with some initial facts, and then call `run()` method to perform the inference. You can see as a result that new inferred facts are added to the working memory, including the final fact about the animal (if we set up all the initial facts correctly)." |
| 380 | ] |
| 381 | }, |
| 382 | { |
| 383 | "cell_type": "code", |
| 384 | "execution_count": 43, |
| 385 | "metadata": { |
| 386 | "trusted": true |
| 387 | }, |
| 388 | "outputs": [ |
| 389 | { |
| 390 | "name": "stdout", |
| 391 | "output_type": "stream", |
| 392 | "text": [ |
| 393 | "Animal is tiger\n" |
| 394 | ] |
| 395 | }, |
| 396 | { |
| 397 | "data": { |
| 398 | "text/plain": [ |
| 399 | "FactList([(0, InitialFact()),\n", |
| 400 | " (1, Fact(color='red-brown')),\n", |
| 401 | " (2, Fact(pattern='dark stripes')),\n", |
| 402 | " (3, Fact('sharp teeth')),\n", |
| 403 | " (4, Fact('claws')),\n", |
| 404 | " (5, Fact('forward looking eyes')),\n", |
| 405 | " (6, Fact('gives milk')),\n", |
| 406 | " (7, Fact('mammal')),\n", |
| 407 | " (8, Fact('carnivor')),\n", |
| 408 | " (9, Fact(animal='tiger'))])" |
| 409 | ] |
| 410 | }, |
| 411 | "execution_count": 43, |
| 412 | "metadata": {}, |
| 413 | "output_type": "execute_result" |
| 414 | } |
| 415 | ], |
| 416 | "source": [ |
| 417 | "ex1 = Animals()\n", |
| 418 | "ex1.reset()\n", |
| 419 | "ex1.factz([\n", |
| 420 | " Fact(color='red-brown'),\n", |
| 421 | " Fact(pattern='dark stripes'),\n", |
| 422 | " Fact('sharp teeth'),\n", |
| 423 | " Fact('claws'),\n", |
| 424 | " Fact('forward looking eyes'),\n", |
| 425 | " Fact('gives milk')])\n", |
| 426 | "ex1.run()\n", |
| 427 | "ex1.facts" |
| 428 | ] |
| 429 | }, |
| 430 | { |
| 431 | "cell_type": "code", |
| 432 | "execution_count": null, |
| 433 | "metadata": {}, |
| 434 | "outputs": [], |
| 435 | "source": [] |
| 436 | } |
| 437 | ], |
| 438 | "metadata": { |
| 439 | "kernelspec": { |
| 440 | "display_name": "Python 3.7.4 64-bit (conda)", |
| 441 | "metadata": { |
| 442 | "interpreter": { |
| 443 | "hash": "86193a1ab0ba47eac1c69c1756090baa3b420b3eea7d4aafab8b85f8b312f0c5" |
| 444 | } |
| 445 | }, |
| 446 | "name": "python3" |
| 447 | }, |
| 448 | "language_info": { |
| 449 | "codemirror_mode": { |
| 450 | "name": "ipython", |
| 451 | "version": 3 |
| 452 | }, |
| 453 | "file_extension": ".py", |
| 454 | "mimetype": "text/x-python", |
| 455 | "name": "python", |
| 456 | "nbconvert_exporter": "python", |
| 457 | "pygments_lexer": "ipython3", |
| 458 | "version": "3.9.5" |
| 459 | } |
| 460 | }, |
| 461 | "nbformat": 4, |
| 462 | "nbformat_minor": 2 |
| 463 | } |
| 464 | |