Abstract

modelagem temporal e análise e, mais especificamente, ordenação temporal são problemas muito importantes nos domínios de bioinformática e biologia computacional, como a análise temporal dos eventos que caracterizam um determinado processo biológico poderiam fornecer insights significativos em o seu desenvolvimento e progressão. Particularmente, no caso do câncer, a compreensão da dinâmica e da evolução da doença pode levar a melhores métodos de previsão e tratamento. Neste artigo, abordar, do ponto de vista computacional, o

ordenação temporal

problema, que se refere à construção de uma coleção ordenada de dados biológicos multi-dimensionais, coleção que reflete uma evolução temporal precisa de sistemas biológicos. Nós introduzimos uma nova abordagem, baseada em aprendizado por reforço, mais precisamente, no

, para o problema de ordenação temporal biológica Q-learning. A avaliação experimental é realizada utilizando vários conjuntos de dados de microarranjos de DNA, duas das quais contêm dados de expressão genética do cancro. As soluções obtidas são correlacionadas tanto com a dada ordenação correcta (nos casos em que esta é fornecida para validação), ou para o tempo de sobrevivência global dos doentes (no caso dos conjuntos de dados do cancro), confirmando, assim, um bom desempenho do modelo e indicando o potencial da nossa proposta proposto

Citation:. Czibula G, Bocicor IM, Czibula IG (2013) ordenação temporal de Câncer Microarray de dados através de uma abordagem Reinforcement Learning. PLoS ONE 8 (4): e60883. doi: 10.1371 /journal.pone.0060883

editor: Frank Emmert-Streib, University Belfast da rainha, Reino Unido

Recebido: 25 Dezembro, 2012; Aceito: 04 de março de 2013; Publicação: 02 de abril de 2013

Direitos de autor: © 2013 Czibula et al. Este é um artigo de acesso aberto distribuído sob os termos da Licença Creative Commons Attribution, que permite uso irrestrito, distribuição e reprodução em qualquer meio, desde que o autor original ea fonte sejam creditados

Financiamento:. Este trabalho foi parcialmente financiado pelo Programa Operacional setorial de Desenvolvimento de Recursos Humanos 2007-2013, co-financiado pelo Fundo social Europeu, sob o número do projeto POSDRU /107 /1,5 /S /76841 com o título “estudos de doutoramento modernos: Internacionalização e Interdisciplinaridade” . Os financiadores não tiveram nenhum papel no desenho do estudo, coleta de dados e análise, decisão de publicar ou preparação do manuscrito

CONFLITO DE INTERESSES:.. Os autores declararam que não existem interesses conflitantes

Introdução

os avanços das últimas décadas no campo da biologia resultaram em um aumento exponencial na quantidade de informação biológica. Dependendo do tipo e finalidade das experiências biológicas, os dados recolhidos podem variar a partir de sequências de nucleótidos e de proteínas, estruturas ou funções, a interacções moleculares e vias metabólicas. A análise destes dados revela importantes insights sobre diferentes processos biológicos e, eventualmente, leva a uma melhor compreensão dos organismos vivos.

Os processos biológicos são principalmente dinâmica e, portanto, a fim de caracterizar-los com precisão, os cientistas precisam de informação dinâmica. No entanto, a maioria dos dados existentes é estático, porque muitas vezes é mais difícil e desafiador para seguir um determinado processo ao longo do seu pleno desenvolvimento. Por exemplo, no caso de uma doença, em certas situações, é possível apenas para extrair dados de um conjunto de pacientes corrente, em vez de seguir os mesmos pacientes durante todo o curso da doença. Portanto, a necessidade de extrair informação dinâmica a partir de dados estática aparece e uma possível maneira de alcançar este objetivo seria inferir ordenações temporais a esses dados.

Neste artigo abordar, do ponto de vista computacional, o biológico

ordenação temporal (TO) problema

, que se refere à construção de uma coleção ordenada de dados biológicos multi-dimensionais, coleção que reflete uma evolução temporal precisa de um determinado processo biológico. divisão celular e crescimento, o desenvolvimento, a linhagem celular, metabolismo, ou, mais em particular, certas classes de doenças (como o cancro) são apenas alguns exemplos de tais processos biológicos dinâmicos. Os dados de entrada multi-dimensional pode ser o resultado de várias experiências biológicas: a expressão da proteína, microarrays de ADN, matrizes SNP, alterações do número de cópia cromossómica, hibridação comparativa do genoma. Neste trabalho, nós restringimos a considerar conjuntos de dados que consistem em amostras derivadas de experiências de expressão gênica por microarrays.

