Vapnik – Chervonenkis teori - Vapnik–Chervonenkis theory

Del av en serie om
Maskininlärning och datamining
Problem Klassificering Kluster Regression Anomali upptäckt AutoML Föreningsregler Förstärkning lärande Strukturerad förutsägelse Funktionsteknik Funktionsinlärning Online -lärande Semi-övervakat lärande Lärande utan tillsyn Lär dig rangordna Grammatikinduktion
Övervakat lärande ( klassificering  • regression ) Beslutsträd Ensembler Säckväv Förstärkning Slumpmässig skog k -NN Linjär regression Naiva Bayes Artificiellt nervsystem Logistisk återgång Perceptron Relevansvektormaskin (RVM) Stödvektormaskin (SVM)
Kluster BJÖRK BOTA Hierarkisk k -medel Förväntning – maximering (EM) DBSCAN OPTIK Genomsnittligt skift
Minskad dimension Faktoranalys CCA ICA LDA NMF PCA PGD t-SNE
Strukturerad förutsägelse Grafiska modeller Bayes netto Villkorligt slumpmässigt fält Dold Markov
Anomali upptäckt k -NN Lokal avvikelse faktor
Artificiellt neuralt nätverk Autoencoder Kognitiv beräkning Djup lärning DeepDream Flerlagers perceptron RNN LSTM GRU ESN Begränsad Boltzmann -maskin GAN SOM Konvolutionellt neuralt nätverk U-Net Transformator Spikande neuralt nätverk Memtransistor Elektrokemiskt RAM -minne (ECRAM)
Förstärkning lärande Q-lärande SARSA Temporal skillnad (TD)
Teori Bias -variansavvägning Beräkningslärande teori Empirisk riskminimering Occam lärande PAC -lärande Statistiskt lärande VC -teori
Maskininlärningsplatser NeurIPS ICML ML JMLR ArXiv: cs.LG
Relaterade artiklar Ordlista över artificiell intelligens Lista över datamängder för maskininlärningsforskning Kontur av maskininlärning
v t e

Vapnik – Chervonenkis -teorin (även känd som VC -teorin ) utvecklades under 1960–1990 av Vladimir Vapnik och Alexey Chervonenkis . Teorin är en form av beräkningslärningsteori , som försöker förklara inlärningsprocessen ur en statistisk synvinkel.

VC -teori är relaterat till statistisk inlärningsteori och till empiriska processer . Bland annat Richard M. Dudley och Vladimir Vapnik har tillämpat VC-teori på empiriska processer .

Introduktion

VC -teorin omfattar minst fyra delar (som förklaras i The Nature of Statistical Learning Theory ):

• Teori om konsekvens av inlärningsprocesser
  • Vilka är (nödvändiga och tillräckliga) förutsättningar för konsekvens i en inlärningsprocess baserad på empirisk riskminimeringsprincip ?
• Nonasymptotisk teori om inlärningsprocessernas konvergenshastighet
  • Hur snabb är inlärningsprocessens konvergenshastighet?
• Teori om att kontrollera inlärningsprocessernas generaliseringsförmåga
  • Hur kan man kontrollera inlärningsprocessens konvergenshastighet ( generaliseringsförmågan )?
• Teori om att konstruera inlärningsmaskiner
  • Hur kan man konstruera algoritmer som kan styra generaliseringsförmågan?

VC Theory är en viktig delgren av statistisk inlärningsteori . En av dess huvudsakliga tillämpningar inom statistisk inlärningsteori är att tillhandahålla generaliseringsvillkor för inlärningsalgoritmer. Ur denna synvinkel är VC -teorin relaterad till stabilitet , vilket är ett alternativt tillvägagångssätt för att karakterisera generalisering.

Dessutom är VC -teori och VC -dimension avgörande för teorin om empiriska processer , när det gäller processer som indexeras av VC -klasser. Detta är förmodligen de viktigaste tillämpningarna av VC -teorin och används för att bevisa generalisering. Flera tekniker kommer att introduceras som används i stor utsträckning i den empiriska processen och VC -teorin. Diskussionen bygger huvudsakligen på boken Weak Convergence and Empirical Processes: With Applications to Statistics .

