Transduktion (maskininlärning)

I logik , statistisk slutledning och övervakad inlärning är transduktion eller transduktiv slutledning resonemang från observerade, specifika (tränings)fall till specifika (test)fall . Däremot är induktion resonemang från observerade träningsfall till allmänna regler, som sedan tillämpas på testfallen. Distinktionen är mest intressant i de fall där förutsägelserna av den transduktiva modellen inte kan uppnås med någon induktiv modell. Observera att detta orsakas av transduktiv slutledning på olika testuppsättningar som producerar ömsesidigt inkonsekventa förutsägelser.

Transduktion introducerades av Vladimir Vapnik på 1990-talet, motiverat av hans åsikt att transduktion är att föredra framför induktion eftersom induktion enligt honom kräver att man löser ett mer generellt problem (att sluta sig till en funktion) innan man löser ett mer specifikt problem (beräkning av utdata för nya fall ): "När du löser ett problem av intresse, lös inte ett mer allmänt problem som ett mellansteg. Försök att få svaret som du verkligen behöver men inte ett mer generellt." En liknande observation hade gjorts tidigare av Bertrand Russell : "vi kommer att komma till slutsatsen att Sokrates är dödlig med en större inställning till säkerhet om vi gör vårt argument rent induktivt än om vi går till vägen "alla människor är dödliga" och sedan använder avdrag" (Russell 1912, kap VII).

Ett exempel på inlärning som inte är induktiv skulle vara i fallet med binär klassificering, där ingångarna tenderar att gruppera sig i två grupper. En stor uppsättning testingångar kan hjälpa till att hitta klustren, vilket ger användbar information om klassificeringsetiketterna. Samma förutsägelser skulle inte kunna erhållas från en modell som inducerar en funktion som endast baseras på träningsfallen. Vissa människor kan kalla detta ett exempel på det närbesläktade semi-övervakade lärandet , eftersom Vapniks motivation är helt annorlunda. Ett exempel på en algoritm i denna kategori är Transductive Support Vector Machine (TSVM).

En tredje möjlig motivation som leder till transduktion uppstår genom behovet av att approximera. Om exakt slutledning är beräkningsmässigt oöverkomlig, kan man åtminstone försöka se till att approximationerna är bra vid testingångarna. I det här fallet kan testinmatningarna komma från en godtycklig fördelning (inte nödvändigtvis relaterad till distributionen av träningsingångarna), vilket inte skulle tillåtas i semi-övervakat lärande. Ett exempel på en algoritm som faller i denna kategori är Bayesian Committee Machine (BCM).

Exempel på problem

Följande exempelproblem kontrasterar några av de unika egenskaperna hos transduktion mot induktion.

En samling poäng ges, så att några av punkterna är märkta (A, B eller C), men de flesta av punkterna är omärkta (?). Målet är att förutsäga lämpliga etiketter för alla omärkta punkter.

Det induktiva tillvägagångssättet för att lösa detta problem är att använda de märkta punkterna för att träna en övervakad inlärningsalgoritm och sedan låta den förutsäga etiketter för alla de omärkta punkterna. Med detta problem kommer dock den övervakade inlärningsalgoritmen bara att ha fem märkta punkter att använda som grund för att bygga en prediktiv modell. Det kommer säkerligen att kämpa för att bygga en modell som fångar strukturen av denna data. Till exempel, om en algoritm för närmaste granne används, kommer punkterna nära mitten att betecknas "A" eller "C", även om det är uppenbart att de tillhör samma kluster som punkten märkt "B".

Transduktion har fördelen av att kunna ta hänsyn till alla punkter, inte bara de märkta punkterna, medan märkningsuppgiften utförs. I det här fallet skulle transduktiva algoritmer märka de omärkta punkterna enligt de kluster som de naturligt tillhör. Punkterna i mitten skulle därför med största sannolikhet vara märkta med "B", eftersom de är packade mycket nära det klustret.