O

problema de ordenação temporal

abordados neste documento, que será definido na seguinte, ea importância do problema vai ser enfatizada. Nós também apresentamos várias abordagens afins para resolver o problema TO, já existentes na literatura.

A Declaração e Problema Relevância

modelagem temporal e análise e, mais especificamente, ordenação temporal é uma direção importante pesquisa dentro de campos múltiplos. De uma perspectiva de aprendizagem de máquina, em muitas situações, ordenando um determinado conjunto de casos no tempo fornece informações mais significativo do que atribuir-lhes certas classes de dados. Portanto, o problema geral de ordenação temporal é comparável, como importância, para o problema de classificação [1].

Dentro dos bioinformática e quadro biologia computacional, o problema ordenação temporal pode ser expressa em várias formas. Uma definição deste problema refere-se à determinação e que descreve a sequência de eventos que caracterizam um processo biológico. Se o processo em questão é cancro, por exemplo, o objectivo é encontrar uma ordem temporal para as alterações genéticas e da via que ocorrem durante a génese e evolução da doença. Sabe-se que a maioria dos tumores se desenvolvem por causa de mau funcionamento das redes de sinalização complexas, que é o resultado de mutações que aparecem em determinados genes-chave (oncogenes ou genes supressores de tumores) [2]. Portanto, estudando a ordem em que estas mutações acontecer poderia levar a uma melhor compreensão da evolução do cancro. Existem vários trabalhos na literatura que abordam o problema de ordenação temporal como foi descrito acima e estes serão apresentados na seguinte subseção.

O problema de ordenação temporal também pode ser formulado como o problema de construir uma coleção ordenada de dados biológicos multi-dimensional, recolha que reflecte uma evolução temporal exacta de um determinado processo biológico. O objectivo final é o de encontrar certos padrões nos dados de entrada, que variam ao longo do tempo e utilizá-los de forma eficiente, a fim de ser capaz de oferecer uma caracterização adequada do processo em questão. No que se refere esta direcção do estudo, existem basicamente duas obras que têm abordado este problema e estes também serão discutidos na subsecção seguinte. Nós mencionar que enfrentar o problema de ordenação temporal, formulada nesta segunda maneira.

Uma das aplicações mais importantes deste problema está dentro do campo da investigação oncológica. A maioria dos experimentos cancerosas humanas fornecer dados sem informação temporal, porque muitas vezes é muito difícil, ou mesmo impossível, a seguir os mesmos pacientes sobre o pleno desenvolvimento da doença. Em vez disso, as amostras experimentais são recolhidos a partir de bancos actuais de doentes, cujas doenças estão em diferentes fases de desenvolvimento e, consequentemente, cada amostra reflecte um grau diferente de progressão do cancro. A construção de uma série temporal de correcto dessas amostras pode, por um lado, fornecer informação significativa sobre o processo complexo da evolução do cancro. Por outro lado, a ordem temporal poderiam ser usados ​​para a previsão dos tempos de sobrevivência de doentes diagnosticados de novo: assumindo que, para os pacientes nos dados de entrada iniciais estabelecidos tempos de sobrevivência seria fornecido, quando novos pacientes, com tempos de sobrevivência desconhecidos são adicionados o conjunto de dados, a ordem temporal recuperado para todo o conjunto de amostras (incluindo os recém-adicionados) pode oferecer informações sobre as expectativas de vida globais das novas pacientes.

revisão da Literatura

o general para o problema é conhecido por ser NP-completo [1], o que significa que as soluções exactas são muito difíceis de obter e, portanto, vários métodos heurísticos têm sido aplicados para o resolver. O problema geral foi principalmente abordado por pesquisadores da comunidade de inteligência artificial (aprendizagem de máquina, mineração de dados) [1], [3]. Dentro do campo de mineração de dados, existem muitos estudos que extraem informação temporal de diferentes tipos de textos (, médicos, artigos de jornal gerais) [4] – [7]. Outras aplicações incluem triagem fotos de cidades a fim de observar o seu desenvolvimento ao longo do tempo [8] ou a construção de cronologias arqueológicos de vários artefactos [9].

