Aprendizado supervisionado tem sido principalmente utilizado para classificação. Neste trabalho são mostrados os benefícios do uso de rankings ao invés de classificação de exemplos isolados. Um rankeador é um algoritmo que ordena um conjunto de exemplos de tal modo que eles são apresentados do exemplo de maior para o exemplo de menor expectativa de ser positivo. Um ranking é o resultado dessa ordenação. Normalmente, um ranking é obtido pela ordenação do valor de confiança de classificação dado por um classificador. Este trabalho tem como objetivo procurar por novas abordagens para promover o uso de rankings. Desse modo, inicialmente são apresentados as diferenças e semelhanças entre ranking e classificação, bem como um novo algoritmo de ranking que os obtém diretamente sem a necessidade de obter os valores de confiança de classificação, esse algoritmo é denominado de LEXRANK. Uma área de pesquisa bastante importante em rankings é a análise ROC. O estudo de árvores de decisão e análise ROC é bastante sugestivo para o desenvolvimento de uma visualização da construção da árvore em gráficos ROC. Para mostrar passo a passo essa visualização foi desenvolvido uma sistema denominado PROGROC. Ainda do estudo de análise ROC, foi observado que a inclinação (coeficiente angular) dos segmentos que compõem o fecho convexo de curvas ROC é equivalente a razão de verossimilhança que pode ser convertida para probabilidades. Essa conversão é denominada de calibração por fecho convexo de curvas ROC que coincidentemente é equivalente ao algoritmo PAV que implementa regressão isotônica. Esse método de calibração otimiza Brier Score. Ao explorar essa medida foi encontrada uma relação bastante interessante entre Brier Score e curvas ROC. Finalmente, também foram explorados os rankings construídos durante o método de seleção de exemplos do algoritmo de aprendizado semi-supervisionado multi-descrição CO-TRAINING / Supervised learning has been used mostly for classification. In this work we show the benefits of a welcome shift in attention from classification to ranking. A ranker is an algorithm that sorts a set of instances from highest to lowest expectation that the instance is positive, and a ranking is the outcome of this sorting. Usually a ranking is obtained by sorting scores given by classifiers. In this work, we are concerned about novel approaches to promote the use of ranking. Therefore, we present the differences and relations between ranking and classification followed by a proposal of a novel ranking algorithm called LEXRANK, whose rankings are derived not from scores, but from a simple ranking of attribute values obtained from the training data. One very important field which uses rankings as its main input is ROC analysis. The study of decision trees and ROC analysis suggested an interesting way to visualize the tree construction in ROC graphs, which has been implemented in a system called PROGROC. Focusing on ROC analysis, we observed that the slope of segments obtained from the ROC convex hull is equivalent to the likelihood ratio, which can be converted into probabilities. Interestingly, this ROC convex hull calibration method is equivalent to Pool Adjacent Violators (PAV). Furthermore, the ROC convex hull calibration method optimizes Brier Score, and the exploration of this measure leads us to find an interesting connection between the Brier Score and ROC Curves. Finally, we also investigate rankings build in the selection method which increments the labelled set of CO-TRAINING, a semi-supervised multi-view learning algorithm

