Om den Måttbaserade Ansatsen till Övervakad Inlärning av Begrepp

A classifier is a piece of software that is able to categorize objects for which the class is unknown. The task of automatically generating classifiers by generalizing from examples is an important problem in many practical applications. This problem is often referred to as supervised concept learning, and has been shown to be relevant in e.g. medical diagnosis, speech and handwriting recognition, stock market analysis, and other data mining applications. The main purpose of this thesis is to analyze current approaches to evaluate classifiers as well as supervised concept learners and to explore possible improvements in terms of alternative or complementary approaches. In particular, we investigate the metric-based approach to evaluation as well as how it can be used when learning. Any supervised concept learning algorithm can be viewed as trying to generate a classifier that optimizes a specific, often implicit, metric (this is sometimes also referred to as the inductive bias of the algorithm). In addition, different metrics are suitable for different learning tasks, i.e., the requirements vary between application domains. The idea of metric-based learning is to both make the metric explicit and let it be defined by the user based on the learning task at hand. The thesis contains seven studies, each with its own focus and scope. First, we present an analysis of current evaluation methods and contribute with a formalization of the problems of learning, classification and evaluation. We then present two quality attributes, sensitivity and classification performance, that can be used to evaluate learning algorithms. To demonstrate their usefulness, two metrics for these attributes are defined and used to quantify the impact of parameter tuning and the overall performance. Next, we refine an approach to multi-criteria classifier evaluation, based on the combination of three metrics and present algorithms for calculating these metrics. In the fourth study, we present a new method for multi-criteria evaluation, which is generic in the sense that it only dictates how to combine metrics. The actual choice of metrics is application-specific. The fifth study investigates whether or not the performance according to an arbitrary application-specific metric can be boosted by using that metric as the one that the learning algorithm aims to optimize. The subsequent study presents a novel data mining application for preventing spyware by classifying End User License Agreements. A number of state-of-the-art learning algorithms are compared using the generic multi-criteria method. Finally, in the last study we describe how methods from the area of software engineering can be used to solve the problem of selecting relevant evaluation metrics for the application at hand.Den tekniska utvecklingen har förändrat vår livsstil och utökat den globala ekonomins fokus från produktion av varor till insamling och förädling av information. En konsekvens av denna förändring är att vi blir mer beroende av databaser för lagring och databehandling. Antalet, och speciellt storleken på, databaserna växer snabbt, vilket gör det allt svårare att extrahera användbar information. Tekniker och metoder från s.k. informationsutvinning (Eng: data mining) har visat sig väl lämpade för denna uppgift såväl inom industri som inom flera vetenskapliga och tekniska områden. Informationsutvinning, eller kunskapsupptäckande, är ett tvärvetenskapligt område med anknytning till artificiell intelligens, statistik, databasteknik och datorsystemteknik. Områdets syfte är att utveckla kunskap och metoder för att kunna extrahera användbar information från stora mängder data. En vanligt förekommande uppgift är att utvinna information som kan användas för att beskriva olika typer av objekt eller händelser. Denna information kan sedan användas för att kategorisera dessa objekt eller händelser. Om den utvunna informationen kan användas för att sortera data under ett begränsat antal kategorier antyder detta att den innehåller en generell beskrivning av varje kategori. Inom lärande system, ett datavetenskapligt område med nära anknytning till artificiell intelligens, har man tagit fram metoder som är särskilt användbara för att automatiskt generera kategoribeskrivningar genom att generalisera från redan kategoriserad data. Denna typ av metoder går under benämningen övervakad inlärning av begrepp. Metoderna kallas allmänt för inlärningsalgoritmer och kategoribeskrivningarna som genereras kallas för klassificerare då de används för att klassificera, eller kategorisera data. Utvärdering av inlärningsalgoritmer och klassificerare krävs för att försäkra sig om att det studerade problemet löses tillräckligt väl av en viss metod och även för att kunna välja en lämplig inlärningsalgoritm från de många tillgängliga. Avhandlingen behandlar kritiska frågor om utvärdering av lärande system och presenterar nya ansatser och mått speciellt avsedda för utvärdering av algoritmer inom övervakad inlärning av begrepp och klassificerare. Inlärningsalgoritmer utvärderas typiskt efter hur korrekta de inlärda klassificerarna är i sin kategorisering av ny data (data som inte använts för inlärning och för vilka kategorin inte är känd sedan tidigare för inlärningsalgoritmen). Korrekthet mäts genom att man låter en klassificerare kategorisera en mängd data och sedan dividerar antalet korrekta kategoriseringar med det totala antalet kategoriseringar. Teoretiska, såväl som empiriska studier har påvisat flera brister med detta mått. Först och främst begränsas utvärderingen då endast en kvalitetsaspekt granskas. Övervakad inlärning av begrepp används inom ett brett spektra av tillämpningsområden (exempelvis: diagnos, bild- och ljudigenkänning, prediktion) och varje specifik tillämpning har sin egen uppsättning mål och krav som måste uppnås. Dessutom är det känt att korrekthet som mått inte är speciellt tillförlitligt då dess förutsättningar, som att mängden data skall vara jämnt fördelad över samtliga kategorier, sällan uppfylls i skarpa situationer. Flera alternativa mått har presenterats tidigare men få metoder existerar för att välja lämpliga mått givet ett visst problem eller en specifik tillämpning. Det centrala temat i avhandlingen är den måttbaserade ansatsen, som går ut på att skräddarsy utvärdering och inlärning för specifika tillämpningar genom att systematiskt välja passande mått baserat på en tillämpnings mål och krav. Avhandlingen presenterar bland annat en generell metod för viktad utvärdering av flera mått och föreslår en metod för systematiskt val av mått baserat på tillämpningsmål. Vidare presenterar avhandlingen en metod för måttbaserad inlärning, som går ut på att få en inlärningsalgoritm att ta hänsyn till relevanta mått redan under inlärningsfasen. Resultaten visar att denna metod ökar möjligheterna att skapa klassificerare som är specialanpassade för en viss tillämpning. Möjligheterna med måttbaserad utvärdering och inlärning bedöms som stora då informationsutvinning i allt högre grad används inom såväl forskning som näringsliv och målen med tillämpningarna varierar stort. Idag används informationsutvinningstekniker och övervakad inlärning av begrepp inom bland annat: medicin (diagnosticering av patienter samt prediktion av vårdbehov), IT-säkerhet (intrångsdetektion, sortering av skräppost, detektion av integritetskränkande programvara), video- och bildanalys (igenkänning via fingeravtryck och ansiktsdrag), automatiserad språkförståelse (kategorisering av textdokument, igenkänning av språk)