Översikt över VC -teori i empiriska processer

Bakgrund om empiriska processer

Låt vara slumpmässiga element definierade på ett mätbart utrymme . För alla mått på och mätbara funktioner , definiera ${\ displaystyle X_ {1}, \ ldots, X_ {n}}$ ${\ displaystyle ({\ mathcal {X}}, {\ mathcal {A}})}$${\ displaystyle Q}$${\ displaystyle ({\ mathcal {X}}, {\ mathcal {A}})}$${\ displaystyle f: {\ mathcal {X}} \ to \ mathbf {R}}$

${\ displaystyle Qf = \ int fdQ}$

Mätbarhetsfrågor ignoreras här, för mer teknisk detalj se. Låt oss vara en klass av mätbara funktioner och definiera: ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle f: {\ mathcal {X}} \ to \ mathbf {R}}$

${\ displaystyle \ | Q \ | _ {\ mathcal {F}} = \ sup \ {\ vert Qf \ vert \: \ f \ i {\ mathcal {F}} \}.}$

Definiera det empiriska måttet

${\ displaystyle \ mathbb {P} _ {n} = n^{-1} \ sum _ {i = 1}^{n} \ delta _ {X_ {i}},}$

där δ här står för Dirac -måttet . Det empiriska måttet inducerar en karta som ges av: ${\ displaystyle {\ mathcal {F}} \ to \ mathbf {R}}$

${\ displaystyle f \ mapsto \ mathbb {P} _ {n} f = {\ frac {1} {n}} (f (X_ {1})+...+f (X_ {n}))}}$

Antag nu att P är den underliggande sanna fördelningen av data, vilket är okänt. Empiriska processer teori syftar till att identifiera klasser för vilka uttalanden som följande håller: ${\ displaystyle {\ mathcal {F}}}$

• enhetlig lag av stora antal :

  ${\ displaystyle \ | \ mathbb {P} _ {n} -P \ | _ {\ mathcal {F}} {\ underset {n} {\ to}} 0,}$

Det vill säga , som${\ displaystyle n \ to \ infty}$

${\ displaystyle \ left | {\ frac {1} {n}} (f (X_ {1})+...+f (X_ {n}))-\ int fdP \ right | \ to 0}$

enhetligt för alla .${\ displaystyle f \ i {\ mathcal {F}}}$

• enhetlig central gränssats :

${\ displaystyle \ mathbb {G} _ {n} = {\ sqrt {n}} (\ mathbb {P} _ {n} -P) \ rightsquigarrow \ mathbb {G}, \ quad {\ text {i}} \ ell ^{\ infty} ({\ mathcal {F}})}$

I det förra fallet kallas Glivenko -Cantelli -klassen, och i det senare fallet (under antagandet ) kallas klassen Donsker eller P -Donsker. En Donsker-klass är Glivenko-Cantelli i sannolikhet genom en tillämpning av Slutskys sats . ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle \ forall x, \ sup \ nolimits _ {f \ in {\ mathcal {F}}} \ vert f (x) -Pf \ vert <\ infty}$${\ displaystyle {\ mathcal {F}}}$

Dessa påståenden är sanna för ett enda , med standard LLN , CLT -argument under regelbundenhetsförhållanden, och svårigheten i de empiriska processerna kommer in eftersom gemensamma uttalanden görs för alla . Intuitivt då kan uppsättningen inte vara för stor, och det visar sig att geometrin spelar en mycket viktig roll. ${\ displaystyle f}$${\ displaystyle f \ i {\ mathcal {F}}}$${\ displaystyle {\ mathcal {F}}}$${\ displaystyle {\ mathcal {F}}}$

Ett sätt att mäta hur stor funktionsuppsättningen är att använda de så kallade täckningsnumren . Täckningsnumret ${\ displaystyle {\ mathcal {F}}}$

${\ displaystyle N (\ varepsilon, {\ mathcal {F}}, \ | \ cdot \ |)}$

är det minimala antal bollar som behövs för att täcka uppsättningen (här antas det uppenbarligen att det finns en underliggande norm på ). Entropin är logaritmen för täckningsnumret. ${\ displaystyle \ {g: \ | gf \ | <\ varepsilon \}}$${\ displaystyle {\ mathcal {F}}}$${\ displaystyle {\ mathcal {F}}}$

