Simulation 3- assuming hyperbins

[timm]

(wei- please review the following argument)

summary

in the following sim, we find that we need 50 to 150 samples when the number of bins for each numeric attribute is low (e.g. bins=2) and the number of dimensions are low (e.g. dims=3)

comments:

• is it reasonable to use low bins (e.g. bins=2). Wellyes, says audris in his "universal predictor" paper.
• is it reasonable to use low dims (e.g. dims=3). well, yes. wei reports that we often FSS down to dims=3

details

So i assumed that the data had "dims" dimensions, each with a percentile chopped into "bins"

then i said the prodbability of bugs was10% <= p <= 40% and 3 <= bins <= 7 and 2 <= dims <= 7

then i distributed the probability of the bugs around the bins**dims of the hypercube of the independent variables (bugs created randomly using r()**2 so that the mininorty of the bins had the majority of the bigs

then i weighted each part of the hypercube by p/(dims*bins)

then i ran it all 1000 times , increasing the number of samples until we had a 2/3rds chance of finding the bugs (call that the "n66" number) with a sanity condition of n <= 1000

code

from __future__ import division

import random
r = random.random
any = random.choice

def ps(dims,bins,p=0.1,skew=2):
  space = bins**dims
  f1  = [r()**skew for _ in xrange(space)]
  all = sum(f1)
  f2  = [x/all for x in f1]
  return [p*1/space*x for x in f2]

def ns(dims=3,bins=2,p=0.1):
  w = sum(ps(dims,bins,p))
  n = 10
  found = 0
  while found < 0.66 and n < 1000:
    n += 10
    found = 1 - ((1 - w) ** n)
  print "_%s, _%s, _%s, %s" % (int(p*10),dims,bins,n)

print "p,dims,bins,n66"
for _ in xrange(1000):
  ns(dims= any([3,4,5,6,7]),
     bins= any([2,3,4,5,6,7]),
     p   = any([0.1,0.2,0.3,0.4]))

analysis

then i ran a decision tree learner and got at tree with a correlation of 92% in a 10-way. note that, in the following tree:

• p does not matter. the effects are driven by bins and dims
• we get low number of samples to reach n66 (50 to 200) when
  • bins=2 and dims=3,4
    • and bins=3 and dims=3
• otherwise, we large hundreds of samples

results

bins =  _2
|   dims =  _3 : 50 (25/672) [11/436.36]
|   dims =  _4 : 107.6 (20/3028.75) [5/3456.25]
|   dims =  _5 : 203.26 (31/11974.82) [12/10088.09]
|   dims =  _6 : 336.43 (17/31955.71) [11/31618.62]
|   dims =  _7 : 613.33 (23/64163.71) [7/87900.89]
bins =  _3
|   dims =  _3 : 159.14 (21/7091.16) [14/8226.53]
|   dims =  _4 : 455.48 (22/58697.52) [9/107415.61]
|   dims =  _5 : 905.79 (24/17515.97) [14/14086.41]
|   dims =  _6 : 1000 (18/0) [18/0]
|   dims =  _7 : 1000 (17/0) [7/0]
bins =  _4
|   dims =  _3 : 370 (19/27314.13) [8/51881.93]
|   dims =  _4 : 891.94 (22/16804.96) [9/19220.29]
|   dims =  _5 : 1000 (33/0) [11/0]
|   dims =  _6 : 1000 (16/0) [18/0]
|   dims =  _7 : 1000 (30/0) [18/0]
bins =  _5
|   dims =  _3 : 755.31 (20/61678.75) [12/72781.25]
|   dims =  _4 : 1000 (23/0) [17/0]
|   dims =  _5 : 1000 (22/0) [12/0]
|   dims =  _6 : 1000 (18/0) [12/0]
|   dims =  _7 : 1000 (20/0) [14/0]
bins =  _6
|   dims =  _3 : 860 (18/28511.11) [9/28511.11]
|   dims =  _4 : 1000 (18/0) [5/0]
|   dims =  _5 : 1000 (19/0) [5/0]
|   dims =  _6 : 1000 (29/0) [15/0]
|   dims =  _7 : 1000 (25/0) [9/0]
bins =  _7 : 998.33 (116/41.88) [52/278.18]

t

[WeiFoo]

Questions:

1. why space = bins*_dims, not bins_dims

• in python ** is exponentiaion. so bins=2 on dimes=3 results in 2**3 = 8 regions in hyperspace

1. in HDP, each target has different source data sets with different matched features, then it means the reasonable small size for source data set will change according to different targets. does it make sense?

size if not the issue... the distribution of bugs within that size is the issue

[WeiFoo]

Example

target: ar1

some source data sets

• NOTE: x-axis is the sample size =[10,20,30....], y-axis is the probability: p = 1- (1-w)**N

[timm]

not clear on what ur saying above

[WeiFoo]

the point here is,

• no turning point(sample size) here, which is good enough to cover the data set.
• even for the the same source data set, say: LC. arff, may have different dims because of matched features with different targets, then resulting in different sample size according to p = 1-(1-w)**n

[timm]

what is the xaxis?

and your graphs suggest we dont have a min limit and my maths does (50 to 200 is fine for low dim).

so how do your graphs address the effect we are trying to xplain?

[timm]

Updated the sim

now the skew is skewed 1 (uniform) to 2

also, i am working from a lower bound of dims=2

from __future__ import division
import sys

import random
r = random.random
any = random.choice

def ps(dims,bins,p=0.1,skew=2):
  space = bins**dims
  f1  = [r()**skew for _ in xrange(space)]
  all = sum(f1)
  f2  = [x/all for x in f1]
  return [p/space*x for x in f2]

def ns(dims=3,bins=2,p=0.1,skew=2):
  w = sum(ps(dims,bins,p,skew))
  n = 10
  found = 0
  while True:
    if found > 0.66: break
    if n > 1000: break
    n += 10
    found = 1 - ((1 - w) ** n)
  print " _%s, _%s, _%s,  %s" % (int(p*10),dims,bins,n)

print "p,dims,bins,n66"
for i in xrange(10000):
  if i % 50 == 0: sys.stderr.write('%s ' % i)
  ns(dims= any([2,3,4,5,6,7]),
     bins= any([2,3,4,5,6,7]),
     skew = any([1,1.1,1.25,1.5,2]),
     p   = any([0.1,0.2,0.3,0.4]))

in the following we get a correlation of r^2 = 97% in 10000 samples. note that adding or deleting the skew para does not effect the samples

many cases where n=50 to 200 is just fine.

dims =  2
|   bins =  2 : 30
|   bins =  3
|   |   p =  10% : 100 
|   |   p =  20%: 50 
|   |   p =  30% : 40 
|   |   p =  40% : 30 
|   bins =  4 : 100
|   bins =  5 : 15
|   bins =  7 : 27
|   bins =  6 : 190
dims =  3
|   bins =  2 : 49
|   bins =  3
|   |   p =  10% : 300 
|   |   p =  20% : 150 
|   |   p =  30% : 100 
|   |   p =  40% : 80 
|   bins =  4
|   |   p =  10% : 690 
|   |   p =  20% : 350 
|   |   p =  30% : 230 
|   |   p =  40% : 180 
|   bins =  5 : 580
|   bins >=  6 : 1000 
dims =  4
|   bins =  2 : 100
|   bins =  3 : 450
|   bins =  4 : 910
|   bins >=  5 : 1000 
dims =  5
|   bins =  2
|   |   p =  10% : 350 
|   |   p =  20% : 180 
|   |   p =  30% : 120 
|   |   p =  40% : 90 
|   bins =  3 : 880
|   bins >=  4 : 1000 
dims =  6
|   bins =  2
|   |   P =  10% : 690 
|   |   P =  20% : 350 
|   |   P =  30% : 230 
|   |   P =  40% : 180 
|   bins >=  3 : 1000 
dims =  7 : 1000

[WeiFoo]

Distributions of matched features

Small source--Small target in KS test, Small source-- Large target in prediction

(dim =1 : number of matched features used in each source-target, 120 is the counts)
dim=1 : 120
dim=2 : 249
dim=3 : 171
dim=4 : 60
dim=5 : 14

Large source--Small target in KS test, Large source-- Large target in prediction

dim=1 : 220
dim=2 : 136
dim=3 : 64
dim=4 : 21

[timm]

just confirming: at dim=1, does that mean that we are predicting using a training set with TWO columns (one for that dimension and one for the class?)

[WeiFoo]

yes, that's right.

[timm]

more simulation studies

this time, dims = 1 to 7
results are classified <50 <100 <200 >200

in a 10-way, very high precision, recall, TP rates for ge200

               TP Rate   FP Rate   Precision   Recall  F-Measure   ROC Area  Class
                 0.977     0.025      0.986     0.977     0.982      0.998      ge200
                 1         0.006      0.971     1         0.985      0.999      lt50
                 0.81      0.005      0.953     0.81      0.876      0.995      lt100
                 0.843     0.033      0.698     0.843     0.764      0.983      lt200
Weighted Avg.    0.952     0.02       0.956     0.952     0.953      0.997

here's the tree (from C4.5) note that when dims <=2, we need ge200 (more than 200 samples)

in the following, the lines marked "X" are the expected case (all we need is two bins, median chop, and dims <=-3) Note that in all those branches, we usually need lt 50 samples (occasional exception: when target class is rate (10%) then we many need to go to 200 samples)

which is totally consistent with wei's result

X dims <= 2
X |   dims <= 1
X |   |   p <= 0.1
X |   |   |   bins <= 3:   lt50 
  |   |   |   bins > 3:   lt100 
X |   |   p > 0.1:   lt50 
X |   dims > 1
X |   |   bins <= 3
X |   |   |   p = 0.1:   lt200 
X |   |   |   p > 0.1:   lt50 
  |   |   bins > 3
  |   |   |   bins <= 5
  |   |   |   |   p = 0.1:   lt200 
  |   |   |   |   p > 0.1
  |   |   |   |   |   p <= 0.2
  |   |   |   |   |   |   bins <= 4:   lt100 
  |   |   |   |   |   |   bins > 4:   lt200 
  |   |   |   |   |   p > 0.2:   lt100 
  |   |   |   bins > 5
  |   |   |   |   p <= 0.2:   ge200 
  |   |   |   |   p > 0.2:   lt200 
X dims > 2
X |   bins <= 2
X |   |   dims <= 5
X |   |   |   dims <= 3
X |   |   |   |   p <= 0.2:   lt100 
X |   |   |   |   p > 0.2:   lt50 
  |   |   |   dims > 3
  |   |   |   |   p = 0.1:   lt200 
  |   |   |   |   p > 0.1
  |   |   |   |   |   dims <= 4:   lt100 
  |   |   |   |   |   dims > 4
  |   |   |   |   |   |   p <= 0.3:   lt200 
  |   |   |   |   |   |   p > 0.3:   lt100 
  |   |   dims > 5:   ge200 
  |   bins > 2
  |   |   dims <= 3
  |   |   |   bins <= 4
  |   |   |   |   p <= 0.3
  |   |   |   |   |   bins <= 3
  |   |   |   |   |   |   p = 0.1:   ge200 
  |   |   |   |   |   |   p > 0.1:   lt200 
  |   |   |   |   |   bins > 3:   ge200 
  |   |   |   |   p > 0.3:   lt200 
  |   |   |   bins > 4:   ge200 
  |   |   dims > 3:   ge200