Do ponto de vista da bioinformática e biologia computacional, diferentes formas do para o problema têm sido estudados e um número significativa de pesquisas concentrar em várias formas de cancro. Devido ao facto de que esta doença é um processo evolutivo, que é accionado por mutações e alterações do comportamento das células [10], uma linha importante de ofertas de trabalho com o desenvolvimento de modelos e inferindo ordens temporais para descrever as alterações em células cancerosas de ADN, bem como a determinar a ordem em que os eventos de mutação de genes e variações da via acontecer durante a evolução do câncer

.

Vários modelos probabilísticos têm sido propostas, a fim de recuperar a ordem temporal e casual em que as mutações acontecem no nível de genes e vias , durante a progressão do cancro [10] – [12]. Na obra de Hjelm

et al.

[11], o objetivo é estudar a evolução cromossômica em células cancerosas através da introdução e utilização de modelos probabilísticos generativas gráficas. Gerstung

et al.

[10] propõem um modelo probabilístico baseado em redes bayesianas, mais especificamente em uma classe de modelos gráficos chamado ocultos conjuntivas Bayesian Networks (H-CBNs), que foram propostas anteriormente para estudar o acúmulo de mutações e suas interdependências na progressão do cancro [12]. Os testes foram efectuados em conjuntos de dados que contêm dados de mutação transversais pertencentes a diferentes tipos de cancro (colorectal, pancreático e glioblastoma primário) e as conclusões de que estas H-CBNs fornecer um modelo de tumorigénese intuitiva [10].

Uma abordagem diferente para este problema é baseada em builduing modelos de árvore de possíveis eventos de mutação genética [13] – [17]. Desper

et al.

[13], [14] propor um modelo de árvore de oncogênese e usando dados de hibridação genômica comparativa eles mostram que, em determinadas hipóteses, seu algoritmo infere a árvore correta de eventos (onde um evento é visto como uma perda ou um ganho em um determinado cromossoma braço). A sua abordagem baseia-se na ideia de um máximo de peso ramificação em um gráfico. Esta metodologia proposta foi desenvolvido por Beerenwinkel

et al.

, Cujo modelo incluir várias árvores oncogenetic, correspondentes a várias sequências temporais de eventos que podem levar ao câncer [15], [16]. Pathare

et al

[17] analisar a progressão do câncer oral, utilizando ambos os modelos:.. Árvores distância introduzidas pela Desper

et al

[14] e a mistura de árvores oncogenetic introduzidas pela Beerenwinkel

et al.

[15], [16].

abordagens matemáticas também têm sido propostas para resolver o problema de identificar a sequência temporal de mutações que levam à progressão do cancro [18], [19]. Attolini

et al.

[18] introduzir uma abordagem matemática evolutiva chamada Refazendo os passos evolutivos em Câncer (RESIC), a fim de identificar a ordem temporal de mutações genéticas no desenvolvimento do câncer e testá-lo em vários cancro colorectal , glioblastoma e conjuntos de dados de leucemia. Este método foi desenvolvido em [19], a fim de incorporar, além de alterações genéticas, modificações das vias de sinalização molecular pelo qual o câncer progride.

Outra direção importante investigação centra-se em uma formulação diferente do TO problema. Dentro desta linha de trabalho, o problema é o de construir uma colecção separada de dados biológicos multi-dimensional que reflecte uma evolução temporal precisa de um processo biológico. Nós resolver o problema a partir do ponto de vista desta segunda definição. Para o nosso conhecimento, há principalmente dois trabalhos que abordam a biologiocal para o problema, tal como formulada acima, ambos usando dados de expressão de genes obtidos a partir de experimentos de microarray. Estes serão apresentados brevemente a seguir.

A primeira técnica, que usa dados de expressão do gene do cancro, é introduzido por Gupta e Bar-Joseph [20]. Os autores provar formalmente que, sob determinados pressupostos biológicos sobre o conjunto de dados de entrada, a única solução para o problema do caixeiro viajante (TSP) representa a ordenação temporal correta, com uma probabilidade alta. O TSP é definida de acordo com as amostras que compõem os dados de entrada estabelecidos, que são caracterizados pelos dados de expressão de genes de multi-dimensionais, como vértices e as distâncias entre eles são calculados usando a Manhattan () métrica. O método é aplicado a um conjunto de dados de 50 doentes com glioma e os resultados mostram uma boa correlação com a duração de sobrevivência dos pacientes. Além disso, um classificador que utiliza a ordenação obtido é definida, o que prova a superar outros classificadores desenvolvidos para a tarefa considerados e os principais genes que estão associados ao cancro são identificados.

