Graphing Bellman

Trees and their implementation in Python make the concepts easier to understand. I use the Zim wiki along with "kate" editor , MIT class 600, Ipython, along with many other open source programs. The graph was created in Zim which has Python extensions. I reviewed the MIT 600 course again today and there are some very interesting things about probability and logical fallacies. I particularly enjoyed the anecdote about shooting at a wall and then painting a bull's eye afterward to make it appear as if the person was a perfect marksman. A related reference to the "minimum principle".



digraph KnapSack { "Index"->"2-5-0" "Objects [A,B,C]+Weights [5,3,2]+Value[9,7,8][]"->"Weight left"->"2-5-0" "Total Value"->"2-5-0" "2-5-0"[color=green] "1-5-0" "0-5-0" "X-5-0"[color=red] "2-5-0"->"1-5-0"[label=" Leave 2" color="orange"][color=blue] "2-5-0"->"1-3-8"[label=" Take 2" color="orange"][color=blue] "1-3-8"->"0-3-8"[label=" Leave 1" color="orange"][color=blue] "0-3-8"->"X-3-8"[label=" Leave 0" color="orange"][color=blue] "0-3-8"->"X-X-X"[label=" Leave 0" color="orange"][color=blue] "1-3-8"->"0-0-15"[label=" Take 1" color="orange"][color=blue] "0-0-15"->"Y-Y-Y"[label=" Nothing" color="orange"][color=blue] "0-0-15"->"Y-Y-Y"[label=" Nothing" color="orange"][color=blue] "1-5-0"->"0-5-0"[label=" Leave 1" color="orange"][color=blue] "1-5-0"->"0-2-7"[label=" Take 1" color="orange"][color=blue] "0-2-7"->"X-2-7"[label=" Leave 0" color="orange"][color=blue] "0-2-7"->"X-X-X"[label=" NO" color="orange"][color=blue] "0-5-0"->"X-5-0"[label=" Leave 0" color="orange"][color=blue] "0-5-0"->"X-0-9"[label=" take 0" color="orange"][color=blue] }
numCalls=0
def maxVal(w, v, i, aW):
 #print 'maxVal called with:', i, aW
 global numCalls
 numCalls += 1
 if i == 0:
  if w[i] <= aW: return v[i]
  else: return 0
 without_i = maxVal(w, v, i-1, aW)
 if w[i] > aW: return without_i
 else: with_i = v[i] + maxVal(w, v, i-1, aW - w[i])
 return max(with_i, without_i)

# def maxVal0(w, v, i, aW):
m = {}
#return fastMaxVal(w, v, i, aW, m)

def fastMaxVal(w, v, i, aW, m):
 global numCalls
 numCalls+=1
 try: return m[(i, aW)]
 except KeyError:
  if i == 0:
   if w[i] <= aW:
    m[(i, aW)] = v[i]
    return v[i]
   else:
    m[(i, aW)] = 0
    return 0
  without_i = fastMaxVal(w, v, i-1, aW, m)
  if w[i] > aW:
   m[(i, aW)] = without_i
   return without_i
  else: with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i], m)
  res = max(with_i, without_i)
  m[(i, aW)] = res
  return res
weights=[5,3,2]
values=[9,8,7]
print fastMaxVal(weights,values,len(values)-1,5,m),numCalls
weights=[1,5,3,4]
values=[15,10,9,5]
print fastMaxVal(weights,values,len(values)-1,5,m),numCalls
weights=[1,1,5,5,3,3,4,4]
values=[15,15,10,10,5,5,5,5]
print fastMaxVal(weights,values,len(values)-1,15,m),numCalls
weights=[1,1,5,5,3,3,4,4,1,1,5,5,3,3,4,4]
values=[15,15,10,10,5,5,5,5,15,15,10,10,5,5,5,5]
print fastMaxVal(weights,values,len(values)-1,15,m),numCalls

Besides the graphing of functions, it is possible to take the data from a decision tree in Python and write it out to plot it as a digraph. Using something new I learned it is possible to create a RoseGarden midi file and a video of the changes to a graph to indicate how it is processed using dvd-slideshow and ffmpeg to create a complete video presentation with annotated source and speech..

dot -Tps digraph.dot -o dgraph1.jpg

2 comments:

mirae said...

well hello there professor, just zooming by for my weekly blogging on my way to infinity and here I am looking at all these formulas trying to find something I can relate to and I always do find something I can relate to in your mind.
that allegory about shooting a hole in the wall and then adding the bulls eye after made me laugh and laugh and laugh but the more I think of it the more disturbing it becomes haha.
we probably do that all the time without being conscious of doing this,anytime we say I won it is in retrospect. haha.
have a beautiful week.
sending you sweetly configured kisses.

Paul Mohr said...

I'm glad you enjoyed that. I will try to keep my equations to a minimum and concentrate on the funny stuff :)

Automated Intelligence

Automated Intelligence
Auftrag der unendlichen LOL katzen