Två tillräckliga villkor finns nedan, under vilka det kan bevisas att uppsättningen är Glivenko-Cantelli eller Donsker. ${\ displaystyle {\ mathcal {F}}}$

En klass är P -Glivenko -Cantelli om den är P -mätbar med kuvert F så att den uppfyller: ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle P^{\ ast} F <\ infty}$

${\ displaystyle \ forall \ varepsilon> 0 \ quad \ sup \ nolimits _ {Q} N (\ varepsilon \ | F \ | _ {Q}, {\ mathcal {F}}, L_ {1} (Q)) < \ infty.}$

Nästa villkor är en version av den berömda Dudleys teorem . Om är en funktionsklass så att ${\ displaystyle {\ mathcal {F}}}$

${\ displaystyle \ int _ {0}^{\ infty} \ sup \ ngränser _ {Q} {\ sqrt {\ log N \ vänster (\ varepsilon \ | F \ | _ {Q, 2}, {\ mathcal { F}}, L_ {2} (Q) \ höger)}} d \ varepsilon <\ infty}$

då är P -Donsker för varje sannolikhetsmått P så att . I den sista integralen betyder notationen ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle P^{\ ast} F^{2} <\ infty}$

${\ displaystyle \ | f \ | _ {Q, 2} = \ left (\ int | f |^{2} dQ \ right)^{\ frac {1} {2}}}$.

Symmetrisering

Majoriteten av argumenten för hur man ska binda den empiriska processen, förlitar sig på symmetrisering, maximal och koncentration ojämlikhet och kedja. Symmetrisering är vanligtvis det första steget i bevisen, och eftersom det används i många maskininlärningsprov om begränsande empiriska förlustfunktioner (inklusive beviset för VC -ojämlikhet som diskuteras i nästa avsnitt) presenteras det här.

Tänk på den empiriska processen:

${\ displaystyle f \ mapsto (\ mathbb {P} _ {n} -P) f = {\ dfrac {1} {n}} \ sum _ {i = 1}^{n} (f (X_ {i} ) -Pf)}$

Visar sig att det finns ett samband mellan den empiriska och följande symmetriserade process:

${\ displaystyle f \ mapsto \ mathbb {P} _ {n}^{0} f = {\ dfrac {1} {n}} \ sum _ {i = 1}^{n} \ varepsilon _ {i} f (X_ {i})}$

Den symmetrerade processen är en Rademacher -process , villkorat av data . Därför är det en sub-gaussisk process genom Hoeffdings ojämlikhet . ${\ displaystyle X_ {i}}$

Lemma (symmetrisering). För varje icke -minskande, konvex Φ: R → R och klass av mätbara funktioner , ${\ displaystyle {\ mathcal {F}}}$

${\ displaystyle \ mathbb {E} \ Phi (\ | \ mathbb {P} _ {n} -P \ | _ {\ mathcal {F}}) \ leq \ mathbb {E} \ Phi \ left (2 \ left \ | \ mathbb {P} _ {n}^{0} \ right \ | _ {\ mathcal {F}} \ right)}$

Beviset för Symmetrization lemma bygger på att införa oberoende kopior av de ursprungliga variablerna (ibland kallat ett spökprov ) och att ersätta den inre förväntan av LHS med dessa kopior. Efter en tillämpning av Jensens ojämlikhet kunde olika tecken införas (därav namnet symmetrization) utan att ändra förväntan. Beviset kan hittas nedan på grund av dess lärorika karaktär. ${\ displaystyle X_ {i}}$

Ett typiskt sätt att bevisa empiriska CLT, använder först symmetrisering för att vidarebefordra den empiriska processen till och sedan argumentera villkorat om data, med hjälp av att Rademacher -processer är enkla processer med fina egenskaper. ${\ displaystyle \ mathbb {P} _ {n}^{0}}$

VC -anslutning

Det visar sig att det finns ett fascinerande samband mellan vissa kombinatoriska egenskaper hos uppsättningen och entropinumren. Enhetliga täckningsnummer kan styras av begreppet Vapnik -Chervonenkis -uppsättningar - eller inom kort VC -uppsättningar . ${\ displaystyle {\ mathcal {F}}}$