O segundo estudo que se aproxima esta a forma de biológico à problema é introduzido por Magwene

et al.

[21] e o método proposto baseia-se na árvore de extensão mínima e PQ-árvores. O algoritmo de mínimos Spanning Tree é aplicado sobre, um grafo não-dirigido ponderada, em que cada nó é representado por uma instância do conjunto de dados, representada por dados de microarray multi-dimensional. A eficácia deste método é comprovada por testar os algoritmos de conjuntos de dados artificiais, bem como on-séries temporais conjuntos de dados de expressão de genes derivados de experimentos de microarranjos de DNA.

A principal contribuição deste trabalho é que ele introduz um nova abordagem para o TO problema, formulado como o problema de construir uma coleção ordenada de amostras biológicas multi-dimensionais, com base no aprendizado por reforço. Reforço de aprendizagem [22] é uma abordagem para a inteligência da máquina em que um agente [23] podem aprender a se comportar de uma certa maneira, recebendo castigos ou recompensas em suas ações escolhidas. Para o melhor de nosso conhecimento, a TO problema não foi abordado na literatura utilizando aprendizado por reforço, até agora. Vários experimentos realizados em diferentes conjuntos de dados de microarranjos de DNA mostram que o reforço proposto aprendizagem abordagem baseada êxito identifica ordenações temporais precisas sobre as dadas amostras biológicas.

Métodos

Nesta seção apresentamos a nossa reforço de aprendizagem baseados proposta para a identificação de uma ordenação temporal de uma série de amostras biológicas. Mesmo que, neste estudo, para restringir os dados de expressão de genes obtidos a partir de experiências de microarranjo, a aplicabilidade do nosso método é mais geral e pode ser utilizado com diferentes tipos de dados biológicos multi-dimensional.

Começamos por apresentar o fundamentos da

reforço

aprendizagem, em seguida, detalhamos a nossa abordagem.

aprendizado por reforço. Background

O objetivo da construção de sistemas que podem se adaptar a seus ambientes e aprender com as suas experiências tem atraído pesquisadores de diversos campos, incluindo ciência da computação, matemática, ciências cognitivas [22].

Reinforcement Learning

(RL) [24] é uma abordagem para a inteligência da máquina que combina duas disciplinas para resolver com êxito problemas que nem disciplina pode resolver individualmente:

programação dinâmica e

aprendizado supervisionado

. Na literatura de aprendizado de máquina, RL é considerado o tipo mais confiável de aprendizagem, uma vez que é o mais semelhante à aprendizagem humana. Ofertas de aprendizagem

Reforço com o problema de como um agente autônomo que percebe e age em seu ambiente pode aprender a escolher as acções ideais para atingir seus objetivos [25]. O campo de

agentes inteligentes

[26] é uma importante área de pesquisa e desenvolvimento no campo da inteligência artificial, agentes sendo considerados novos meios importantes na concepção e implementação de sistemas de software complexos. Um agente é uma entidade computacional, tal como um sistema de software ou um robô, situado em um certo environnment, que é capaz de perceber e agir de acordo com o seu ambiente e é capaz de actuar autonoumously, a fim de atingir os seus objectivos de concepção. Os agentes estão agindo em nome dos usuários, são

flexível

[27], o que significa que eles são

reativa

(capaz de responder às mudanças que ocorrem em seu ambiente),

pró-ativa

(capazes de exibir objetivo comportamento dirigido) e também tem um

capacidade sociais

(são capazes de interagir com outros agentes).

aprendizagem por reforço é útil em uma série de problemas práticos, tais como aprender a controlar robôs autonoumous [28], aprender a otimizar operatons em fábricas ou aprender a jogar jogos de tabuleiro. Em todos estes problemas, um agente artificial tem de aprender (por reforço) para escolher ações ideais, a fim de atingir os seus objectivos.