Nos últimos 30 anos, a área de aprendizagem de máquina desenvolveu-se de forma comparável com a Física no início do século XX. Esse avanço tornou possível a resolução de problemas do mundo real que anteriormente não poderiam ser solucionados por máquinas, devido à dificuldade de modelos puramente estatísticos ajustarem-se de forma satisfatória aos dados de treinamento. Dentre tais avanços, pode-se citar a utilização de técnicas de aprendizagem de máquina na área de Química Medicinal, envolvendo métodos de análise, representação e predição de informação molecular por meio de recursos computacionais. Os dados utilizados no contexto biológico possuem algumas características particulares que podem influenciar no resultado de sua análise. Dentre estas, pode-se citar a complexidade das informações moleculares, o desbalanceamento das classes envolvidas e a existência de dados incompletos ou rotulados de forma incerta. Tais adversidades podem prejudicar o processo de identificação de compostos candidatos a novos fármacos, se não forem tratadas de forma adequada. Neste trabalho, foi abordada uma técnica de aprendizagem de máquina semi-supervisionada capaz de reduzir o impacto causado pelo problema da incerteza na rotulação dos dados, aplicando um método para estimar rótulos mais confiáveis para os compostos químicos existentes no conjunto de treinamento. Na tentativa de evitar os efeitos causados pelo desbalanceamento dos dados, foi incorporada ao processo de estimação de rótulos uma abordagem sensível ao custo, com o objetivo de evitar o viés em benefício da classe majoritária. Após o tratamento do problema da incerteza na rotulação, classificadores baseados em Máquinas de Aprendizado Extremo foram construídos, almejando boa capacidade de aproximação em um tempo de processamento reduzido em relação a outras abordagens de classificação comumente aplicadas. Por fim, o desempenho dos classificadores construídos foi avaliado por meio de análises dos resultados obtidos, confrontando o cenário com os dados originais e outros com as novas rotulações obtidas durante o processo de estimação semi-supervisionado / In the last 30 years, the area of machine learning has developed in a way comparable to Physics in the early twentieth century. This breakthrough has made it possible to solve real-world problems that previously could not be solved by machines because of the difficulty of purely statistical models to fit satisfactorily with training data. Among these advances, one can cite the use of machine learning techniques in the area of Medicinal Chemistry, involving methods for analysing, representing and predicting molecular information through computational resources. The data used in the biological context have some particular characteristics that can influence the result of its analysis. These include the complexity of molecular information, the imbalance of the classes involved, and the existence of incomplete or uncertainly labeled data. If they are not properly treated, such adversities may affect the process of identifying candidate compounds for new drugs. In this work, a semi-supervised machine learning technique was considered to reduce the impact caused by the problem of uncertainty in the data labeling, by applying a method to estimate more reliable labels for the chemical compounds in the training set. In an attempt to reduce the effects caused by data imbalance, a cost-sensitive approach was incorporated to the label estimation process, in order to avoid bias in favor of the majority class. After addressing the uncertainty problem in labeling, classifiers based on Extreme Learning Machines were constructed, aiming for good approximation ability in a reduced processing time in relation to other commonly applied classification approaches. Finally, the performance of the classifiers constructed was evaluated by analyzing the results obtained, comparing the scenario with the original data and others with the new labeling obtained by the semi-supervised estimation process

Com o aumento da capacidade de armazenamento, as bases de dados são cada vez maiores e, em muitas situações, apenas um pequeno subconjunto de itens de dados pode ser rotulado. Isto acontece devido ao processo de rotulagem ser frequentemente caro, demorado e necessitar do envolvimento de especialistas humanos. Com isso, diversos algoritmos semissupervisionados foram propostos, mostrando que é possível obter bons resultados empregando conhecimento prévio, relativo à pequena fração de dados rotulados. Dentre esses algoritmos, os que têm ganhado bastante destaque na área têm sido aqueles baseados em redes. Tal interesse, justifica-se pelas vantagens oferecidas pela representação via redes, tais como, a possibilidade de capturar a estrutura topológica dos dados, representar estruturas hierárquicas, bem como modelar manifolds no espaço multi-dimensional. No entanto, existe uma grande quantidade de dados representados em tabelas atributo-valor, nos quais não se poderia aplicar os algoritmos baseados em redes sem antes construir uma rede a partir desses dados. Como a geração das redes, assim como sua relação com o desempenho dos algoritmos têm sido pouco estudadas, esta tese investigou esses aspectos e propôs novos métodos para construção de redes, considerando características ainda não exploradas na literatura. Foram propostos três métodos para construção de redes com diferentes topologias: 1) S-kNN (Sequential k Nearest Neighbors), que gera redes regulares; 2) GBILI (Graph Based on the Informativeness of Labeled Instances) e RGCLI (Robust Graph that Considers Labeled Instances), que exploram os rótulos disponíveis gerando redes com distribuição de grau lei de potência; 3) GBLP (Graph Based on Link Prediction), que se baseia em medidas de predição de links gerando redes com propriedades mundo-pequeno. As estratégias de construção de redes propostas foram analisadas por meio de medidas de teoria dos grafos e redes complexas e validadas por meio da classificação semissupervisionada. Os métodos foram aplicados em benchmarks da área e também na classificação de gêneros musicais e segmentação de imagens. Os resultados mostram que a topologia da rede influencia diretamente os algoritmos de classificação e as estratégias propostas alcançam boa acurácia. / With the increase capacity of storage, databases are getting larger and, in many situations, only a small subset of data items can be labeled. This happens because the labeling process is often expensive, time consuming and requires the involvement of human experts. Hence, several semi-supervised algorithms have been proposed, showing that it is possible to achieve good results by using prior knowledge. Among these algorithms, those based on graphs have gained prominence in the area. Such interest is justified by the benefits provided by the representation via graphs, such as the ability to capture the topological structure of the data, represent hierarchical structures, as well as model manifold in high dimensional spaces. Nevertheless, most of available data is represented by attribute-value tables, making necessary the study of graph construction techniques in order to convert these tabular data into graphs for applying such algorithms. As the generation of the weight matrix and the sparse graph, and their relation to the performance of the algorithms have been little studied, this thesis investigated these aspects and proposed new methods for graph construction with characteristics litle explored in the literature yet. We have proposed three methods for graph construction with different topologies: 1) S-kNN (Sequential k Nearest Neighbors) that generates regular graphs; 2) GBILI (Graph Based on the informativeness of Labeled Instances) and RGCLI (Robust Graph that Considers Labeled Instances), which exploit the labels available generating power-law graphs; 3) GBLP (Graph Based on Link Prediction), which are based on link prediction measures and generates small-world graphs. The strategies proposed were analyzed by graph theory and complex networks measures and validated in semi-supervised classification tasks. The methods were applied in benchmarks of the area and also in the music genre classification and image segmentation. The results show that the topology of the graph directly affects the classification algorithms and the proposed strategies achieve good accuracy.

Cette étude a pour sujet les hypergraphes. / This study has for subject the hypergraphs.

<p>Cilj &ndash; Cilj istraživanja u okviru doktorske disertacije je razvoj sistema za automatsku polu-nadgledanu klasifikaciju podataka. Sistem bi trebao biti primenljiv na &scaron;irokom spektru domena gde je neophodna klasifikacija podataka, a te&scaron;ko je, ili čak nemoguće, doći do dovoljno velikog i raznovrsnog obučavajućeg skupa podataka<br />Metodologija &ndash; Modeli opisani u disertaciji se baziraju na kombinaciji ko-trening algoritma i tehnika učenja sa grupom hipoteza. Prvi korak jeste obučavanje grupe klasifikatora velike raznolikosti i kvaliteta. Sa ovim ciljem modeli eksploati&scaron;u primenu različitih konfiguracija ko-trening algoritma na isti skup podataka. Prednost ovog pristupa je mogućnost kori&scaron;ćenja značajno manjeg anotiranog obučavajućeg skupa za inicijalizaciju algoritma.<br />Skup nezavisno obučenih ko-trening klasifikatora se kreira generisanjem predefinisanog broja slučajnih podela obeležja polaznog skupa podataka. Nakon toga se, polazeći od istog inicijalnog obučavajućeg skupa, ali kori&scaron;ćenjem različitih kreiranih podela obeležja, obučava grupa ko-trening klasifikatora. Nakon ovoga, neophodno je kombinovati predikcije nezavisno obučenih klasifikatora.<br />Predviđena su dva načina kombinovanja predikcija. Prvi način se zasniva na klasifikaciji zapisa na osnovu većine glasova grupe ko-trening klasifikatora. Na ovaj način se daje predikcija za svaki od zapisa koji su pripadali grupi neanotiranih primera kori&scaron;ćenih u toku obuke ko-treninga. Potom se primenjuje genetski algoritam u svrhu selekcije najpouzdanije klasifikovanih zapisa ovog skupa. Konačno,<br />163<br />najpouzdanije klasifikovani zapisi se koriste za obuku finalnog klasifikatora. Ovaj finalni klasifikator se koristi za predikciju klase zapisa koje je neophodno klasifikovati. Opisani algoritam je nazvan Algoritam Statistike Slučajnih Podela (Random Split Statistics algorithm, RSSalg).<br />Drugi način kombinovanja nezavisno obučenih ko-trening klasifikatora se zasniva na GMM-MAPML tehnici estimacije tačnih klasnih obeležja na osnovu vi&scaron;estrukih obeležja pripisanih od strane različitih anotatora nepoznatog kvaliteta. U ovom algoritmu, nazvanom Integracija Vi&scaron;estrukih Ko-treninranih Klasifikatora (Integration of Multiple Co-trained Classifiers, IMCC), svaki od nezavisno treniranih ko-trening klasifikatora daje predikciju klase za svaki od zapisa koji je neophodno klasifikovati. U ovoj postavci se svaki od ko-trening klasifikatora tretira kao jedan od anotatora čiji je kvalitet nepoznat, a svakom zapisu, za koga je neophodno odrediti klasno obeležje, se dodeljuje vi&scaron;e klasnih obeležja. Na kraju se primenjuje GMM-MAPML tehnika, kako bi se na osnovu dodeljenih vi&scaron;estrukih klasnih obeležja za svaki od zapisa izvr&scaron;ila estimacija stvarnog klasnog obeležja zapisa.<br />Rezultati &ndash; U disertaciji su razvijena dva modela, Integracija Vi&scaron;estrukih Ko-treninranih Klasifikatora (IMCC) i Algoritam Statistike Slučajnih Podela (RSSalg), bazirana na ko-trening algoritmu, koja re&scaron;avaju zadatak automatske klasifikacije u slučaju nepostojanja dovoljno velikog anotiranog korpusa za obuku. Modeli predstavljeni u disertaciji dizajnirani su tako da omogućavaju primenu ko-trening algoritma na skupove podataka bez prirodne podele obeležja, kao i da unaprede njegove performanse. Modeli su na vi&scaron;e skupova podataka različite veličine, dimenzionalnosti i redudantnosti poređeni sa postojećim ko-trening alternativama. Pokazano je da razvijeni modeli na testiranim skupovima podataka postižu bolje performanse od testiranih ko-trening alternativa.<br />Praktična primena &ndash; Razvijeni modeli imaju &scaron;iroku mogućnost primene u svim domenima gde je neophodna klasifikacija podataka, a anotiranje podataka dugotrajno i skupo. U disertaciji je prikazana i primena razvijenih modela u nekoliko konkretnih<br />164<br />situacija gde su modeli od posebne koristi: detekcija subjektivnosti, vi&scaron;e-kategorijska klasifikacija i sistemi za davanje preporuka.<br />Vrednost &ndash; Razvijeni modeli su korisni u &scaron;irokom spektru domena gde je neophodna klasifikacija podataka, a anotiranje podataka dugotrajno i skupo. Njihovom primenom se u značajnoj meri smanjuje ljudski rad neophodan za anotiranje velikih skupova podataka. Pokazano je da performanse razvijenih modela prevazilaze performanse postojećih alternativa razvijenih sa istim ciljem relaksacije problema dugotrajne i mukotrpne anotacije velikih skupova podataka.</p> / <p>Aim &ndash; The research presented in this thesis is aimed towards the development of the system for automatic semi-supervised classification. The system is designed to be applicable on the broad spectrum of practical domains where automatic classification of data is needed but it is hard or impossible to obtain a large enough training set.<br />Methodology &ndash; The described models combine co-training algorithm with ensemble learning with the aim to overcome the problem of co-training application on the datasets without the natural feature split. The first step is to create the ensemble of co-training classifiers. For this purpose the models presented in this thesis apply different configurations of co-training on the same training set. Compared to existing similar approaches, this approach requires a significantly smaller initial training set.<br />The ensemble of independently trained co-training classifiers is created by generating a predefined number of random feature splits of the initial training set. Using the same initial training set, but different feature splits, a group of co-training classifiers is trained. The two models differ in the way the predictions of different co-training classifiers are combined.<br />The first approach is based on majority voting: each instance recorded in the enlarged training sets resulting from co-training application is classified by majority voting of the group of obtained co-training classifiers. After this, the genetic algorithm is applied in order to select the group of most reliably classified instances from this set. The most reliable instances are used in<br />167<br />order to train a final classifier which is used to classify new instances. The described algorithm is called Random Split Statistic Algorithm (RSSalg).<br />The other approach of combining single predictions of the group of co-training classifiers is based on GMM-MAPML technique of estimating the true hidden label based on the multiple labels assigned by multiple annotators of unknown quality. In this model, called the Integration of Multiple Co-trained Classifiers (IMCC), each of the independently trained co-training classifiers predicts the label for each test instance. Each co-training classifier is treated as one of the annotators of unknown quality and each test instance is assigned multiple labels (one by each of the classifiers). Finally, GMM-MAPML technique is applied in order to estimate the true hidden label in the multi-annotator setting.<br />Results &ndash; In the dissertation the two models are developed: the Integration of Multiple Co-trained Classifiers (IMCC) and Random Split Statistic Algorithm (RSSalg). The models are based on co-training and aimed towards enabling automatic classification in the cases where the existing training set is insufficient for training a quality classification model. The models are designed to enable the application of co-training algorithm on datasets that lack the natural feature split needed for its application, as well as with the goal to improve co-training performance. The models are compared to their co-training alternatives on multiple datasets of different size, dimensionality and feature redundancy. It is shown that the developed models exhibit superior performance compared to considered co-training alternatives.<br />Practical application &ndash; The developed models are applicable on the wide spectrum of domains where there is a need for automatic classification and training data is insufficient. The dissertation presents the successful application of models in several concrete situations where they are highly<br />168<br />beneficial: subjectivity detection, multicategory classification and recommender systems.<br />Value &ndash; The models can greatly reduce the human effort needed for long and tedious annotation of large datasets. The conducted experiments show that the developed models are superior to considered alternatives.</p>