Tänk på en samling delmängder av provutrymmet . sägs välja en viss delmängd av den ändliga uppsättningen om för vissa . sägs krossa S om den väljer ut var och en av sina 2 ⁿ delmängder. Den VC-index (liknande VC dimensionen + 1 för en lämpligt vald klassificerare uppsättning) av är den minsta n för vilka ingen uppsättning av storlek n splittras av . ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle {\ mathcal {X}}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle W}$${\ displaystyle S = \ {x_ {1}, \ ldots, x_ {n} \} \ delmängd {\ mathcal {X}}}$${\ displaystyle W = S \ cap C}$${\ displaystyle C \ i {\ mathcal {C}}}$${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle V ({\ mathcal {C}})}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle {\ mathcal {C}}}$

Sauer's lemma säger sedan att antalet delmängder som väljs ut av en VC-klass uppfyller: ${\ displaystyle \ Delta _ {n} ({\ mathcal {C}}, x_ {1}, \ ldots, x_ {n})}$${\ displaystyle {\ mathcal {C}}}$

${\ displaystyle \ max _ {x_ {1}, \ ldots, x_ {n}} \ Delta _ {n} ({\ mathcal {C}}, x_ {1}, \ ldots, x_ {n}) \ leq \ sum _ {j = 0}^{V ({\ mathcal {C}})-1} {n \ välj j} \ leq \ vänster ({\ frac {ne} {V ({\ mathcal {C}} ) -1}} \ höger)^{V ({\ mathcal {C}})-1}}$

Vilket är ett polynomiskt antal delmängder snarare än ett exponentiellt tal. Intuitivt betyder detta att ett ändligt VC-index innebär att det har en uppenbar förenklad struktur. ${\ displaystyle O (n^{V ({\ mathcal {C}})-1})}$${\ displaystyle {\ mathcal {C}}}$

En liknande gräns kan visas (med en annan konstant, samma hastighet) för de så kallade VC-subgrafklasserna . För en funktion av subgraf är en delmängd av sådan att: . En samling kallas en VC-subgrafklass om alla undergrafer utgör en VC-klass. ${\ displaystyle f: {\ mathcal {X}} \ to \ mathbf {R}}$${\ displaystyle {\ mathcal {X}} \ times \ mathbf {R}}$${\ displaystyle \ {(x, t): t <f (x) \}}$${\ displaystyle {\ mathcal {F}}}$

Överväga en uppsättning indikatorfunktioner i för diskret empirisk typ av åtgärd Q (eller ekvivalent för någon sannolikhet åtgärd Q ). Det kan då visas att det är anmärkningsvärt, för : ${\ displaystyle {\ mathcal {I}} _ {\ mathcal {C}} = \ {1_ {C}: C \ i {\ mathcal {C}} \}}$${\ displaystyle L_ {1} (Q)}$${\ displaystyle r \ geq 1}$

${\ displaystyle N (\ varepsilon, {\ mathcal {I}} _ {\ mathcal {C}}, L_ {r} (Q)) \ leq KV ({\ mathcal {C}}) (4e)^{V ({\ mathcal {C}})} \ varepsilon ^{-r (V ({\ mathcal {C}})-1)}}}$

Tänk vidare på det symmetriska konvexa skrovet på en uppsättning : att vara en samling funktioner i formen med . Sedan om ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle \ operatorname {sconv} {\ mathcal {F}}}$${\ displaystyle \ sum _ {i = 1}^{m} \ alpha _ {i} f_ {i}}$${\ displaystyle \ sum _ {i = 1}^{m} | \ alpha _ {i} | \ leq 1}$

${\ displaystyle N \ left (\ varepsilon \ | F \ | _ {Q, 2}, {\ mathcal {F}}, L_ {2} (Q) \ right) \ leq C \ varepsilon ^{-V}}$

följande gäller för det konvexa skrovet på : ${\ displaystyle {\ mathcal {F}}}$

