Segmentação de Strings com Aprendizado de Máquina

Gravatar publicou em

Ciência de Dados Programação

O uso de inteligência artificial na linguagem vêm apresentando interessantes resultados, principalmente na área de tradução. Outros exemplos incluem sugestões de correção em erros ortográficos e até mesmo o reconhecimento de fala.

Para testar um algoritmo simples que trabalha com elementos de uma linguagem, foi desenvolvido um programa com o objetivo de conseguir separar as palavras de uma string que não contenha espaços. Por exemplo, ao receber "thisishowitshouldwork", o programa deveria retornar "this is how it should work". 

O problema consiste em determinar o que deve ser considerado uma palavra, visto que é impossível listar todas as palavras conhecidas em Inglês e não há como construir um modelo eficiente que consiga generalizar sua estrutura.

A abordagem foi utilizar aprendizado supervisionado e uma grande quantidade de texto como base de treinamento para que o programa conseguisse passar a identificar as diversas palavras que compõem a língua inglesa. A vantagem de utilizar textos ao invés de uma simples lista contendo todas as palavras conhecidas é a possibilidade de verificar a frequência com que cada uma aparece. Conhecendo a probabilidade de aparição de cada palavra, pode-se calcular a mais provável divisão da string recebida.

Portanto, é possível determinar que a probabilidade de uma certa divisão da string é função das probabilidades de cada palavra obtida na divisão. Para aumentar a qualidade dos resultados, poderia ser considerada a probabilidade de uma palavra ocorrer após outra certa palavra, mas devido à relativa pequena quantidade de texto utilizado na etapa de treinamento, foi considerada apenas a probabilidade individual de cada palavra.

Outra questão a ser considerada é como lidar com palavras que nunca apareceram na base de treinamento. É impossível garantir, por maior que seja seu texto, que ele contém todas as palavras existentes na língua. Foi utilizada Suavização de Laplace para o cálculo das probabilidades, de modo a evitar que palavras não encontradas tenham probabilidade zero. Por fim, foi realizada uma normalização para possibilitar a comparação entre divisões da string de diferentes números de palavras.

A probabilidade de uma palavra pode então se expressa por: 

 

 

onde n é o número de aparições da palavra na base de treinamento, T o total de palavras analisadas, k é uma constante e V é o vocabulário total estimado. Foram utilizados k = 1 e V = 2.000.000.

A probabilidade de uma segmentação é então:

onde p1, p2, … pn são as possíveis palavras obtidas nessa segmentação.

Com as fórmulas determinadas, é preciso lidar agora com um problema de limitação computacional. Uma string de n letras possui 2n-1 modos de ser segmentada, de modo que para calcular a melhor segmentação da string "thisishowitshouldwork" já seria necessário comparar o resultado das mais de 1 milhão de possíveis divisões. 

Para contornar esse problema, pode-se ajustar o algoritmo para segmentar a string sempre em duas partes, f (first part)  e r (rest). Caso a probabilidade de f seja X vezes maior que a de r, pode-se considerar que a divisão encontrou uma boa segmentação em f e então deve tentar segmentar r também.

Portanto, têm-se que:

 

 

 

onde foi utilizado X = 10 para strings menores que 50 caracteres e X = 15 caso contrário, para diminuir o tempo de cálculo em strings maiores. 

Feito o cálculo das probabilidades e possuindo um modo de avaliar as diferentes segmentações possíveis, o programa está pronto para testes. 

Inicialmente, verifiquemos como diferentes segmentações da string de referência "thisishowitshouldwork" são avaliadas. 

 Segmentação   Probabilidade
  t hisishowitshouldwork  1,06e-07
  th is is how it should work  1,57e-05
  thi si show it should work  1,96e-06
  this is how it should work  1,14e-04
 
 
 
 
Tabela 1 - Probabilidades de segmentação da string 'thisishowitshouldwork' 

Pode-se observar que a segmentação correta é aquela que possui maior probabilidade, de acordo com o esperado. 

Seguem abaixo outros resultados obtidos, onde sample_size é o total de palavras encontradas na base de treinamento, vocab é o tamanho do vocabulário estimado, NULL_PROB é a probabilidade mínima (para palavras nunca vistas) e split_factor corresponde ao fator X da equação acima. O número que acompanha a segmentação refere-se à probabilidade da mesma.

<~~ k = 1, sample_size = 2.697.372, vocab = 2000000, NULL_PROB = 2.14e-07 ~~>
Please type a sequence of words to be segmented (or 0 to stop)
idontknowwhatweareyellingabout
i dont know what wear eye ll ing about
2.84e-06
Took 0.008062 seconds to calculate with split factor = 10
thepasswordisnewspaper
the pass word is news paper
2.03e-05
Took 0.002943 seconds to calculate with split factor = 10
itstheendoftheworldasweknowit
its the end of the world as we know it
5.92e-05
Took 0.009799 seconds to calculate with split factor = 10
idontunderstandwhyitdidnotworkthere
i dont under st and why it did not work there
3.55e-05
Took 0.035966 seconds to calculate with split factor = 10
closingtimeopenallthedoorsandletyououtintotheworld
closing time open all the doors and let you out in to the world
6.89e-06
Took 0.096056 seconds to calculate with split factor = 15
asyoucanseeitstillsplitswordsitshouldnt
as you can see it still split sword sit shouldnt
2.14e-06
Took 0.03346 seconds to calculate with split factor = 10
pleasedonttellmewhattodo
please dont tell me what to do
2.07e-05
Took 0.004592 seconds to calculate with split factor = 10
whatdoyouthinkofthenewguy
what do you think of the new guy
3.63e-06
Took 0.004329 seconds to calculate with split factor = 10
ihavetosayididnotexpectthattohappen
i have to say i did not expect that to happen
9.44e-06
Took 0.01048 seconds to calculate with split factor = 10

Com menos de 2,7 milhões de palavras analisadas, os resultados apresentam satisfatória precisão. Nota-se que alguns trechos das strings foram segmentadas em palavras diferentes das esperadas, como "split sword sit shouldnt" ao invés de "splits words it shouldnt" ou "the pass word is news paper" ao invés de "the password is newspaper". Os principais motivos que levam a essa imprecisão são a pequena quantidade de base de treinamento utilizada e a simplificação feita para consideradar apenas a probabilidade da palavra em si, e não da palavra de acordo com suas predecessoras. "split sword sit shouldnt" não faz sentido nenhum como frase, mas as probabilidades das palavras "split", "sword" e "sit" combinadas eram maiores que as de "splits", "words" e "it". Também é possível que a palavra "splits" não tenha aparecido nenhuma vez  dentre todas as analisadas.

Outras ocorrências são os erros das segmentações "wear eye ll ing" ao invés de "we are yelling" e "under st and" ao invés de "understand". Nesse caso, o erro pode ser atribuído à qualidade da base de treinamento, uma vez que "ll", "ing" e "st" não deveriam ser consideradas palavras pelo programa, mas por estarem presentes entre as 2,7 milhões analisadas, o agente classificou-as como válidas.

Na posse de uma base de treinamento maior e de mais qualidade e utilizando algoritmos mais refinados para o cálculo das probabilidades, os resultados obtidos certamente seriam ainda melhores.





Leia mais sobre: