A Google új mesterséges intelligenciája egyszerű, szerkeszthető kóddá alakítja a komplex modelleket

A szerzők: Walker Ravina, walkerravina@google.com (Google) Ethan Sterling, esterling@google.com (Google) Olexiy Oryeshko, olexiy@google.com (Google) Nathan Bell, nathanbell@google.com (Google) Honglei Zhuang, hlz@google.com (Google) Xuanhui Wang, xuanhui@google.com (Google) Yonghui Wu, yonghui@google.com (Google) Alexander Grushetsky, grushetsky@google.com (Google) A szerzők: Székesfehérvár, Walkerravina@google.com (Google) Szilárd István, esterling@google.com (Google) Olexij Oryeshko, olexiy@google.com (Google) Születési név: Nathan Bell, nathanbell@google.com Honglei Zhuang, hlz@google.com (Google) Zsuzsa János, xuanhui@google.com (Google) Yonghui Wu, yonghui@google.com (Google) Alekszandr Grushetszkij, grushetsky@google.com (Google) absztrakt A modellezés célja, hogy a tanári modell ismereteit hűségesen olyan modellre továbbítsa, amely gyorsabb, általánosabb, értelmezhetőbb, vagy más kívánatos tulajdonságokkal rendelkezik. Az emberi olvashatóság fontos és kívánatos szabvány a gépi tanult modell értelmezhetősége szempontjából. Az olvasható modellek átláthatók és felülvizsgálhatók, manipulálhatók és telepíthetők, mint a hagyományos forráskód. Ennek eredményeképpen az ilyen modelleket a gépi tanulás kontextusán kívül is lehet javítani, és szükség esetén manuálisan szerkeszteni. Tekintettel arra, hogy az ilyen modellek közvetlen képzése nehéz, javasoljuk, hogy a hagyományos módszerekkel értelmezhető modelleket képezzék, majd tömör, ember által olvasható kódba destillál A javasolt desztillációs módszertan közelíti meg a modell egyedi numerikus funkcióit a darab-lineáris görbékkel lokalizált módon. A kapott görbék modelljei pontosak, tömörek, emberi olvashatóak és jól szabályozottak az építés által. Leírunk egy darab-lineáris görbékbe illesztő algoritmust, amely hatékonyan és megbízhatóan magas színvonalú eredményeket eredményez a felhasználási esetek széles skáláján. demonstráljuk az általános desztillációs technika és a görbékbe illesztő algoritmus hatékonyságát négy adatkészlet segítségével az osztályozási, regressziós és rangsorolási feladatok között. CCS koncepciók az . Computing methodologies Machine learning approaches kulcsszavak Modell desztilláció; emberi olvasható; darabos-lineáris görbék 1 Bevezetés Az értelmezhető modellek kritikusak a nagy tételek döntéshozatali forgatókönyvekhez [ Az ilyen típusú gyógyszerek alkalmazása, a gyógyszerek alkalmazása, a gyógyszerek alkalmazása, a gyógyszerek alkalmazása, a gyógyszerek alkalmazása, a gyógyszerek alkalmazása ( Az egyéni hozzájárulásoknak ellenőrizhetőnek és érthetőnek kell lenniük az eredmények átláthatóságának, elszámoltathatóságának és méltányosságának biztosítása érdekében. 21 Az e.g A klasszikus generalizált additív modellekben (GAM-ok) az univariátus funkciók széles körben használatosak. ], a modell az univariate alakú funkciók összege, 11 ahol a xi ’s n funkciók és a fi ’s az alakfunkciók. Egy ilyen modell egyszerű, de gyakran kevésbé pontos, mint egy modell a funkciók kölcsönhatásaival. Az [ ] kimutatták, hogy a páros jellegű interakciók korlátozott számának hozzáadása lehetővé teszi a GAM-stílusú additív modellek számára, hogy a teljes mértékben interaktív modell pontosságának jelentős részét rögzítsék. Az al 18 vagy a termékek csoportjainak jellemzői, ahol az egyik funkció (vagyis fi) nagyságát egy másik „kontextus” funkció (i.e.ci) funkciója (vagyis gi vagy gi,j) modulálja [32]. ahol a külső funkció gi rögzíti a nemlineáris viselkedést [7]. Valójában a Kolmogorov–Arnold reprezentációs elmélet [16, 27] garantálja, hogy az n bemenetek minden folyamatos többváltozós funkciója 2n ilyen kifejezés összegeként képviselhető, Gyakorlatilag gyakran elegendő egy külső funkció, amely értelmezhető modellt eredményez. A klasszikus GAM modellekben a spline-eket alakú funkcióként használják [ ]. Egy másik gyakran használt alakú funkció a darab-lineáris funkciók [ Ezek a jelölések kis mennyiségű változót tartalmaznak ( . csomópontok) és így tömörek és emberi olvashatóak. Azonban az ilyen ábrázolások közvetlen optimalizálása gyakran kevésbé pontos modelleket eredményez, mint az alternatív modell ábrázolások. Az [ ] kimutatták, hogy a tanulási spline GAM-ek kevésbé pontosak, mint a tanulás csomagolt döntéshozatali erdei GAM-ek. Kísérleteink hasonló eredményeket mutatnak a szelektív-lineáris görbékből álló GAM-ek közvetlen optimalizálására a Stochastic Gradient Descent (SGD) módszerekkel. Általánosságban elmondható, hogy a döntéshozatali erdei GAM-eket használó modellreprezentációk előnyösek a modelloptimalizálás során, de a kapott modellek nem emberi olvashatóak. Ez akkor is így van, ha létezik egy egyszerűbb modell egy tömör, emberi olvasható formával, amely összehasonlítható pontosságot biztosít. 11 30 Az e.g Az al 17 A modellekből származó desztillációs munka ihlette, amelyben viszonylag kis döntéshozatali erdőket vagy ideghálózatokat lehet desztillálni sokkal nagyobb csoportokból, de nem közvetlenül az adatokból, hogy megfeleljenek a komplex modellek pontosságának. az , ], javasoljuk, hogy a modellek optimalizálása után külön eljárás során az értelmezhető modelleket olvasható képviseletekké destilláljuk. Ez elválasztja a kezdeti, megtanult modellképviseletet a végleges, közzétett modellképviselettől. Például a javasolt desztillációs módszertan alkalmazható az additív modellekre, amelyeket csomagolt, fokozott döntéshozatali fák használatával képeznek [ ], valamint az additív neurális hálózatok 5 12 17 [ 2 ] 32 Egyéb Ebben a cikkben leírunk egy olyan technikát, amellyel az egységes alkatrészekből álló modelleket emberi olvasható ábrázolásokká destilálhatjuk, különösen a szakaszban leírt darab-lineáris görbékre. A destillációs technikánk kimenetelét a Listing illusztrálja A figurát which show textual and graphical representations of piecewise-linear curves obtained by applying our approach to a decision forest GAM trained on the COMPAS dataset (described in Section A desztillált modell a döntési erdő GAM modelljének tömör ábrázolása, és az ember által olvasható forráskódra alakul át. Innen fogjuk használni a „görbeket” a darabos lineáris görbékre, a „görbék modelleket” a modellekre, ahol minden egyes komponens görbék, és a „kódot” a görbékmodellek vagy görbék szöveges ábrázolására. A két 1 1, az Az 1.) A dokumentum többi része a következőképpen van felépítve.Az előzetes bemutatás után Beszéljünk a görbe modellek használatának előnyeiről Ezután leírjuk a lokalizált desztillációs folyamatot a szakaszban és a darabos lineáris megközelítés algoritmusa, néha szegmentált regressziónak nevezik [ ], a görbe modellek létrehozásához a szakaszban Végül bemutatjuk a kísérleti eredményeket az adatkészletek esetében: COMPAS, FICO, MSLR-WEB30K és CWS a szakaszban A dokumentumot fejezd be a fejezetben 2, 3. 4 30 5. 6 7. 2 Előzetes A papíron keresztül konkrét példaként fogjuk használni a papíron használt adatkészleteket, hogy megmagyarázzuk módszereinket. Így először leírjuk őket ebben a szakaszban. 2.1 Adatbázisok A következő négy adatkészletet használtuk a különböző beállítások megjelenítésére: osztályozás, regresszió és rangsorolás. A COMPAS adatkészlet1 egy ProPublica vizsgálat eredménye [4] a Broward megyében, Floridában, a vádlottakra vonatkozó sajátos COMPAS modell pontszám lehetséges faji előítéletére vonatkozóan. Az adatkészletet széles körben tanulmányozták az előítélet, a méltányosság és az értelmezhetőség összefüggésében [8, 9, 14, 23]. A címkék bináris jellegűek, és jelzik, hogy az egyén számára egy bizonyos időszakon belül előfordult-e visszaesés. Az osztályozó pontosságának mérésére a fogadó működési jellemzői görbe (AUC-ROC) alatt található területet használjuk. A COMPAS 6 jellemzővel rendelkezik, amelyek közül négy példaként szerepel ebben a dokumentumban: kor, priors_count, length_of_stay A FICO adatkészlet [1] valós, anonimizált hitelkérelmekből és kockázati pontszámokból áll. A címkék egy egyén kockázati pontszámai. A regresszor pontosságának mérésére a gyökér átlagos négyzethibát (RMSE) használjuk. A FICO-nak 24 fea-ture-ja van, és példaként két funkciót használunk papírunkban: MSinceMostRecentDelq, Months Since Most Recent Delinquency; PercentTradesWBalance, Percent Trades with Balance. Az MSLR-WEB30K adatkészlet [19] egy széles körben használt tanulás-to-rangsor benchmark adatkészlet. A címkék dokumentumonkénti releváns ítéletek. A rangsor pontosságának mérésére k = 5 (NDCG@5) normalizált kedvezményes kumulatív nyereséget használunk. Az MSLR-WEB30K jelentősen nagyobb mind a funkciók számában (136) és a képzési példák számában (~2,000,000 keresztvalidációs hajtásonkénti). Ezt használjuk a görbe-közelítő algoritmusunk összehasonlításához a pwlf [13], egy nyilvánosan elérhető alternatíva, a pontosság, a robusztusság és a hatékonyság alapján. Két funkciót használunk példaként papírunkban: feature_0011, A Chrome Web Store (CWS) adatkészlet egy privát és anonimizált adatkészlet, amely a Chrome Web Store naplóiból származik. Minden lekérdezés megfelel a Chrome Web Store látogatásának. Az egyes lekérdezések belsejében lévő elemek azok voltak, amelyeket a felhasználónak mutattak. címkék megfelelnek a felhasználói műveleteknek, mint például a kattintás, a telepítés, a rangsor pontossága. A Chrome Web Store-ból származó hasonló, de különálló adatkészletet korábban Zhaung és társai tanulmányozták [32]. A korábbi munkákkal ellentétben ebben az esetben nem használunk lekérdezésszintű „kontextus” funkciókat, hanem csak 14 elemszintű funkciót használunk. A lekérdezések is eltérőek. Mindegyik esetben egy döntési erdő GAM-t destillálunk, és értékeljük a destillált görbe modellek pontosságát.A COMPAS és a FICO adatkészletek magas tételt jelentő tartományokat képviselnek [ ] amelyben az alábbiakban tárgyalt görbe modellek előnyei különösen meggyőzőek. FICO, MSLR-WEB30K, és CWS korábban az értelmezhetőség összefüggésében tanulmányozták Továbbá az MSLR-WEB30K eredményei azt mutatják, hogy ennek a megközelítésnek a pontossága nem korlátozódik a kis adathalmazokra. 21 [ 2 ] 7 , 18 Az 32 Egyéb 2.2 Lineáris görbék A lineáris görbület ( ) az S = [(xk, yk )]K k = 1 vezérlőpontok listája határozza meg, amelyeken a görbe át kell haladnia. a vezérlőpontok között a kimeneti y értékeket lineáris interpolációval határozzák meg a szomszédos vezérlőpontok között. A baloldali vagy jobboldali vezérlőpontokon túl a kimeneti értékeket a szomszédos vezérlőpont yk értékére korlátozzák. PWLCurve A legtöbb esetben az érdeklődés 5 vagy 6 vezérlőpontja, 4 vagy 5 belső szegmens meghatározása elegendő a kívánt viselkedés rögzítéséhez. Lehetővé tesszük az opcionális x-transzformációt, amelyet az fx argumentummal határoztunk meg, hogy a különböző skálákkal rendelkező adatokhoz illeszkedjenek a görbék. Amikor egy x-transzformáció jelen van, azt az összes vezérlőpont bemeneti értékére és x-értékére alkalmazzák, majd a transzformált térben lineáris interpolációt hajtanak végre. Támogatjuk az identitást (alapértelmezett), log, log1p és symlog1p transzformációkat. Itt a symlog1p definíciója sgn(x) * log1p(abs(x)) és nagyon változó funkció 3 Háttér és motiváció Az értelmezhető modellek kritikus fontosságúak a nagy tőkeáttételű döntésekhez [21], és számos előnnyel járnak a bonyolultabb modellstruktúrákkal szemben [ az , ]. In this section we explain how distilling interpretable mod-els into curve models reinforces these benefits and addresses a variety of real-world engineering challenges. Here, one underlying theme is that distilling models into human-readable source code . 6 10 egy új gépi tanulási problémát egy megalapozott szoftverfejlesztési problémára csökkenti a meglévő megoldások bőségével 4.1 Nagyobb átláthatóság Egy modell átlátható, ha olyan szöveges vagy grafikai ábrázolást biztosít, amely lehetővé teszi viselkedésének átfogó megértését.Az egyik módszer, amelyben a javasolt módszer nagyobb átláthatóságot biztosít, a modell grafikai ábrázolásainak egyszerűsítése, miközben megtartja alapvető jellemzőit.Gyakran állítják, hogy az értelmezhető modell alakjainak cselekményei Bár ez az állítás szorosan igaz, általában félrevezető. Hacsak nem adunk konkrét útmutatást, az emberek természetesen csökkentik a telek bizonyos finom részleteit, amikor a modell megértését fejlesztik. Az értelmezhető modellek tömör ábrázolására való desztillálásával eldobjuk az idegen char-aktőröket, és csökkenti a modell megértéséhez szükséges mentális erőfeszítést. Például nem azonnal nyilvánvaló, hogy az egyénnek milyen megértésnek kell származnia a feature_0011 (testáram hossza) és a feature_0128 (link szám) jellemzőiből az eredetileg megtanult MSLR-WEB30K modellben, amely a képen látható Valójában a különböző egyének minőségi szempontból eltérő megértéseket vonhatnak le ezekből a grafikus ábrázolásokból. azonban, figyelembe véve azt a további tudást, hogy a desztillált görbe modellt a képen szereplő átfedett görbék képviselik. Ha közel azonos pontossággal rendelkezik, a megfigyelő sokkal erősebb következtetéseket vonhat le a modell alapvető jellemzőiről. Az értelmezhetőséget még tovább növelheti a monotonitás korlátozása. Pontos leírás 2. 2 6.4 Az Nyilvánvaló, hogy amikor a desztilláció összehasonlítható pontossággal egyszerűbb modellt eredményez, azt mondanánk, hogy a desztillációs folyamat sikeres volt. Azonban azok az esetek, amikor a desztilláció alacsonyabb pontosságú modellt eredményez, további vizsgálatot igényelnek, mert a látszólagos „hibát” gyakran a tanármodell alapvető jellemzőihez lehet tulajdonítani, amelyeket nem adtak át sikeresen a diáknak. Ennek a jelenségnek az egyik reprezentatív példáját vizsgáljuk. Bár ennek az elvnek a teljes megvitatása túlmutat e tanulmány hatókörén, megjegyezzük, hogy az ötlet a strukturális korlátozások használatának kiterjesztésének tekinthető a „interpretálható” modellek meghatározására, amelyeket éppen most alkalmaznak a modellben az egyes funkciók szerkezetére. A korlátozott számú ellenőrző pontot tartalmazó görbék) átláthatóságát megkérdőjeleznék. mert megsértik az emberi értelmezhetőség előírt fogalmát 6.2 Egyéb Az e.g 3.2 Konstruktív szabályozás The proposed method can also be viewed as a post-hoc regularization process that is completely compatible with, and complementary to, optimization-based regularization techniques ( L1/L2 büntetések vagy monotonitási korlátozások). A szabályszerűsítés összefüggésében a tömörítésre összpontosítunk a minimális leírás hosszúságának elvével összhangban [ ] a modell kiválasztásához. Ustun és Rudin [ ] hasonló érvelést alkalmaztak a kis, egész értékű súlyokkal rendelkező lineáris modellek motiválására. A görbék korlátozott leírási hossza korlátozott kapacitást biztosít az idioszinkratikus viselkedés-ior rögzítésére. Ennek eredményeként a görbék desztillációja sikeresen eltávolítja az aberrációkat a tanári modellfunkciókból. A figurát Minél kevesebb a szegmens, annál nagyobb a hatás. A legrövidebb görbe modell megtalálása érdekében a javasolt módszert a vezérlőpontok számának csökkenésével ismételten alkalmazhatjuk. és a görbe megközelítés algoritmusa (lásd Bár nehéz közvetlenül összehasonlítani a különböző funkcionális ábrázolásokkal rendelkező modelleket, a megfelelő kód hosszának és olvashatóságának összehasonlítása tanulságos. Az e.g 28 24 1 2. 4) Az 5 ) A görbe alapú szabályszerűsítés egyik gyakorlati előnye az, hogy a szabályosságot az építés kényszeríti, és az egyes görbék összetettsége könnyen látható és számszerűsíthető. Ezért a görbe modelleket elfogadó szervezetek objektív iránymutatásokat állíthatnak be a modell összetettségére vonatkozóan, amelyeket a fejlesztők megjósolhatnak a modelljelöltek jóváhagyása során. Az ilyen iránymutatások megadhatják a görbe szegmensek maximális számát, a görbe vezérlőpontonkénti jelentős számjegyek maximális számát vagy a görbe monotonitását. Hasonlóan a kriptográfiában a semmiből származó számok használatához. ], a görbe modellek lehetővé teszik a fejlesztők számára, hogy megelőzően kezeljék a potenciális gyengeségek gyanúit, és konstruktívan bizonyítsák egy adott modelljelölt robusztusságát. Általánosságban elmondható, hogy a görbe modellek körüli fejlesztés szabványosítása egyszerű módja annak, hogy a szervezetek szisztematikusan érvényesítsék a legjobb gyakorlatokat, megvédjék a gyakori hibákat és csapdákat, és felgyorsítsák a modell ellenőrzését és jóváhagyását. . vezetők, termékmenedzserek stb.) részt venni ebben a jóváhagyási folyamatban. 29 Az e.g 3.3 Olvasható, szerkeszthető kód A görbe modellkód olvasható, felülvizsgálható, egyesíthető és verzióztatható, mint a hagyományos forráskód. Meg lehet érteni, hogy egy görbe modell hogyan viselkedne új vagy szélsőséges körülmények között azáltal, hogy mentálisan „értékelné” a modellt hipotetikus „mi lenne?” forgatókönyvek alatt anélkül, hogy további eszközökre lenne szükség. A modelleknek a hagyományos forráskód-ellenőrzési folyamatnak való alávetése megkönnyíti a modell jellemzőinek szigorúbb vizsgálatát és a nagyobb elszámoltathatóságot, mint a nem olvasható modellekkel lehetséges. Valójában a „modellek felülvizsgálata” a forráskód-ellenőrzés révén biztosítja, hogy a COMPAS modell esetében maga a jelölt modell – nem a modell különálló, potenciálisan összeegyeztethetetlen leírása vagy műalkotása, vagy a képzés módja – a felülvizsgál Az [ ] megvitatta, hogyan lehet egy ilyen megközelítés a képzés elfogult jellemzőkkel, majd eltávolítja őket potenciálisan jobb, mint egyszerűen a képzés elfogult jellemzők nélkül. 1. Az al 2 A modell átláthatósága elengedhetetlen a nagy tételekkel kapcsolatos döntések összefüggésében [ A büntető igazságszolgáltatásban, a pénzügyekben, az egészségügyben és más területeken felmerülő problémák.A modell teljes forrását egyszerű, hordozható, ember által olvasható kódban biztosítva a modellek átláthatók. ], amelyeket univerzálisan érthető if-then nyelven fejeznek ki, a görbe modellek feláldozzák a hozzáférhetőséget a nagyobb kifejeződés és az általános célú alkalmazás érdekében. 21 3 3.4 Együttműködési modell kialakítása A görbe desztilláció kompatibilis bármely algoritmussal vagy modellezési technikával, amely egyvariált funkciókat eredményez.A kísérletek szakaszában a javasolt technikát alkalmazzuk az erdei GAM-ok több adatkészleten történő meghatározására. A javasolt technikát az ideghálózatokon keresztül megtanult GAM-okra, valamint a korlátozott interakciókkal rendelkező hasonló ideghálózatokra alkalmazta. A görbe modellek köré szervezett együttműködési fejlesztés lehetővé teszi a mérnökök számára, hogy különböző eszközök, technikák vagy platformok sokaságát alkalmazzák egy (potenciálisan nagyméretű) modell összetevőinek optimalizálására. A mérnökök szabadon választhatnak olyan modellezési megközelítést, amely maximalizálja termelékenységüket, hasonlóan ahhoz, ahogyan a mérnökök több IDE-t, kódformázót vagy lintert használnak szoftverek együttes fejlesztésére. 32 3.5 Közvetlen bevetés A görbe modellek gyorsan értékelhetők és egyszerűen telepíthetők. Mivel az értékelés minimális számításokat igényel - csak egy maroknyi lebegőpont-művelet per görbe - a görbe modellek jól alkalmasak a teljesítménykritikus alkalmazásokhoz. egy COMPAS modell C++ megvalósítását mutatja 2 szegmensben. Általában a görbe modellek egyszerűen telepíthetők, mert sokféle integrációs lehetőséget kínálnak. A görbék beágyazhatók a konfigurációs fájlokba, átadhatók CGI paramétereken keresztül, kézzel beágyazhatók összetett alkalmazásokba egy darabos módon, szisztematikusan lefordíthatók célképzésre, vagy néhány fokozatos kiterjesztéssel értékelhetők a meglévő futtatási rendszerek. 2 4 LOCALIZED DISTILLATION A desztillációs folyamatunk két bevitelt igényel: egy tanármodellt, amely egy vagy több univariátus funkciót tartalmaz, és egy reprezentatív adatkészletet (általában a képzési adatok). A módszerünk különbözik a hagyományos desztillációs technikáktól, mivel (1) minden univariátus funkciót elszigetelten desztillálunk, és (2) az egyes univariátus funkciók megközelítésekor az átlagos négyzethibára (MSE) optimalizáljuk. használja a megközelítés algoritmus leírt szakaszban Ha a tanármodell más univariátus funkciókba beágyazott univariátus funkciókat tartalmaz, akkor a forrásfunkciókat alulról felfelé helyettesítjük. PWLCurve 5. A végleges modellt úgy építjük fel, hogy minden eredeti egyváltozós funkciót helyettesítünk a A közeledés. PWLCurve Hagyományosan a modell destillációja ugyanazt (vagy legalábbis hasonló) célt használó globális optimalizációt foglal magában az eredeti tanármodell képzésével. Ez a cél eltérhet a pontorientált MSE céltól. Például a rangsorolási célok gyakran párorientált definíciókkal rendelkeznek. Miért javasoljuk a lokalizált optimalizálást egy MSE célt használva minden körülmények között? Az elsődleges válasz az, hogy az értelmezhető modellek összefüggésében jelentős érték van az egyes forráskódú funkciók és a célfunkciók közötti erős egy-egy-egy-megfelelés fenntartásában. Figyelemre méltó, hogy ez lehetővé teszi számunkra, hogy a tanármodellben minden egyes alakfunkciót a megfelelő görbe cseréje ellen Azonnal elmondhatjuk, hogy az x1 alakú funkcióját nem közelítette meg jól egy görbe. A kísérletek szakaszában azt mutatjuk, hogy a szinte minden alakú funkció értelmes viselkedése pontosan rögzíthető három-öt szegmensű görbékkel. 5 A globális optimalizálási megközelítés ( A célmodell valamennyi görbületének paramétereinek egyidejű optimalizálása (probléma-specifikus metrikával) pontosabb eredményt eredményezhet, számítástechnikai szempontból drágább, és hiányozna a tanármodellhez hasonló egy-egy megfelelés, ami megnehezítené a desztillációs kudarcok diagnosztizálását. Az E 5 PIECEWISE-LINEAR CURVE APPROXIMATION Tekintettel a f (x) → y egységes számfunkcióra, a célunk az, hogy c (x) → y, amely hűen megközelíti a f (x) azáltal, hogy minimalizálja az MSE(c(x), f (x)) mintadatok. Mennyi metrikus veszteség keletkezik, ha a képzett modellben minden c (x) helyébe a megfelelő f (x) lép. PWLCurve Az E Ezenkívül a módszertan gyakorlati sikerét is de- A megközelítési algoritmus szilárdságára és hatékonyságára összpontosít. Ahhoz, hogy lehetővé tegye a görbe desztilláció szisztematikus használatát a modellképzési csővezetékekben, a megközelítési algoritmusnak minimális konfigurációval kell futnia. lineáris megközelítés algoritmusa, így a gyakorlatban a felhasználóknak csak a és A paraméterek monotonitása = 5 szegmens és =Hamis elegendő ahhoz, hogy nagy pontosságot kapjon (amint azt kísérleteink bizonyítják), kívánatos vizsgálni, hogy a modellt tovább lehet-e egyszerűsíteni kevesebb szegmenssel vagy monotonitás korlátozásokkal. . less than 1 second per function) which enables interactive analysis via Jupyter notebooks [ ] vagy más eszközök. Ezek a gyakorlati megfontolások tájékoztatták a különböző döntéseket a tervezés Különösen egy olyan algoritmust részesítünk előnyben, amely gyorsan és megbízhatóan magas pontosságú eredményeket eredményez minimális konfigurációval, szemben azzal, amely feláldozza ezeket a gyakorlati megfontolásokat a marginális pontosság növelése érdekében. pwlfit num_segments mono num_segments mono Az e.g 15 pwlfit Ebben a fejezetben bemutatjuk a kiemelkedő jellemzőket és a figyelemre méltó jellemzőket. Felhívjuk az érdeklődő olvasókat, hogy olvassák el a nyilvánosan elérhető forráskódot. [ megtekintése ] a további részletekért. pwlfit pwlfit 22 5.1 Algoritmus Az (x, y, súly) pontok listáját és a k szegmensek kívánt számát figyelembe véve keresünk egy minimálisra csökkenteni az átlagos négyzethibát, MSE. A k-szegmenseket a k + 1 vezérlőpontok jellemzik – az x-csomópontok és azok megfelelő y-csomópontjai. Csak az x-csomópontokat figyelembe véve megoldhatjuk az optimális y-csomópontok és az ebből eredő hiba lineáris legkisebb négyzetkifejezését. Mivel nem ismerjük a helyes x-csomópontokat, a lehetséges x-csomópontok terét keresjük, és minden lépésnél megoldjuk a legkisebb négyzetkifejezését a hiba kiszámításához.2 PWLCurve PWLCurve A teljesítmény érdekében véletlenszerűen egy nagy adatkészletet körülbelül egymillió pontra tesztelünk, mielőtt beilleszkednénk. Csökkentjük a mintavételt, hogy csökkentsük a rendezés költségeit, ami a nagy adatok futási idejét uralja. Ez a mintavétel elhanyagolható minőségveszteséget eredményez. az x-értékeket az adatokból, a kumulatív tömeggel egyenletesen elválasztva, és keresse meg az x-csomópontok kombinációit a mintavételezett jelöltekből. Az alapértelmezett 100 mintát használva a jelöltjeink a kumulatív tömeg (0%, 1.01%, . . . , 98.9%, 100%) x-értékek. 5.1.1 A kezdeti mintavételi eljárás. num_samples Az ismétlődő x-értékekkel rendelkező adatok esetében egyes jelöltjeink többszörösek lesznek. Például a COMPAS-adatkészlet hosszúság_for_stay funkciójában szereplő értékek 55%-a 0 vagy 1. Ilyen esetekben ismétlődően újratanulmányozunk magasabb arányban (például 0%, 0,505%, 1,01%, stb.), amíg megfelelő számú különálló jelöltet nem gyűjtünk össze, soha nem haladva meg a megadott értéket. A paraméter. 5.1.2 A csomópontok diszkréciója num_samples Annak érdekében, hogy minimálisra csökkentsük az egyes lineáris legkevesebb négyzet lépések költségeit, az adatokat egy új technikával kondenzáljuk, amelyet a Melléklet leír. adva A teljes adatot két szintetikus pontra kondenzálhatjuk a két szomszédos pár jelöltet illetően, összesen 2 * ( - 1) szintetikus pontok. minden olyan funkció esetében, amely a szomszédos jelölt x-csomópár között lineáris, amit a diszkrét jelölt kiválasztása garantál. 5.1 A kondenzáció A b. num_samples num_samples 𝑥-knots, these condensed points perfectly recreate the loss of that function over the full data set. We run our linear least squares solver on the condensed points instead of the full data set, which reduces our cost per solve from O(num_points) to O( ). This is purely a performance optimization, with no quality implications. num_samples After discretization, the solution space consists of num_samples num_segments+1 𝑥-knot combinations, which is still too large for an exhaustive search. To make the search tractable we use a greedy search heuristic that optimizes one 𝑥-knot at a time. Specifically, at each step of the process we evaluate the error associated with each candidate 𝑥-knot, and keep the candidate that yields the least error. With this approach, we optimize in two stages. We begin with a single 𝑥-knot as our solution, and greedily add the best remaining candidate 𝑥-knot until our solution consists of (num_segments + 1) 𝑥-knots. Then we cycle through our solution, removing one 𝑥- knot at a time and replacing that 𝑥-knot with the best remaining candidate 𝑥-knot, which could be the same 𝑥-knot that we just removed. We continue this cycle of iterative improvements until our solution converges, or until we’ve exceeded the maximum number of iterations (defaulting to 10 iterations). 5.1.4 Globális optimalizálás Greedy Search . pwlfit can impose a minimum and/or maximum slope on the solution via bounded least squares. Instead of solving the least squares expression directly for the 𝑦-knots, we solve it for the deltas between adjacent 𝑦-knots. 5.1.5 Slope Constraints & Monotonicity. Then we impose a min/max slope by bounding the deltas. Slope restrictions can be used to limit the spikiness of curves, but we primarily use them to impose monotonicity. For example, specifying =0 korlátozza a monoton nem csökkenő funkciókat, miközben =0 restricts to monotonically non-increasing functions. Specifying a greater than 0 or a kevesebb, mint 0 korlátozza a szigorúan növekvő vagy csökkenő funkciókat. can deduce the direction of monotonicity by applying iso-tonic regression [ ] to the condensed points. We fit an increasing and a decreasing isotonic regression, and use the direction that minimizes mean squared error. The user can override this behavior by specifying the direction explicitly or by disabling monotonicity entirely. min_slope max_slope min_slope max_slope pwlfit 26 can also interpolate in a transform of feature engineering. transforms the 𝑥-values before learning the curve. Specifically, Válasszon egy X-transzformációs jelöltet. , among , vagy az x-értékek tartományán alapul, majd folytassa ezt az átalakítást, ha növeli a Pearson-korrelációt Alternatív megoldásként a felhasználó megadhat bármilyen szigorúan növekvő 1D átalakítást, vagy megadhatja az identitás átalakítást az átalakítás kikapcsolásához. 5.1.6 Input Transformations. pwlfit pwlfit pwlfit fx log log1p symlog1p fx 6 EXPERIMENTS 6.1 Distillation Accuracy Table and Figure show the results obtained from experiments on the different datasets. A complete set of results can be found in Table in Appendix The results of applying our distillation technique with our piecewise-linear approximation algorithm are presented as Különböző számú szegmensek használatából származó eredményeket mutatunk be monotonitási korlátozással és egyéb alapértelmezett paraméterek nélkül. Minden esetben a vezérlőpontokat négy jelentős számjegyre vágtuk le. 1 4a 2 A. pwlfit • We directly learn the curves with the Adadelta[ ] optimizer. We initialize the 𝑦 values of the control points as zeros. For the 𝑥 values of the control points we use the quantiles for numerical features ( . 0%, 50%, 100% for a three point, two segment curve) or all unique values for categorical features. We then apply Adadelta to optimize the 𝑦 values. Simultaneously optimizing 𝑥 and 𝑦 values was also attempted, but the results were always worse than optimizing SGD: 31 e.g 𝑦 values alone. • Neural Additive Models (NAMs) [ ] is another method for learning interpretable models proposed by Agarwal . We present their result for reference where applicable. NAM: 2 Az al • We train a bagged, boosted decision forest allowing feature interactions to demonstrate the accuracy of a non-interpretable, high-complexity "black box" model. Interacting forest: • : We train a bagged boosted decision forest GAM by restricting each tree to use only one feature. This model is also the source model for our distillation technique. GAM forest • We apply our distillation technique using an alternative piecewise-linear approximation algorithm pwlf: pwlf [13]. On each dataset we used five fold cross validation and present the metric mean and sample standard deviation across folds. We used three different metrics to evaluate accuracy: AUC-ROC, RMSE, and NDCG@5 for the three different tasks of classification, regression, and ranking. Further details on our experimentation setup can be found in Appendix and further details on the datasets, labels, and metrics can be found in Preliminaries A 2.1 Egyéb Our results show that applying our distillation technique with 4-5 segments with olyan modelleket állít elő, amelyek mind a forrás GAM-erdő, mind a NAM-modellekhez hasonlóan pontosak az összes adatkészlet esetében, kivéve a CWS-t, ahol kis szakadék marad. below. In the case of the COMPAS dataset these models are as accurate as full complexity models. Applying our technique with produces competitive results, albeit less accurate on the MSLR-WEB30K dataset. By contrast, the results show that learning curves directly via SGD is less general. On the FICO and CWS datasets more segments are required to achieve accuracy comparable to the GAM forest models. On the MSLR-WEB30K dataset the accuracy is inferior even with many more segments. pwlfit 6.2 pwlf The consistent accuracy of applying our distillation approach with on these four datasets and three separate tasks (classification, regression, learning to rank) demonstrates that the process is not sensitive to either the specific data or the top level objective being used. pwlfit 6.2 Distillation Failures A szakaszban we explained how distillation yielding a model with inferior accuracy warrants further investigation because the purported "failure" can often be attributed to essential yet non-interpretable characteristics of the teacher model not transferring to the student model. The accuracy gap observed on the CWS dataset is an example of this phenomenon. Figure shows the worst two fits from the CWS dataset. The plots have been redacted to maintain the privacy of the dataset. For each plot it is clear that the original teacher submodel had some non-interpretable behavior which was lost during distillation. This is most evident for feature 𝑥1, the worst offender, where the output is highly erratic. If the original teacher submodel is not distilled for these two features then the accuracy gap between the original teacher model and 5 segment non-monotonic distillation drops from 0.0059 to 0.003 ( . ~50% of the gap is recovered). 3.1 5 i.e To identify the above two failures we applied the following method. • Begin with the original teacher model. For each submodel compute the metric delta against the teacher model from distilling only that submodel and no others. • Perform the above on each cross validation fold using the validation set and average the metric deltas across folds. • A jellemzőket a kapcsolódó méterdelta szerint rendezzük, hogy meghatározzuk a legrosszabb lepárlásokat. 6.3 Efficiency & Robustness The experiments of the previous section showed that more accurately distills the source model across datsets than . We also found on the MSLR-WEB30K dataset that is more efficient and robust than . Figure shows per fit metrics from the first fold of the MSLR-WEB30K dataset as the number of segments varies without monotonicity. The top plot shows the time in seconds, as measured on a ThinkStation P520, to fit each of the 136 submodels of the source GAM forest. We find that is faster in the average case as the number of segments increases, and has a narrower distribution. The bottom plot shows the RMSE of each fit against the 136 submodels of the source GAM forest. We again find that performs favorably in the average case with a narrower runtime distribution. pwlfit pwlf pwlfit pwlf 4b pwlfit pwlfit It’s worth noting that by default does not perform any down-sampling. For the MSLR-WEB30K dataset running without any downsampling was prohibitively expensive. For all of our experi-ments we ran with a pre-processing downsample to a random 1000 examples. We found this to be a fair point for balancing speed and quality when comparing to . It is of course possible with both algorithms to modify the number of samples used to strike a different trade-off between run time and accuracy. pwlf pwlf pwlf pwlfit 6.4 Monotonicity As discussed in Section can fit monotonic curves with automatic direction detection. Figure compares curve models fit with and without monotonicity constraints (automatically inferring the direction) across datasets. For the COMPAS dataset monotonic and non monotonic models are comparably accurate, while for FICO, MSLR-WEB30K, and CWS, non-monotonic models are more accurate. 5, pwlfit 4a Monotonicity with respect to appropriate features is desirable for interpretable models. In these cases a monotonic model may be preferable to a non-monotonic one, even if it is less accurate. For example, Figure összehasonlítja az MSinceMostRecentDelq és a PercentTradesWBalance funkciók FICO adatkészletén található monoton és nem monoton 5 szegmenses görbékmodelleket. Tekintettel ezeknek a funkcióknak a szemantikus jelentésére, az átláthatóság és az ösztönzők szempontjából kívánatos, hogy a modell kimenete monoton legyen mindegyikük tekintetében. 6 7 CONCLUSION We have introduced a novel method for distilling interpretable models into human-readable code using piecewise-linear curves and demonstrated its efficacy on four datasets. We have shown that curve models match or outperform the accuracy achieved by other additive models. On smaller datasets, curve models match the accuracy of more complex models, like interacting decision forests. Our localized distillation methodology is applicable to any model containing univariate numerical functions and is straightforward to implement using the publicly-available library. pwlfit [22] We have explained how curve model distillation reinforces interpretability and addresses a variety of real-world engineering challenges. Curve models are 1) transparent, 2) well-regularized, 3) easy to analyze for presence of biases or other fairness issues, and 4) can be directly edited or improved outside the context of machine learn-ing to fix the aforementioned fairness issues. Distilling models into human-readable code allows one to address novel machine learning problems using well-established software engineering methods. Curve models can be improved by multiple contributors in parallel, reviewed, and made to systematically follow best practices. Curve models are well-suited for production applications, since they can be natively supported in many languages, are easy to deploy, and fast to evaluate. ACKNOWLEDGMENTS Köszönjük Vytenis Sakenas, Jaime Fernandez del Rio, Benoit Zhong és Petr Mitrichev támogatásukért és az algoritmusok és az optimalizálási infrastruktúra biztosításáért, amelyeket kísérleteinkben használtak. Köszönjük továbbá Paul Heymann, Diego Federici, Mike Bendersky, Paul Haahr és Petr Mitrichev hasznos visszajelzéseikért és részletes felülvizsgálataikért. Végül köszönjük Xinyu Qian-nak, Janelle Lee-nak, Po Hu-nak és Chary Chen-nek, hogy előkészítették a CWS adatkészletet kísérleteinkhez. Referenciák [1] 2018. FICO Explainable Machine Learning Challenge. https://community.fico. com/s/explainable-machine-learning-challenge. [2] Rishabh Agarwal, Nicholas Frosst, Xuezhou Zhang, Rich Caruana, and Geoffrey E. Hinton. 2020. Neural Additive Models: Interpretable Machine Learning with Neural Nets. arXiv :cs.LG/2004.13912 [3] Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. 2017. Learning Certifiably Optimal Rule Lists. In . Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’17) [4] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016. Machine bias: There’s software used across the country to predict future criminals. 23 (2016). És a feketékkel szemben előítéletes.ProPublica [5] Cristian Buciluundefined, Rich Caruana, and Alexandru Niculescu-Mizil. 2006. Model Compression. In . 535–541. A 12. ACM SIGKDD Nemzetközi Tudásfelfedezés és Adatbányászat Konferencia (KDD ’06) [6] Rich Caruana, Yin Lou, Johannes Gehrke, Paul Koch, Marc Sturm, and Noemie Elhadad. 2015. Intelligible Models for HealthCare: Predicting Pneumonia Risk and Hospital 30-Day Readmission. In . 1721–1730. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’15) [7] Chaofan Chen, Kangcheng Lin, Cynthia Rudin, Yaron Shaposhnik, Sijia Wang, and Tong Wang. 2018. An Interpretable Model with Globally Consistent Explanations for Credit Risk. arXiv :cs.LG/1811.12615 [8] Alexandra Chouldechova. 2017. Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments. 5, 2 (Jun 2017), 153–163. Big Data https://doi.org/10.1089/big.2016.0047 [9] ![Text Box: CDF](file:///C:/Users/user/AppData/Local/Temp/msohtmlclip1/01/clip_image063.gif)Julia Dressel és Hany Farid. 2018. A pontosság, a méltányosság és a korlátozások előrejelzése visszaesés. 4, 1 (2018). Science Advances https://doi.org/10.1126/sciadv.aao5580 [10] Mengnan Du, Ninghao Liu, and Xia Hu. 2019. Techniques for interpretable machine learning. 63, 1 (dec 2019), 68–77. Főoldal > ACM https://doi.org/10. 1145/3359786 [11] Trevor Hastie and Robert Tibshirani. 1986. Generalized Additive Models. 1, 3 (08 1986), 297–310. A statisztika. sci [12] Geoffrey Hinton, Oriol Vinyals és Jeff Dean. 2015. A tudás desztillálása egy neurális hálózatban. arXiv :állam.ML/1503.02531 [13] Charles F. Jekel and Gerhard Venter. 2019. A . pwlf: A Python Library for Fitting 1D Continuous Piecewise Linear Functions https://github.com/cjekel/piecewise_ linear_fit_py [14] Jon Kleinberg. 2018. Inherent Trade-Offs in Algorithmic Fairness. In . Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’18) [15] Thomas Kluyver, Benjamin Ragan-Kelley, Fernando Pérez, Brian Granger, Matthias Bussonnier, Jonathan Frederic, Kyle Kelley, Jessica Hamrick, Jason Grout, Sylvain Corlay, Paul Ivanov, Damián Avila, Safia Abdalla, and Carol Willing. 2016. Jupyter Notebooks – a publishing format for reproducible computational workflows. In , F. Loizides and B. Schmidt (Eds.). IOS Press, 87 – 90. Positioning and Power in Academic Publishing: Players, Agents and Agendas [16] ![Text Box: CDF](file:///C:/Users/user/AppData/Local/Temp/msohtmlclip1/01/clip_image072.gif)A. K. Kolmogorov. 1957. A többféle változó folyamatos funkcióinak átszámítása egy változó folyamatos funkcióinak felfüggesztésével és hozzáadásával. 114 (1957), 369–373. Doklady Akademii Nauk SSSR [17] Yin Lou, Rich Caruana, and Johannes Gehrke. 2012. Intelligible Models for Classification and Regression. In . 150–158. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’12) [18] Yin Lou, Rich Caruana, Johannes Gehrke és Giles Hooker. 2013. Pontos intelligens modellek páros interakciókkal. 623 és 631 között. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’13) [19] Tao Qin and Tie-Yan Liu. 2013. Introducing LETOR 4.0 Datasets. abs/1306.2597 (2013). CoRR http://arxiv.org/abs/1306.2597 [20] Tao Qin, Tie-Yan Liu, and Hang Li. 2010. A general approximation framework for direct optimization of information retrieval measures. 13, 4 (2010), 375–397. Information retrieval [21] Cynthia Rudin. 2018. Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead. arXiv :stat.ML/1811.10154 [22] Ethan Sterling and Walker Ravina. 2019. . pwlfit: A Piecewise-Linear Curve Fitting Library https://github.com/google/pwlfit [23] Sarah Tan, Rich Caruana, Giles Hooker, and Yin Lou. 2018. Distill-and-Compare: Auditing Black-Box Models Using Transparent Model Distillation. In . 303–310. Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society (AIES ’18) [24] Berk Ustun and Cynthia Rudin. 2014. Methods and Models for Interpretable Linear Classification. arXiv :stat.ME/1405.4047 [25] Wikipedia. 2020. Bhatia–Davis inequality. [Online; accessed 03-September-2020]. http://en.wikipedia.org/w/index.php? title=Bhatia%E2%80%93Davis%20inequality&oldid=875899600. [26] A Wikipédia. 2020. az izotóniás regresszió. [Online; accessed 30-November-2020]. http://en.wikipedia.org/w/index.php?title= Isotonic%20regression&oldid=989717822. [27] Wikipedia. 2020. Kolmogorov–Arnold representation theorem. [Online; hozzáférhető augusztus 10-től 2020-ig] http://en.wikipedia.org/w/index.php?title=Kolmogorov%E2%80%93Arnold% 20representation%20theorem&oldid=964097101. [28] Wikipedia. 2020. Minimum description length. [Online; hozzáférhető 12 augusztus 2020]. http://en.wikipedia.org/w/index. php?title=Minimum%20description%20length&oldid=965620302. [29] Wikipedia. 2020 Nothing-up-my-sleeve szám. [Online; accessed 12-August-2020]. http://en.wikipedia.org/w/ index.php?title=Nothing-up-my-sleeve%20number&oldid=972510276. [30] A Wikipédia. 2020 Segmentált regresszió. [Online; accessed 10-August-2020]. http://en.wikipedia.org/w/index.php? title=Segmented%20regression&oldid=910888930. [31] Matthew D. Zeiler. 2012. ADADELTA: An Adaptive Learning Rate Method. abs/1212.5701 (2012). arXiv Részletesebben :1212.5701 http://arxiv.org/abs/1212.5701 [32] Honglei Zhuang, Xuanhui Wang, Michael Bendersky, Alexander Grushetsky, Yonghui Wu, Petr Mitrichev, Ethan Sterling, Nathan Bell, Walker Ravina és Hai Qian. 2021. értelmezhető rangsor általánosított additív modellekkel. . to appear. Proceedings of the 14th ACM International Conference on Web Search and Data Mining (WSDM ’21) Kísérleti részletek A.1 Keresztes érvényesítés Öt keresztellenőrzést hajtottunk végre minden adatkészleten. • : Az adatkészleteket 5 egyenlő részre osztottuk. mindegyik részt egyszer használtuk tesztkészletként (20%) a fennmaradó részeket képzési készletként (80%) használtuk. ugyanazokat a véletlenszerű hajtásokat használtuk, mint a NAM papíron [ ]. No validation set was used given the small size of the data. Instead we used out of bag evaluation wherever a validation set would be used (see below). COMPAS & FICO 2 • : We used the predefined folds and partitions from the original dataset. For each fold it allocates 60% for training 20% for validation and 20% for testing. MSLR-WEB30K • az : We used a dataset of 60,000 queries and 2,690,439 items with an average of ~44 items per query. The dataset was split into 5 equal parts. Each part was used once as a test set. Of the remaining parts 80% was used as training and 20% as validation. Overall this resulted in 64% for training, 16% for validation and 20% for test for each fold. CWS A.2 Ensemble Learning For both SGD and tree models, we trained ensembles with 56 bags using a bag fraction of 7 to produce the random subsets. For MSLR-WEB30K and CWS, queries were randomly divided into bags. For the other datasets, individual examples were randomly divided into bags. When applying our distillation technique, we distilled the ensembles into a single per feature. When learning the curves directly via SGD, we averaged the learned 𝑦-coordinate values across bags to obtain the final model. PWLCurve A.3 Loss Functions We trained SGD and tree models using log-loss for the COMPAS dataset, mean squared error (MSE) for the FICO dataset, and ranking loss (ApproxNDCG [ ]) for the MSLR-WEB30K and CWS datasets. 20 A.4 Hyper-paraméterek For the COMPAS, and FICO datasets hyper-parameters were tuned using out of bag evaluation on the training set of the first fold. For MSLR-WEB30K and CWS, we used the validation sets of the first fold. • az A fentiek alapján a fentiekből kifolyólag a fentiekből kifolyólag a fentiekből kifolyólag a fentiekből kifolyólag kifolyólag a fentiekből kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag kifolyólag. ] optimizer and tuned a sufficient maximum number of steps for convergence. No other pa-rameters were tuned. SGD: 31 • We trained depth 5 trees using an inter-nal boosted forest algorithm. We tuned a sufficient maximum number of steps for convergence. No other parameters were tuned. Interacting forest: • az We trained depth 3 trees restricted to using a single feature with an internal boosted forest algorithm. We tuned a sufficient maximum number of steps for convergence. No other parameters were tuned. GAM forest: In all cases, we trained models for the tuned maximum number of steps and then truncated models after training. Truncation used a confidence-based truncation algorithm which attempts to select the earliest step for which no later step provides a confident win. This algorithm was run on the validation set if present or otherwise utilized out of bag evaluation. A.5 Code A GitHub repozitórium [ ] contains several Jupyter note-books applying our distillation technique and performing the analyses shown in this paper. Please reference the v0.2.0 release to get the accompanying data files and appropriate version of the Jupyter notebooks. pwlfit 22 B. Lineáris elítélés Linear condensing is a data optimization designed to reduce the runtime complexity of our piecewise-linear curve fitting. B.1 Motiváció / Áttekintés Válassza ki a jelölt x-csomópontok egy csoportját, és keresi ezeknek az x-csomópontoknak a kombinációit. Minden egyes figyelembe vett kombináció esetében megoldja az ideális y-csomópontok lineáris legkisebb négyzetkifejezését, kiszámítja a kapott négyzethibát, és előnyben részesíti azt a kombinációt, amely a legalacsonyabb hibát eredményezi. pwlfit Minden megoldás lineáris a bemeneti méretben, ami lassú a nagy adatokhoz. Le tudnánk mintavételezni, hogy megmentse a számítást a pontosság költségei mellett. Ehelyett bevezettünk egy technikát a számítás megmentésére a pontosság költsége nélkül. Az adatokat O(#candidates) szintetikus pontokká kondenzáljuk. Ezek a szintetikus pontok tökéletesen újrateremtik az igazi négyzetes hibát a teljes adatok felett minden egyes alkalommal Ezután optimalizáljuk a szintetikus pontokat a valós pontok helyett. PWLCurve Ez azért lehetséges, mert előre ismerjük a jelölt x-csomópontokat. Az ilyen x-csomópontok között mindig lineáris lesz a szomszédos x-csomópontok között a jelöltek csoportjában. Amint azt az elméletben mutatjuk, sok pontot önkényesen két pontra kondenzálhatunk úgy, hogy a lineáris illeszkedések ugyanazok legyenek a két ponton, mint a teljes csoportban. A korollárisban ezt a folyamatot minden egyes jelölt x-csomópár között külön-külön alkalmazzuk, két pontot termelve mindegyik pár között. Ez ugyanaz a szintetikus pontokon, mint a teljes adatkészleten. (akár egy olyan állandóig, amelyet biztonságosan figyelmen kívül hagyunk, mert minden esetben ugyanaz PWLCurve PWLCurve a) a PWLCurve B.2 Definitions A kényelem érdekében standard definíciókat használunk, és a súlyozott 2D pontokra specializáljuk őket. Hagyja, hogy a „pont” utaljon a forma valós értékű hármasára (x, y, súly) a súlyozással 0. Definition B.1. > Hagyja, hogy a „vonal” utaljon a f (x) =mx + b m, b, x ∈ R függvényre. Definition B.2. Bármely funkció esetében f : R → R és véges pont P, határozza meg a négyzetes hiba SE( f , P) az összege ( f ( x ) −y)2 · súlya minden egyes pont P. Ha P üres, úgy a négyzetes hiba 0. Meghatározás B.3. Bármely véges pont-készlet P esetében a „legjobb illeszkedési vonalat” a legjobb f-vonalat (P) úgy határozzuk meg, mint az L-vonalat, amely minimalizálja az SE-t (L, P). A degenerált esetben, ahol több vonal minimalizálja az SE-t, a legjobb illeszkedési vonal legyen a nulla lejtővel rendelkező megoldás, és ha több megoldásnak nulla lejtővel rendelkezik, a legjobb illeszkedési vonal legyen a nulla y-interceptel rendelkező megoldás. Meghatározás B.4. There are two degenerate cases that require tie-breaking. If the point set is empty, every line has the same squared error, so our definition chooses 𝑓 (𝑥) = 0 as the best fit line. If the point set is nonempty but all its points have the same 𝑥, then any line with the correct value at 𝑥 will minimize the squared error, so our definition choose the horizontal line. B.3 Theorem A B5 elmélet. P P ′ Figyelembe véve egy sor pontot készíthetünk egy készletet of two or fewer points such that Ezek a tulajdonságok azért kívánatosak, mert (2) lehetővé teszi számunkra, hogy az O(N + M) N pontok adatkészletén keresztül kiszámítsuk az M vonalak négyzethibáját a naiv O(N M) helyett, és (1) lehetővé teszi számunkra, hogy ezt a tulajdonságot a vonalakról a korollárisban lévő darab-lineáris görbék hasznos osztályára terjesszük. A megjegyzés. Note that the points in 𝑃 ′ are constructed, rather than chosen from 𝑃. The construction of 𝑃 ′ is implemented in [ megtekintése Az AS pwlfit 22 linear_condense.linear_condense. Bizonyíték. Hagyjuk, hogy X, Y és W képviselje az x, y és a súly értékeit a P-nek. Elutasítjuk a triviális esetet, ahol P üres; ebben az esetben egy üres P ′ kielégíti a követelményeket. Hasonlóképpen elutasítjuk azt az esetet, ahol min(X ) = max (X ) mivel P ′ = {Centroid (P)} teljesíti kívánt tulajdonságainkat. 𝑚𝑎𝑥 (𝑋). < Először is átdolgozzuk a koordinátarendszert úgy, hogy az eredete a P centroidja és y = 0 a legmegfelelőbb vonal. (Ez egyszerűsíti a matematikát.) B.3.1 A koordinátarendszer átalakítása. 𝐶𝑒𝑛𝑡𝑟𝑜𝑖𝑑 (𝑃) = (𝑋 · 𝑊 /𝑠𝑢𝑚(𝑊 ), 𝑌 · 𝑊 /𝑠𝑢𝑚(𝑊 )). We translate the coordinate frame by this centroid so that, under the new coordinates, 𝐶𝑒𝑛𝑡𝑟𝑜𝑖𝑑 (𝑃) = (0, 0). After translation, 𝑋 · 𝑊 = 0 and 𝑌 ·𝑊 = 0. Additionally, we skew the coordinate system by the slope of the best fit line: we replace 𝑌 with 𝑌 − 𝑋 · 𝑠𝑙𝑜𝑝𝑒 (𝑏𝑒𝑠𝑡 𝑓 𝑖𝑡𝑙𝑖𝑛𝑒 (𝑃)). With the centroid at the origin, the slope of the best fit line is 𝐶𝑜𝑣𝑎𝑟𝑖𝑎𝑛𝑐𝑒 (𝑋, 𝑌,𝑊 )/𝑉 𝑎𝑟𝑖𝑎𝑛𝑐𝑒 (𝑋,𝑊 ) = Az új koordinátakörben SE (legjobb f itline (P), P) = SE (y = 0, P) = Y 2 ·W Ezután könnyedén átalakíthatjuk a P ′-t vissza az eredeti koordinátarendszerbe azáltal, hogy megfordítjuk a csavart és a fordítást. Az alábbiakban azt mutatjuk be, hogy SE(line, P) SE(best f itline (P), P) plusz fennmaradó kifejezések. ebből egy P ′-ot vonunk le oly módon, hogy SE(line, P ′ ) egyenlő a fennmaradó kifejezésekkel. B.3.2 Az önkényes vonal négyzetes hibája. Egy önkényes vonal esetében y = mx + b, SE(y = mx + b, P) = (mX + b − Y) 2 · W = (m2X 2 + 2bmX − 2mXY + b 2 − 2bY + Y 2 ) · W. A mi koordinátarendszerünkben X ·W = 0, Y ·W = 0, és XY ·W = 0. Így SE(y = mx + b, P) = (m2X 2 + b 2 + Y 2 ) ·W. Y 2 ·W = SE (legjobb f itline (P), P) SE(y = mx + b, P) = m 2X 2 ·W + b 2 ·W + SE(legjobb f itline (P), P) m 2X 2 ·W + b 2 ·W = SE(y = mx + b, P) − SE(legjobb f itline (P), P). B.3.3 Négyszögletes hiba a P ′ felett. B.3.3 Négyszögletes hiba a P ′ felett. SE(y = mx + b, P ′ ) = SE(y = mx + b, P) − SE(legjobb f vonal (P), P) for all lines𝑦 = 𝑚𝑥+𝑏 ⇐⇒ (𝑚𝑋 ′+𝑏−𝑌 ′ ) 2 ·𝑊 ′ = 𝑚2𝑋 2 ·𝑊 +𝑏 2 ·𝑊 for all lines 𝑦 = 𝑚𝑥 + 𝑏. The above equation can be viewed as a quadratic polynomial in the two variables 𝑚 and 𝑏. To hold for all values of 𝑚 and 𝑏, the coefficients of each 𝑚𝑐 𝑏 𝑑 must be equal on both sides of the equation. Then the equation holds iff: 1. 𝑋 ′2 ·𝑊 ′ = 𝑋 2 ·𝑊 , and 2. 𝑋 ′ ·𝑊 ′ = 0, and 3. 𝑠𝑢𝑚(𝑊 ) = 𝑠𝑢𝑚(𝑊 ′ ), and 4. 𝑌 ′ ·𝑊 ′ = 0, and 5. 𝑌 ′2 ·𝑊 ′ = 0, and 6. 𝑋 ′𝑌 ′ ·𝑊 ′ = 0. (5) ⇐⇒ 𝑌 ′ = 0, which also guarantees (4) and (6). We will use 1-3 to derive a satisfactory 𝑋 ′ and 𝑊 ′ . We’ve determined that 𝑌 ′ = 0. B.3.4 Az X ′ és W ′ származéka. Hagyjuk X ′ := (x1, x2) és W ′ := (w1, w2). Az általánosság elvesztése nélkül hagyjuk x1 <= x2. Ezután, hogy kielégítsük a négyzetes hiba kifejezést, szükséges és elegendő, hogy: Because we have three equations in four unknowns, we cannot directly solve for 𝑥1, 𝑥2,𝑤1,𝑤2. To produce a fourth equation, we choose the constraint that 𝑥1/𝑥2 = 𝑚𝑖𝑛(𝑋)/𝑚𝑎𝑥 (𝑋). This choice will simplify the math, and will ensure that 𝑚𝑖𝑛(𝑋) <= 𝑥1 <= 𝑥2 <= 𝑚𝑎𝑥 (𝑋). Ezzel a negyedik egyenletgel megoldjuk az egyidejű egyenleteket, hogy: Vegye figyelembe, hogy mivel a centroid nulla, min(X) < 0 < max (X), így ezek a kifejezések mind meghatározottak. (A nevezők soha nem 0 és az értékek a négyzet gyökerei alatt soha nem negatív.) P ′ = (x1, 0,w1), (x2, 0,w2) megfelel a követelményeknek. <= x1 <= x2 <= max (X). Azt akartuk, hogy P ′ kielégítse a négyzetes hiba kifejezést, amit tesz, és az x-értékeket is a P x-értékei határozzák meg, amit most bizonyítunk. Let μ := E(X,W ), az X várható értéke W-vel súlyozva, ami egyenértékű a Centroid (P) x-értékével. A Bhatia–Davis egyenlőtlenség [25], stddev(X,W ) 2 <= (μ −min(X)) (max (X) − μ). (Ez az egyenlőtlenség egyenértékű azzal a megfigyeléssel, hogy egy eloszlás standard eltérése maximalizálódik, amikor az összes x a szélsőségekben van – azaz min(X) vagy B.3.5 Ellenőrizze, hogy min(X) Mivel μ nulla a P esetében, az stddev(X,W) 2 <= −min(X)max (X) B.4 Corollary Corollary B.6. Given a set of points 𝑃 and a set of x-knots 𝐾, we can construct a set of points 𝑃 ′ with |𝑃 ′ | <= 2(|𝐾| − 1) such that, for any PWLCurve 𝐶 whose x-knots are elements of 𝐾, 𝑆𝐸(𝐶, 𝑃) = 𝑆𝐸(𝐶, 𝑃 ′ ) + 𝑐, where 𝑐 is a constant determined exclusively by 𝑃 and 𝐾 that’s the same for every 𝐶. Megjegyzendő, hogy a P ′ pontjai konstruálva vannak, nem pedig P-ből választva. . linear_condense.condense_around_knots A darab-lineáris görbék állandóak az x-csomópontok tartományát meghaladó bemeneti értékek esetében, így C állandó x = max (K) = K[k − 1). B.4.1 Előzetes feldolgozás P szorítással. Ezért a P x-értékeit [K[0], K[k − 1]-re tömöríthetjük anélkül, hogy megváltoztatnánk a SE(C, P) értéket. To construct 𝑃 ′ from 𝑃, we first partition 𝑃 by 𝐾 into 𝑘 + 1 disjoint pieces labeled 𝑃0, 𝑃1, ..., 𝑃𝑘 . B.4.2 Partíció P által K. Because we clamped 𝑃, 𝑃0 and 𝑃𝑘 are empty. Therefore Ð𝑘−1 𝑖=1 𝑃𝑖 = 𝑃. A PWLCurve lineáris egymást követő vezérlőpontok között, így C lineáris minden Pi felett. B.4.3 Minden partíciót két pontra konvertálhatunk. az elméletből minden Pi esetében kétpontos P ′ i-t állíthatunk elő minx (Pi) <= minx (P ′ i) <= maxx (P ′ i) <= maxx (Pi), úgy, hogy bármely vonal L, Ez a dokumentum a CC by 4.0 Deed (Attribution 4.0 International) licenc alatt érhető el. Ez a dokumentum a CC by 4.0 Deed (Attribution 4.0 International) licenc alatt érhető el.