Greg's Notebook, Summer 2007

---

Back to Greg's Wiki

---

June 28 : Better Spill Model

Let's back up and just think about this as an optimization problem. Assume we know (or can estimate) the following for each node i:

pi : overall performance of the two-class branch classifier
Pi : overall performance of the multi-class classifier
ti : time-per-image for two-class branch classifiers 
Ti : time-per-image for multi-class classifiers

And we want to choose

Ri : ratio of test images which end up being evaluated by multi-class classifier

As we make the speed/performance trade-off, our "knob" can be the values R₁. Now we just need to find R_2..N which maximize performance per unit time. Rough estimates, as a function of the level L:

$t\sim 1/L$         $T\sim 1/L^{2}$

for an ideal balanced tree. Performance is harder to estimate (maybe we have no choice but to measure this?)

I'd like to measure each of the above 4 quantities, and how they scale with level L. Then use this to derive fairly optimal spills (instead of generating envelopes like I'm doing now, which is time-consuming).

June 27 : Analyze Optimal Spills

Results below are for N_train=10 and a 3-level tree (see left). Random ratios are converted into their equivalent spill values. I try 10,000 random values which form an envelope of possible speed-to-performance ratios.

Skim off just the best performance-to-speed ratios:

top
take june29c c3
[c,s3,p3]= benchcascade(c3,'ratio',10000);
[s,p]= slidefunc(s3,p3,50,'median','max');
l3= interp1(s,p,s3);
lim3=l3-.0005*(s3/1300).^1.5; 
f= find(p3>lim3);  
plot(s3,p3,'.',s3(f),p3(f),'r.')

As can be seen, we get a 3-times speed increase for a 10% drop in performance. Now plot the ratios corresponding to the above "skimmed" values:

bot
[tmp,indx]= sort(s3(f));  
spill=[c{1}.spill(f);c{2}.spill(f);c{4}.spill(f)];
ratio= spill2ratio(spill);
x= s3(f(indx)); 
styles={'k-','r-','g-','b-'};
for i=1:4, 
y= ratio(i,indx);
[xx,yy]= slidefunc(x,y,10,'mean','mean'); 
plot(xx,yy,styles{i}); hold on;
end

Here a ratio of .5 for level=1 means that 50% the test images will end up getting stuck in the root node. Thus ratio(l=1)=1.0 means there is effectively no cascade (maximum performance). At the other extreme, a ratio(l=4)=1.0 means all test images are evaluated at the bottom leaves (maximum speed).

Conclusions

What is the optimal way to distribute test images throughout the cascade? By creating an envelope of random ratios (ie. spills) and skimming the best performance-to-speed ratios, we now know the answer in advance. But what exactly is the model pictured here? What is the justification?

June 26 : Current Spill Heuristic

For spill I currently use the function getspill(lmax,krange,mode). The idea is to move some ratio

$r(k,l)=1/(k^{l})$

of the test files to each level l. That's mode=2. So here's an example for depth of lmax=3:

krange= -6:2:6; [spill,ratio]=getspill(3, krange, 2); [krange' ratio spill]

ans =

       k      r(k,0)    r(k,1)    r(k,2)    r(k,3)        spill(0)  spill(1)  spill(2)  
   -6.0000    0.9831    0.0154    0.0013    0.0002    	   0.0169    0.0937    0.1511
   -4.0000    0.9270    0.0579    0.0114    0.0036    	   0.0730    0.2064    0.2404
   -2.0000    0.7024    0.1756    0.0780    0.0439    	   0.2976    0.4098    0.3600
    0.0000    0.2500    0.2500    0.2500    0.2500    	   0.7500    0.6667    0.5000   <= 3/4 2/3 1/2
    2.0000    0.0333    0.1333    0.3000    0.5333    	   0.9667    0.8621    0.6400
    4.0000    0.0028    0.0452    0.2288    0.7232    	   0.9972    0.9547    0.7596
    6.0000    0.0002    0.0131    0.1491    0.8376    	   0.9998    0.9869    0.8489

As you can see a low value of k=-6 leaves most test files in the root node, while a high value k=6 pushes most (~84%) of the test files to the leaves at lmax=3.

For example at k=0 you want an equal amount at each level. No problem: just spill 3/4, 2/3 and then 1/2 at levels 1, 2 and 3 respectively.

Anyway at the moment this is the best heuristic I have for choosing a range of spills.