import sys sys.dont_write_bytecode=True # no .pyc files from the import * from about import * from lib import * def _do(): """A every iteraction, some performance score is logged back with the 'Do' loop, using 'seen'. Note the use of 'controlled' to print the eras.""" for x,d in do(range(0,50), era=10, haltOn='fx', epsilon=0.05): y = 1.0/(1 + e**(-0.1*x)) d.seen(x,fx=y) done(d,0,1,value=lambda s: '%4.2f' % s) def do(iterator=range(0,100), epsilon=0.01, haltOn= None, era = 100, also = None, cohen = The.math.cohen, cmp = lambda old, new: new - old): """syntactic sugar for calling the Do class. Without this helper function, you need to do for x,d in Do(....).loop(): ... With this function, you can do: for x,d in do(....): ... """ for tick,doings in Do(iterator=iterator, epsilon= epsilon, haltOn=haltOn, era= era, also=also, cohen=cohen, cmp=cmp).loop(): yield tick,doings class Do: """'Do' adds to features to a standard iterator. 'Do' lets you run an optimizer many times, while incrementally storing performance results. Using those results, 'Do' also lets you determine in the optimizer should quit early. For a simple example of its usage, see '_do()', above. Note that during each iteration, we log some performance value using the 'seen' method. For a more typical example of usage, see search.py and the 'sa' function. From that example,here's 50 runs of SA from k=0 to 1000 where all the results are grouped together in 'era's of size 30. On the left is era number followed by [sampleSize] of items in that era. Then there is a quantile chart showing the 10,30,50,70,90-th percentile of the performance scores in that era. This first run stops if the mean results in any era are within an epsilon on 20% of max; i.e. epsilon=0.2. 'Best' is the 'eb' scores and 'every' are the 'e' scores. FIRST RUN: -----| best |----------------------------------------- ---------------- 0 [ 128] | -- * - ,0.62, 0.71, 0.79, 0.85, 0.91 30 [ 128] | -- * ,0.79, 0.85, 0.88, 0.91, 0.94 60 [ 120] | - *- ,0.75, 0.79, 0.82, 0.86, 0.89 90 [ 30] | * ,0.80, 0.80, 0.80, 0.80, 0.80 ------| every |-------------------------------------------------------- 0 [ 128] |--- *-- ,0.53, 0.67, 0.77, 0.82, 0.90 30 [ 128] | -- *- ,0.74, 0.81, 0.87, 0.90, 0.94 60 [ 120] | - *- ,0.74, 0.78, 0.82, 0.86, 0.89 90 [ 30] |-------* ,0.53, 0.80, 0.80, 0.80, 0.80 This second run stops if we reach an epsilon of within 2.5% of max; i.e. epsilon=0.025. Notice we run for more eras than in the FIRST RUN. SECOND RUN: ------| best |-------------------------------------------------------- 0 [ 128] | ---- *-- ,0.60, 0.76, 0.79, 0.84, 0.91 30 [ 128] | -- * ,0.77, 0.84, 0.89, 0.91, 0.95 60 [ 128] | *- ,0.84, 0.87, 0.92, 0.94, 0.97 90 [ 128] | - * ,0.87, 0.91, 0.92, 0.94, 0.97 120 [ 128] | --* ,0.86, 0.93, 0.94, 0.94, 0.97 150 [ 30] | *,0.97, 0.97, 0.97, 0.97, 0.97 ------| every |-------------------------------------------------------- 0 [ 128] | --- * -- ,0.60, 0.70, 0.76, 0.81, 0.88 30 [ 128] | --- *-- ,0.69, 0.83, 0.86, 0.91, 0.96 60 [ 128] | ----- *- ,0.67, 0.85, 0.89, 0.93, 0.96 90 [ 128] | -- *- ,0.79, 0.87, 0.91, 0.94, 0.97 120 [ 128] | --- * - ,0.66, 0.80, 0.88, 0.94, 0.97 150 [ 30] |--* ,0.51, 0.62, 0.63, 0.83, 0.83 Another thing we can 'Do' is stop if the improvement in the new era is very small compared to the last one. Here's the last run (epsilon=0.025) but in this run, we say "very small" is less than one standard deviation of the all the scores seen in the run. This is the Cohen test for effect size so we denote it cohen=1. THIRD RUN: -----| best |--------------------------------------------------------- 0 [ 128] | -- *- ,0.64, 0.75, 0.81, 0.86, 0.91 30 [ 128] | - *- ,0.80, 0.84, 0.89, 0.91, 0.97 60 [ 128] | -*- ,0.84, 0.89, 0.92, 0.94, 0.98 90 [ 120] | *- ,0.84, 0.88, 0.91, 0.91, 0.98 ------| every |------------------------------------------------------- 0 [ 128] | ---- * - ,0.59, 0.72, 0.80, 0.87, 0.91 30 [ 128] | -- *-- ,0.73, 0.83, 0.87, 0.91, 0.97 60 [ 128] | ----- *- ,0.62, 0.83, 0.89, 0.92, 0.98 90 [ 120] | - *- ,0.81, 0.88, 0.89, 0.91, 0.98 Finally, our last run shows a run with typical settings for this `Do'-ing; i.e. epsilon=0.01 (1% of max) and cohen=0.2 (i.e. "very small" is less than 20% of one standard deviation). Note that its the same as the SECOND RUN shown above since, in this model, achieving 1% of max is not possible. FOURTH RUN: ------| best |-------------------------------------------------------- 0 [ 128] | ---- *-- ,0.60, 0.76, 0.79, 0.84, 0.91 30 [ 128] | -- * ,0.77, 0.84, 0.89, 0.91, 0.95 60 [ 128] | *- ,0.84, 0.87, 0.92, 0.94, 0.97 90 [ 128] | - * ,0.87, 0.91, 0.92, 0.94, 0.97 120 [ 128] | --* ,0.86, 0.93, 0.94, 0.94, 0.97 150 [ 30] | *,0.97, 0.97, 0.97, 0.97, 0.97 ------| every |-------------------------------------------------------- 0 [ 128] | --- * -- ,0.60, 0.70, 0.76, 0.81, 0.88 30 [ 128] | --- *-- ,0.69, 0.83, 0.86, 0.91, 0.96 60 [ 128] | ----- *- ,0.67, 0.85, 0.89, 0.93, 0.96 90 [ 128] | -- *- ,0.79, 0.87, 0.91, 0.94, 0.97 120 [ 128] | --- * - ,0.66, 0.80, 0.88, 0.94, 0.97 150 [ 30] |--* ,0.51, 0.62, 0.63, 0.83, 0.83 """ def __init__(i, iterator=range(0,100), epsilon= 0.005, haltOn=None, era= 100, also=None, cohen=The.math.cohen, cmp=lambda old, new: new - old): i.iterator=iterator i.era = era i.epsilon = epsilon i.all = Nums() i.now = Nums() i.also = also i.cohen = cohen i.haltOn = haltOn i.cmp = cmp def thisEra(i,tick): """Internally, 'Do' instances keep time rounded off to the nearest era size.""" return int(tick/i.era)*i.era def small(i,where) : "Small is, say, 30% of std.dev seen so far" return i.all[where].s*i.cohen def close2Best(i,where,when) : "mean within epsilon of best" return i.now[(where,when)].mu > (1 - i.epsilon) def improving(i,where,when): """The difference in means between now and last is not small.""" before = when - i.era new = i.now[(where,when)] old = i.now[(where,before)] return i.cmp(old.mu, new.mu) > i.small(where) def earlyStop(i,when): "Early stop if close to best or not improving." where = i.haltOn if where: if i.close2Best(where,when) or \ not i.improving(where,when): return True return False def seen(i,tick,**d): "Syntactic sugar for adding new items" when = i.thisEra(tick) for where,what in d.items(): i.seen1(when,what,where) def seen1(i,when,what,where): "Primitive data add. Also adds to parent." if i.also: i.also.seen1(when,what,where) i.all[where].seen(what) i.now[(where, when)].seen(what) def loop(i): "Every time we change eras, check for early stop." before = 0 for tick in i.iterator: now = i.thisEra(tick) if before and now != before: if i.earlyStop(before): break before = now yield tick,i def done(doings,lo,hi, key =lambda z:'%10s' % z, value=lambda z: '%2d' % z ): d = doings.now wheres= {} whens = {} for where,when in d.keys(): wheres[where] = 1 whens[ when ] = 1 wheres = sorted(wheres.keys()) whens = sorted(whens.keys()) for where in wheres: print '\n------|',str(where),'|'+'-'*75,'\n' for when in whens: if (where,when) in d: all = d[(where,when)].cached() s = "?" if len(all) > 5: s= xtile(all,show = value, lo=lo,hi=hi,width=25) print '%10s' % key(when),\ '[%5s]' % len(all), s """ ### xtile: Pretty Print Distributions The function _xtile_ takes a list of (possibly) unsorted numbers and presents them as a horizontal xtile chart (in ascii format). The default is a contracted _quintile_ that shows the 10,30,50,70,90 breaks in the data (but this can be changed- see the optional flags of the function). """ def xtile(lst,lo=0,hi=100,width=50, chops=[0.1 ,0.3,0.5,0.7,0.9], marks=["-" ," "," ","-"," "], bar="|",star="*",show= lambda s:" %3.0f" % s): def pos(p) : return ordered[int(len(lst)*p)] def place(x) : tmp= int(width*float((x - lo))/(hi - lo)) if tmp == width: tmp += -1 return tmp def pretty(lst) : return ', '.join([show(x) for x in lst]) ordered = sorted(lst) lo = min(lo,ordered[0]) hi = max(hi,ordered[-1]) what = [pos(p) for p in chops] where = [place(n) for n in what] out = [" "] * width for one,two in pairs(where): for i in range(one,two): out[i] = marks[0] marks = marks[1:] out[int(width/2)] = bar loc = place(pos(0.5)) #print loc, len(out) out[loc] = star return ''.join(out) + "," + pretty(what) def _tile() : import random r = random.random def show(lst): return xtile(lst,lo=0, hi=1,width=25, show= lambda s:" %3.2f" % s) print "one", show([r()**0.5 for x in range(1000)]) print "two", show([r()**2 for x in range(1000)])w def _tile2(): def show(lst): return xtile(lst,lo=0, hi=1,width=25, show= lambda s:" %3.2f" % s) print "one", show([0.21, 0.29, 0.28, 0.32, 0.32, 0.28, 0.29, 0.41, 0.42, 0.48]) print "two", show([0.71, 0.92, 0.80, 0.79, 0.78, 0.9, 0.71, 0.82, 0.79, 0.98]) if __name__ == '__main__' : eval(cmd('_do()'))