Otimização de Repetição Espaçadade Flashcards: Relatório Final

Guilherme Hilário Monteiro, Graduação (Matemática Aplicada), projeto deconclusão para a disciplina Métodos de Otimização ministrada pelo prof.Bernardo da Costa em 2019.2.

Este trabalho está licenciado com uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 3.0 Brasil.

Repetição espaçada trata-se de uma abordagem à memorização que, dado umcerto objetivo de memorização, leva em conta o tempo entre atividadesassociadas a esse objetivo, de modo a minimizar o esforço e o tempoconsumido enquanto maximizar o domínio sobre o conteúdo. Esse método é, emgeral, associado ao uso de flashcards, frequentemente através do software Anki.Assumirei a familiaridade do leitor com o software (mais informações disponíveisem sua página oficial e sua página da Wikipédia) para que possamos poupardetalhes do conceito de repetição espaçada de flashcards.

OBJETIVO PRIMÁRIO: Usar a biblioteca cvxpy para definir programas deexibição de flashcards para o Anki através da solução de um problema deotimização.

Primeira Abordagem Consideramos um período de 60 dias e um acervo de flashcards, cada flashcardsendo representado por um natural a partir de uma enumeração. Seja

uma função modelada de modo a representar, através dotempo (tendo como como unidade um dia), a intensidade do domínio do usuáriosobre um flashcard , ou alternativamente a probabilidade estimada desseindivíduo lembrar de , ou ainda, o quão "bem" o usuário lembra de .Denominamos por funções-memória. Assumimos que, ao ser apresentado ocard pela -ésima vez no momento , o usuário tem seu domínio sobre ela em

decaimento de um a zero linearmente a partir de e, ao atingir zero, essedomínio permanece nulo:

sendo a velocidade de decaimento linear . Para uma representação quealinhe-se a realidade, espera-se que esteja associada ao número de vezesque foi visto até , i.e., , como também à dificuldade do conteúdode . Tal medida poderia ser obtida através do número de caracteres em , inputdo usuário sobre o card individual ou sobre o deck que a contém, ou ainda podeser estimado através do histórico de feedbacks dado pelo usuário. No que serefere à última ideia citada, poderíamos ter variante conforme as respostasdo usuário no período de 60 dias. No entanto, não abordamos aobtenção/estimação de um valor para nesse trabalho. Mais que isso,deixamos de lado a funcionalidade do Anki de ajustar o programa de acordo como feedback do usuário.

Retomando a modelagem, vamos assumir apenas que

de modo que o "esquecimento" é mais rápido para cards com mais altadificuldade , mas se torna mais lento cada vez que revemos o card .Gostaríamos ainda de pesar os flashcards com uma certa medida deimportância . O que temos em mente para a inclusão davariação no tempo para essa medida é a necessidade do domínio do conteúdode determinados cards em determinados eventos que ocorrerão no período queestamos considerando, como uma prova ou entrevista de emprego, porexemplo. Naturalmente, teremos definido pelo usuário de forma paramétrica.

PRIMEIRA FUNÇÃO-OBJETIVO Agora, de forma mais específica, afirmamos que nosso objetivo é maximizarnosso domínio total sobre todas as cartas, levando em conta também suaimportância de modo a ajustar prioridades. Com isso, chegamos a funçãoobjetivo a ser maximizada , que, dada uma matriz cuja entrada localizada nainterseção da -ésima linha e da -ésima coluna é , retorna

sendo

º

e o número de repetições por flashcard, o qual assumimos igual para todocard.

OBSERVAÇÃO: Para manter simplicidade, a primeira vez que o indivíduo vê umcard também é incluída na nossa definição de repetição.

Incluímos o termo como um "normalizador" entre simulações, para quepossamos comparar as mudanças no valor ótimo para diferentes escolhas paraos números de flashcards e repetições, funções-objetivo e outros parâmetros.