${\ displaystyle \ log N \ vänster (\ varepsilon \ | F \ | _ {Q, 2}, \ operatorname {sconv} {\ mathcal {F}}, L_ {2} (Q) \ höger) \ leq K \ varepsilon ^{-{\ frac {2V} {V+2}}}}$

Den viktiga konsekvensen av detta faktum är att

${\ displaystyle {\ frac {2V} {V+2}}> 2,}$

vilket är tillräckligt för att entropi -integralen ska konvergera, och därför kommer klassen att vara P -Donsker. ${\ displaystyle \ operatorname {sconv} {\ mathcal {F}}}$

Slutligen övervägs ett exempel på en VC-subgrafklass. Varje ändligt dimensionellt vektorutrymme för mätbara funktioner är VC-subgraf för index som är mindre än eller lika med . ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle f: {\ mathcal {X}} \ to \ mathbf {R}}$${\ displaystyle \ dim ({\ mathcal {F}})+2}$

Bevis: Ta poäng . Vektorerna: ${\ displaystyle n = \ dim ({\ mathcal {F}})+2}$${\ displaystyle (x_ {1}, t_ {1}), \ ldots, (x_ {n}, t_ {n})}$

${\ displaystyle (f (x_ {1}), \ ldots, f (x_ {n}))-(t_ {1}, \ ldots, t_ {n})}$

är i ett n - 1 dimensionellt delrum av R ⁿ . Ta en ≠ 0 , en vektor som är ortogonal till detta delrum. Därför:

${\ displaystyle \ sum _ {a_ {i}> 0} a_ {i} (f (x_ {i})-t_ {i}) = \ sum _ {a_ {i} <0} (-a_ {i} ) (f (x_ {i})-t_ {i}), \ quad \ forall f \ i {\ mathcal {F}}}$

Tänk på uppsättningen . Den här uppsättningen kan inte plockas ut eftersom om det finns något sådant som skulle kunna innebära att LHS är strikt positivt men RHS är icke-positivt. ${\ displaystyle S = \ {(x_ {i}, t_ {i}): a_ {i}> 0 \}}$${\ displaystyle f}$${\ displaystyle S = \ {(x_ {i}, t_ {i}): f (x_ {i})> t_ {i} \}}$

Det finns generaliseringar av begreppet VC-subgrafklass, t.ex. finns det begreppet pseudodimension. Den intresserade läsaren kan titta in.

VC Ojämlikhet

En liknande inställning övervägs, vilket är vanligare för maskininlärning . Låt är ett funktionsutrymme och . En funktion kallas en klassificerare. Låt vara en uppsättning klassificerare. På samma sätt som i föregående avsnitt definierar du krossningskoefficienten (även känd som tillväxtfunktion): ${\ displaystyle {\ mathcal {X}}}$${\ displaystyle {\ mathcal {Y}} = \ {0,1 \}}$${\ displaystyle f: {\ mathcal {X}} \ to {\ mathcal {Y}}}$${\ displaystyle {\ mathcal {F}}}$

${\ displaystyle S ({\ mathcal {F}}, n) = \ max _ {x_ {1}, \ ldots, x_ {n}} | \ {(f (x_ {1}), \ ldots, f ( x_ {n})), f \ i {\ mathcal {F}} \} |}$

Observera här att det går en 1: 1 mellan var och en av funktionerna i och uppsättningen som funktionen är 1. Vi kan alltså definiera att vara samlingen av delmängder som erhålls från ovanstående kartläggning för varje . Därför är krossningskoefficienten exakt i det föregående avsnittet ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle f \ i {\ mathcal {F}}}$

${\ displaystyle \ max _ {x_ {1}, \ ldots, x_ {n}} \ Delta _ {n} ({\ mathcal {C}}, x_ {1}, \ ldots, x_ {n})}$.

Denna ekvivalens tillsammans med Sauer's Lemma innebär att det kommer att vara polynom i n , för tillräckligt stort n förutsatt att samlingen har ett ändligt VC-index. ${\ displaystyle S ({\ mathcal {F}}, n)}$${\ displaystyle {\ mathcal {C}}}$