Modelos para aprendizado não supervisionado podem fornecer restrições complementares úteis para melhorar a capacidade de generalização de classificadores. Baseando-se nessa premissa, um algoritmo existente, denominado de C3E (Consensus between Classification and Clustering Ensembles), recebe como entradas estimativas de distribuições de probabilidades de classes para objetos de um conjunto alvo, bem como uma matriz de similaridades entre esses objetos. Tal matriz é tipicamente construída por agregadores de agrupadores de dados, enquanto que as distribuições de probabilidades de classes são obtidas por um agregador de classificadores induzidos por um conjunto de treinamento. Como resultado, o C3E fornece estimativas refinadas das distribuições de probabilidades de classes como uma forma de consenso entre classificadores e agrupadores. A ideia subjacente é de que objetos similares são mais propensos a compartilharem o mesmo rótulo de classe. Nesta tese, uma versão mais simples do algoritmo C3E, baseada em uma função de perda quadrática (C3E-SL), foi investigada em uma abordagem que permitiu a estimação automática (a partir dos dados) de seus parâmetros críticos. Tal abordagem faz uso de um nova estratégia evolutiva concebida especialmente para tornar o C3E-SL mais prático e flexível, abrindo caminho para que variantes do algoritmo pudessem ser desenvolvidas. Em particular, para lidar com a escassez de dados rotulados, um novo algoritmo que realiza aprendizado semissupervisionado foi proposto. Seu mecanismo explora estruturas intrínsecas dos dados a partir do C3E-SL em um procedimento de autotreinamento (self-training). Esta noção também inspirou a concepção de um outro algoritmo baseado em aprendizado ativo (active learning), o qual é capaz de se autoadaptar para aprender novas classes que possam surgir durante a predição de novos dados. Uma extensa análise experimental, focada em problemas do mundo real, mostrou que os algoritmos propostos são bastante úteis e promissores. A combinação de classificadores e agrupadores resultou em modelos de classificação com grande potencial prático e que são menos dependentes do usuário ou do especialista de domínio. Os resultados alcançados foram tipicamente melhores em comparação com os obtidos por classificadores tradicionalmente usados. / Unsupervised learning models can provide a variety of supplementary constraints to improve the generalization capability of classifiers. Based on this assumption, an existing algorithm, named C3E (from Consensus between Classification and Clustering Ensembles), receives as inputs class probability distribution estimates for objects in a target set as well as a similarity matrix. Such a similarity matrix is typically built from clusterers induced on the target set, whereas the class probability distributions are obtained by an ensemble of classifiers induced from a training set. As a result, C3E provides refined estimates of the class probability distributions, from the consensus between classifiers and clusterers. The underlying idea is that similar new objects in the target set are more likely to share the same class label. In this thesis, a simpler version of the C3E algorithm, based on a Squared Loss function (C3E-SL), was investigated from an approach that enables the automatic estimation (from data) of its critical parameters. This approach uses a new evolutionary strategy designed to make C3E-SL more practical and flexible, making room for the development of variants of the algorithm. To address the scarcity of labeled data, a new algorithm that performs semi-supervised learning was proposed. Its mechanism exploits the intrinsic structure of the data by using the C3E-SL algorithm in a self-training procedure. Such a notion inspired the development of another algorithm based on active learning, which is able to self-adapt to learn new classes that may emerge when classifying new data. An extensive experimental analysis, focused on real-world problems, showed that the proposed algorithms are quite useful and promising. The combination of supervised and unsupervised learning yielded classifiers of great practical value and that are less dependent on user-defined parameters. The achieved results were typically better than those obtained by traditional classifiers.

Earth Observation is the gathering of information about planet Earth’s system via Remote Sensing technologies for monitoring land cover types and their changes. Through the years, image classification techniques have been widely studied and employed to extract useful information from Earth Observation data such as satellite imagery. One of the most attractive use cases is the monitoring of polar regions, that recently observed some dramatic changes due to global warming. Indeed drifting ice caps and icebergs represent threats to ship activities and navigation in polar areas, and the risk of collision with land-derived ice highlights the need to design a robust and automatic Sea-Ice classification for delivering up-to- date and accurate information. To achieve this goal, satellite data such as Sentinel-1 Synthetic Aperture Radar images from the European Union’s Copernicus program can be given in input to a Deep Learning classifier based on Convolutional Neural Networks capable of giving the content categorization of such images as output. For the task at hand, the availability of labeled data is generally scarce, there- fore the problem of learning with limited labeled data must be faced. There- fore, this work aims at leveraging the broader pool of unlabeled satellite data available to open up new classification solutions. This thesis proposes a Semi-Supervised Learning approach based on Generative Adversarial Networks. Such an architecture takes in input both labeled and unlabeled data and outputs the classification results exploiting the knowledge retrieved from both the data sources. Its classification performance is evaluated and it is later compared with the Supervised Learning approach and the Transfer Learning approach based on pre-trained networks. This work empirically proves that the Semi-Supervised Generative Adversarial Networks approach outperforms the Supervised Learning method, improving its Overall Accuracy by at least 5% in configurations with less than 100 training labeled samples available in the use cases under evaluation, achieving performance comparable to the Transfer Learning approach and even over- coming it under specific experimental configurations. Further analyses are then performed to highlight the effectiveness of the proposed solution. / Jordobservation är samlingen av information om jordklotets system via fjärravkänningstekniker för övervakning av landskapstyper och deras förändringar. Under årens lopp har bildklassificeringstekniker studerats och använts för att extrahera användbar information från jordobservationsdata som satellitbilder. Ett av de mest attraktiva användningsfallen är övervakningen av polära regioner, som nyligen observerade några dramatiska förändringar på grund av den globala uppvärmningen. Driftande istäcken och isberg representerar ett verkligt hot mot fartygsaktiviteter och navigering inom polära områden, och risken för kollision med land-baserad is belyser behovet av att utforma en robust och automatisk Hav-Is-klassificering för att leverera aktuell och korrekt information. För att uppnå detta mål kan satellitdata som Sentinel-1 Synthetic Aperture Radar-bilder från Europeiska unionens Copernicus-program ges som input till en Deep Learning-klassificerare baserad på Convolutional Neural Networks som kan ge innehållskategorisering av sådana bilder som output. För den aktuella uppgiften är tillgängligheten av märkt data i allmänhet otillräcklig, därför måste problemet med inlärning med begränsad mängd märkt data ställas inför rätta. Därav syftar detta arbete till att utnyttja den bredare samlingen av omärkt satellitdata som finns tillgänglig för att öppna nya klassificeringslösningar. Denna avhandling föreslår en Semi-Supervised Learning-strategi baserad på Generative Adversarial Networks. En sådan arkitektur tar som input både märkt och omärkt data, och matar ut klassificeringsresultat som utnyttjar den kunskap som hämtats från båda datakällorna. Dess klassificeringsprestanda ut- värderas och jämförs senare med tillvägagångssättet Supervised Learning och metoden Transfer Learning baserat på förtränade nätverk. Detta arbete bevisar empiriskt att Semi-Supervised Generative Adversarial Network överträffar metoden Supervised Learning och förbättrar dess totala noggrannhet med minst 5% i konfigurationer med mindre än 100 tränings- märkta prover tillgängliga i användningsfallen under utvärdering, vilket uppnår prestanda som både är jämförbar med Transfer Learning-metoden och överlägsen jämte den under specifika experimentella konfigurationer. Ytterligare analyser utförs sedan för att belysa effektiviteten hos den föreslagna lösningen.

Natural Language Processing (NLP) develops computational approaches to processing language data. Supervised machine learning has become the dominant methodology of modern NLP. The performance of a supervised NLP system crucially depends on the amount of data available for training. In the standard supervised framework, if a sequence of words was not encountered in the training set, the system can only guess at its label at test time. The cost of producing labeled training examples is a bottleneck for current NLP technology. On the other hand, a vast quantity of unlabeled data is freely available. This dissertation proposes effective, efficient, versatile methodologies for 1) extracting useful information from very large (potentially web-scale) volumes of unlabeled data and 2) combining such information with standard supervised machine learning for NLP. We demonstrate novel ways to exploit unlabeled data, we scale these approaches to make use of all the text on the web, and we show improvements on a variety of challenging NLP tasks. This combination of learning from both labeled and unlabeled data is often referred to as semi-supervised learning. Although lacking manually-provided labels, the statistics of unlabeled patterns can often distinguish the correct label for an ambiguous test instance. In the first part of this dissertation, we propose to use the counts of unlabeled patterns as features in supervised classifiers, with these classifiers trained on varying amounts of labeled data. We propose a general approach for integrating information from multiple, overlapping sequences of context for lexical disambiguation problems. We also show how standard machine learning algorithms can be modified to incorporate a particular kind of prior knowledge: knowledge of effective weightings for count-based features. We also evaluate performance within and across domains for two generation and two analysis tasks, assessing the impact of combining web-scale counts with conventional features. In the second part of this dissertation, rather than using the aggregate statistics as features, we propose to use them to generate labeled training examples. By automatically labeling a large number of examples, we can train powerful discriminative models, leveraging fine-grained features of input words.