Retomemos nossa escolha para . Se , então para todo . Segundo nossa modelagem, esse cenário poderepresentar um evento em que o usuário perde completamente seu domíniosobre o card , evento qual pode ser denominado "esquecimento". Esse cenárioé altamente indesejável, pois pode implicar que todo trabalho sobre até entãose anulou (inclusive, faria sentido "resetar" os efeitos das repetições sobre avelocidade de decaimento nessa situação). Logo, estabelecemos a restrição

para todo e .

OBSERVAÇÃO: Poderíamos definir como o inverso do número de diasesperado para que esqueça-se o card após estudá-lo pela primeira vez.

A restrição nos permite integrar analiticamente se supormos constante paratodo :

onde foram incluídos para facilitar a escrita.

Uma vez que a forma quadrática é negativa semidefinida, é, portanto,côncava. Desse modo, chegamos ao problema de otimização

Figura 1: As funções-memória para sete dos 30 cards, esses seteordenados por dificuldade. Naturalmente, as descontinuidades representam os

.

A restrição se deve ao fato de que gostaríamos de ver apenas uma vezpor dia (considerando que, em essência, estamos "continuizando" um problemadiscreto, ver Punindo Acúmulo de Repetições, Outras Ideias).

Vê-se uma redundância teórica com a restrição , no sentido de que o pontode máximo será o mesmo com ou sem essa. No entanto, caso o número decards ou repetições seja alto, o problema pode assumir uma complexidadeelevada demais para que o algoritmo note essa condição. Portanto, a mantemoscomo um "guia" para o algoritmo de otimização.

RESULTADOS Geramos 30 cards com dificuldades tomadas aleatoriamente em efixamos . A otimização via cvxpy nos dá os resultados exprimidos naseguinte visualização:

Vê-se que, para constante, a importância torna-se irrelevante para aotimização. Isso é esperado, uma vez que as restrições do problema e ostermos cuja soma gera a função objetivo são independentes entre cards.

Figura 2

Para , é fácil ver que o ponto ótimo deve ser gerado aosepararmos as repetições o máximo possível, de modo que

onde é o momento ótimo para a primeira apresentação do card .

Outro ponto muito interessante que notamos mais recentemente no curso doprojeto é que, para , o ponto ótimo de acordo com nossoalgoritmo de otimização parece ser aproximadamente determinado por

, i.e.,

Porém, por essa definição, se , o que contradiz a restrição .Removendo a restrição, testes numéricos mostram que, de fato, nossa hipóteseestá correta:

O gráfico acima considera o problema de otimização com apenas uma carta, deimportância . O eixo das abcissas está associado a . O ponto e ovalor ótimos obtidos são outputs do cvxpy. As distâncias consideradas são deFrobenius e o erro absoluto. O valor ótimo estimado é avaliada no ponto ótimoestimado.

É possível que o crescimento lento dessas distâncias se deva a complexidadedo problema aumentando com o número de variáveis a ser otimizada peloalgoritmo. No entanto, também foi conferido por testes numéricos, mas nãoexibido no gráfico, que o valor ótimo estimado é maior ou igual ao valor ótimoobtido para todo número de repetições e dificuldade testados. Portanto,assumiremos que o ponto ótimo estimado é o verdadeiro ponto ótimo e odenotaremos por .

OBSERVAÇÃO: É facilmente detetável que a proximidade do ponto ótimo obtidopara o problema com 30 flashcards exibido na Figura 1 em relação ao pontoótimo estimado para esse caso não está tão baixa quanto os resultados queacabamos de obter. Novamente, devemos considerar a complexidade: o númeromáximo de variáveis tomadas no segundo problema é 60, enquanto no primeirofixamos variáveis.

A ideia mais natural para a estimativa da ponto ótimo do problema com édefinir