Em um cenário de reforço de aprendizagem, o sistema de aprendizagem seleciona ações a serem executadas no ambiente e recebe

recompensas

(ou

reforços

) sob a forma de valores numéricos que representam uma avaliação das acções seleccionadas [29]. Em RL, o computador é simplesmente dado uma meta a atingir. O computador então aprende a alcançar esse objetivo por meio de interações de tentativa e erro com seu ambiente. aprendizado por reforço é aprender o que fazer – como mapear situações para acções – de modo a maximizar a recompensa numérica. O aluno não é dito que as acções a tomar, como na maioria das formas de aprendizagem de máquina, mas em vez disso deve descobrir quais ações deu a mais alta recompensa por tentar-los. Em um problema de aprendizado por reforço, o agente recebe a recompensa como um feedback do ambiente; a recompensa é recebido no final, em estado terminal, ou em qualquer outro estado, onde o agente tem a informação correta sobre o que ele fez bem ou mal. O agente vai aprender a selecionar as ações que maximizam a recompensa recebida.

O objetivo do agente, em uma tarefa RL é maximizar a soma dos reforços recebidos quando a partir de um estado inicial e prosseguir para um estado terminal.

Um problema de aprendizagem reforço tem três partes fundamentais [22].

O ambiente

é representado por “estados”. Por interações com o meio ambiente, um sistema RL vai aprender uma função que mapeia estados para ações.

A função de reforço

. O objetivo do sistema de aprendizado por reforço é definido utilizando o conceito de uma função de reforço, que é a função de reforços o agente tenta maximizar. Esta função mapeia pares estado-ação para reforços. Depois de uma ação é executada em um determinado estado, o agente receberá uma avaliação da ação em uma forma de recompensa escalar. O agente vai aprender a executar as ações que irão maximizar o valor total da recompensa recebida em um caminho a partir do estado inicial para um estado final [30].

O valor (utilidade) função

é um mapeamento dos estados para os valores de estado. O valor de um estado indica a conveniência do estado e é definido como a soma das recompensas recebidas em um caminho daquele estado para um estado final. O agente vai aprender a escolher as ações que levam a estados que têm uma utilidade máxima [30]

Uma tarefa geral RL é caracterizada por quatro componentes:.

a

espaço de estado

que especifica todas as possíveis configurações do sistema;

um

espaço de ação

que lista todas as ações disponíveis para o agente de aprendizagem para executar;

a

função de transição

que especifica os resultados possivelmente estocásticos de tomar cada ação em qualquer estado;.

a

função de recompensa

que define a possível recompensa de tomar cada uma das acções

em cada passo de tempo, o sistema de aprendizagem recebe alguma representação do estado do meio ambiente, é preciso uma ação e um passo mais tarde ele recebe uma recompensa escalar e encontra-se em um novo estado. Os dois conceitos básicos por trás aprendizado por reforço é tentativa e erro, pesquisa e recompensa adiada [31]. A tarefa do agente é aprender uma política de controle, que maximiza a soma esperada das recompensas recebidas, com recompensas futuras com desconto exponencialmente por seu atraso, onde é definido como (é o fator de desconto para as futuras recompensas).

Um aspecto importante no aprendizado por reforço é o

exploração

. O agente tem de ser capaz de explorar seu ambiente, tentando novas acções (talvez não os melhores), que pode levar a melhores seleções de acção futuros [32]

Há dois projetos básicos RL a serem considerados:.

o agente aprende a

função de utilidade

(

U

) sobre os estados (ou estados histórias) e usa-o para selecionar as ações que maximizem a utilidade esperada de seus resultados.

o agente aprende um

função de valor de ação

(

Q

) dando a utilidade esperada de tomar uma determinada ação em um determinado estado. Isso é chamado

Q-learning

.

Um agente que aprende funções de utilidade [33] deve ter um modelo do ambiente, a fim de tomar decisões, como tem que conhecer a estados em que a sua acção vai liderar. Em um

Q-learning

cenário, no qual o agente aprende uma função de valor de ação, não há necessidade de ter um modelo do ambiente.

A nossa abordagem. Metodologia

