Resumos de aula: PLN - 2019

Nome	Resumo
Michelle Kaori Hamada	O tema: “Feature hashing”. Ela aborda uma continuação da matriz (esparsa) de termo-contexto visando principalmente o tamanho da matriz, em que transformamos um vetor esparso para um vetor denso uma vez que este é uma estrutura mais “fácil” de trabalhar nos algoritmos de aprendizado de máquina. Como a estrutura de dados usada vai depender do tamanho do vocabulário, consideramos a mesma idéia dos vetores em SVD na matriz PPMI, que reduzimos o vocabulário por meio da fatoração por três matrizes. Contudo, as matrizes a serem criadas são tão grandes que torna impossível guardá-la na memória não podendo, portanto, operá-las. A solução para tal é a utilização de hashing, de tabelas de dispersão. Para se resolver os problemas de busca, inserção e remoção em uma tabela (vetores/arrays) com n elementos, existem várias maneiras que possuem custos diferentes: Busca sequencial O(n); Busca Binária O(log2(n)), melhor que sequencial mas ainda lento, pois se n é grande, por exemplo log2 (1000000) = 20; Uso de árvores balanceadas (acesso O(log(n)) bem melhor que a busca sequencial). Entretanto, há uma estrutura ainda melhor que são as tabelas hash/tabelas de espalhamento/tabelas de dispersão. O acesso médio da busca é igual a O(1), isso significa “constante” na média. O seu pior caso é O(n), na medida do possível uma constante pequena. São estruturas de dados eficientes para implementar um dicionário. Nas tabelas hashing ocorre o acesso/endereçamento direto, considerando que os valores das chaves estejam entre: 0,1, , m-1: Pode-se usar diretamente o valor de cada chave em seu índice de tabela (cada chave x armazenada no compartilhamento x). O endereçamento direto se baseia no fato de que é possível examinar uma posição qualquer em O(1). Isto é aplicável quando podemos alocar uma tabela com uma posição para cada chave possível. Essa é uma técnica simples que funciona quando o universo de chaves é razoavelmente pequeno. A dificuldade de usar endereçamento é justamente quando o número de chave/reserva é muito grande, ou seja, a alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande. Mas se o conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U, dessa forma temos como espaço utilizado O(|U|) e tempo de busca O(1). Dada a limitação, se a quantidade de chaves for maior, uma das soluções é empilhar as chaves mas o melhor mesmo seria espalhá-las uniformemente. Isso pode ser feito através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela (endereço base): hash(chave) -> {0,1, , m-1}, assim h(k) é uma função h que mapeia o universo U de chaves para entradas de tabela de espalhamento T[0, , m-1]: h: U -> {0,1, ,m-1}. Uma das dificuldades dessa técnica é a possibilidade de ao menos duas instâncias serem mapeadas para a mesma posição, contudo uma forma de tratar essas colisões seria por meio de encadeamento. Há também como evitar essas colisões utilizando uma função Hash que apresente um “comportamento randômico”. A operação de inserção é executada em tempo O(1), a remoção de um elemento é executado em tempo O(1) e a busca leva tempo proporcional ao comprimento da lista. A seguir observamos algumas das funções de dispersão. A primeira foi o método da divisão em que sua aplicação é fácil, eficiente e largamente empregado. Nele a chave k é dividida pela dimensão da tabela m e o resto da divisão é o endereço base h(k) = k mod m. O resultado são os endereços no intervalo: [0,m-1], exemplo: m=12 e k=100 -> h(k) = k mod m -> h(100) = 100 mod 12 = 4. Os melhores valores para m são números primos pois podemos gerar um hash único multiplicando cada um dos dígitos ou letras constituintes por um número primo e somando-os. Por exemplo, supondo que desejamos alocar n=2000 elementos de 8 bits, e que não nos importamos em procurar em listas (ligadas) de tamanho médio 3. Para determinarmos o tamanho apropriado para a tabela T, seria fazer m=701, pois este é um número primo próximo de 2000/3, pois queremos saber que número dividindo 2000 dê no mínimo 3 chaves por índice, então a = n/m = 2000/701 ~ 3. Outro método é o da multiplicação. Ele utiliza uma constante A (0<A<1), sendo h(k) calculado como: h(k) = m(kA mod 1) arredondando para baixo. A vantagem deste é que o valor de m não é crítico como no método de divisão. Entretanto, a escolha de que a constante A seja adequada é crítica. Para a constante A, existem também valores que são melhores do que outros, em particular a razão áurea que encontramos em muito na natureza, seu valor é A ~ (sqrt(5) - 1)/2 = 0,6180339887. Existe também o método da dobra, utilizado principalmente quando o número é muito grande. Consiste em quebrar a chave em partes e combiná-las de algum modo. Por exemplo, se as chaves são números de 8 dígitos e a tabela hash tem 100 entradas, devemos quebrar a chave em 3 números: Número 1 - 3 dígitos; Número 2 - 3 dígitos; Número 3 - 2 dígitos. E então somá-los, considerando os 3 últimos dígitos da soma para compor a chave. Quando a chave dada for uma string, uma alternativa é interpretá-la como um natural em uma base conveniente (gato = 7 * (26^3) + 1 * (26^2) + 20 * (26^1) + 15 = 124243), mas quanto mais longas as palavras forem maior o desafio uma vez que o valor calculado pode ser muito grande. Um problema dessa conversão é várias palavras teriam os mesmos valores uma vez que as posições relativas são perdidas. Em suma, como vantagens a tabela hash possui que é um algoritmo simples e eficiente para inserção, remoção e busca, e de desvantagens é que ela não possui nenhuma garantia de balanceamento, possui espaço sub-utilizado nas tabelas e o grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. A feature hashing que é uma maneira rápida e eficiente para tratar vetores com muitas características. No lugar dos índices ( de uma matriz, como a de termo-contexto), será utilizado um valor de hash. Voltando para o contexto de SVD, usamos o hash para comprimir mas de forma uniforme, resolve, por exemplo, quando uma palavra existe apenas uma vez. Assim, essa estratégia permite reduzir dimensionalidade (número de características - e.g., colunas, pois não há como linhas não tem como diminuir). Em seguida vimos as aplicações, primeiro o Teste1 que possui o hashF que recebe uma palavra e calcula o seu valor, quanto maior o comprimento maior o seu valor, nele não temos controle do contradomínio. No Teste2, já acrescentamos um contradomínio que vai de 0 a 99. No Teste3 ocorre com colisão, é feito também uma matriz de posição, a função de hashing modelando por 100 e contabiliza quantas palavras caem na mesma posição. Quanto maior o M, maior será a variação. No teste4 temos o M ideal. Para matrizes termo- contexto a feature hashing utilizada (“hashing trick”), utiliza uma função de hashing mais sofisticada, que é muito utilizada para textos, aplicamos o testePLN para analisarmos. A saída ainda é esparsa mas muito menor.
Rodrigo Hiroaki Ideyama	Resumo PLN 12 Na aula de número 12 de processamento de linguagem natural, o tema foi sobre Feature hashing. Antes de começar a falar sobre isso, ele deu uma breve revisada de matriz- esparsa que são matrizes que possuem na grande maioria dos seus elementos formados por zeros. Nelas, podemos economizar um espaço significativo de memória se apenas os termos diferentes de zero forem armazenados. Caso não armazenar as posições que têm zeros, as operações usuais sobre essas matrizes (somar, pivotar, inverter e multiplicar) também podem ser feitas em tempo muito menor. Jesús mostrou o tamanho da matriz (sem stopwords) para cada tipo de exemplo por meio do |V| (ufabc-bcc, notícias, quatro obras do Machado de Assis, todas as obras do Machado de Assis e português). Também disse do vetor denso que havia falado que é uma estrutura mais “fácil” de trabalhar nos algoritmos de aprendizado de máquina e que existem os três métodos dele (PCA, FA, SVD). Ele acabou falando que o SVD é preferível no lugar das matrizes PPMI (Positive P ou matriz termo-termo, ou matriz termo-documento. O “ruído” de similaridade entre palavras (ou documentos) pode ser eliminado quando considerarmos apenas os principais valores singulares (assim, a versão que trunca a matriz pode ser útil). Dimensões menores nas matrizes podem tornar outros algoritmos (e.g. aprendizado de máquina) mais “simples”. Porém, o custo computacional para decompor uma matriz é caro. Avalie se o custo vale a pena. Depois dessa revisão da aula 11, ele deu início ao conteúdo Hashing (tabelas de dispersão), também chamado de tabelas de espalhamento, que são estruturas de dados eficientes para implementar um dicionário que busca com acesso médio igual a O(1), o que significa “constante” na média, sendo no pior caso é O(n) e na medida do possível uma constante pequena. As vantagens do hash é o algoritmo ser simples e eficiente para inserção, remoção e busca e as desvantagens s~ao nenhuma garantia de balanceamento, espaço subutilizado na tabela e o grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Além do hashing, para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, temos a busca sequencial, que tem como função de complexidade igual a O(n); busca binária, que acessa em O(log2(n)), sendo ainda lento se o número de elementos é grande; e uso de árvores balanceadas, que tem como função de complexidade O(log(n)), que, comparando com a busca sequencial, temos um desempenho bem melhor. Logo em seguida, Jesús falou de acesso/endereçamento direto que, quando o universo de chaves U é considerado pequeno, pode-se alocar uma tabela com uma posição para cada chave, isto é, |T| = |U|. Logo, cada posição da tabela, que pode ser implementada como um vetor, representa uma chave de U e armazena um elemento ou um ponteiro para o elemento, o que possibilita em analisar uma posição qualquer em O(1). Porém, vamos supor que a chave seja o RA de um estudante da UFABC, ou seja, trata-se de um número inteiro de 8 dígitos, então são 100000000 elementos (ou chaves). Caso cada posição da tabela ocupar 127 bytes, é necessário de mais de 1 Gigabyte de memória apenas para a tabela, mesmo que ela não esteja cheia. Por meio desse exemplo, dá para concluir que a alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande. Para a solução desse problema, o professor falou das tabelas de dispersão/espalhamento que através da utilização de uma função conveniente (função hash), a chave é transformada em um endereço de tabela (endereço base) formadas por inteiros dentro do intervalo [0...m-1], no qual m é o tamanho da tabela. Todavia, devido a isso, pode ocorrer o fenômeno chamado colisão que é a possibilidade de mais de uma chave seja mapeada em uma única posição da tabela. Felizmente, dá para evitar colisões através de encadeamento que usa-se uma função Hash que apresenta “comportamento randômico”. Após toda essa introdução de hashing, Jesús falou das funções hashing, entre elas: * Método da divisão: a chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base: h(k) = k mod m resulta em endereços no intervalo [0,m-1]. É considerado fácil, eficiente e largamente empregado. Se m for número primo, tende a ser melhor, porque números primos tendem a distribuir os restos das divisões de maneira mais uniforme do que números não primos. Porém caso m não é um número primo pode-se utilizar: h(k) = (k mod p) mod m onde p é um número primo maior que m. E também divisores não primos podem apresentar bom desempenho com a condição que não tenham fatores não primos maiores do que 20. * Método da multiplicação: utiliza uma constante A, sendo 0<A<1 e h(k) calculado como: h(k) = ?m(kA mod 1)? (kA mod 1) = kA - ?kA? Nesse caso, a vantagem deste método é que o valor de m não é crítico como no método da divisão, todavia a escolha de uma constante A adequada é crítica, sendo o valor da razão áurea ser a melhor para ela: A (5-1) / 2=0,6180339887 * Método da dobra: quebra a chave em partes e combina elas de algum modo. Como exemplo dado em aula, se as chaves são números de 8 dígitos e a tabela hash tem 1000 entradas, quebra a chave em três números. Então soma-os, considerando os três últimos dígitos da soma para compor a chave. Esses foram os métodos citados que consideram a chave como um número natural, porém o professor falou também quando a chave é uma cadeia de caracteres (hash para string), nesse caso, um dos jeitos é entender a chave como um natural em uma base conveniente. Contudo, palavras mais longas representam um desafio maior, pois o valor calculado pode ser muito grande. No próximo tópico, feature hashing (“Hashing trick”), ele falou que é uma maneira rápida e eficiente para tratar vetores com muitas características que no lugar de utilizar índices (de uma matriz, por exemplo termo-contexto), será utilizado um valor de hash. Assim, essa estratégia permite reduzir a dimensionalidade (número de características - e.g., colunas). Para o término da aula, ele mostrou em práticas esses conceitos de hashing citados anteriormente, por meio dos programas teste1.py, teste2.py, teste3.py, teste4.py, testePLN.py e testePLN2.py
Mauro Mascarenhas de Araujo	Aula de 18/07: "Feature hashing". A aula iniciou-se com uma breve revisão de matriz (esparsa) termo-contexto, que sofria do problema de escalabilidade por ter crescimento de ordem quadrática diretamente proporcional ao tamanho do vocabulário |V| (um exemplo é que para um vocabulário de aproximadamente 400000 palavras o custo de memória estimado é de 596 GB). Também foi revisto o conceito de transformação de vetor esparso (cuja maior parte dos valores é nula) para um vetor denso, onde embora o tamanho seja menor, a maioria de seus valores não é nula, sendo mais fácil de trabalhar nos algoritmos de aprendizado de máquina. Essa redução pode ser feita através de SVD (Redução de dimensionalidade via Singular Value Definition) que é a fatoração de uma matriz M = wxc grande em três matrizes W?C*, que deverão ser truncadas e, utilizando, efetivamente, a matriz U truncada, com dimensão wxk (Em PLN, normalmente, k=300). Em seguida, foi retomado o conceito de hashing (tabelas de fatoração), cujo principal objetivo é ter uma busca com acesso médio igual à O(1), ou seja, constante. Em comparação, a busca sequencial possui acesso em O(n), a busca binária em O(log2(n)) (Se n for grande, pode ser considerada lenta, dependendo da necessidade) e o uso de árvores balanceadas, que é O(log(n)), mas, embora seja melhor que a busca sequencial, ainda tem como melhorar utilizando funções hash. Tabelas de dispersão, também chamadas de tabelas de espalhamento ou hash tables, possuem busca com tempo de acesso médio O(1), com o pior caso sendo O(n). Sendo assim, elas são estruturas de dados eficientes para implementar um dicionário. Considerando que os valores das chaves variam de 0 a m-1, é possível utilizar o valor de cada chave diretamente em seu índice na tabela (como em um vetor/array); o endereçamento direto se baseia no fato de que podemos examinar uma posição qualquer em O(1), onde é possível alocar uma tabela com uma posição para cada chave possível. Embora esta técnica seja eficiente quando o universo de chaves U é razoavelmente pequeno, a dificuldade de usar endereçamento direto está no fato que a alocação de uma tabela T de tamanho |U| é inviável para um universo muito grande, sendo que a quantidade de chaves K armazenada na tabela pode ser muito menor do que o universo de chaves U, onde embora o tempo de busca seja O(1), o espaço utilizado será O(|U|). Sendo assim, a ideia é que através de uma função conveniente (função hash), a chave seja transformada em um endereço da tabela (endereço base): hash(chave) -> {0, 1, ..., m-1}, logo, h(k) é uma função h que mapeia o universo U de chaves para entradas da tabela de espalhamento T[0,...,m-1], h : U -> {0, 1, ..., m-1}. Porém, ainda há o problema de colisão, isto é, dado duas chaves, k1 e k1, h(k1) ser igual à h(k3), sendo assim, mapeadas para a mesma posição na tabela de espalhamento. Uma forma de tratar este problema é o encadeamento (além de utilizar uma função que evite colisões ao máximo, que apresente comportamento randômico). Basicamente, as operações de inserção e remoção levam tempo O(1), enquanto a busca leva tempo proporcional ao tamanho da lista. Uma opção de função possível é o método da divisão, onde dado uma chave k, ela é dividida pelo tamanho da tabela m, o resto da divisão é o endereço base : h(k) = k mod m, resultando em endereços no intervalo [0,m-1] (Para k=12 e m=100, o resultado seria 4, por exemplo); neste caso, bons valores para m são números primos (resumidamente, eles tem a melhor chance de retornar um valor único). Para uma tabela de 2000 elementos com uma lista de tamanho médio, o m adequado seria 701, uma vez que é o número primo mais próximo de 2000/3. Uma breve comparação mostrou que m=701 possui um comportamento muito mais aleatório que m=17, por exemplo. Há também o método da multiplicação, que utiliza uma constante A tal que 0<A<1, sendo h(k) dada por h(k)=floor(m*((k*A) mod 1))= m*(k*A - floor(k*A)), sendo que a principal vantagem desse método é que o valor de m não é crítico como no da divisão, porém a escolha da constante A adequada é crítica. Neste caso, alguns valores de A são melhores que outros, em particular a razão áurea (também conhecida como razão dourada): A = 0.0680. Por fim, há também o método da dobra, que consiste em quebrar as chaves e combiná-las de algum modo: um exemplo é se as chaves possuírem 8 dígitos e a tabela 1000 entradas, basta quebrar a chave em 3 números, com os primeiros numeros com 3 dígitos e o último com 2 e somá-los, considerando os 3 últimos dígitos da soma para compor a chave: h(73419883)=15, por exemplo. Para strings, um possível método é o da divisão, onde o correspondente de todos os caracteres são somados de acordo com seus valores da tabela ASCII e depois retornado o valor do módulo da soma por m. Outra possibilidade é considerar cada caractere como um natural em uma base conveniente, por exemplo: gato = 7*26^3 + 1*26^2 + 20*26 + 15 = 124243, porém, palavras muito grandes podem ter um valor calculado muito grande. Enfim, o hash é um algoritmo simples e eficiente para inserção, remoção e busca, porém não possui qualquer garantia de balanceamento, pode ter espaço sub-utilizado nas tabelas, o grau de espalhamento é sensível à função de hashingutilizada e ao tipo de informação usada como chave. Em PLN, usa-se o Feature Hashing, ou hashing trick, que é uma maneira rápida e eficiente para tratar vetores com muitas características, onde lugar de utilizar índices (de uma matriz, por exemplo termo-contexto), será utilizado um valor de hash, permitindo reduzir a dimensionalidade. A seguir foram apresentados alguns algoritmos que calculavam o hash das palavras do vocabulário (teste1.py, teste2.py, teste3.py e teste4.py). Para a aplicação nas obras de Machado de Assis, um bom valor para M seria 20000. Por fim, foram apresentados a aplicação prática da feature hashing em matrizes termo-contexto nas obras de Machado de Assis (testePLN.py, testePLN2.py).
Igor Neres Trindade	Na aula de hoje, 18/07/2019, abordamos Feature Hashing em uma tentativa de melhorar as estratégias de identificação de similaridade entre palavras discutidas em aulas anteriores. Até então, vimos como representar palavras na forma de vetores, seja utilizando matrizes termo-documento ou termo-contexto. Esta última, por sua vez, como representa a relação entre palavras, escala de forma quadrática em relação ao vocabulário, o que resulta em uma matriz enorme para vocabulários muito grandes. Na aula passada, vimos que essas matrizes são esparsas e que podemos utilizar uma técnica de decomposição em valores singulares e obter, por consequência, um vetor denso. Essa ideia poderia ser aplicada, por exemplo, na matriz PPMI. Mas, se não conseguirmos carregar essa matriz gigantesca na memória, não conseguiremos sequer operar. Dessa forma, abordamos Hashing para resolver esse problema. Hashing, ou tabelas de dispersão, funcionam distribuindo um valor em um de seus vários armazenamentos para rápida posterior busca. São estruturas de dados que, diferentemente de vetores ou arrays, permite busca de algum elemento com acesso médio constante. No pior caso, entretanto, a busca possui complexidade de O(n). São estruturas muito eficientes para implementar um dicionário! Em nosso contexto de análise de similaridade entre palavras, há uma tabela de tamanho muito grande, cuja alocação pode ser inviável. Tabelas de dispersão, por outro lado, possibilitam que o conjunto de chaves armazenadas (índice da tabela) sejam muito menor que o universo de chaves que, em nosso caso, é o vocabulário. E isso é feito através da aplicação de uma função, chamada de hash, que recebe uma chave e faz um mapeamento para algum contradomínio que pode ser controlado. Como o conjunto de chaves armazenadas na tabela pode ser muito menor que o universo, há a possibilidade de que duas chaves sejam mapeadas para uma mesma posição na tabela e devemos tratar essas colisões através de encadeamentos, como listas ligadas. A fim de evitar essas colisões, devemos garantir que a função hash apresente um comportamento aleatório, rearranjando os elementos de forma mais uniformemente distribuído possível. Há muitas pesquisas ocorrendo nesse sentido! São muitas as funções hash existentes. Essas funções devem ser baratas computacionalmente, de complexidade constante, como equações. Na aula, analisamos algumas, começando pelo método da divisão, que é um dos mais simples existentes: define-se um controle m sobre o tamanho da tabela de dispersão e, para cada chave k, calcula-se o resto da divisão de k por m. Bons valores para esse valor m são números primos, pois eles são valores indivisíveis por outros outros (além de um e ele mesmo), o que minimiza as colisões. Quando se deseja distribuir um número elementos em listas de tamanho específico, em cada chave, portanto, escolhe-se o número primo mais próximo da divisão do número de elemento pelo tamanho médio da lista. Um outro método existente é o da multiplicação. Define-se uma constante, entre zero e um, subtraindo-se o piso da chave multiplicada por essa constante por essa mesma multiplicação, sem piso. Esse resultado é, então, multiplicado por um valor m qualquer, não tão crítico quanto a constante escolhida anteriormente. Um valor muito bom para a primeira constante é o número de ouro, também conhecido por número de Deus, que pode ser encontrados em muitos padrões, como medidas do corpo humano, sequência de fibonacci e formato de cérebro humano. O porquê disso funcionar? Mistérios da vida! Existe também o método da dobra, um pouco menos comum. em que a chave é quebrada em três números, que são somados, considerando somente os três últimos dígitos deste resultado. Podemos usar tabelas Hash para strings também. Elas são de grande utilidade para o processamento de linguagem natural. Um algoritmo simples seria iterar sobre todos os caracteres de uma string, somando os valores correspondentes à tabelas ASCII ou unicode. Entretanto, podem existir anagramas, e palavras de tamanhos maiores (até certo ponto) podem possuir mais anagramas, o que traria um desequilíbrio na distribuição dos elementos na tabela. Uma alternativa seria multiplicar cada valor desses caracteres por uma base conveniente, somando tudo e aplicando módulo sobre esse resultado. De maneira geral, tabelas de dispersão são eficientes para as operações de inserção, remoção e busca e permitem comprimir o número de índices de nossos vetores. Entretanto, não há garantia de balanceamento, o que pode gerar um espaço subutilizado na tabela. Para isso, há muita pesquisa na área, principalmente na tentativa de criar uma função hash universal. Referente à aplicação dessa estratégia em matrizes termo-contexto, utilizaremos hash para cada diminuir o número de colunas, as palavras que darão o contexto. Cada palavra ainda será representada por um vetor, mas será um vetor menor. Se comparado à redução de dimensionalidade via SVD, o resultado será similar, porém feito com muito mais rapidez e eficiência.
July Anne Pinheiro	Aula 12: Feature hashing Hashing (tabelas de dispersão) Existem diversas formas para armazenamento de dados visando a forma mais prática para a realização de uma busca, inserção ou remoção de informação em tabelas (vetores/arrays): * Busca sequencial: acesso em O(n) * Busca Binária: acesso em O(log2(n)) ainda lento se n é grande. * Uso de árvores balanceadas: acesso em O(log(n)), porém bem melhor que a busca sequencial. * Tabelas de dispersão(Hash tables): Busca com acesso médio igual a O(1). Isso significa “constante” na média. No pior caso é O(n). Na medida do possível uma constante pequena. OBS: São estruturas de dados eficientes para implementar um dicionário. Tabelas de dispersão(Hash tables) Acesso/Endereçamento direto O endereçamento direto se baseia no fato de que podemos examinar uma posição qualquer em tempo de busca O(1) . Isto é aplicável quando podemos alocar uma tabela com uma posição para cada chave possível. Considerações: A dificuldade de usar endereçamento direto é óbvia: A alocação de uma tabela T de tamanho pode ser inviável para um universo muito grande. O conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U. Tabelas de dispersão/espalhamento Através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela (endereço base). h(k) é uma função h que mapeia o universo U de chaves para entradas da tabela de espalhamento T[0,...,m-1]. hash(chave) ? {0, 1, ,m-1} Importante: * Está técnica apresenta a dificuldade referente a possibilidade de duas chaves k1 e k3 serem mapeadas para a mesma posição na Tabela de Espalhamento. * Para evitar colisões usa-se uma função Hash que apresente “comportamento randômico”. Análise das operações * Inserção e remoção é executada em tempo O(1). * Busca leva tempo proporcional ao comprimento da lista. A seguir foram apresentados algumas funções de dispersão Funções Hash (de espalhamento): ? Método da divisão Fácil, eficiente e largamente empregado. A chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base: h(k) = k mod m Resulta em endereços no intervalo: [0, m-1]. Importante: Uma boa escolha de valores para m são os números primos. Funções Hash (de espalhamento): ? Método da multiplicação O método utiliza uma constante A (0<A<1), sendo h(k) calculado como: h(k) = m(kA mod 1) A vantagem deste método é que o valor de m não é crítico como no método de divisão,porém a escolha de A sim. Alguns valores de A são melhores do que outros, em particular a razão áurea(0,6180). Funções Hash: ? Método da dobra Quebre a chave em partes e combine-as de algum modo. Exemplo: Se as chaves são números de 8 dígitos, e a tabela hash tem 1000 entradas, quebre a chave em 3 números por exemplo e some-os, considerando os 3 últimos dígitos da soma para compor a chave. 73419883 ? 734 + 198 + 83 = 1015 ? 015 ? h(k) = 15 Hash para strings Até aqui consideramos o caso da chave ser um número natural. k = 'gato' Uma alternativa é, interpretar a chave de cadeia de caracteres como um natural em uma base conveniente, por exemplo: gato = 7.26^2 + 1.26^2 + 20.26^1 + 15 = 124243 Palavras mais longas representam um desafio maior, pois o valor calculado pode ser muito grande. Sobre hash Vantagens: algoritmo simples e eficiente para inserção, remoção e busca. Desvantagens: Sem garantia de balanceamento, pode ter espaços subutilizado nas tabelas. O grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Feature hashing ("Hashing trick”) Uma forma de tratativa de vetores com muitas características de forma rápida e eficiente. Será utilizado um valor de hash no lugar de utilizar índices, com essa estratégia, uma redução de dimensionalidade é permitida. Feature hashing na matriz termo-contexto: * Cada palavra é representado por um vetor cumprido mas com muitos valores nulos. * Cada palavra é representado por um vetor ’menor’. * Não temos controle do contradomínio Durante a aula foram apresentados os resultado de alguns testes efetuados em dados relacionados a machado de assis e ufabc para análise de resultados quanto à similaridade das palavras. Além de implementações para matrizes termo-contexto utilizando feature hashing ("Hashing trick”).
Elsio Antunes Junior	18/07, Aula 12 - Feature hashing; Da aula anterior: Seguindo com estudo de semântica e similaridade de palavras, vimos que uma matriz termo-contexto tem tamanho |V|x|V| é esparsa (contém muitos valores nulos) e grande, o que implica o uso de alguma estrutura de dados específica; Em redução de vetores esparsos em vetores densos via SVD, CBOW e Brown clustering e em redução de dimensionalidade via PCA (projeção num vetor que maximize a variância) e SVD (fatorar a matriz em três); Hoje será apresentado mais uma técnica que é o uso de Hashing (tabelas de dispersão) para diminuir um dos eixos da nossa matriz termo-documento; Apresentação; Para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, há várias maneiras: Busca sequencial, Busca binária, árvores balanceadas, essas duas últimas com complexidade assintótica O(log n); Tabelas de dispersão, também chamadas de tabelas de espalhamento ou hash tables tem complexidade teórica da ordem de O(1), portanto constante; No pior caso é O(n), mas na média é constante, com uma constante pequena, dependendo de uma boa função de hash; Isso decorre do fato de que, quando o universo de chaves é relativamente pequeno, o acesso é por endereçamento direto pela chave no índice da tabela, o que significa que podemos examinar uma posição qualquer em O(1); São estruturas de dados eficientes para implementar um dicionário; Quando o universo de chaves é grande usamos uma função hash que mapeia o universo de chaves para um conjunto k de chaves armazenadas e tratamos as colisões com listas encadeadas em cada campo; Algumas funções de dispersão se baseiam em algumas técnicas, a saber; método da divisão : A chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base h(k) = k mod m que esulta em endereços no intervalo: [0, m-1]; Bons valores para m são os números primos; A explicação é longa e complexa mas se baseia no fato de que se o número não for primo, uma distribuição de k chaves pode se concentrar nos múltiplos dos divisores de m fazendo com que a distribuição da tabela não seja homogênea, como seria o ideal; Ao plotar o gráfico da distribuição de chaves aleatórias vemos que as chaves se concentram em forma de rampas (o número de rampas dos divisores de m, por isso a menor perda é com o numero primo, que forma uma rampa apenas, mas ainda assim é uma rampa) e esse é o motivo pelo qual se argumenta que o método da divisão não é o melhor (a distribuição não é homogênea); O método da multiplicação é similar, escolhe-se uma constante A (entre 0 e 1) e calcula-se h(k) = m(kA mod 1); A vantagem deste método é que o valor de m não é crítico como no método de divisão, mas a escolha de uma constante A adequada é crítica; Alguns valores de A são melhores do que outros, em particular a razão áurea; outros métodos como o método da dobra usam propriedades da posição de caracteres do número para espalhar as chaves de forma mais homogenia; No caso específico do hash para strings a chave é calculada a partir de somas de substituições de caracteres por seus valores de ascii ou pela ordem do alfabeto; Discutiu-se em sala que a simples soma desses valores (ou mesmo o produto, devo acrescentar) colocaria na mesma chave todos os anagramas de uma mesma palavra, dado a comutatividade deste tipo de operação; O problema se resolve se inserirmos a cada soma uma potência de um número cujo expoente depende da posição do caractere na palavra; Feature hashing ("Hashing trick”); Dado que temos em nossa matriz termo-contexto uma quantidade muito grande de dados e muitos desses dados são valores nulos, podemos utilizar um valor de hash no lugar dos índices; Os códigos python disponibilizados tratam de como implementar o hash; Como podemos usar um valor m arbitrário, se torna possível buscar pelo melhor valor m de acordo com o trabalho que estamos fazendo; as análises dos gráficos para diversos valores de m mostram que no caso de obras de Machado de Assis o número 1000 nos permite obter um gráfico quase homogêneo;
Giselle Silva de Santana	Nesta décima segunda aula, do dia 18/07/2019, foi abordado o tema “Feature Hashing”, com exposição de alguns códigos em Python. Inicou-se a aula com uma breve revisão sobre matriz (esparsa): termo contexto, tema abordado na aula dez, e vetores densos, que são estruturas mais fáceis de trabalhar nos algoritmos de aprendizado de máquina, que foi o tema abordado na aula anterior. Após a breve revisão, iniciou-se o assunto da aula. Para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, há várias maneiras: Busca Sequencial: acesso em O(n); Busca Binária: acesso em O(log2(n)), que é lento se n é grande; Uso de árvores balanceadas: acesso em O(log(n)), tem acesso bem melhor do que na busca sequencial. As Hash Tables (tabelas de dispersão ou tabelas de espalhamento), possuem busca com acesso médio igual a O(1). Isso significa “constante” na média, possuindo complexidade no pior caso igual a O(n) e na medida do possível uma constante pequena. Tais tabelas são estruturas de dados eficientes para implementar um dicionário. Pode-se usar diretamente o valor de cada chave em seu índice de tabela (cada chave x armazenada no compartilhamento x). O endereçamento direto se baseia no fato de que podemos examinar uma posição qualquer em O(1), é uma técnica simples que funciona quando o universo de chaves U é razoavelmente pequeno, porém a alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande. O conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U, espaço utilizado: O(|U|) e tempo de busca O(1). Para tabelas de dispersão/espalhamento, através da aplicação de uma função conveniente (função hash), a chave é trasformada em um endereço de tabela (endereço base) e h(k) é uma função h que mapeia o universo U de chaves para entradas da tabela de espalhamento T[0, ,m-1]. Uma dificuldade dessa técnica é a possibilidade de duas chaves k1 e k3 serem mapeadas para a mesma posição na Tabela de Espalhamento, que é chamada de colisão. Uma maneira de tratar colisões é através de encadeamento, usando-se uma função hash que apresente “comportamento randômico”. Foram apresentados alguns métodos para uso de funções hash (de espalhamento). O método da divisão é fácil, eficiente e largamente empregado, nesse método a chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base: k(k) = k mod m, resulta em endereços no intervalo: [0, m-1], onde números primos são bons valores para m. O método da multiplicação, o método utiliza uma constante A (0<A<1), sendo h(k) calculado como: kA – [kA]. A vantagem de tal método é que o valor de m não é crítico como no método de divisão, mas a escolha de uma constante A adequada é crítica. A razão áurea é um bom valor para A, sendo A ~ (sqrt(5)-1)/2 = 0,6180339887. O método da dobra quebra a chave em partes e combine-as de algum modo. Nem sempre a chave é um número, se a chave é uma cadeia de caracteres, pode-se interpretá-la como um natural em uma base conveniente, onde palavras mais longas representam um desafio maior, pois o valor calculado pode ser muito grande. A vantagem sobre o hash é que é um algoritmo simples e eficiente para inserção, remoção e buscas, porém possui como desvantagem que não dá nenhuma garantia de balanceamento, o espaço é sub- utilizado nas tabelas e o grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Por fim, foi apresentado o conceito de Feature hashing, ou hashing trick, que é uma maneira rápida e eficiente para tratar vetores com muitas características. No lugar de utilizar índices, é utilizado um valor de hash, permitindo assim reduzir a dimensionalidade. O uso de feature hashing em uma matriz termo-contexto, cada palavra é representada por um vetor ‘menor’, enquanto que usualmente cada palavra é representada por um vetor comprido com muitos valores nulos.
Matheus Tulio Pereira da Cruz	Queremos transformar um vetor esparso em um vetor denso, assim ficamos apenas com os dados relevantes. Se não conseguimos carregar uma matriz muito grande, também não conseguiremos fatorar essa matriz. Para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, há varias maneiras: \- busca sequencial : acesso em O(n) \- Busca binária: acesso em O(log2(n)) \- Uso de árvores balanceadas : acesso em O(log2(n)) Busca em tabelas hash possuem um acesso médio igual a O(1), ou seja, acesso em tempo constante. No pior caso é O(n) São estruturas de dados eficientes para implementar um dicionário. 1 - acesso/endereçamento direto: técnica simples que funciona quando o universo de chaves U é razoavelmente pequeno. A dificuldade de usar endereçamento direto é a alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande O conjunto de chaves K armazenavas na tabela pode ser muito menor do que o universo de chaves U: \- Espaço utilizado: O(|U|) \- Tempo de busca: O(1) 2 - Tabelas de dispersão / espalhamento Através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela Hash(chave) -> {0,1,...,n} h(k) é uma função h que mapeia o universo U de chaves para entradas da tabela de espalhamento T[0, 1, ..., m - 1] Uma dificuldade dessa técnica é a possibilidade de duas chaves serem mapeadas para a mesma posição da tabela . Para evitar colisões usa-se uma função Hash que apresente “comportamento randômico”. \- Inserção é executada em tempo O(1) \- Remoção de um elemento x é executada em tempo O(1) \- Busca leva tempo proporcional ao comprimento da lista Método da divisão é fácil, eficiente e largamente empregado. A chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base: h(k) = k mod m Um bom número para divisão é um número primo. Estudar porque o número primo é uma boa escolha. O método da multiplicação utiliza uma constante (0 <A< 1) A vantagem deste método é que o valor de m não é crítico como no método de divisão. Uma boa constante é aproximadamente ((raiz de 5) - 1) / 2 -> para testes empíricos foi o melhor valor . Método da dobra : quebre a chave em partes e combine as de algum modo. Exemplo: se as chaves são números de 8 dígitos, e a tabela hash tem 1000 entradas, quebre a chave em 3 números: \- Número 1: 3 dígitos \- Número 2: 3 dígitos \- Número 3: 2 dígitos Some-os, considerando os 3 últimos dígitos da soma para compor a chave. Hash para strings: Problema de usar módulo de 51 é um pouco ruim porque você perde a referência de posição das letras, ou seja, anagramas possuem o mesmo valor. Uma alternativa é, por exemplo, se a chave é uma cadeia de carácteres podemos interpretá-la como um natural em uma base conveniente Vantagens de Hash: algoritmo simples e eficiente para inserção, remoção e busca Desvantagens de hash: nenhum amarantos de balanceamento, espaço sub-utilizado nas tabelas, o grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Solução para isso é feature hashing. A compressão de um vetor esparso tem um problema quando o corpus é muito grande, o processamento acaba sendo muito demorado. Feature hashing é uma maneira rápida e eficiente para tratar vetores com muitas características No lugar de utilizar índices, será utilizado um valor de hash. Na matriz termo-contexto, cada palavra é representado por um vetor cumprido mas com muitos valores nulo. Depois do feature hashing, cada palavra é representado por um vetor ‘menor’. É importante escolher um M que deixe a distribuição de elementos no vetor de forma uniforme, ou seja, cada índice do vetor tenha um número de elementos muito parecidos. Feature hashing pode ser utilizado para qualquer estrutura de dados que precise de uma redução no número de dados, não só em PLN.
Renato de Avila Lopes	Feature Hashing Da aula passada Matriz esparsa termo contexto Cada palavra é representada por um vetor com muitos valores nulos Tamanho da matriz sem stopwords supondo 4 bytes para armazenar um inteiro Ementas UFABC BCC 96 palavras 0.035 MB Notícias 1580 palavras 9523 MB Todas obras de Machado 62 933 palavras ~ 15 GB Idioma português ~ 400 000 palavras ~ 596 GB Vetor denso é uma estrutura mais fácil de trabalhar nos algoritmos de aprendizado de máquina Hashing - Tabela de dispersão - tabelas de espalhamento - hash tables Busca em tabela - vetores / arrays Busca sequencial O (n) Busca binária O (log2(n)) - lento para n grande Árvores balanceadas O (log(n)) - bem melhor que busca sequencial Hash table Busca com acesso médio igual a O (1) - constante na média Pior caso O (n) Constante pequena Estrutura de dados eficiente para implementar um dicionário Acesso / Endereçamento direto Valores das chaves: 0, 1, ..., m - 1 Pode se usar o valor de cada chave em seu índice de tabela Endereçamento direto - examinar uma posição qualquer em O (1) Tabela com uma posição para cada chave possível Universo de chaves razoavelmente pequeno Dificuldade: Alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande O conjunto de chaves k pode ser muito menor que o universo de chaves U Espaço O (|U|) Tempo de busca O (1) Através de uma função conveniente (hash) a chave é transformada em um endereço base hash (chave) -> {0, 1, ... , m - 1} h(k) Função que mapeia U para entradas da tabela de espalhamento T [0, ... , m - 1] h : U -> {0, 1, ... , m - 1} Dificuldade: possibilidade de duas chaves serem mapeadas para a mesma posição Solução: encadeamento com função hash que apresenta comportamento randômico Inserção O (1) Remoção O (1) Busca proporcional ao comprimento da lista Funções hash Método da divisão: fácil, eficiente e largamente empregado Chave k dividida pela dimensão da tabela m Resto da divisão é o endereço base h (k) = k mod m. Endereços no intervalo [0, m - 1] h (100) = 100 mod 12 = 4 melhores valores para m números primos Exemplo n = 2000 elementos de 8 bits em listas ligadas de tamanho médio 3 Tamanho apropriado m = 701, pois este é o número primo próximo de 2000 / 3 h (k) = k mod 701 Método da multiplicação Utiliza uma constante A onde 0 <A< 1 e h(k) = piso (m (kA mod 1) ) e kA mod 1 = kA - piso(kA) Valor de m não é crítico, mas escolha de A é Alguns valores de A são melhores que outros, em particular A = 0,6180339887 (razão áurea) Método da dobra Quebra a chave em partes e as combina d algum modo Exemplo: Números de 8 dígitos, tabela com 1000 entradas Quebre a chave em 3 números: 1 (3 dígitos) 2 (3 dígitos) e 3 (2 dígitos) Some os 3 últimos dígitos 734 198 83 -> 734 + 198 + 83 = 1015 -> 015 -> h(k) = 15 Hash para strings k = gato h(k) = ? Utilizando método da divisão resultaria no mesmo valor para anagramas Alternativa: interpretar como um natural em ase conveniente gato = 7 * 26^3 + 1 * 26^2 + 20 * 26^1 + 15 = 124243 Palavras mais longas valor calculado muito grande Algoritmo simples e eficiente para inserção remoção e busca Porém nenhuma garantia de balanceamento Espaço sub utilizado nas tabelas Grau de espalhamento sensível a função hash e tipo de chave Desafio hash universal Feature hashing Hashing trick Maneira mais rápida e eficiente para tratar vetores com muitas características Utiliza valor de hash, não índices Reduz dimensionalidade (exemplo colunas na matriz termo contexto) Programa teste1.py casa h = 408 casas = 523 programação h = 1426 programacao h = 1164 Programa teste2.py casa = 8 casas = 23 programação h = 26 programacao h = 64 Programa teste3.py com Machado-palavras-unicas.txt com m = 100, m = 701, m = 10000, m = 1000, m = 20000 (melhor m) Programa testePLN.py Foi utilizado o programa testePLN2.py sobre a pasta machado-db com a entrada alegria
Rafael Augusto Zanatta	Nessa aula vimos Feature hashing que pe uma técnica que utilizamos a Hashing (tabelas de dispersão)na qual para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, há várias maneiras: Busca sequencial é uma forma de utilização, porém a complexidade para isso é na ordem de m O(n), temos também a busca binária com uma complexidade um pouco melhor, porem ainda na ordem de (log2(n)) ainda lento, pois se n é grande (log2 (1000000) = 20) outra forma é a utilização de árvores balanceadas com complexidade na ordem de O(log(n)) acesso bem melhor do que na busca sequencial. Para as Buscas em tabelas (vetores/arrays) temos a técnica de tabela de dispersão ou tabela de espalhamento ou ainda hash tables nessas técnicas possuímos uma complexidade com acesso médio igual a O(1), ou seja, na média a busca é constante e no pior caso é O(n) portanto essas estruturas de dados são eficientes para implementar um dicionário e para isso uma das formas que podemos implementar é o endereçamento direto que é uma técnica simples que funciona quando o universo de chaves U é razoavelmente pequeno, elas se baseiam no fato de que podemos examinar uma posição qualquer em O(1), mas isto somente é aplicável quando podemos alocar uma tabela com uma posição para cada chave possível, porem temos como desvantagem o fato de que a alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande. Para as tabelas de dispersão ou espalhamento ela funciona da seguinte forma através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela (endereço base) na qual mapeia um universo de chaves para as entradas da tabela de espalhamento, porem um dos problemas que encontramos são as colisões que é quando ocorre a possibilidade de duas chaves serem mapeadas para a mesma posição na tabela, uma das técnicas para tratar dessas colisões é através de encadeamento ou para evita-las usa-se uma função Hash que apresente “comportamento randômico”. Ao utilizar essa técnica temos que para as operações de inserção ela é executada em tempo O(1) a remoção é executada em tempo O(1) e a busca leva um tempo proporcional ao comprimento da lista. Outro tipo de função utilizada na tabela hash é o método da divisão, pois ela é fácil e eficiente. O método da multiplicação também é usado, pois uma das vantagens desse método é que o valor de m não é crítico como no método de divisão, mas a escolha de uma constante A adequada é crítica. O método da dobra baseia-se basicamente na quebra da chave em partes e depois as combinamos de algum modo. As vantagens de utilizar-se a hashing é que o algoritmo é simples e eficiente para inserção, remoção e busca e como desvantagens temos que não possuímos nenhuma garatia de balanceamento, pode have espaços sub utilizados nas tabelas e o grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Feature hashing ("Hashing trick”)é uma maneira rápida e eficiente para tratar vetores com muitas características no lugar de utilizar índices (de uma matriz, por exemplo termo-contexto), será utilizado um valor de hash, assim, essa estratégia permite reduzir dimensionalidade (número de características – e.g., colunas)
Tamiris Gabriele da Silva Lira	A décima segunda aula de Processamento de Linguagem Natural teve como tema Feature Hashing. Assim, iniciamos com uma revisão sobre Hashing. Para a busca em tabelas existem várias estratégias, como a busca sequencial (O(n)), busca binária (O(log2(n))) e o uso de árvores balanceadas (log(n)). As Hash tables também existem para solucionar esse problema. Também chamadas de tabelas de dispersão ou tabelas de espalhamento, as hash tables fazem a busca com acesso constante (O(1)) e, por isso, dicionários podem ser implementados através dessa estrutura de dados de maneira eficiente. Assim, considerando valores de chaves de 0 até m-1, é possível examinar qualquer posição em O(1), desde que cada chave esteja em uma posição. Se o universo for grande, no entanto, a alocação de uma tabela do tamanho desse universo não é viável. O número de chaves k armazenadas pode ser menor que o tamanho do universo, de forma que o espaço utilizado será O(|U|) e o tempo de busca continuará em O(1). Uma função de hash será a responsável por mapear o universo U para entradas da tabela de espalhamento; assim hash(chave) -> {0, 1, ..., m-1}. Essa estratégia acarreta, inevitavelmente, em colisões, ou seja, mais de uma chave sendo mapeada para a mesma posição na tabela de dispersão. Para evitar isso, a função hash deve apresentar "comportamento randômico", mas quando as colisões acontecem podem ser tratadas através de encadeamento. Após essa introdução, o professor apresentou algumas funções de espalhamento. A primeira, o Método da Divisão, é amplamente empregada e consiste em dividir a chave k pela dimensão da tabela m, de forma que h(k) = k mod m e tem resultados em endereços de 0 até m-1. É necessário que o valor de m reduza o número de colisões, distribuindo as chaves da maneira mais uniforme possível. Assim, bons valores para m são números primos. O Método da multiplicação usa uma constante A (0<A<1) e calcula a função de espalhamento como h(k) = floor(m(kA mod 1)), o que permite que a escolha do tamanho da tabela não seja crítica, ainda que a escolha de A seja. Um bom valor para A é encontrado na razão áurea, com A = (sqrt(5) - 1)/2. O Método da dobra consiste em quebrar a chave em partes e combiná-las de alguma forma. Ao aplicar Hash para strings, se a chave for uma cadeia de caracteres, pode-se " interpretá-la como um natural em uma base conveniente", ainda que palavras longas gerem valores calculados muito grandes. Finalmente, o professor apresentou o conceito de Feature Hashing, que utiliza um valor de hash no lugar de índices (como os da matriz termo-contexto), o que permite reduzir a dimensionalidade. O programa teste1.py recebe uma palavra e devolve um valor de hash baseado no valor unicode dos caracteres da palavra; já o programa teste2.py retorna um valor de hash para a palavra baseado no método da divisão usando um valor m igual a 100. O programa teste3.py aplica o teste2.py e mostra de forma gráfica o espalhamento das chaves fornecidas na entrada. O teste4.py mostra que 1000 e 20000 seriam bons números de m para o espalhamento das palavras únicas na obra de Machado de Assis. Por fim, o programa testePLN.py mostra o Feature Hashing aplicado a matrizes termo-contexto.
Bruno Menezes Gottardo Ladeia	O tema da aula 12 foi feature hashing. Foram revisados métodos e formas de buscas em tabelas, finalmente citando as vantagens de hash por terem acesso médio igual a O(1), o que as tornam estruturas eficientes para implementar um dicionário. Existem várias técnicas de implementação de hashs. A primeira seria a de acesso/endereçamento direto, onde cada chave de acesso corresponde ao valor, i.e. uma chave x armazena x em sua estrutura, de forma que U(x) = x. É uma técnica bastante simples que funciona bem quando o universo de chaves U é razoavelmente pequeno. Para universos muito grandes começa a ficar inviável e o conjunto de chaves K efetivamente armazenadas no universo U poderm vir a ser bem pequenas. O espaço utilizado é O(|U|) e tempo de busca O(1), ambos no caso médio. A segunda forma é criando tabelas de dispersão/espalhamento. Nesta segunda implementação a chave é testada por uma função conveniente, que a converte num endereço de tabela. hash(chave) -> {0, 1, ..., m-1}, ou seja h(k) mapeia chaves do universo U para endereços da tabela de espalhamento T[0, ..., m-1]. Nesta técnicas existem colisões, isto quer dizer que chaves k2 e k3, por exemplo, possam ser mapeadas para a mesma posição na Tabela de Espelhamento, gerando o que é chamado de uma colisão. Para tratar estas colisões, geralmente implementa-se uma estrutura cadeada na estrutura, o que faz com que ela tenha busca O(n) no pior caso, sendo n o tamanho da lista. Para evitar colisões, geralmente empregam-se funções hash que apresentam um "comportamento randômico". Inserção leva O(1) e remoção O(1). Existem várias funções de dispersão. A do método da divisão é um das mais utilizadas, por ser simples de implementar e eficiente. A chave k é dividida pela dimensão da tabela m, o resto da divisão vira o endereço da base: h(k) = k mod m e isso resulta em endereços no intervalo: [0, m-1]. e.g. Para m=12 e k=100, h(100) = 100 mod 12 = 4. Bons valores para m são números primos e o motivo para isso não é óbvio, para maiores informações seguem dois links: http://stackoverflow.com/questions/1145217/why-should-hash-functionsuse-a- prime-number-modulus e https://computinglife.wordpress.com/2008/11/20/why-do- hash-functions-use-prime-numbers/. Outro método é o da multiplicação. Utiliza- se uma constante A (0<A<1) e h(k) passa a ser calculado como: h(k) = piso(m(kA mod 1)) e (kA mod 1) = kA - piso(kA). Para este método a escolha do m não é crítico, mas a do A sim. A razão áurea costuma ser a melhor constante para esta dispersão. Método da dobra consiste em quebrar a chave em partes e as combinar de alguma forma, e.g. 73419883 -> 734 + 198 + 83 = 1015 -> 015 -> h(k) = 15. Para as chaves até agora foram considerados apenas números naturais e como faremos para strings? Poderíamos representar uma cadeia de caracteres como um natural em uma base conveniente, porém para palavras mais longas seria ineficiente. Entra o feature hashing. Consiste numa maneira rápida e eficiente para tratar vetores com muitas características. O valor de hash é utilizado no lugar dos índices da matriz, reduzindo a dimensionalidade da matriz termo- contexto, tornando-a menos esparsa.
Rodrigo Akiyama Abrantes	Resumo da aula 12 de Processamento de Linguagem Natural – Feature Hashing Para a resolução de problemas que envolvem operações de busca, inserção e remoção em uma tabela com n elementos, existem diversos métodos de resolução como: Busca sequencial, busca binária, árvores binárias, etc. Cada uma estas metodologias possui um grau de complexidade e performance diferente, o que significa que seu uso é dependente da quantidade de valores envolvidos. A utilização de tabelas de dispersão (Hashes) realizada a busca com um acesso médio às estruturas de dados igual a O(1), isto é, com um tempo constante na média que, na medida do possível, será pequeno. O pior caso seria O(n). Por isto, esta é uma estrutura de dados eficiente para a implementação de um dicionário. Utilizando o conceito de acesso direto e considerando que os valores das chaves sejam de 0 até m-1, pode-se utilizar diretamente o valor de cada chave em seu índice na tabela. Desta forma, torna-se possível examinar uma posição qualquer em O(1), pois cada chave x estará armazenada no compartilhamento x. Isto é aplicável quando é alocada uma tabela com uma posição para cada chave possível. Cada linha da estrutura de índice apontará para a linha correspondente na tabela de dados, onde o número da linha de índice será o mesmo da tabela de dados. Esta técnica funciona somente quando o universo de chaves é razoavelmente pequeno. Utilizando uma função hash, é possível realizar a transformação da chave em um endereço de tabela. Deste modo, a função hash h(k) é uma função h que irá mapear o universo U de chaves para entradas na tabela de espalhamento T. Uma possível dificuldade deste método é a possibilidade de duas chaves diferentes serem mapeadas para uma mesma posição na Tabela de espalhamento. Este tipo de colisão pode ser tratada por meio de encadeamento, formando uma estrutura de lista encadeada dos elementos da tabela de espalhamento. Empregando este método, as operações de inserção e remoção são executadas em O(1) e a busca leva um tempo proporcional ao comprimento da lista. Analisando agora algumas funções de dispersão. O método da divisão é fácil, eficiente e largamente empregado. A chave k é dividida pela dimensão da tabela m, o resto da divisão será o endereço base para a tabela de espalhamento. Os endereços estarão contidos no conjunto [0,m-1]. Os melhores valores de m serão números primos, pois estes são divisíveis apenas por 1 ou por eles mesmo, evitando colisões!. O método da multiplicação utiliza uma constante A (0<A<1), sendo h(k) calculado como o h[m(kA mod 1)]. A vantagem deste método é que o valor de m não será crítico como no método da divisão (onde um número primo é o ideal). Porém, a escolha da constante A adequada será crítica. No método da dobra, a chave resultante é quebrada em partes e estas são combinadas de alguma forma (via algoritmo). Sobre o hash, as vantagens é a sua simplicidade e eficiente para as operações básicas. As desvantagens é são a não garantia de balanceamento, má utilização do espaço nas tabelas e a dependência do grau espalhamento à função de hashing utilizada.
Marcelo de Souza Pena	Aula 12 de PLN sobre feature hashing, também conhecido como hashing trick. Mais uma revisão sobre matriz termo-contexto, como ela é esparsa e para vocabulários grandes precisa de muito armazenamento. Revisão sobre transformar um vetor esparso em um vetor mais denso e fácil de trabalhar com SVD na matriz PPMI. Revisão sobre tabelas hash, como é possível realizar buscas em O(1) em média, muito mais rápido que outras formas de busca e como são ideais para implementar dicionários. Até então nada de novo, aplica uma função conveniente (ou função hash) e vai na posição resultante da tabela (tabelas de dispersão/endereçamento), em cada posição pode ter uma lista ligada para tratar colisões (quando a função leva dois caras para o mesmo endereço). Neste caso a inserção e remoção são feitas em O(1) e a busca é proporcional ao comprimento da lista. Uma função usada em tabelas de dispersão é o método da divisão, em que a chave é dividida pela dimensão da tabela e o resto da divisão é usado no endereçamento. O ideal para dimensão da tabela é um número primo, idealmente o maior primo que seja próximo da divisão do tamanho da tabela pelo fator de colisão desejado. Há também o método da multiplicação que usa uma constante A que varia entre 0 e 1 e multiplica a chave, então o resto da divisão por 1 é multiplicado pelo tamanho da tabela e o resultado arredondado para baixo. Esse método depende muito da escolha da constante A. Idealmente usa-se a proporção áurea porque dá bons resultados. Outro método é o da dobra, que quebra o valor da chave em números de três dígitos, soma todos eles e usa os três últimos dígitos. Além de usar hash com número é possível usar com strings somando os valores ASCII de cada dígito ou mesmo sua posição no alfabeto. Hash é simples e eficiente, mas depende de uma boa escolha de função para evitar colisões e garantir bom espalhamento. É possível utilizar hash para reduzir dimensionalidade em PLN de forma que ao invés de cada palavra ser representada por uma linha da matriz termo-contexto, ela é representada por um bem menor, cujos índices são valores hash. Exemplo de algoritmo que soma os valores ASCII dos caracteres de uma palavra e mostra o valor. Outro exemplo de código que faz a mesma coisa, mas divide o valor por 100, retornando um valor entre 0 e 99. Terceiro exemplo de código que abre um dataset, cria uma matriz de colisão cheia de zeros, lê o dataset dando um índice a cada palavra e imprime um gráfico mostrando as colisões. Dependendo do valor de M usado na divisão o número de colisões fica mais espalhado. Quarto exemplo de código usa uma hash diferente e bem melhor neste caso. Último exemplo de código usa a mesma hash anterior, pega uma lista de stopwords, lê documentos, cria o vocabulário de palavras únicas que não são stopwords, conta os pares de palavras e mostra as chaves, calcula o PPMI e imprime a tabela em uma versão e o grafo em outra. Alkoresmi da cidade de koresmi é o criador do termo algoritmo.
Eracton Ferreira Ramalho	Nesta aula 11 vamos aprender sobre feature hashing. O primeiro ponto importante é definir e relembrar a definição de hashing. Para iniciar devemos lembrar quais as formas de busca dentro de uma tabela (vetores). Para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, há várias maneiras: busca sequencial (acesso em O(n)), busca binária (acesso em O(log2(n)) e uso de árvores balanceadas O (log(n)). No endereçamento direto considere que os valores das chaves sejam: 0, 1, ,m-1: Pode-se usar diretamente o valor de cada chave em seu índice de tabela (cada chave x armazenada no compartilhamento x). O endereçamento direto se baseia no fato de que podemos examinar uma posição qualquer em O(1). Isto é aplicável quando podemos alocar uma tabela com uma posição para cada chave possível. Está é uma técnica simples que funciona quando o universo de chaves U é razoavelmente pequeno. Quais os pontos negativos? A dificuldade de usar endereçamento direto é obvia: A alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande. O conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U. Por exemplo, espaço utilizado: O(|U|) e o Tempo de busca: O(1). Já com a tabela de dispersão ou espalhamento a distribuição é feita através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela (endereço base). Onde se pode considerar h(k) como uma função h que mapeia o universo U de chaves para entradas da tabela de espalhamento T[0,...,m-1]. E qual o ponto negativo dessa estrutura? A possibilidade de duas chaves k1 e k3 serem mapeadas para a mesma posição na Tabela de Espalhamento. Assim, para não acontecer isso, deve ser usada uma função Hash que apresenta comportamento randômico. Analise das operações: inserção é executada em tempo O(1). Remoção de um elemento x é executada em tempo O(1). Um fato importante é que a busca leva tempo proporcional ao comprimento da lista. Vimos algumas funções de dispersão. A primeira foi com o método da divisão. Ele é fácil, eficiente e largamente empregado. A chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base: h(k) = k mod m. Sendo que resulta em endereços no intervalo: [0, m-1]. E quais os valores bons para o m? Os números primos. A segunda foi o método da multiplicação. O método utiliza uma constante A (0<A<1), sendo h(k) calculado como: >), sendo h(x) calculado como: h(k) = [m(kA mod 1)]. A vantagem deste método é que o valor de m não é crítico como no método de divisão. Mas a escolha de uma constante A adequada é crítica. Consultar slide 26. Também vimos o método da dobra. E o feature hashing? É uma maneira rápida e eficiente para tratar vetores com muitas características. No lugar de utilizar índices (de uma matriz, por exemplo termo-contexto), será utilizado um valor de hash. Assim, essa estratégia permite reduzir dimensionalidade.
Arthur Veloso Kamienski	Hashing: tabelas hash, também chamadas de tabelas de dispersão ou espalhamentos, são tabelas que resolvem o problema de busca em tabelas. Fazendo uma busca em uma tabela de maneira sequencial, temos um acesso em O(n), pois devemos atravessar todos os elementos para encontrar o desejado. Já em uma busca binária, isso se reduz à O(log2(n)), que é melhor que uma busca sequencial, apesar de ainda poder ser lento para um n muito grande. Também podemos utilizar uma árvore balanceada, que realiza uma busca em O(log(n)). Em uma tabela hash, por outro lado, a busca é realizada em O(1), ou seja, no caso médio leva um tempo constante para se encontrar um valor. No pior caso, entretanto, a tabela tem tempo O(n). As tabelas hash utilizam um par chave- valor para que os valores sejam acessados em tempo constante a partir da chave, devido ao fato de que o endereçamento toma tempo constante. Para um universo de valore pequeno, podemos utilizar um endereçamento de mesmo tamanho do universo. No entanto, isso pode consumir um espaço de memória muito grande. Podemos, portanto, utilizar uma função hash, que mapeia uma chave a uma posição da tabela. Caso duas chaves sejam mapeadas para a mesma posição pela função, as entradas são encadeadas. Assim, ao se acessar um valor que apresenta colisão, deve-se fazer uma travessia pela lista encadeada para encontrar o valor desejado. Deste modo, a inserção e remoção de um valor na tabela leva tempo O(1), no entanto, a busca é proporcional ao tamanho da lista. Como função de dispersão, podemos utilizar o método da divisão: o valor da chave K é dividido pelo tamanho da tabela M e a posição na tabela I é o resto dessa divisão (I=K%M), resultando em endereços no intervalo [0, m-1]. Bons valores de M são números primos. Também existe o método da multiplicação, que utiliza uma constante A, 0<A<1, de modo que a posição na tabela é dada pelo piso de M(KA%1). Diferente do método da divisão, o valor de A é crítico (e não o de M). Por fim, pode-se utilizar o método da dobra, que quebra a chave em partes e combina-a para encontrar a posição na tabela. Por exemplo, para uma tabela de 1000 entradas e chaves de 8 dígitos, podemos quebrar a chave em três números (de 3, 3 e 2 dígitos) e somá-los, selecionando os três ultimos dígitos da soma como posição da tabela. Para chaves representadas como strings, podemos converte-las para números naturais somando os valores de cada character da string, ou interpretando-os como um natural em uma base conveniente (base 26, por exemplo). Algoritmos de hash, no entanto, não apresentam nenhuma garantia de balanceamento. Além disso, o espaço da tabela pode ser sub-utilizado e o grau de espalhamento é sensível à função utilizada. Tabelas hash podem ser utilizadas para tratar o problema de matrizes e vetores esparsos, ao converter um vetor longo em uma chave menor. Assim, o espaço de armazenamento é significativamente reduzido. Isso é chamado de feature hashing
Paula Keiko Miyashita	A aula 12 abordou o tópico de Feature Hashing, depois de uma pequena revisão da aula anterior, onde estudamos a necessidade de diminuir o espaço necessário para guardar informações. A técnica apresentada na aula anterior foi SVD, onde se decompõe a matriz original em três outras matrizes e realiza o truncamento, perdendo um pouco da informação, mas mantendo a essência da matriz original e simplificando as operações sobre ela. Depois da revisão entramos no tema de Hashing (tabela de dispersão), a importância do hashing foi demonstrada depois de mostrarmos diferentes formas de busca, inserção e remoção em uma tabela com n elementos: a busca sequencial tem complexidade O(n), a busca binária tem complexidade O(log2(n)) e utilizando árvores balanceadas temos complexidade O(log(n)). Com as Hash tables (também conhecidas como tabelas de espalhamento/dispersão) podemos conseguir o tempo médio de acesso como O(1), desta maneiras hash tables se mostram estrutudas e dados eficientes para implementação de dicionários. Para que se possa acessar os dados de uma tabela com complexidade constante, é necessário que possamos alocar uma tabela com uma posição para cada chave possível, assim utilizamos cada chave como índice da tabela. No entanto, esta técnica só é viável se o universo de chaves é razoavelmente pequeno, para isso utilizamos tabelas de dispersão/espalhamento. Utilizando uma função hash (função conveniente), transforma-se a chave em um endereço da tabela (endereço base), com esta técnica diferentes chaves podem apontar para a mesma posição da tabela de espalhamento, nestas situações pode- se utilizar encadeamento (e uma busca convencional dentro da cadeia). Assim, a busca de um elemento se torna proporcional ao comprimento da lista/número de elementos encadeados, ou seja, para diminuir o tempo de busca devemos espalhar a informação de maneira mais uniforme possível de maneira que as listas tenham aproximadamente o mesmo tamanho. Foram estudadas algumas funções de espalhamento: Método da divisão, onde a chave é dividida pelo tamanho da tabela, e o resto da divisão é o endereço base; Método da multiplicação, onde multiplicamos a chave por uma constante entre 0 e 1, multiplicamos o resto de sua divisão por 1 pelo tamanho da tabela (quantidade de endereços) e arredondamos para baixo para obter seu endereço (deste modo o tamanho da tabela não é crítico, como no método da divisão, mas o valor da constante entre 0 e 1 sim); Método da dobra, onde se quebra a chave em partes e as recombina de outra maneira para gerar o endereço. Passamos para a aplicação de hashing em PLN, que começou com hashing em strings, utilizando o valor ASCII de cada letra que compõe a palavra e dividindo por um número escolhido, outra alternativa apresentada foi a consideração de uma base do tamanho do alfabeto utilizado. Numa matriz termo-contexto pode-se utilizar hashing para diminuir a dimensionalidade da tabela, reduzindo o número de colunas, desta maneira o vetor que representa cada palavra torna-se menor. Para finalizar a aula foram apresentados e explicados alguns scripts em python que aplicavam e demonstravam o resultado do hashing.
Gustavo Murayama	Na matriz esparsa termo-contexto, foram vistas técnicas como SVD. Com Hashing (tabelas de dispersão), a busca de acesso médio é igual a O(1) (“constante” na média) sendo o pior caso O(n). Hash Tables são extremamente rápida, tornando- as uma estrutura de dados eficiente para implementar um dicionário, levando em conta o acesso a uma posição de uma tabela com n elementos, por exemplo, em uma busca sequencial, que o é feita em O(n), uma busca binária, que leva tempo O(log2(n)), ou árvores balanceadas, em tempo O(log(n)). Ao tratarmos de endereçamento direto, podemos usar diretamente o valor de cada chave em seu índice de tabela, se baseando no fato de que podemos examinar qualquer posição em tempo O(1) (aplicável quando podemos alocar uma tabela com uma posição para cada chave possível). Há a desvantagem do tamanho do conjunto universo |U| ser muito grande para ser alocado em uma tabela T. Além disso, o conjunto de chaves K armazenadas na tabela pode ser muito menor que o universo de chaves U. Através da aplicação de uma função hash, a chave pode ser transformar em um endereço de tabela: hash(chave) -> {0, 1, , m - 1 }, sendo h(k) uma função h que mapeia o universo U de chaves para entradas de tabela de espalhamento T[0, , m - 1]. Uma dificuldade seria duas chaves serem mapeadas para a mesma posição na Tabela de Espalhamento. Podemos contornar esse problema ao tratar as colisões com encadeamento. Ao analisar as operações realizadas pela tabela Hash, observamos que a inserção e remoção é executada em tempo O(1) e a busca leva tempo proporcional ao comprimento da lista. Para evitar colisões, é usado uma função Hash que apresente comportamento randômico, como o Método da Divisão, que é fácil, eficiente e largamente empregada. A chave k é dividida pela dimensão da tabela m, e o resto da divisão é o endereço base: h(k) = k mod m. Bons valores para m são números primos. O Método da Multiplicação utiliza uma constante A maior que 0 e menor que 1, sendo h(k) calculado como h(k) = ? m(kA mod 1) ?, sendo kA mod 1 = kA - ? kA ?. Dessa forma, o valor de m não é crítico como no método da divisão, porém, a escolha adequada da constante A é crítica. Alguns valores A são melhores que outros, em particular a razão áurea. O Método da Dobra quebra a chave em partes e as combina de algum modo. Em todos esses métodos, consideramos a chave como sendo um número, mas caso seja uma string, há alternativas a serem realizadas: se uma chave é uma cadeia de caracteres, então podemos interpretá-la como um natural em uma base conveniente. A grande vantagem do hash é que é um algoritmo simples e eficiente para inserção, remoção e busca, porém, em contrapartida, não há nenhuma garantia de balanceamento, há espaços subutilizados nas tabelas e o grau de espalhamento é sensível à função de hashing utilizado e ao tipo de informação usada como chave.
Joao Victor Fontinelle Consonni	A décima segunda aula de PLN começou revisando brevemente o conceito de matriz termo-contexto, uma matriz esparsa que, mesmo na sua versão densa, obtida por meio da aplicação do método SVD sobre a matriz PPMI, ainda resulta em uma tabela extensa e que requer um método de busca eficiente. Relembramos alguns conceitos vistos Algoritmos e Estruturas de Dados, entre eles a busca sequencial, com tempo de acesso O(n); a busca binária, com tempo de acesso O(log2(n)); e árvores balanceadas, com acesso em O(log(n)). Contudo, para se implementar um dicionário, uma das estruturas de dados mais eficientes são as tabelas de Hash, que apresentam uma busca com acesso médio igual a O(1). As tabelas de Hash conseguem esse grau de eficiência pois fazem endereçamento e acesso direto, ou seja, utiliza-se o valor de cada chave em seu índice de tabela. Isso é aplicável em casos em que podemos alocar uma tabela com uma posição para cada chave possível, o que requer um universo de chaves razoavelmente pequeno. Para lidar com o universos grandes, é comum a utilização de uma função de hash para transformar a chave em um endereço de tabela, o que implica em mapear o universo de chaves para entradas da tabela de espalhamento. O problema desta técnica é que ela pode mapear duas chaves para um mesmo endereço da tabela de espalhamento. Nestes casos, é importante implementar um método de tratamento de colisões, como o encadeamento. Uma das possíveis formas de implementar a função de hash é por meio do método da divisão, que divide o valor da chave, k, pela dimensão da tabela, m, e utiliza o resto da divisão como o endereço base. O ideal é que m seja um número primo para garantir maior dispersão. Outro método visto foi o da multiplicação, que utiliza uma constante em sua formulação. Essa constante deve ser escolhida com cuidado para garantir boa dispersão (a razão áurea é particularmente eficiente). Outro método visto para implementar a função de hash foi o método da dobra, que quebra a chave em partes e depois as combina de forma diferente. Para quaisquer um destes métodos, quando a chave for um string, podemos traduzir as letras em números, a fim de obter uma chave numérica equivalente. Tabelas de hash geralmente dependem de algoritmos simples e eficientes para inserção, remoção e busca de elementos. O grau de espalahamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave, o que não garante balnceamento em todos os casos e pode ocasionar na sub-utilização das tabelas. No contexto de PLN, Feature Hashing é uma maneira rápida e eficiente para tratar vetores com muitas características. Utilizando o valor do hash do vetor, ao invés dos índices da matriz, é possível reduzir a dimensionalidade. Assim, cada palavra é representada por um vetor obtido epla aplicação da função de hash sobre o vetor da palavra. Por fim, foram apresentados alguns exemplos de aplicações implementadas em python para demonstrar os conceitos vistos na aula.
Lucas Ferraz Nicolau	Vimos que a dimensão da matriz termo-contexto depende do tamanho do vocabulário utilizado. Em caso de vocabulários extensos, temos matrizes esparsas que são ineficientes para armazenamento da informação. Uma solução deste problema utiliza a SVD, consistindo da fatoração da matriz em outras três matrizes mas. ainda assim, o processo de fatoração da matriz também pode ser muito caro e ineficiente. Uma outra técnica que pode ser utilizada para resolver este problema se baseia no uso de hashing ou tabelas de dispersão. Quando trabalhamos com vetores em computação e precisamos realizar alguma operação com algum elemento desse conjunto, utilizamos algum algoritmo de busca. Existem a busca sequencial de ordem de tempo O(n) e as buscas binária e com uso de árvore balanceada que são mais eficientes por serem de ordem de tempo O(log n). Entretanto, as buscas mais eficientes são realizadas por meio de estruturas de tabela de espalhamento, ou hash tables, que consegue operar a informação em tempo constante O(1). Devido sua eficiência, essa estrutura é utilizada para implementação de dicionários e em análises de PLN. Pelo endereçamento direto, pode-se usar diretamente o valor de cada chave em seu índice da tabela, onde qualquer posição destas pode ser examinada em O(1). Esta técnica entretanto, se limita a tabelas pequenas pois a alocação de uma tabela de um universo muito grande exigiria mais espaço em memória do que é viável. Com o uso de tabelas de dispersão, realizamos a conversão do endereço de tabela para um endereço base uniforme através da aplicação de uma função conveniente (função hash). deste modo, muitas chaves são armazenadas em um espaço menor, logo, existindo colisão entre elementos. Para melhor desempenho, esta função deve ter um comportamento randômico e deve ser do menor custo possível. Existem diversas funções utilizadas como função hash. O método da divisão consiste em utilizar uma função que uso o resto da divisão da chave pela dimensão da tabela, isto é, o módulo, tendo os melhores valores com tabelas de tamanho primo, de acordo os resultados empíricos. O método da multiplicação se baseia no produto da chave por uma constante entre 0 e 1, não sendo crítica com relação a dimensão da tabela mas em relação a constante que, por sua vez, pode ser melhor quando assume valores específicos, em particular, a razão áurea. O método da dobra utiliza a combinação de partes do valor da chave quando este é muito longo, por exemplo, somando as divisões dos dígitos da chave. Em PLN, queremos utilizar a função hash em strings. uma maneira de realizar este procedimento é utilizando os respectivos valores dos caracteres na tabela ASCII. Para não perdermos a posição relativa dos caracteres, podemos realizar a multiplicação por potências, entretanto, palavras muito compridas podem resultar em operações de processamento mais demorado. O Feature Hashing é uma estratégia que permite a redução da dimensionalidade associada a uma matriz termo-documento utilizando os vetores desta matriz por um valor hash ao invés do índice, como seria na abordagem inicial.
Matheus Dos Santos Pereira	Resumo da aula 12 de processamento de Linguagem Natural, sobre Feature Hashing, começando a matéria da aula vimos um pouco de tabela de dispersão, para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, há várias maneiras, como por exemplo busca sequencial: acesso em O(n) , busca Binária: acesso em O(log2(n), ainda lento se n é grande (log2 (1000000) = 20) e uso de árvores balanceadas: acesso em O(log(n)), acesso bem melhor do que na busca sequencial. Busca com acesso médio igual a O(1). Isso significa “constante” na média. No pior caso é O(n). Na medida do possível uma constante pequena, por isso devemos tentar usar Hash tables, A dificuldade de usar endereçamento direto é óbvia: A alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande. O conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U: Espaço utilizado: O(|U|), Tempo de busca: O(1), Através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela (endereço base). Uma dificuldade dessa técnica é a possibilidade de duas chaves k1 e k3 serem mapeadas para a mesma posição na Tabela de Espalhamento. Inserção é executada em tempo O(1). Remoção de um elemento x é executada em tempo O(1). Busca leva tempo proporcional ao comprimento da lista. Método da divisão: A chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base: h(k) = k mod m, resulta em endereços no intervalo: [0, m-1]. Bons valores para m são números primos (O motivo não é óbvio!) Método da multiplicação, O método utiliza uma constante A (0<A<1), sendo h(k), A vantagem deste método é que o valor de m não é crítico como no método de divisão, mas a escolha de uma constante A adequada é crítica, alguns valores de A são melhores do que outros, em particular a razão áurea. Método da dobra, quebre a chave em partes e combine-as de algum modo, por exemplo, se as chaves são números de 8 dígitos, e a tabela hash tem 1000 entradas, quebre a chave em 3 números, some-os, considerando os 3 últimos dígitos da soma para compor a chave, 73419883 ? 734 + 198 + 83 = 1015 ? 015 ? h(k) = 15. Sobre hash, algumas vantagens, algoritmo simples e eficiente para inserção, remoção e busca, desvantagens, nenhuma garantia de balanceamento, espaço subutilizado nas tabelas. O grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Feature hashing, é uma maneira rápida e eficiente para tratar vetores com muitas características. No lugar de utilizar índices (de uma matriz, por exemplo termo-contexto), será utilizado um valor de hash. Assim, essa estratégia permite reduzir dimensionalidade (número de características – e.g., colunas). Depois vimos alguns testes e aplicações utilizando python.
Amanda Cruz Francesconi	FEATURE HASHING. Para se resolver problemas de busca há diversas abordagens, uma delas é o Hashing, ou tabelas de dispersão, que executa uma busca com tempo constante O(1), no pior dos casos realiza em O(n). Por essa propriedade essa é uma estrutura de dados eficiente para implementar um dicionário através de um acesso direto. A desvantagem de uma alocação em matriz é que para universos muito grandes, pois assim a tabela que precisiará ser reservada para isso será inviável. Uma possibilidade de acontecer em tabelas de dispersão é a oclusão: duas chaves serem mapeadas para a mesma posição na tabela de espalhamento. A função de espalhamento tende a manter uma distribuição homogênea de chaves mapeadas para cada posição da tabela de espalhamento. Uma das formas de resolver as colisões é através de encadeamento, nesse caso a função hash apresenta um comportamento aleatório. 1. Método da divisão: a chave é dividida pela dimensão da tabela m, o resto da divisão é o endereço da base, resulta em endereços no intervalo de 0 a m-1. Os melhores valores de m são números primos. Tomamos alfa como fator de colisão, sendo determinado por m/n. 2. Método da multiplicação: calculado como o piso de m*(k*A mod1), sendo A uma constante entre 0 e 1. A vantagem desse método é que o valor de m não é crítico, porém é necessário fazer a escolha de A adequada. A razão áurea é uma boa constante. 3. Método da dobra: quebre a chave em partes e combine-as de algum modo, por exemplo dividir um número grande em 3 partes diferentes e somar as partes resultando na chave que será mapeada. HASH PARA STRINGS: uma das estratégias é somar o código ASC de cada uma das letras da string e fazer o resultado módulo 51. Uma das consequências é que todos os anagramas terão valores iguais. Uma alternativa é considerar a posição de cada caracter porém palavras longas apresentam um desafio por resultarem em um valor muito alto. Um desafio que está gerando pesquisas ultimamente é a criação de um hash universal. Feature Hashing: uma maneira rápida e eficiente para tratar vetores com muitas características, ao invés de utilizar índices será utilizado um hash, a ideia é diminuir o dimensionamento da matriz termo-contexto, assim cada palavra será representada por um vetor menor uma vez que normalmente os vetores compridos contém muitos valores nulos.Teste em phyton: função hash recebe uma palavra e retorna a soma dos valores na tabela ASC de cada uma das letras, main imprime "digite uma palavra" e retorna o h obtido da função hash. Dessa maneira não se tem controle do contra-domínio, ao se finalizar a função hash fazendo a soma mod x. Também é possível determinar o range de saída. No main é possível também criar um vetor de colisão que indicará quantas palavras estão em cada posição, assim pode-se descobrir se a função de distribuição utilizada é boa.
Leonardo Nascimento	Solucionado o problema com o tamanho da matriz termo-contexto, aplicando SVD na matriz PPMI e extraindo a matriz de Word Embeddings, o problema passa a ser a busca de palavras. Existem várias maneiras de se resolver problemas de busca, inserção e remoção em uma tabela com n elementos. A busca sequencial tem acesso em O(n), a busca binária tem acesso em O(log2(n)), a busca em uma árvore balanceada tem acesso em O(log(n)) e a busca em uma tabela de hash tem acesso em O(1) para o caso médio e O(n) para o pior caso. Por causa desse desempenho no caso médio, temos que tabelas de hash, também conhecidas como tabelas de dispersão e tabelas de espalhamento, são estruturas de dados eficientes para implementar um dicionário. Considerando um universo de chaves razoavelmente pequeno, o acesso e endereçamento direto é uma técnica simples, onde se aloca uma tabela com uma posição para cada chave possível e usa-se diretamente o valor de cada chave em seu índice. O problema está em alocar uma tabela para um universo de chaves muito grande, que reflete no mau aproveitamento do espaço quando o conjunto de chaves é muito menor do que o tamanho do universo. A base de uma tabela de hash está na função de hash, uma função conveniente que transforma uma chave em um endereço da tabela, mapeando o universo de chaves para entradas da tabela. Todavia, existe a possibilidade de duas chaves serem mapeadas para uma mesma posição e, para evitar colisões, as funções de hash devem apresentar comportamento randômico. Só que mesmo assim as colisões ainda podem acontecer, e nesses casos são tratadas com encadeamento. O método da divisão é uma função de hash eficiente onde uma chave k é dividida pela dimensão da tabela m, e o resto da divisão é o endereço da base, representada por h(k) = k mod m. Porém, bons valores para m são números primos. Com o método da multiplicação utilizamos uma constante A tal que 0 <A< 1, e a função de hash sendo calculada como h(k) = floor(m(kA mod 1)). A vantagem deste método está no fato de que o valor de m não é crítico como no método da divisão. Porém, a escolha de uma constante A adequada é crítica, e alguns valores de A são melhores do que outros, em particular a razão áurea. Outro método bastante simples é o método da dobra, onde se quebra a chave em partes e as combina de algum modo para definir seu endereço. Pensando em cadeias de caracteres, as funções de hash apresentadas até aqui também podem ser utilizadas se convertermos as letras para seus respectivos códigos na tabela ASCII, por exemplo. Feature hashing ou hashing trick para matrizes termo-contexto é uma maneira rápida e eficiente para tratar vetores com muitas características, e no lugar índices são utilizados valores de hash, uma estratégia para se reduzir dimensionalidade.
Laura Cestavo Borges Dos Santos	A aula do dia 19/7 foi sobre feature hashing. Em aulas passadas vimos que as matrizes termo-contexto, as quais são esparsas, ou seja, tem muitos termos nulos, exigiam uma grande quantidade de armazenamento, sendo impossível em algumas vezes. Guardar também as três matrizes do algoritmo de SVD também podia sair caro. Hashing são tabelas de dispersão. Para se resolver os problemas de busca, inserção e remoção em tabelas e vetores tradicionais há várias técnicas, com diferentes complexidades. Temos a busca sequencial, busca binaria e uso das arvores balanceadas. No caso das tabelas hash temos busca com acesso médio igual a O(1), ou seja, é constante na média, sendo o pior caso O(n). Hash tables são estruturas de dados eficientes para implementar dicionários, por exemplo. Tabelas hash podem ter acesso/endereçamento direto, pois considere que os valores das chaves sejam 0 até m-1. É possível usar diretamente o valor de cada chave em seu índice da tabela. O endereçamento direto se baseia no fato que podemos examinar uma posição qualquer em tempo constante (O(1)), isso é aplicável quando podemos alocar uma tabela com uma posição para cada chave possível. Essa técnica simples funciona quando o universo de chaves é razoavelmente pequeno e alocar uma tabela para universos grandes pode ser inviável, ou seja, essa técnica utiliza muito espaço à medida que o universo cresce. Uma outra opção são as tabelas de dispersão/espalhamento, onde através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço da tabela. Uma dificuldade dessa técnica é a possibilidade de duas chaves k1 e k3 serem mapeadas para a mesma posição na Tabela de Espalhamento. Uma forma de tratar as colisões é através do encadeamento, sempre que um elemento for colocado em uma posição que já há alguém, ele é ligado ao ultimo elemento, formando uma lista encadeada. Para evitar as colisões, é ideal usar uma função hash que tenha comportamento randômico. Uma das funções hash conhecidas é o método da divisão, que é fácil, eficiente e largamente empregado. Nele a chave k é dividida pela dimensão da tabela m e o resto é o endereço. Bons valores para m são número primos. O método da divisão pode fazer com que sequencias de números, tenham sequências de endereços bases, especialmente quando o m é menor. Outro método é o da multiplicação. A vantagem desse método é que o valor de m não é crítico, como no da divisão. Mas escolher a constante A adequada é crítico. Um terceiro método é o da dobra, onde ele quebra a chave em partes e as combina de alguma forma. Feature hashing é uma maneira rápida e eficiente para tratar vetores com muitas características. No lugar de utilizar índices (como na matriz contexto), será utilizado um valor de hash. Dessa forma diminui-se a dimensionalidade, pois cada vetor é representado por um vetor menor.
Jairo da Silva Freitas Junior	Na aula 12 iniciamos recapitulando os desafios relacionados ao uso de matrizes termo-conceito,que são muito grandes e esparsas. Mesmo empregando SVD para redução de dimensionalidade, é importante destacar que se a matriz for grande demais para caber em memória é inútil pensar em SVD. Uma estrutura de dados eficiente para implementar dicionários é a Hash Table / Tabela de Dispersão / Tabela de Espalhamento. Esta estrutura possui busca constante na média e funciona através da aplicação de uma função hash que mapeia cada chave para um endereço (compartimento) de tabela. Como esta tabela tem dimensão menor que o universo de chaves pode ocorrer colisões de chaves (duas chaves apontam para o mesmo compartimento). Para evitar isso é preciso empregar uma função hash com comportamento randômico e pode-se tratar as colisões usando encadeamento (onde cada compartimento contém uma lista ligada dos componentes que apontam pra ele). Uma função hash eficiente e largamente empregada é o método da divisão, onde o resto da divisão da chave k pelo número de compartimentos é o endereço do compartimento (isto é h(k) = k mod m). Se o número da constante hash e o número de compartimentos da tabela forem coprimos (máximo divisor comum = 1) as colisões entre chaves são minimizadas nos casos comuns, caso contrário teremos d vezes mais colisões, onde d é o maior divisor comum entre a constante hash e o número de compartimentos. Logo, números primos são boas escolhas para o número de compartimentos. Outra função hash usada é o método da multiplicação, que multiplica a chave por uma constante entre 0 e 1 e subtrai o piso do resultado dele mesmo (h(k) = floor(m(kA mod 1)). O valor de m neste caso não é crítico, mas o de A sim. Um valor de A bom é a razão áurea (A = 0,6180...). Outro método possível é o método da dobra que quebra as chaves em partes as combina. Para o caso particular de processamento de linguagem natural, uma forma de aplicar as funções hash é interpretar as cadeias comom um natural em uma base conveniente (ex: tamanho do alfabeto). As desvantagens dessa função hash é que não há garantia de balanceamento, espaço sub-utilizado nas tabelas e sensibilidade do grau de espalhamento à função de hashing utilizada. Para nos ajudar a reduzir a dimensionalidade das matrizes termo-contexto, podemos empregar o Feature Hashing para reduzir a dimensão das colunas da matriz. Assim, no lugar de uma matriz |V| x |V| temos uma matriz |V| por |C|, onde |V| é o tamanho do vocabulário e |C| < |V| a quantidade de compartimentos da tabela hash. Fizemos alguns exemplos Python em sala com a função hash do método da divisão e vimos o quanto o valor de M influencia na qualidade do espalhamento. Discutimos também que o hashing trick tende a manter palavras similares em escrita na mesma chave ou em chave próximas.
Eduardo Haberler Cardoso	A décima segunda aula de PLN, ministrada no dia 18 de Julho, teve como tema principal a Feature Hashing. Inicialmente foram relembrados os conceitos relacionados aos tamanhos de matrizes termo-contexto, dos seus respectivos tamanhos e também como matrizes PPMI ´pdem ser utilizadas para aumentar a eficiência de armazenamento das informações em questão. Em seguida, os conceitos de busca com o foco no uso do Hashing, i.e., as tabelas "de espalhamento" ou "de dispersão", foram apresentados. O uso das tabelas de hash para busca são os mecanismos mais eficientes para esta aplicação pois possibilitam a busca em O(1) no melhor caso e O(n) no pior caso, esta ferramenta se mostra bastante relevante para implementações de dicionários. Esta ação, de encontrarmos o valor armazenado em O(1) recebe o nome de endereçamento direto, mais especificamente esta ação utiliza a própria chave que desejamos encontrar como índice da tabela hash. Porém esta técnica tem um custo de memória alto e ineficiente, uma vez que teríamos que ter uma tabela do tamanho do universo de possibilidades de procura. Para solucionar esta questão é utilizado uma função hash, que tem como entrada o valor da chave que desejamos procurar e como saída o índice da tabela hash, onde os valores são armazenados. Porém, por estarmos trabalhando com funções tem que possuem como conjunto imagem um universo menor do que o universo de possibilidades, teremos menos posições na tabela do que possíveis valores a serem buscados. Na prática, isto quer dizer que podemos ter mais de um valor de chave levando à mesma posição na tabela hash, este fenômeno leva o nome de colisão. O uso das tabelas hash requerem uma abordagem de tratamento das colisões. Podemos fazer um encadeamento, onde cada posição da tabela é o início de uma lista encadeada e, caso haja a colisão, alocamos o novo valor no fim da lista. Posteriormente, entramos nos métodos de sintetização das funções hash. Primeiramente foi apresentado o método da divisão onde h(k) = k mod m e h(k) é o índice na tabela, k é a chave dividida pela dimensão da tabela m, este último, preferencialmente precisa ser primo, para reduzir o número de colisões e otimizar a distribuição na tabela. Os métodos da multiplicação e métodos de dobra também foram apresentados e podem ser conferidos no material disponível. Em seguida vimos algumas opções de transformarmos cadeias de texto em chaves para utilizarmos as ferramentas de hash previamente apresentadas. Apesar destas técnicas oferecerem resultados promissores para aplicações de busca, inserção e remoção, temos algumas desvantagens, como a não garantia de balanceamento, uma sub-utilização das tabelas e um grau de espalhamento incerto, a depender da função de hashing e do tipo de informação utilizada como chave. Para finalizar, foi apresentado código da aplicação dos conceitos de hash na construção de dicionários e matrizes termo-contexto, otimizando em muito a eficiência de armazenamento.
Felipe de Campos Mesquita	Na aula 12 de Processamento de Linguagem Natural o tema foi Hashing. Começamos com um resumo da aula anterior falando das matrizes esparsa termo-contexto. A bibliografia da aula continua sendo o livro Speech and language processing: Na introduction to natural language processing, computational linguistics, and speech recognition de Daniel Jurafsky e James H Martin. No tema de hashing que pode ser traduzido e encontrado em português como tabelas de dispersão, tabelas de espalhamento ou ainda pelo no nome em inglês mesmo, hash tables. Quando falamos de busca em tabelas (vetores/arrays) queremos resolver problemas de busca, inserção e remoção em uma tabela com n elementos, para isso podemos usar uma busca sequencial (acesso O(n)), busca binária (acesso em O(log2(n) ainda lento se n é grande) e uso de árvores balanceadas (acesso O(log(n) e acesso bem melhor do que na busca sequencial). Nas tabelas hash, a busca com acesso médio é igual a O(1), isso significa constante na média e no pior caso é O(n), na medida do possível uma constante pequena. Hash tables são uma estrutura eficiente e muito comum para implementar um dicionário. O endereçamento direto se baseia no fato de que podemos examinar uma posição qualquer em O(1), isto é aplicável quando podemos colocar uma tabela com um posição para cada chave possível. Algumas considerações: A dificuldade de usar um endereçamento direto é óbvia, a alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande. E O conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chave U (espaço utilizado: O(|U|) e tempo de busca O(1)). O hash é calculado através de uma função conveniente (função hash), a chave é transformada em um endereço de tabela. Na aula vimos o método da divisão que envolve o conceito de funções hash. Este método é fácil, eficiente e largamente utilizado. A chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base ( h(k) = k mod m). Bons valores para m são números primos. Também vimos na aula o método da multiplicação que usa tabelas hash. O método utiliza uma constante A (0<A<1), sendo h(k) calculado como h(k) = chão(m(kA mod 1)), a vantagem deste método é que o valor de m não é crítico como no método da divisão. Alguns valores de A são melhores do que outros, em particular a razão áurea (A = 0,6180...). Também vimos na aula o método da dobra que também utiliza funções hash e em seguida na aula vimos alguns exemplos de códigos que foram rodados usando python para demonstrar alguns conceitos do que vimos a respeito de técnicas que usam o conceito de hash.
Ramon Neres Teixeira Jardim	No início da aula foi relembrado os problemas relacionados ao alto uso de memória ao se trabalhar com matrizes termo-contexto e a utilização da técnica SVD na matriz PPMI para reduzir os problemas de uso de memória mantendo o máximo possível da semântica presente nas matrizes. Posteriormente foi introduzido o conceito de hashing, utilizadas para reduzir a complexidade da busca, inserção e remoção de elementos em uma tabela. Os métodos mais comuns de busca são: a busca sequencial, que encontra o item desejado em tempo O(n), a busca binária que tem tempo O(log2(n)) e a busca em árvores balanceadas, que também é O(log2(n)). Os três casos têm problemas de performance quando n é muito grande, fazendo necessário o uso de uma técnica mais rápida, o que é possibilitado pelo uso das tabelas de hash. As tabelas de hash ou tabelas de dispersão conseguem fazer uma busca com tempo de acesso médio em torno de O(1), mas podendo chegar a O(n) em casos extremos (possivelmente devido à uma função de hash ruim). Esta estrutura de dados consiste em uma estrutura de ados que pode ter suas posições examinadas em O(1), armazenando uma dupla contendo chave e valor, sendo a chave a posição do elemento no vetor. Também é necessária uma função de hash, que mapeia os valores em chaves de forma biunívoca (ou quase) em tempo constante. Dessa forma, para fazer uma busca, inserção ou remoção nesta tabela, basta aplicar a função de hash no elemento que se deseja encontrar e então checar a posição retornada pela função, fazendo a operação desejada. Infelizmente, as funções de hash costumam não ser biunívocas, o que nos leva a um problema de colisão, ou seja, alguns valores são mapeados na mesma chave. Para resolver isso, cada posição da estrutura pode ser uma lista, de forma que todas as colisões sejam armazenadas nesta lista, e uma pequena busca linear seja feita naquela lista de colisões quando esta chave for buscada. Existem vários métodos para a criação de funções de hash, alguns deles são: o método da divisão que divide um valor (inteiro) pela dimensão da tabela e utiliza o resto da divisão como chave, o método da multiplicação que utiliza uma constante entre 0 e 1 e calcula o hash como (tamanho da tabela) * (a parte decimal do produto entre a constante e a chave) e o método da dobra que divide a chave em parte e as combina. Uma aplicação das tabelas de hash em PLN é a técnica de feature hashing, que uma forma eficiente de se tratar vetores com muitas características. Nesta técnica, ao invés de se utilizar os índices da matriz, utiliza-se um valor de hash, reduzindo o número de colunas.
Rodolfo Azevedo Dos Santos	Feature Hashing É uma técnica para trabalhar com vetores de dimensão muito grande Da aula anterior... Estrutura que utilizamos depende do vocabulário. Se o vocabulário for muito extenso não da para representa-lo na memória. Compreensão: Transformar um vetor esparso em vetor denso (Uma aplicação é utilizar SVD). Hashing (tabelas de dispersão) Há várias maneiras de resolver problemas de busca em tabelas (vetores/arrays) Hash é uma estrutura. Busca com tempo médio de O(1): Acesso constante Constante na média, no pior caso é O(n) São eficientes para implementar um dicionário. (1) Acesso/Endereçamento direto Funciona quando o universo de chaves (keys) U é razoavelmente pequeno Colisão: Em uma determinada posição há vários números. Se universo grande não é possível alocar tabela. Hash perfeito: Tenta distribuir tudo de forma uniforme (2) Tabelas de dispersão/espelhamento Aplicação de uma função conveniente (função hash) que transforma a chave em um endereço da tabela. Função h. H(k) Mapeia a chave para algum domínio que pode ser controlado (na tabela de espelhamento) Tem que ser o mais barato possível, no geral O(1). Não pode ser O(n) ou O(logn) Há a possibilidade de duas chaves serem mapeadas na mesma posição na tabela de espalhamento (colisão) Objetivo: Tornar colisão uniforme para todos os valores As melhores funções de espalhamento mantém a colisão uniforme Uma forma de resolver as colisões é encadeando. ( Se duas estão ligadas então cria uma lista ligada). Também é possível utilizar Hash de Hash. Funções Hash Método da divisão: é o mais simples que existe. Recebe um número e retorna um número que é resultado dessa divisão (resto da divisão). Resulta em [0,...,m-1] Dessa forma temos controle do tamanho da tabela. Exemplo: m=12 (vetor de tamanho 12) k = 100 h(100)= 100 mod 12 = 4 Melhores valores de m são números primos, por quê? O motivo não é óbvio! Alfa é o fator de colisão (acha o melhor número primo dado a colisão aceitável) Método da multiplicação: Utiliza uma constante A, tal que 0 <A< 1. A escolha dessa constante é crítica. A = 0,618 (razão áurea – ótimo valor para uma função de espelhamento) Método da dobra: Quebra a chave em partes e as combina de alguma forma (quando o número é muito grande na quantidade de dígitos). É uma heurística Hash para string: Converte letra em número Desvantagem: Nenhuma garantia de balanceamento e grau de espalhamento é sensível a função de hash. Feature Hashing: Maneira rápida e eficiente para tratar vetores com muitas características Eixo x: Domínio da função de espalhamento Teste1.py: Ord retorna o UNICODE (número inteiro) Palavras próximas possuem h próximo (porque está somando) % indica o contradomínio (modula o valor de modo a controlar o tamanho)
Thiago Henrique Gomes Panini	Na décima segunda aula de Processamento de Linguagem Natural, o professor abordou as Tabelas de dispersão/espalhamento que, por sua vez, possui um universo U de chaves e um espaço amostral com “k” chaves. Uma dificuldade dessa abordagem é a possibilidade de duas chaves, “k1” e “k2” por exemplo, serem mapeadas para a mesma posição na tabela. Para evitar essas colisões, é possível aplicar uma função Hash que apresente um comportamento randômico, sendo esta uma função com o menor custo computacional possível . Vejamos algumas dessas funções. O método da divisão recebe um número k e retorna o resto da divisão entre esse número e um outro número m. Os resultados estarão em um espaço amostral que vai de 0 até m – 1, mostrando assim a quantidade de elementos da tabela de dispersão. Em um exemplo passado em aula, temos os parâmetros m=12 e k=100, fazendo com que a função retorne 100 mod 12 = 4. O módulo, aqui, indica a nova posição do elemento. Quais são os melhores valores para o parâmetro m? A resposta para essa pergunta é: números primos. A justificativa não é trivial e o professor indicou que pesquisássemos em fóruns como o stack overflow. Um outro exemplo prático mostrou o tamanho ótimo para a tabela para n=200 elementos de 8 bits com, no máximo, 3 elementos colidindo. O método da multiplicação utiliza uma constante A que aria entre 0 e 1. A vantagem deste método é que o valor de m não é crítico como no método da divisão. Para complementar, o professor passou alguns exemplos de valores para que possamos ter uma melhor noção sobre este método que, por sua vez, pode ser definido por: (kA mod 1) = kA – [kA]. Existem também outros métodos como o método da dobra, por exemplo. Entrando em detalhes sobre a função de hash, a grande vantagem é que trata-se de uma algoritmo simples e eficiente para inserção, remoção e busca. Dado que precisamos de uma função computacionalmente favorável, temos detalhes sobre o Feature Hashing. Um exemplo com um conjunto de dados foi mostrado para exemplificar o feature hashing, indicando um conjunto de dados, representando um idioma, com incríveis 40 milhões de palavras únicas (contando palavras novas e com erros de escrita). Para consolidar os conceitos, o professor Jesus mostrou scripts em python (.py) com códigos utilizando as bibliotecas NumPy e afins utilizando como base as obras de Machado de Assis (análises de similaridade). Feature hashing está relacionada a qualquer estrutura que precise de diminuição de espaço, em qualquer âmbito. A função de hashing pode mapear a estrutura grande em uma estrutura reduzida para agilizar o processamento.
Rodrigo San Martin Ignacio Gomes	Aula 12. 18/07. Feature Hashing. Para realizar buscas, inserção e remoção em uma tabela com n elementos, podem ser realizados busca sequencia, com acesso em O(n), busca binária, com acesso em O(log(n)) ou busca com uso de árvores balanceadas, com acesso em O(log(n)). Para busca binária, a busca ainda é custosa com n grande, pois por exemplo log2 (100.000) = 20. Já para acesso em arvores balanceadas, o acesso é mais rápido, tem custo de acesso média igual a O(1), que não significa exatamente o valor numérico de 1, mas sim que é uma constante, preferencialmente pequena. Assim, essas estruturas de dados são eficientes para implementar um dicionário. Para acesso ou endereçamento direto, considerando que os valores das chaves sejam: 0, 1, ..., m-1, pode-se usar diretamente o valor de cada chave em seu índice de tabela (cada chave x armazenada no compartilhamento x). O endereçamento direto se baseia no fato da possibilidade de examinar uma posição qualquer em O(1). No entanto, a alocação de uma tabela T de tamanho U pode ser inviável para um universo grande. O conjunto de chaves K armazenadas na tabela pode ser menor que o universo de chaves U, com espaço utiliza = O(U) e tempo de busca O(1). Uma alternativa é a utilização de tabelas de dispersão ou espalhamento ou hashing, que através da aplicação de uma função conveniente, a chave é transformada em um endereço da tabela de endereço base. h(k) é uma função h que mapeia o universo U de chaves para entradas na tabela de espalhamento T[0, ..., m-1]. Essa técnica pode resultar no mapeamento de duas chaves para a mesma posição da Tabela de Espalhamento. Esse problema é solucionado com o encadeamento, que é basicamente a montagem de uma pilha com os valores de k. Para evitar essas colisões, a função Hash precisa apresentar comportamento randômico. Para tanto, podem ser utilizados métodos com o da divisão, com h(k) = k mod m, resultando em endereços no intervalo de [0, m-1]. Nesse caso, os valores adequados para m devem ser primos, que resultam em um numero de espalhamento mais próximo de aleatório, reduzindo o número de colisões. Logo, o hashing de features é uma maneira rápida e eficiente para tratar vetores com muitas features. Ao invés de utilizar índices como os de uma matriz termo-contexto, é utilizado um valor de hash. Assim essa estratégia permite reduzir a dimensionalidade da matriz termo-contexto, reduzindo o número de colunas e consequentemente o custo.
Marcelo Schirbel Gomes	Feature Hashing Vamos aplicar os conceitos de hash para verificar similaridade de palavras. Pois percebemos que é muito complicado carregar a matriz esparsa na memória para fazer os cálculos, visto que a matriz é muito grande. Nas Hash Tables podemos fazer buscas com acesso médio de O(1), é um acesso constante. Sendo no pior caso, O(n). A nossa limitação principal seria o tamanho da lista de chaves. E o interessante é o modo como rearanjar esses números. A dificuldade é justamente alocar o tamanho do universo, quando muito grande. Temos um armazenamento muito grande, mas ganhamos muito tempo na busca. Através da função hash transformamos uma chave num endereço da tabela. Mas sempre haverão os efeitos de colisão, pois aplicar a função hash sobre duas chaves, teremos o mesmo valor. A sacada do algoritmo é deixar essas colisões uniformes para todas as entradas. Método da Divisão A chave é dividida pela dimensão da tabela. E temos que os melhores valores para essa divisão são os números primos. Método da Multiplicação Usa uma constante, entre 0 e 1, não podendo ser os extremos. Esse valor não é tão crítico como na divisão, mas é muito complexo tomar a decisão de qual número escolher. Assim, as chaves não ficarão em uma ordem, como no módulo da divisão, mas ficarão em um fator "aleatório". E percebemos que esse espalhamento é uniforme quando o número descrito for próximo da razão áurea. Método da Dobra Dividimos um número grande em três partes. Somamos os números dessas partes e aplicamos a função de espalhamento nessa soma. Usando em Palavras Agora devemos usar isso para as palavras. E podemos fazer essa conversão de letras em números. Usamos o código ASCII ou Unicode. As vantanges estão em fazer um algoritmo muito simples e eficiente. A desvantagem é que não controlamos tao bem o espalhamento e nem do balanceamento. \--- Featuring Hash Usaremos hash para resolver o problema de espalhamento não uniforme em nossas matrizes. Pois temos um documento em cada linha e cada coluna conta as relações entre as palavras. E o uso de palavras distintas na literatura pode variar a quantias que tornam o uso desse algoritmo inútil, de tanto tempo de processamento. No lugar de usar índices de uma matriz, usamos o valor de hash. Assim, poderemos reduzir a dimensionalidade. Não diminuiremos o número de linhas, mas o de colunas. E usaremos a função de espalhamento para trazer próximas as palavras com mesmo sentido semântico.
Pedro Ricardo Bronze	Busca em tabelas pode ser de diferentes maneiras e complexidades computacionais: Sequencial(O(n)), Binária(O(log2(n))), Árvores Balanceadas. No pior dos casos temos O(n) (lê-se 'O de n') para acessar valores em uma estrutura de dados. A dificuldade de usar o endereçamento é por exemplo o caso de uma tabela T de tamanho |U| pode ser inviável se a tabela e muito grande. Uma solução são as tabelas de espalhamento/dispersão, uma dificuldade é quando ocorrer 'colisão', ou seja, uma função hash mapeia duas chaves a mesma posição. Encadeamento é uma das formas de tratar essa colisões, sendo que o cálculo não pode envolver ter de percorrer todos os outros elementos. Basicamente o fato de colisão define quantos elementos máximos você quer alocar em cada uma das posições. Pelo método de divisão, que é fácil, eficiente e largamente empregado a equação 'h(k) = k mod m' aponta como k termos devem ser endereçados em m endereços. Hipoteticamente 2000 valores poderiam ser espalhados em 700 posições com uma média de aproximadamente 3 valores por chave. Outro método é o da multiplicação h (k) = [m(kA mod 1)] => (kA mod 1) = kA - [kA], para a chave k. Um bom número para utilizar é '(sqrt(5)-1)/2', 0,618 que se relaciona com a famosa proporção áurea. Outro método é o método da dobra que propõem quebrar a chave em partições combinando-as. No caso de strings podemos separar palavras de uma sentença e então utilizar o hashing para armazenamento. Cada letra por exemplo sendo mapeado a um número e multiplicada por uma base conveniente. Um exemplo de quão volumoso pode se tornar o armazenamento em memória de strings é que já foram contabilizadas 40 milhões de palavras diferentes na língua inglesa, isso em grande parte devido a erros ortográficos gerando uma enorme quantidade de palavras inexistentes. Hashing consegue resolver esse problema, a lógica é a de que diversas palavras podem aparecer uma única vez e podemos eliminá-las ao contabilizar a quantidade de vezes que estas aparecem em documentos. Como lição de casa o professor sugeriu que estudássemos o porquê da utilização de números primos para hashing. Um tópico do stackoverflow foi apontado como uma fonte para entendermos essa questão não trivial.
Diego Pereira de Lima	Na aula do dia 18 de julho do professor Jesus Mena Chalco, foi abordado os conceitos e alguns exemplos práticos de “Feature Hashing”. Porém, retomando os conceitos da aula anterior, foi dado uma abordagem da matriz de termo contexto com o viés de matriz esparsa com os casos de exemplo da aula anterior. O que atrapalha os algoritmos para aprendizagem de máquina, sendo mais confortável trabalhar com vetores mais “densos”. Para entender as tabelas de dispersão, ou hashing, precisamos lembrar que há vários métodos de busca de elementos em vetores como uma busca sequencial, binária ou por arvores balanceadas, onde cada uma possui uma complexidade devido a estrutura de dados e método do algoritmo. Na busca em tabelas de dispersão a complexidade é baixa O(1), ou seja constante e no pior caso é linear. É uma estrutura bem eficiente para implementar dicionários, pois seu acesso é direto. Ou seja, se temos oportunidade em espaço, podemos mapear cada chave com acesso direto aos dados, tornando uma espécie de função “injetora”. Então cada chave é transformada para um endereço de memória por uma função hash. Porém, ao formar uma hash é necessário tratar colisões, e as funções que manipulam e extraem informações de tabela hash possuem esta função. Como no caso do método da divisão que visa extrair o endereço base a partir do resto da divisão da chave pela dimensão da tabela. Há o método da multiplicação para calcular o endereço, se baseando em uma constante entre zero e um escolhida arbitrariamente. Há o método da dobra onde este visa quebrar a chave em partes e as combinar de algum modo. Para strings, poderia se extrair o valor na tabela ascii para cada caractere e depois realizar a somatória entre eles, porém anagramas possuiriam os mesmos valores. Ou seja, apesar do modelo hash ser eficiente e simples, utiliza tabelas em muitas vezes grandes e sensível ao espalhamento. Enfim a técnica de Feature Hashing visa reduzir a dimensionalidade de grandes vetores que ao invés de utilizar índices de uma matriz termo contexto utiliza-se o valor hash, tornando-a mais “densa”. Assim foi passado alguns exemplos em aula destas extrações e transformações neste método de redução de dimensionalidade das matrizes termo-contexto.
Estevao Crippa da Veiga	Para realizar busca, inserção e remoção em vetores e matrizes, podemos utilizar técnicas como busca sequencial, busca binária e busca em árvores, que têm complexidade de busca igual a O(n), O(log2(n)) e O(log(n)), respectivamente. Mas é possível utilizar uma técnica com complexidade O(1), utilizando tabelas de dispersão. Assim, no pior caso, temos complexidade O(n). Essa estrutura de dados é eficiente para implementar dicionários. Considere x chaves pertencentes a um universo X. Uma primeira forma é utilizar uma estrutura com x posições em que cada elemento é inserido diretamente na sua chave. É uma técnica que funciona para um universo X relativamente pequeno. Outra forma é utilizar uma função hash, em que cada chave é transformada em um endereço da tabela. Mas em caso de duas chaves colidirem na mesma posição, deve-se arrumar uma outra estrutura de dados para armazenar os elementos nessa posição Para elaborar uma função hash, existem algumas técnicas. O método da divisão parte do princípio que a chave k é dividida pela dimensão m da tabela e resto dessa divisão se torna o endereço base. O valor de k é extremamente importante e recomenda-se o uso de números primos para tal valor. Já o método da multiplicação considera o endereço base como o piso de da multiplicação de m pelo resto da divisão de kA por 1, em que A é uma constante que varia de 0 a 1. A escolha de A é extremamente importante, assim recomenda-se o uso do número de Euler para A. O método da dobra quebre a chave em partes e combina- as de algum modo; O que deve ser considerado em qualquer um dos métodos anteriores é o grau de espalhamento, que é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Assim, a melhor função mantém o maior grau de espalhamento possível. No contexto de PLN, o feature hash é uma maneira rápida e eficiente para tratar vetores com muitas características, em que no lugar de um índice utilizamos uma função hash, permitindo reduzir a dimensionalidade e, por consequência, o número de atributos.
Victor Arruda Ganciar	__Hashing__ Para resolver problemas de busca, inserção e remoção de elementos em uma tabela com n elementos existem diferentes métodos, como: busca sequencial, busca binária, árvores e _hashing_. _Hashing_ , também conhecido como tabela de dispersão ou espalhamento, é um método de busca de dados em uma tabela com tempo médio de O(1), que significa acesso constante na média, e que traz grande vantagem em relação aos demais métodos. Estas estruturas são muito eficientes para implementar um dicionário e por isso são usadas em processamento de linguagem natural. O endereçamento direto é uma técnica simples que pode ser usada quando o universo de chaves é suficientemente pequeno para caber na tabela de índices, porém esse método se torna um problema quando o universo de chaves é muito maior que o conjunto de chaves armazenadas. Uma função _hash_ transforma a chave em um endereço na tabela através de operações. A dificuldade nesse método se dá pela possibilidade de duas chaves diferentes, após o processo de transformação, gerarem o mesmo endereço na tabela, essa situação é conhecida como colisão, e uma forma de tratar as colisões é através do encadeamento. Diferentes operações podem ser utilizadas para gerar um endereço na tabela a partir da chave informada, como o método da divisão, fácil, eficiente e largamente utilizado onde a chave k é dividida pela dimensão da tabela m e o resto da divisão é o endereço a ser utilizado. O método da multiplicação utiliza uma constante A = [0, 1] e a vantagem para o método da divisão é que m não é crítica, porém a escolha de A deve ser adequada. O método da dobra quebra a chave em partes e as combina de algum modo. O _hashing_ é um algoritmo simples e eficiente para inserção, remoção e busca de elementos em uma tabela, porém não há garantia de balanceamento, os espaços podem ser sub-utilizados e o grau de espalhamento é sensível à função utilizada e ao tipo de informação usado como chave. _Featuring hashing_ é uma maneira rápida e eficiente para tratar vetores com muitas características.
Rafael Ribeiro Gomes da Silva	Nesta décima segunda aula analisamos que os métodos aprendidos até a aula passada serviriam para um conjunto menor de dados e que a melhor abordagem seria a redução do vetor para melhor manipulação e otimização do processamento. Para isso, é utilizada uma das funções mais conhecidas na computação, o hashing. O hashing é extremamente eficiente para a implementação de um dicionário, porque o caso médio é O(1) e seu pior caso tem assintoticidade O(n). Para um universo consideravelmente pequeno, é possível utilizar o endereçamento e acesso direto, onde cada chave tem seu índice na tabela e é armazenada em um compartimento específico, quando todas as chaves podem obter apenas um conjunto de valores. Porém, nessa abordagem temos a desvantagem de não utilizar corretamente o espaço caso não existam chaves o suficiente, além de não ser eficiente para um universo grande. A segunda forma é através do uso de tabelas de dispersão e espelhamento, ao contrário da outra abordagem múltiplas chaves podem ser mapeadas para o mesmo endereço, para evitar a condição de colisão, através de encadeamento. Quanto às operações, a inserção e remoção são executadas em tempo O(1) e a busca tem tempo proporcional ao comprimento da lista. O método da divisão, é simples e muito utilizado. A chave k é dividida pelo módulo baseado na dimensão da tabela, e os melhores valores são os números primos. O método da multiplicação, leva em consideração o número áureo e que o valor ao contrário da divisão o valor de m não é crítico, mas a constante utilizada sim. O método da dobra, quebra a chave em uma quantidade padrão de dígitos para formar uma nova chave. O problema que como são baseadas na tabela ascii, palavras anagramas são interpretadas da mesma maneira, para isso são atribuídos pesos para as letras e posições. Para as strings, o feature hashing trata os vetores com valores de hash ao invés de índices, reduzindo a dimensionalidade..O valor de M deve ser bem pensado, ou se não a matriz não será balanceada e os valores serão ineficientes.
Lucas Zanoni de Oliveira	Na aula 12 do dia 18/07/2019, em seu início foi relembrado o que foi visto na aula anterior, onde foi resgatada a matriz esparsa (termo-contexto), vetor esparso e denso e SVD. Feito isso, o novo conceito foi apresentado: hashing (tabelas de dispersão). Quando temos problemas de busca, inserção e remoção em tabelas, podemos utilizar alguns métodos como: busca binária, busca sequencial e uso de árvores balanceadas, que nos darão um desempenho no pior dos casos de O(n) e uma média de O(1), fazendo com que sejam estruturas de dados eficientes para que um dicionário seja implementado. Dois pontos importantes nesse prisma é o “acesso/endereçamento direto” que é uma técnica simples que funciona quando o universo de chaves é razoavelmente pequeno, e “tabelas de dispersão/espelhamento” que é uma forma de tratar colisões através de encadeamento. As funções hash possuem um método da divisão, onde uma chave k é dividida pela dimensão da tabela m, tendo o resto da divisão como o endereço base (h(k) = k mod m). Os melhores valores para m são os números primos. Há também o método da multiplicação que utiliza uma constante 0<A<1, e tendo h(k) calculado por: h(k) = [m(kA mod 1)]; nesse caso o m não é crítico como no da divisão, porém o A é. Além dos dois anteriores temos também o método da dobra que quebra a chave em partes, combinando-as de algum modo. Quanto ao hash em si, podemos destacar sua ventagem de ser simples e dispor de forma eficiente a inserção, remoção e busca, porém não possui nenhuma garantia de balanceamento, espaço sub-utilizado na tabela e o grau de espalhamento é sensível. Posteriormente, foi apresentado o conceito de “feature hashing” que é uma maneira rápida e eficiente para tratamento de vetores com muitas características, onde no lugar de índices são utilizados valores de hash, fazendo com que a sua dimensão (tabela e matriz) se reduza. Em seguida foram realizados alguns exemplos práticos para tabelas e matrizes.
Tiago Suzukayama	Nesta aula, o assunto abordado foi hashing. Para resolver problemas de busca, inserção é remoção em uma tabela com n elementos, temos várias técnica que podem ser utilizadas. Algumas delas são: busca sequencial (com acesso em O(n)), busca binária (com acesso em O(log2(n)) e uso de árvores balanceadas (com acesso em O(log(n)). Utilizando hash tables, que são estruturas de dados eficientes para implementar um dicionários, conseguimos acesso com pior caso O(n). Podemos também utilizar uma técnica chamada endereçamento direto. Considere que os valores das chaves sejam 0, 1, ..., m-1. Pode ser usado o valor de cada chave em seu índice na tabela. O endereçamento direto se baseia no fato de que podemos examinar uma posição qualquer em O(1). É uma técnica simples que funciona quando o universo de chaves U é razoavelmente pequeno. Algumas considerações devem ser levadas em conta: a alocação de uma tabela de tamanho U pode ser inviável para um universo muito grande, e o conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U. Também podemos usar tabelas de dispersão: através da ap?icação de uma função hash, a chave pode ser transformada em um endereço de tabela. Uma dificuldade desta técnica é a possibilidade de duas chaves k1 e k3 serem mapeadas para a mesma posição na tabela. uma das formas de tratas estas colisões é através de encadeamento. Se fizermos uma análise de suas operações, chegamos nos seguintes resultados: inserção possui tempo O(1), remoção possui tempo O(1) e a busca leva tempo proporcional ao tamanho da lista. Algumas das funções de hash são: método da divisão, onde a chave k é divida pela dimensão da tabela m, e o resto da divisão é o enderço base, o método da multiplicação, onde é utilizada uma constante 0<A<1, usando uma função m(k*A mod 1), e por fim o método da dobra, que quebra a chave em partes e as combina de algum modo.
Henrique Augusto Santos Batista	Para se resolver os problemas de busca, inserção e remoção em uma tabela com n elementos, há várias maneiras, algumas listadas a baixo: Busca sequencial: acesso em O(n) Busca Binária: acesso em O(log2(n)), ainda lento se n é grande (log2 (1000000) = 20) Uso de árvores balanceadas: acesso em O(log(n)), acesso bem melhor do que na busca sequencial o hashing é uma busca com tempo de acesso médio igual a O(1) isso significa “constante” na média no pior caso é O(n), na medida do possível é uma constante pequena. Hash tables são estruturas de dados eficientes para implementar um dicionário Considere que os valores das chaves sejam: 0, 1, ,m-1: Pode-se usar diretamente o valor de cada chave em seu índice de tabela (cada chave x armazenada no compartilhamento x) O endereçamento direto se baseia no fato de que podemos examinar uma posição qualquer em O(1). Isto é aplicável quando podemos alocar uma tabela com uma posição para cada chave possível. Essa técnica simples funciona bem quando o universo de chaves é pequeno A dificuldade de usar endereçamento direto é óbvia, a alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande O conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U: Espaço utilizado: O(|U|) Tempo de busca: O(1) Através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela(endereço base): Hash(chave) -> {0,1, ... ,m-1} h(k) é uma função h que mapeia o universo U de chaves para entradas da tabela de espalhamento T[0,...,m-1]. Uma dificuldade dessa técnica é a possibilidade de duas chaves k1 e k3 serem mapeadas para a mesma posição na Tabela de Espalhamento. Inserção é executada em tempo O(1). Remoção de um elemento x é executada em tempo O(1). Busca leva tempo proporcional ao comprimento da lista.
Renan Baisso	Em continuação dos estudos de Processamento de Linguagem Natural (PLN), em que desenvolvemos a ideia de construir uma matriz chamada de termo-documento ou ainda uma outra semelhante denominada de termo-termo. A ideia de se utilizar essas matrizes é ter uma estrutura que auxilie na análise de similaridade entre palavras ou entre textos. Porém, como visto anteriormente, executar processamento utilizando matrizes pode ser algo muito trabalhoso do ponto de vista computacional. Na aula passada estudamos a técnica de SVD que, a princípio nos ajuda a diminuir as matrizes esparsas, mas que demandam alto processamento por realizar a fatoração dos vetores bidimensionais, por isso, será abordado o assunto de Feature Hashing com intuito de otimizar este tipo de procedimento. Mas para tanto, faz-se necessário um breve resumo a respeito de tabelas de dispersão. A ideia principal por trás das tabelas de dispersão é distribuir a informação de maneira uniforme no espaço total da tabela, para que buscam sejam efetuadas com eficiência o(1). Podemos alcançar tal eficiência com uma boa função de Hashing, pois isto nos dará um acesso direto a posição da informação na tabela. As funções de Hashing geralmente são equações que retornam um resultado que representa uma posição da tabela de espalhamento que, por sua vez, pode armazenar mais de um valor para cada posição. Como mencionado anteriormente, as funções de hash tem como característica serem equações matemáticas, por isso as primeiras implementações foram baseadas em operações simples com divisão e multiplicação, cada uma com sua particularidade na escolha de fatores que compõem a expressão matemática, como a preferência por números primos ou o número da proporção Áurea. Desta maneira, podemos compreender a aplicação dessas técnicas na área de PLN, conhecida com Feature Hashing realiza a redução de dimensões passando as colunas de uma matriz para realizar o espalhamento dos termos ou documentos pela tabela hash, logo, teremos uma operação que otimiza o tempo de computação desse procedimento de redução.
Willian Teruya Kimura	No dia 18/07, o professor apresentou o conteúdo referente a Feature Hashing. Para iniciar o conteúdo da disciplina, foi revisado o conteúdo acerca de matriz esparsa de termo-contexto, e a transformação de vetor esparso para um vetor denso, reduzindo o tamanho do mesmo e facilitando para trabalhar em algoritmos de Machine Learning. Em seguida, foi apresentado o conceito de hashing, ou tabela de dispersão. Para introduzir o tema, foi discutido quais são as maneiras de se realizar buscas em tabelas, sendo elas: a) Busca sequencial, sendo o pior caso de sua complexidade do algoritmo O(n); b) Busca Binária, em que a complexidade de seu pior caso é O(log2(n)), ainda sendo lento se o valor de n é grande; c) Árvores balanceadas, em que a complexidade do pior caso é O(log(n)). Tendo em vista essas três formas de busca, fora encontrado uma outra maneira de busca em que a busca é realizada com um acesso médio igual a O(1): os hash tables. O seu pior caso é O(n). Hash tables são estruturas de dados eficientes para se implementar um dicionário. As vantagens do uso dessa estrutura é o endereçamento direto, em que pode-se considerar valores de chaves com valores que sejam: 0,1..m-1, e usar diretamente o valor de cada chave no índice da tabela. Tal endereçamento direto é baseado no fato de que pode se examinar uma posição qualquer em O(1). Há algumas considerações a se considerar, como a inviabilidade de alocar uma tabela caso o tamanho dos dados se trate de um universo muito grande, e que o conjunto de chaves K armazenadas pode ser menor do que o universo de chaves |U|. Através de uma função, a chave é transformada em um endereço de tabela. H(k) é uma função que mapeia o universo de chaves disponíveis para tabelas de espalhamento.
Luana Ferreira do Nascimento	Tabelas de dispersão, tabelas de espalhamento e hash tables são termos referentes ao mesmo modelo de dados em matriz. Estes termos se referem ao modelo onde transformamos os dados em um código hash e salvamos em uma matriz chave-valor. Esta forma de salvar dados faz com que seja possível realizar br com muito mais rapidez, pois as buscam se tornam O(1), ou seja, as buscas levam em média um tempo constante que dificilmente é alterado pela quantidade de dados armazenados na matriz. Estruturas de dados deste tipo são bastante eficientes para armazenar dicionários. A utilização do hash (função que transforma o dado em um código que para aquele dado sempre será o mesmo e a chance de ser utilizado por outros dados o pequena) faz com que o domínio de índices da matriz se torne menor, facilitando o armazenamento de informações extensas, como seria o caso de armazenar uma lista com todos os tokens presentes em um conjunto de documentos. Para criar as chaves dos termos a serem armazenados existem várias técnicas, entre elas: Método da divisão: a chave é dividida pela dimensão da tabela. Este é um método rápido e fácil, mas o tamanho da matriz será decisivo para a performance do modelo de dados. Método da multiplicação: parecido com o método da divisão, mas utiliza uma constante em vez do tamanho da matriz, transferindo a importância de escolha de um número para esta constante. Números primos ou a constante de ouro são boas escolhas para este valor. Método da dobra: divide a chave em pequenas partes e soma estas partes. Quando as chaves forem strings, podemos considerar o valor numérico de cada caractere ou realizar transformações como por exemplo fazer a = 1, ..., z = 26. Também é possível realizar hashing de features (chaves, ou palavras no nosso caso) transformando as tabelas de ocorrência em features em vetores para depois compactar estes vetores.
Paulo Alexander Simoes	Aula 12 :Feature Hashing Recapitulando, matrizes esparsas são fortemente usadas para verificar similaridade e correção de palavras. Pois resumindo os dados com a exclusão dos zeros, acabamos por otimizar no trabalho dos algoritmos de aprendizado de máquina. Onde a mesma ideia pode ser considerada na matriz PPMI. Seguindo a ordem - SVD - Truncation - Embedding. Hashing de dispersão: Para resolvermos os problemas de busca, inserção e remoção em uma tabela com n elementos, há várias maneiras. Como busca sequencial O(n); Busca binária O(log2(n)); árvores balanceadas O(log(n)) acesso bem melhor do que na busca sequencial. Busca com acesso médio igual a O(1). Isso significa “constante” na média. No pior caso é O(n). Na medida do possível uma constante pequena. São estruturas de dados eficientes para implementar um dicionário. Pode-se usar diretamente o valor de cada chave em seu índice de tabela (cada chave x armazenada no compartilhamento x). Isto é aplicável quando podemos alocar uma tabela com uma posição para cada chave possível. Técnica simples que funciona quando o universo de chaves U é razoavelmente pequeno. A dificuldade de usar endereçamento direto é obvia: A alocação de uma tabela T de tamanho |U| pode ser inviável para um universo muito grande.O conjunto de chaves K armazenadas na tabela pode ser muito menor do que o universo de chaves U: Espaço utilizado: O(|U|) Tempo de busca: O(1). Através da aplicação de uma função conveniente (função hash), a chave é transformada em um endereço de tabela (endereço base). h(k) é uma função h que mapeia o universo U de chaves para entradas da tabela de espalhamento T[0,...,m-1].Fácil, eficiente e largamente empregado. A chave k é dividida pela dimensão da tabela m: o resto da divisão é o endereço base: h(k) = k mod m
Rafael Correia de Lima	Nessa décima segunda aula de PLN o tema abordado foi o de Feature Hashing. As hash Tables são estruturas de dados eficientes para implementação de dicionários por contarem com consultas de baixo custo computacional. Algumas técnicas podem ser usada para a criação do dicionário. Uma delas é a de Acesso/Endereçamento Direto que é simples e funciona bem quando o universo de chaves é razoavelmente pequeno, mas tem algumas considerações a serem feitas, como por exemplo a dificuldade de alocação de uma tabela com um universo muito grande. Uma alternativa que visa contornar estes problemas é pela utilização de uma tabela de espalhamento, que através da aplicação de uma função conveniente à palavra para se obter o índice de armazenamento na estrutura do hash. Como as estruturas de hash usuais, é necessário considerar que podem ocorrer colisões quando há palavras para as quais a aplicação da função gera resultados iguais, implicando que estes ocupem o mesmo espaço quando há muitos elementos a serem guardados. Essa função deve ser criada de forma a distribuir os elementos de forma uniforme pela estrutura. Uma das funções de espalhamento que pode ser utilizada é a função do resto da divisão que para uma entrada k a posição de armazenamento é dada por k mod m, onde m é o tamanho da estrutura de hash. Nessa situação pode-se calcular o fator de colisão da hash table criada, dado por n/m, onde n é o número de elementos no universo e m o tamanho da hash table usada. Outras técnicas podem ser agregadas à essa função, como a multiplicação por um fator que pode tornar a distribuição de valores contíguos em chaves bastante distintas.
Murilo Bolzan Dionisio	Features de Hashing: Técnica usada para se atuar com arrays de tamanhos elevados. A ideia sobre isso pode ser agregada ao conceito de matriz e com os termo-contextos apresentados nas aulas anteriores, pois já que o espaço requerido para a matriz em questão é de tamanho elevado. A ideia geral do hash é transformar as operações de busca, inserções e remoções em coisas de maior eficiência. Em uma estrutura sequencial, temos alguns exemplos: Busca sequencial: O(n); Busca Binária: O(log2(n)); Busca em árvores balanceadas: O(log2(n)). É possível ser realizado em uma tabela de hash ou em uma tabela de dispersão as operações em ordem O(1). A função de dispersão é a técnica que faz a transformação dos valores em índices para facilitar os acessos. Um hash perfeito deve ter uma chave única para todas as possíveis chaves. No pior dos casos é possível ocorrer em O(n). Acesso / endereçamento direto: Técnica sucinta que funciona bem quando o grupo de chaves U é consideravelmente pequeno. A tática baseia-se em enumerar todos os símbolos para a tradução. Tabelas de dispersão / espalhamento: essa técnica necessita de duas chaves possam ter o mesmo número de índice, entretanto isto torna o tamanho da tabela bem menor do que o tamanho da quantidade de chaves. Método da divisão: A ideia aqui é utilizar o valor correspondente ao restante da divisão. Fazendo a suposição de que se esteja sendo feito 'k' mod 'm', onde valores ideais para 'm' são números primos por motivos não triviais. Método da multiplicação: A ideia é receber a variável 'k', multiplicá-la por um 'a' e subtrair pelo piso de 'km'. AK - floor(km).
Jair Edipo Jeronimo	Hashing tables ou tabelas de dispersão, são utilizadas para se resolver problemas de busca, inserção e remoção em grandes bases de dados. Por exemplo, para buscas sequenciais o tempo de acesso é O(n) e para buscas binárias O(log2(n)). A ideia das tabelas de dispersão é tornar o acesso médio igual a O(1), ou seja, constante na média. Para isso, o hash utiliza uma estrutura de dados eficiente para implementar um dicionário. O intuito é que para um conjunto de dados e através de uma função, cada termo seja mapeado a um endereço da tabela de dispersão diretamente. Entretanto, existe a possibilidade de para duas chaves diferentes termos o mesmo mapeamento na tabela de espalhamento o que chamamos de colisões e que devem ser tratadas. Uma das formas de evitar este problema é utilizar um encadeamento de termos que são mapeados ao mesmo endereço. Para criar as funções de mapeamento, podemos utilizar diversos métodos, como o da divisão, por exemplo, que é bem simples e eficiente. O método da divisão consiste em pegar uma chave e dividir pela dimensão da tabela, assim o resto da divisão será o endereço da chave. Por motivos de otimização, normalmente o valor do tamanho da tabela hash costuma ser um número primo. Entretanto, para o processamento de linguagem natural, é necessário utilizar funções que recebam palavras ao invés de números. Uma alternativa é converter os caracteres em seu valor na tabela unicode, ou até mesmo, utilizar suas posições na palavra para diferenciar as chaves de entrada. Durante a aula vimos algumas aplicações de métodos e a diferença entre os números que são utilizados como constantes das funções.
Gustavo Zanfelice Dib	Feature Hashing Técnica utilizada para se trabalhar com vetores de tamanho elevado. A ideia pode ser agregada ao conceito de matriz termo-contexto apresentados nas aulas anteriores, já que o espaço necessário para a matriz em questão é de grande escala. A ideia do hash tornar eficiente as operações de busca, inserção e remoção. Em uma estrutura sequencial, temos: Busca sequencial: O(n) Busca Binária: O(log2(n)) Busca em árvores balanceadas: O(log2(n)) Em uma tabela de hash ou tabela de dispersão é possível realizarmos as operações em ordem O(1). A função de dispersão é a tática que transforma os valores em índices para o acesso. Um hash perfeito consegue uma chave única para todas as possíveis chaves. No pior casos é possível ocorrer O(n) Acesso/endereçamento direto: Técnica simples que funciona quando o universo de chaves U é razoavelmente pequeno. A técnica se baseia em enumerar os símbolos para a tradução. Tabelas de dispersão/espalhamento: está técnica está sujeita a duas chaves possam ocupar o mesmo índice, porém isso torna o espaço da tabela bem menor do que o espaço das chaves. Método da divisão A ideia é utilizar o número correspondente ao resto da divisão. Supondo que esteja-se fazendo k mod m, valores ideais para m são números primos por motivos não triviais. Método da multiplicação: A ideia é receber a variável K, multiplicá- la por um "a" e subtrair pelo piso de km. AK - floor(km). Método da dobra: Esta técnica se baseia em escolher um definido número de caracteres e soma os valores de cada "dobra". Por exemplo com k=2 -> 346178 = 34+61+78
Iasmin de Haro Pracchias	Na aula do dia 18/07, o professor apresentou o conceito de busca em tabelas, que pode ser realizado de diversas maneiras, como busca sequencias, busca binárias e busca em árvore, e através de hash tables. Hash tables performam buscas com tempo constante na média, e O(n) no pior caso. Quando podemos construir e alocar uma tabela que possa armazenar cada chave diferente em posição uma posição, podemos falar de acesso direto, ontem para acessar qualquer chave levamos tempo constante O(1). No endereçamento direto podemos armazenar cada chave i no compartimento i. Porém num universo muito grande de chaves de tamanho T, fica inviável computacionalmente criar uma tabela de tamanho T para armazenar todos os elementos possíveis neste universo de chaves. Neste momento podemos utilizar as funções hash que tem o objetivo de mapear universo, chaves e elementos na tabela. Uma dificuldade deste método, considerando que podemos ter um maior número de elementos a serem armazenados que espaço na tabela, são as colisões, onde dois elementos podem ser alocados em uma mesma posição da tabela. Uma forma de tratar colisões seria utilizar listas ligadas na tabela hash, para conseguir armazenar todos os valores que colidem. Vimos alguns métodos de aplicar as funções hash de espalhamento como, o método da divisão, onde o endereço base é o resto da divisão da chave k pela dimensão da tabela, método da multiplicação, e método da dobra. Também vimos hash para strings, e por fim vimos alguns problemas de hash aplicados a PLN por meio de algoritmos escritos em Python.

Observação:

• Resumos na cor laranja, pontuaram na avaliação, entretanto devem ser melhor trabalhados.
• Resumos na cor vermelha estão incompletos e não pontuaram na avaliação.

Arquivo gerado por um programa.