Hurst exponent and variance are two quantities that often characterize real-life, highfrequency observations. We develop the method for simultaneous estimation of a timechanging Hurst exponent H(t) and constant scale (variance) parameter C in a multifractional Brownian motion model in the presence of white noise based on the asymptotic behavior of the local variation of its sample paths. We also discuss the accuracy of the stable and simultaneous estimator compared with a few selected methods and the stability of computations that use adapted wavelet filters. Multifractals have become popular as flexible models in modeling real-life data of high frequency. We developed a method of testing whether the data of high frequency is consistent with monofractality using meaningful descriptors coming from a wavelet-generated multifractal spectrum. We discuss theoretical properties of the descriptors, their computational implementation, the use in data mining, and the effectiveness in the context of simulations, an application in turbulence, and analysis of coding/noncoding regions in DNA sequences. The wavelet thresholding is a simple and effective operation in wavelet domains that selects the subset of wavelet coefficients from a noised signal. We propose the selection of this subset in a semi-supervised fashion, in which a neighbor structure and classification function appropriate for wavelet domains are utilized. The decision to include an unlabeled coefficient in the model depends not only on its magnitude but also on the labeled and unlabeled coefficients from its neighborhood. The theoretical properties of the method are discussed and its performance is demonstrated on simulated examples.

Gaussian Processes (GPs) are promising Bayesian methods for classification and regression problems. They have also been used for semi-supervised classification tasks. In this thesis, we propose new algorithms for solving semi-supervised binary classification problem using GP regression (GPR) models. The algorithms are closely related to semi-supervised classification based on support vector regression (SVR) and maximum margin clustering. The proposed algorithms are simple and easy to implement. Also, the hyper-parameters are estimated without resorting to expensive cross-validation technique. The algorithm based on sparse GPR model gives a sparse solution directly unlike the SVR based algorithm. Use of sparse GPR model helps in making the proposed algorithm scalable. The results of experiments on synthetic and real-world datasets demonstrate the efficacy of proposed sparse GP based algorithm for semi-supervised classification.