En fördel med transduktion är att den kanske kan göra bättre förutsägelser med färre märkta punkter, eftersom den använder de naturliga avbrotten som finns i de omärkta punkterna. En nackdel med transduktion är att den inte bygger någon prediktiv modell. Om en tidigare okänd punkt läggs till i uppsättningen, skulle hela den transduktiva algoritmen behöva upprepas med alla punkterna för att förutsäga en etikett. Detta kan bli beräkningsmässigt dyrt om data görs tillgänglig stegvis i en ström. Vidare kan detta göra att förutsägelserna för några av de gamla punkterna ändras (vilket kan vara bra eller dåligt, beroende på applikationen). En övervakad inlärningsalgoritm, å andra sidan, kan märka nya punkter direkt, med mycket liten beräkningskostnad.

Transduktionsalgoritmer

Transduktionsalgoritmer kan grovt delas in i två kategorier: de som försöker tilldela diskreta etiketter till omärkta punkter och de som försöker regressera kontinuerliga etiketter för omärkta punkter. Algoritmer som försöker förutsäga diskreta etiketter tenderar att härledas genom att lägga till partiell övervakning till en klustringsalgoritm . Två klasser av algoritmer kan användas: platt klustring och hierarkisk klustring. De senare kan delas in ytterligare i två kategorier: de som klustrar genom partitionering och de som klustrar genom agglomerering. Algoritmer som försöker förutsäga kontinuerliga etiketter tenderar att härledas genom att lägga till partiell övervakning till en mångfaldig inlärningsalgoritm .

Partitioneringstransduktion

Partitioneringstransduktion kan ses som top-down-transduktion. Det är en semi-övervakad förlängning av partitionsbaserad klustring. Det utförs vanligtvis enligt följande:

Betrakta uppsättningen av alla punkter som en stor partition. Medan vilken partition P som helst innehåller två punkter med motstridiga etiketter: Partitionera P i mindre partitioner. För varje partition P: Tilldela samma etikett till alla punkter i P.

Naturligtvis kan vilken rimlig partitioneringsteknik som helst användas med denna algoritm. Max flöde min cut partitioneringsscheman är mycket populära för detta ändamål.

Agglomerativ transduktion

Agglomerativ transduktion kan ses som nedifrån och upp-transduktion. Det är en semi-övervakad förlängning av agglomerativ klustring. Det utförs vanligtvis enligt följande:

Beräkna de parvisa avstånden, D, mellan alla punkter. Sortera D i stigande ordning. Betrakta varje punkt som ett kluster av storlek 1. För varje par av punkter {a,b} i D: Om (a är omärkt) eller (b är omärkt) eller (a och b har samma etikett) Slå samman de två klustren som innehåller a och b. Märk alla punkter i det sammanslagna klustret med samma etikett.

Manifoldtransduktion

Manifold-learning-baserad transduktion är fortfarande ett mycket ungt forskningsfält.

Se även

Epilogism

VN Vapnik. Statistisk inlärningsteori . New York: Wiley, 1998. (Se sidorna 339-371)
V. Tresp. A Bayesian Committee Machine , Neural Computation, 12, 2000, pdf .
B. Russell. The Problems of Philosophy , Hemuniversitetsbiblioteket, 1912. [1] .

externa länkar

A Gammerman, V. Vovk, V. Vapnik (1998). " Lärande genom transduktion ." En tidig förklaring av transduktivt lärande.
" A Discussion of Semi-Supervised Learning and Transduction ," Kapitel 25 i Semi-Supervised Learning, Olivier Chapelle, Bernhard Schölkopf och Alexander Zien, red. (2006). MIT Press. En diskussion om skillnaden mellan SSL och transduktion.
Waffles är ett C++-bibliotek med öppen källkod för maskininlärningsalgoritmer, inklusive transduktionsalgoritmer, även Waffles .
SVMlight är ett allmänt SVM-paket som inkluderar det transduktiva SVM-alternativet.