onde é o menor natural tais que essas definições satisfazem . Em outraspalavras, seguir a aproximação entre as repetições com o aumento de dadapor e as fixar no limite estabelecido pela restrição quando essa aproximaçãoa atingir, enquanto redistribuindo as repetições que ainda não alcançaram olimite de forma análoga a nossa hipótese inicial. Não checamos se essa ideiaconfere com os resultados do cvxpy, uma vez que para todosos testes numéricos, sendo é a distância dos valores ótimos obtidos poresse com a restrição e sem a restrição e o valor máximo obtido sem arestrição.

Com os resultados obtidos até então, é fácil provar que

á

Fazendo então , é visualmente notável ao exibirmosseu gráfico que uma possível aproximação para é

sendo . Assumimos que . Não tivemos tempo de conferirtal hipótese propriamente.

Variando o número de repetições porflashcard

SEPARANDO EM DOIS ESTÁGIOS Consideremos agora que os números de repetições para cada card não sãonecessariamente iguais entre si e que o número total de apresentações deflashcards no período considerado é dado, o que nos leva aoseguinte problema de otimização:

onde . No entanto, resolver esse problemadiretamente vai muito além do nível de convexidade do cvxpy, entre váriasrazões para tal estando termos uma variável que define o tamanho de outravariável.

Felizmente, a partir dos achados da seção anterior, o problema é separável emdois estágios. Primeiro,

Figura 3

e, em seguida, usando o ponto ótimo , resolvemos o problema

A solução não será equivalente no sentido estrito da palavra, uma vez que não incorpora . No entanto, nossos testes numéricos nos deram evidênciaspara afirmar que o erro é desprezível.

RESULTADOS Na prática, utilizamos a aproximação côncava para o estágio .Definimos o número total de cards como o mesmo número total de cards doresultado inicial, i.e., o produto da quantidade de cards (30) vezes .

Observa-se um aumento de mais 30% para o valor ótimo obtido. Algointeressante a pontuar é que pode ser nulo para alguns cards se essesestiverem classificados com uma importância consideravelmente baixa. A Figura4 nos mostra que parece não haver uma relação tão forte entre o número ótimode repetições e a dificuldade.

Figura 4

PUNINDO ACÚMULO DE REPETIÇÕES A ideia mais natural para formular o problema abordado nesse projeto éconsiderar um tipo de variável completamente diferente, uma matriz detamanho º , com entradas booleanas representandoapresentar ou não o card em determinado dia. Isso acabou se mostrando serrealmente complicado de lidar sob a estrutura do cvxpy. No entanto, deixemosessa condição de lado por um instante.

Existe uma óbvia bijeção se restringirmos para todos e .Poderíamos, assim, estender nosso problema para

onde a restrição limita o "fardo mental" diário, de modo a permitir muitoscards fáceis em um dia, mas não muitos difíceis. Outrossim, essa poderepresentar limitações no tempo disponível para o estudo dos cards sesupormos que mais alta dificuldade implica que um tempo maior é necessáriopara trabalhar um card propriamente. Uma ideia é definir em módulo 7, demodo a adaptar o trabalho nos flashcards a rotina semanal do usuário (por

exemplo, podemos querer que os para os de sábados domingo sejammaiores).

Uma alternativa mais "maleável" que incluir esse conceito como restrição éincluir o fardo diretamente na função-objetivo, substituindo-a por suaLagrangiana:

Com essa modelagem, podemos permitir que o algoritmo escolha mostrarmuitos cards para períodos onde culmina. Isso pode ser bom ou ruim,dependendo do quão flexível é a agenda do usuário.

Voltando a realidade da nossa biblioteca de otimização, deveríamos poder usaro ponto ideal que obtivemos na seção anterior e corrigir problemas deproximidade através da bijeção supracitada:

onde arredonda cada entrada da matriz ao seu inteiro mais próximo e . Nosso objetivo é satisfazer a restrição enquanto editamos

o mínimo possível. O termo representa o quão distante está de obviamente de forma "normalizada". Com isso, pesamos esses elementos com a"contribuição" de a função objetivo, de modo cards de maior impacto àfunção objetivo deveriam ser perturbados relativamente menos que cards deimpacto menor quando o ajuste for feito sobre o programa para que a restrição