Vejamos, a seguir, que é o conjunto de dados de entrada, que consiste em () amostras multi-dimensionais:, cada amostra a ser identificado por um conjunto de características. Para o tipo de dados considerado, cada funcionalidade é representada por um gene e tem como valor um número real, medir o nível da expressão do gene em questão. . Portanto, cada amostra pode ser codificado por um vector dimensional, onde está o nível de gene para a amostra expressão

A nossa abordagem consiste em duas etapas:

1. Dados pré-processamento.

2.

RL

projeto tarefa.

No seguinte iremos descrever estes passos.

pré-processamento de dados.

microarranjos de DNA permitem medição de milhares de níveis de expressão de gene para cada amostra, pelo qual a dimensão dos dados de entrada pode ser extremamente alta. Para além do facto de que isso pode levar a ineficiência no tempo computacional e espaço, na maioria dos casos, muitos genes pode ser irrelevante para a tarefa de ordenação e podem mesmo aumentar a quantidade de ruído nos dados, conduzindo a uma diminuição no desempenho do temporal sistema de encomendas. Por conseguinte, o objectivo do passo de pré-processamento é a eliminação dos genes que não oferecem informação significativa, ou, de modo equivalente, a selecção desses genes que são mais importantes para uma ordenação temporal preciso.

Como a final objectivo consiste em analisar e temporalmente encomendar conjuntos de dados compreendendo amostras extraídas de pacientes com cancro, no que se segue, descreve-se um método de pré-processamento de segmentação destes tipos particulares de conjuntos de dados. Tais conjuntos de dados geralmente oferecem uma série de informações para cada amostra, para além dos vectores de expressão do gene reais. Uma destas peças adicionais de informações que são normalmente encontradas em conjuntos de dados do cancro é a sobrevivência global, o que significa que o tempo de sobrevivência dos pacientes, a partir do momento em que foram tiradas as amostras. A partir da intuição de que, no caso geral, dois pacientes com tempos de sobrevivência semelhantes também seria relativamente próximo dentro da ordenação temporal, decidimos usar esta informação para identificar um subconjunto de genes que são relevantes para a tarefa de ordenação.

durante o passo de pré-processamento, uma análise estatística é realizada sobre o conjunto de dados, a fim de encontrar um subconjunto de recursos (genes) que são relevantes para a tarefa considerado. A análise estatística das características é executada a fim de reduzir a dimensão dos dados de entrada, através da eliminação de características que não estão correlacionados com a informação biológica adicional seleccionado para o dado conjunto de dados. Mais exatamente que visam identificar genes que não influenciam significativamente a identificação de ordenação temporal.

Para determinar as dependências entre os recursos e a dada informação biológica adicional, o coeficiente de correlação de Pearson é utilizado [34]. A correlação de Pearson é uma medida estatística da correlação linear entre duas variáveis ​​aleatórias que indicam como altamente correlacionadas as variáveis ​​são. Uma correlação de Pearson de entre duas variáveis ​​e indica que não existe uma relação linear entre as variáveis. A correlação de Pearson ou resulta quando as duas variáveis ​​que estão sendo comparados são linearmente monotonicamente relacionados. Uma correlação de Pearson [35] implica que de uma equação linear descreve a relação entre a e, com todos os pontos de dados encontra-se em uma linha para o qual aumenta à medida que aumenta. A correlação dos pontos implica que todos os dados ficam em uma linha para o qual diminui à medida que aumenta.

Como mencionado anteriormente, o objetivo desta etapa é para remover o recurso de definir essas características (genes) que são muito pouco correlacionados com a informação biológica suplementar seleccionado (que é, no caso de conjuntos de dados do cancro, o tempo de sobrevivência). Consequentemente, nós calcular o coeficiente de correlação de Pearson entre cada gene e o tempo de sobrevivência e manter apenas aqueles genes que têm o valor absoluto da correlação maior do que um certo limiar (é escolhido de forma a garantir uma redução radical de dimensionalidade).

a proposta de

RL

tarefa para o TO problema.

Como indicado acima, o TO problema consiste em determinar uma ordenação temporal precisa das amostras de entrada, o que reflete a evolução temporal e desenvolvimento de um determinado processo biológico dinâmico (por exemplo, cancro). Do ponto de vista computacional, o problema a podem ser vistos como o problema de gerar uma permutação de que maximiza a semelhança global sim da sequência de amostras consideradas na ordem: (). A semelhança geral Sim nós consideramos neste documento resume as semelhanças sobre todas as amostras adjacentes e tem que ser maximizado.

