Autor(es):
Jordán, Gladys Castillo 
Data: 2006
Identificador Persistente: http://hdl.handle.net/10773/4857
Origem: RIA - Repositório Institucional da Universidade de Aveiro
Assunto(s): Matemática; Sistemas adaptativos; Algoritmos de aprendizagem; Inteligência artificial; Redes neuronais
Descrição
Nesta tese consideramos o desenvolvimento de algoritmos adaptativos para
classificadores de redes Bayesianas (BNCs) num cenário on-line. Neste
cenário os dados são apresentados sequencialmente. O modelo de decisão
primeiro faz uma predição e logo este é actualizado com os novos dados. Um
cenário on-line de aprendizagem corresponde ao cenário “prequencial”
proposto por Dawid. Um algoritmo de aprendizagem num cenário prequencial
é eficiente se este melhorar o seu desempenho dedutivo e, ao mesmo tempo,
reduzir o custo da adaptação. Por outro lado, em muitas aplicações pode ser
difícil melhorar o desempenho e adaptar-se a fluxos de dados que apresentam
mudança de conceito. Neste caso, os algoritmos de aprendizagem devem ser
dotados com estratégias de controlo e adaptação que garantem o ajuste rápido
a estas mudanças.
Todos os algoritmos adaptativos foram integrados num modelo conceptual de
aprendizagem adaptativo e prequencial para classificação supervisada
designado AdPreqFr4SL, o qual tem como objectivo primordial atingir um
equilíbrio óptimo entre custo-qualidade e controlar a mudança de conceito. O
equilíbrio entre custo-qualidade é abordado através do controlo do viés (bias) e
da adaptação do modelo. Em vez de escolher uma única classe de BNCs
durante todo o processo, propomo-nos utilizar a classe de classificadores
Bayesianos k-dependentes (k-DBCs) e começar com o seu modelo mais
simples: o classificador Naïve Bayes (NB) (quando o número máximo de
dependências permissíveis entre os atributos, k, é 0). Podemos melhorar o
desempenho do NB se reduzirmos o bias produto das restrições de
independência. Com este fim, propomo-nos incrementar k gradualmente de
forma a que em cada etapa de aprendizagem sejam seleccionados modelos
de k-DBCs com uma complexidade crescente que melhor se vai ajustando ao
actual montante de dados. Assim podemos evitar os problemas causados por
demasiado viés (underfitting) ou demasiada variância (overfiting). Por outro
lado, a adaptação da estrutura de um BNC com novos dados implica um custo
computacional elevado. Propomo-nos reduzir nos custos da adaptação se,
sempre que possível, usarmos os novos dados para adaptar os parâmetros. A
estrutura é adaptada só em momentos esporádicos, quando é detectado que a
sua adaptação é vital para atingir uma melhoria no desempenho. Para
controlar a mudança de conceito, incluímos um método baseado no Controlo
de Qualidade Estatístico que tem mostrado ser efectivo na detecção destas
mudanças.
Avaliamos os algoritmos adaptativos usando a classe de classificadores k-DBC
em diferentes problemas artificiais e reais e mostramos as vantagens da sua
implementação quando comparado com as versões no adaptativas. This thesis mainly addresses the development of adaptive learning algorithms
for Bayesian network classifiers (BNCs) in an on-line leaning scenario. In this
scenario data arrives at the learning system sequentially. The actual predictive
model must first make a prediction and then update the current model with new
data. This scenario corresponds to the Dawid’s prequential approach for
statistical validation of models. An efficient adaptive algorithm in a prequential
learning framework must be able, above all, to improve its predictive accuracy
over time while reducing the cost of adaptation. However, in many real-world
situations it may be difficult to improve and adapt to existing changing
environments, a problem known as concept drift. In changing environments,
learning algorithms should be provided with some control and adaptive
mechanisms that effort to adjust quickly to these changes.
We have integrated all the adaptive algorithms into an adaptive prequential
framework for supervised learning called AdPreqFr4SL, which attempts to
handle the cost-performance trade-off and also to cope with concept drift.
The cost-quality trade-off is approached through bias management and
adaptation control. The rationale is as follows. Instead of selecting a particular
class of BNCs and using it during all the learning process, we use the class of
k-Dependence Bayesian classifiers and start with the simple Naïve Bayes (by
setting the maximum number of allowable attribute dependence k to 0). We can
then improve the performance of Naïve Bayes over time if we trade-off the bias
reduction which leads to the addition of new attribute dependencies with the
variance reduction by accurately estimating the parameters. However, as the
learning process advances we should place more focus on bias management.
We reduce the bias resulting from the independence assumption by gradually
adding dependencies between the attributes over time. To this end, we
gradually increase k so that at each learning step we can use a class-model of
k-DBCs that better suits the available data. Thus, we can avoid the problems
caused by either too much bias (underfitting) or too much variance (overfitting).
On the other hand, updating the structure of BNCs with new data is a very
costly task. Hence some adaptation control is desirable to decide whether it is
inevitable to adapt the structure. We reduce the cost of updating by using new
data to primarily adapt the parameters. Only when it is detected that the use of
the current structure no longer guarantees the desirable improvement in the
performance, do we adapt the structure. To handle concept drift, our
framework includes a method based on Statistical Quality Control, which has
been demonstrated to be efficient for recognizing concept changes.
We experimentally evaluated the AdPreqFr4SL on artificial domains and
benchmark problems and show its advantages in comparison against its nonadaptive
versions. Doutoramento em Matemática
Tipo de Documento
Tese de Doutoramento
Idioma
Inglês
Orientador(es)
Gama, João Manuel Portela da; Breda, Ana Maria Reis d'Azevedo