Let är en observerad dataset. Antag att data genereras av en okänd sannolikhetsfördelning . Definiera att vara den förväntade förlusten på 0/1 . Naturligtvis eftersom det är okänt i allmänhet har man ingen tillgång till . Emellertid den empiriska risken , given av: ${\ displaystyle D_ {n} = \ {(X_ {1}, Y_ {1}), \ ldots, (X_ {n}, Y_ {m}) \}}$${\ displaystyle P_ {XY}}$${\ displaystyle R (f) = P (f (X) \ neq Y)}$${\ displaystyle P_ {XY}}$${\ displaystyle R (f)}$

${\ displaystyle {\ hat {R}} _ {n} (f) = {\ dfrac {1} {n}} \ sum _ {i = 1}^{n} \ mathbb {I} (f (X_ { i}) \ neq Y_ {i})}$

kan säkert utvärderas. Då har man följande sats:

Sats (VC -ojämlikhet)

För binär klassificering och 0/1 förlustfunktionen har vi följande generaliseringsgränser:

${\ displaystyle {\ begin {align} P \ left (\ sup _ {f \ in {\ mathcal {F}}} \ left | {\ hat {R}} _ {n} (f) -R (f) \ höger |> \ varepsilon \ höger) & \ leq 8S ({\ mathcal {F}}, n) e ^{-n \ varepsilon ^{2}/32} \\\ mathbb {E} \ vänster [\ sup _ {f \ i {\ mathcal {F}}} \ vänster | {\ hat {R}} _ {n} (f) -R (f) \ höger | \ höger] & \ leq 2 {\ sqrt {\ dfrac {\ log S ({\ mathcal {F}}, n)+\ log 2} {n}}} \ end {align}}}$

I ord säger VC -ojämlikheten att när urvalet ökar, förutsatt att det har en ändlig VC -dimension, blir den empiriska 0/1 -risken en bra proxy för den förväntade 0/1 -risken. Observera att båda RHS för de två ojämlikheterna kommer att konvergera till 0, förutsatt att det växer polynomt i n . ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle S ({\ mathcal {F}}, n)}$

Kopplingen mellan denna ram och den empiriska processramen är uppenbar. Här har man att göra med en modifierad empirisk process

${\ displaystyle \ left | {\ hat {R}} _ {n} -R \ right | _ {\ mathcal {F}}}$

men inte överraskande är idéerna desamma. Beviset för (första delen av) VC -ojämlikhet, förlitar sig på symmetrisering och argumenterar sedan villkorat om data med hjälp av koncentrationsskillnader (särskilt Hoeffdings ojämlikhet ). Den intresserade läsaren kan kolla boken satser 12.4 och 12.5.

Referenser

• ^ Vapnik, Vladimir N (2000). Statistisk inlärningsteoris natur . Informationsvetenskap och statistik. Springer-Verlag . ISBN 978-0-387-98780-4.
• Vapnik, Vladimir N (1989).Statistisk inlärningsteori. Wiley-Interscience . ISBN 978-0-471-03003-4.
• ^ van der Vaart, Aad W .; Wellner, Jon A. (2000). Svag konvergens och empiriska processer: med tillämpningar på statistik (andra upplagan). Springer. ISBN 978-0-387-94640-5.
• ^ Gyorfi, L .; Devroye, L .; Lugosi, G. (1996). En probabilistisk teori om mönsterigenkänning (1: a upplagan). Springer. ISBN 978-0387946184.
• Se referenser i artiklar: Richard M. Dudley , empiriska processer , Shattered set .
• ^ Pollard, David (1990).Empiriska processer: teori och tillämpningar. NSF-CBMS Regional Conference Series in Probability and Statistics Volume 2. ISBN 978-0-940600-16-4.
• Bousquet, O .; Boucheron, S .; Lugosi, G. (2004). "Introduktion till statistisk inlärningsteori". I O. Bousquet; U. von Luxburg; G. Ratsch (red.). Avancerade föreläsningar om maskininlärning . Föreläsningsanteckningar i artificiell intelligens. 3176 . Springer. s. 169–207.
• Vapnik, V .; Chervonenkis, A. (2004). "Om den enhetliga konvergensen av relativa frekvenser av händelser till deras sannolikheter". Teori Probab. Appl . 16 (2): 264–280. doi : 10.1137/1116025 .