A semelhança geral Sim para a sequência de amostras é definida como na Equação (1) 🙁 1) onde indica a semelhança entre os vectores de dimensão e e é definida como. . Aqui pelo que denotam a distância euclidiana e é uma grande constante

Nós definimos a tarefa RL associado ao TO problema da seguinte maneira:

O espaço de estado (o ambiente do agente) será composto de estados , ou seja. O

estado inicial do agente no meio ambiente é. Um estado atingido pelo agente em um dado momento, depois de ter visitado os estados e selecionou ações é um estado

terminal de

(final ou meta) se o número de estados visitados pelo agente na seqüência atual é (ou seja, ) e todas as ações selecionadas são distintas, ou seja.

o espaço ação consiste de ações disponíveis para o problema agente de resolução de problemas e correspondentes aos possíveis valores usados ​​para representar uma solução (permutação de), ou seja, onde.

A função de transição entre os estados é definido como na Fórmula (2). (2) onde. Isto significa que, em um dado momento, de um estado o agente pode se mover em estados sucessores, executando uma das ações possíveis. Dizemos que um estado que é acessível a partir do Estado, ou seja, é o

vizinho

(

sucessor

) estado de.

As transições entre os estados são equiprovável , a probabilidade de transição entre um estado

s

e cada estado vizinho é igual, pois cada estado tem possíveis a partir de estados sucessores (ver Fórmula (2)).

a função recompensa será definido abaixo (Formula (3)).

Vamos considerar um caminho no ambiente acima definida a partir da inicial para um estado final, onde eo estado é um

vizinho

do Estado (). Considerando a tarefa RL definido acima, o ambiente pode ser visualizado como uma árvore. Neste ambiente de árvore, um caminho consiste de vértices distintos (estados) em que cada par adjacente de vértices é ligados por um arco (ação).

A sequência de acções obtidas seguindo as transições entre os estados sucessivos a partir do caminho vai ser denotado por, onde. A sequência será referida como a configuração da ação de

associado ao caminho. O

A configuração da ação

associada a um caminho dá uma sequência de amostras.

Um caminho é chamado

válido

se todas as ações dentro da sua

A configuração da ação

são distintos e cada amostra a partir da sequência é mais semelhante ao exemplo que se segue imediatamente na sequência ordenada do que para qualquer outra amostra, ou seja, e.

o

a configuração da ação

associado a um

caminho válido pode ser visto como um possível para que as amostras de entrada, ou seja, uma permutação que dá a ordem temporal das amostras consideradas, que deve ser, até certo ponto, correlacionados com o tempo de sobrevivência, no caso quando as amostras são representados pelos dados extraídos de doentes com cancro. Consequentemente, podemos associar a um

caminho

válido, um valor indicado por representando a semelhança global (ver equação (1)) da sequência.

O PARA problema formulado como um problema de RL será consistem em treinar o agente de encontrar um caminho a partir do inicial para um estado final com a semelhança global máximo associado. Após o processo de aprendizado por reforço, o agente vai aprender a executar essas transições que maximizam a soma das recompensas recebidas em um caminho a partir do inicial para um estado final.

Temos como objectivo a obtenção de um

válido

circuito que tem a semelhança global máximo da sequência de amostras correspondentes à configuração de acção associado, por conseguinte, define-se a função de reforço como se segue (Fórmula (3)) 🙁 3), onde pelo que denotam a recompensa recebida pelo agente no estado, depois sua história no meio ambiente é.

o agente recebe uma recompensa negativo sobre caminhos que não são válidos, portanto, ele vai aprender a explorar caminhos válidos apenas. Considerando a recompensa definido na Fórmula (3), com o objectivo de aprendizagem é o de maximizar a quantidade total de recompensas recebida em um caminho a partir do inicial para um estado final, pode ser mostrado que o agente é treinado para encontrar um caminho válido que maximiza a semelhança global do ordenamento associada.

o processo de aprendizagem.

Durante a etapa de formação do processo de aprendizagem, o agente irá determinar a sua

óptima política

no ambiente, ou seja, o mapeamento dos estados para ações que maximizam a soma das recompensas recebidas.

para treinar o

pARA agente

, propomos uma abordagem Learning, em que o agente aprende um valor de acção