seja cumprida.

Todavia, embora esse problema seja convexo caso continuizemos a variável (oque costuma ser suficiente para o cvxpy), a biblioteca é incapaz de resolvê-lodevido às suas limitações em relação às varíaveis não-contínuas, mesmo com oauxílio do soluconador GUROBI.

Outras Ideias A seguir, listo algumas ideias descartadas que tive durante o curso da realizaçãodo projeto. Várias outras não foram incluídas nesse relatório, mesmo quealguma dessas tendo sido até implementadas. Em geral, as que não foramincluídas, referiam-se a versão da modelagem onde o número de repetições éigual para todo card, o que consideramos muito aquém do nosso verdadeiroobjetivo.

TEMPO DISCRETO Como não desejamos mostrar um flashcard mais de uma vez por dia e quecontrolar o horário exato em que o usuário verá uma carta é absurdo, variáveisdiscretas seriam mais intuitivas para esse problema. Contudo, embora aceitaspelo cvxpy, variáveis discretas geram tempos de execução muito mais extensosquando em grande número e, com frequência, a otimização problema nãoconverge se usarmos o algoritmo de otimização padrão do cvxpy. Felizmente,no domínio , a função objetiva é contínua em relação a cada variável eesperamos que sua característica quadrática e a geometria incorporada nãogerem variações tão grandes para valores ao aplicarmos .

FUNÇÃO DE DOMÍNIO ALTERNATIVA Uma possibilidade é formular a função-memória como

de modo que, se é constante,

função que é convexa de forma mais explicita e também mais fácil de serescrita. Note também que não é necessário restringir para que assuma essaforma. Ora, uma vez que quaisquer que sejam , de modo que por sisó não incorpora o evento de "esquecimento", fazendo com que o algoritmopossa esticar demais o intervalo entre duas repetições caso não fixemos umnúmero de repetições suficiente. A restrição (ou alguma outra que possasubstituí-la) ainda seria requerida.

INCORPORAR O FARDO MENTAL NONÚMERO DE REPETIÇÕES

Como fomos incapazes de punir o acúmulo de repetições por dia pesando asdificuldades das cartas, podemos limitar a dificuldade encontrada através datotalidade do período considerado:

FEEDBACK COMO VARIÁVEL ALEATÓRIA Uma possível ideia foi definir, para ,

onde é uma variável aleatória que representa o feedback do usuárioao trabalhar o card pela -ésima vez (lembrar ou não do flashcard). Ou seja,

reseta toda vez que o usuário não consegue lembrar do card. Poderíamosassumir que

Alternativamente, poderíamos ter , de modo a representaros múltiplas opções de feedback do Anki (Again, Hard, Good, Easy). Dessemodo, poderíamos ter

Em ambos os casos, a função-objetivo seria . No entanto, encontramosmuitos problemas para resolver as versões mais simples da modelagem, nãorestando tempo para trabalhar sobre essa possibilidade.

Comentário Final

A partir das questões consideradas em Feedback como Variável Aleatória,poderia-se argumentar que traçar um programa para os flashcards de uma sóvez tem poucas vantagens sobre uma abordagem na qual apenas determinamosa próxima repetição de um card logo ao recebermos o feedback sobre arepetição atual. No entanto, um ponto importante que pode ser extraído doproblema abordado nesse trabalho é sua utilidade para determinar quandodeveríamos apresentar um card pela primeira vez. Imagine que tivéssemosobtido êxito em punir o acúmulo de repetições. Assuma também que nossasolução é próxima o suficiente do que uma abordagem online resultaria. Assim,nossa versão seria uma boa maneira de determinar qual o momento maisoportuno de introduzir um novo card levando em conta as possibilidades futurasa longo prazo, algo que um algoritmo que simplesmente considera o próximopasso seria incapaz de fazer.