Anotações sobre Ciência de Dados

Básico

Data science (DS) é um ramo da ciência da computação e da estatísica que, bem, lida com dados. Ela se preocupa com 5 questões:

• Essa coisa é A ou B?
• Essa coisa é estranha?
• Quantas dessas coisas nós temos?
• Como essas coisas estão organizadas?
• Qual é a próxima coisa que eu devo fazer?

Para isso, nós usamos algoritmos sobre um conjunto de dados (data set), geralmente utilizando computadores.

Algoritmos de classificação dividem o data set em duas categorias.

Algoritmos de detecção de anomalias determinam qual porção do data set é anormal. Por exemplo, eles podem ser utilizados para detectar fraudes em cartões de crédito por meio da análise das compras.

Regressão é o procedimento de transformar um data set em um número, geralmente uma predição.

Algoritmos de Clustering agrupam partes dos dados que são de alguma forma relacionadas.

Algoritmos de aprendizagem tentam prever qual é a próxima ação baseado em experiências anteriores e o que é certo ou errado.

A Data Science requer que o data set seja:

• Relevante
• Conectado
• Acurado
• Abundante

Para responder essas questões da melhor forma possível, vários tópicos aparecerem dentro da ciência de dados, cada um tentando resolver um problema diferente mas ainda assim relevante a estas 5 questões. Por exemplo: recuperação de informação, análise de redes e machine learning.

Análise Semântica Latente

Este é o procedimento para recuperar informação de um texto utilizando análise computacional. Ele é geralmente feito por meio da equação TF.IDF, que é descrita no livro "An Introduction to Information Retrieval" por Christopher Manning.

O algoritmo básico consiste de:

• Construir uma matriz termo-frequência (`TF`, ou `T**D`)
• Calcular tf-idf utilizando alguma definição válida
• Realizar decomposição matricial "Single Value Decomposition"
• Calcular similaridade dos documentos (matriz `D**D`)
• Calcular similaridade entre os termos (matriz `T**T'`)

A partir daí, calculamos o TF.IDF:

`tfidf(t) = tf(t)*log(N/(df(t)))`

Onde

• `N`: número de documentos
• `tf(t)`: quantas vezes o termo aparece no geral
• `df(t)`: quantas vezes o termo aparece no documento

Distância de Levenshtein

"In information theory, linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965."

Em C:

// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
{
  int cost;

  /* base case: empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}

O algoritmo mais eficiente para o cálculo da distância de Levenshtein é o algoritmo de Wagner-Fischer.

Análise de Redes

Redes

Uma rede é um grupo de atores e as relações entre eles. Geralmente esses atores são pessoas e suas relações podem ser qualquer tipo de relação social, tal como amizade ou amor. Porém, esses grupo pode ser entendido como uma estrutura de quaisquer itens que se relacionam, como aeroportos e aviões, ou a internet.

Redes geralmente são modeladas utlizando grafos a fim de poderem ser analisadas. Neste sentido, nós devemos transformar as informações que queremos em perguntas matemáticas, geralmente aquelas que fazemos com data science. Essas questões nos darão as métricas que serão trabalhadas acerca de um certo tópico, como as conexões; a distribuição; ou a segmentação.

Métricas de distribuição para redes incluem densidade; distância; e centralidade.

Existem várias métricas de centralidade (`CT`) para grafos, mas todas elas tentam, de alguma maneira, determinar qual são os vértices mais importantes do grafo. Entre elas, incluem-se:

• Centralidade de grau
• Autovetor
• Betweenness (calculada pelo algoritmo de Brandes)
• Pagerank (utilizado pelo Google)

Redes reais se comportam como sistemas complexos. Isto é, elas possuem quatro características intrínsecas principais:

• Alta percolação: todos os nós estão interconectados de alguma forma
• Liberdade de escala: a probabilidade dos graus dos nós segue uma lei de potência
• Clustering: existem comunidades dentro da rede
• "Mundo pequeno": a maior distância entre dois nós quaisquer é proporcional ao logaritmo do número de nós

Curiosamente, essas características não podem ser simultaneamente matematicamente modeladas ou simuladas. Ainda assim, a maioria dos grandes sistemas do mundo real podem ser descritos como uma rede que está sujeita a demonstrar essas propriedades.

Medidas de centralidade

Algumas medidas de centralidade incluem as seguintes:

• Eigencentrality para leigos: representa a influência de um nó na rede. Um nó com alta centralidade de autovetor é conectado aos nós com mais conexões.
• Betweenness para leigos: representa a importância em termos de conectividade entre as comunidades que um nó tem dentro da rede? Um nó com alta betweeness representa, em geral, um mediador.
• Betweenness for engineers: the betweenness b of a vertex i is defined as the number of shortest paths between other pairs of vertices that pass through i. It can be calculated using Brandes algorithm.

E temos ainda vários recursos para nos ajudar a entendê-las:

• Understanding weighted degree betweeness centrality

Machine Learning

Classificador Logístico

• Matriz de pesos `W`
• Matriz de entradas `X`
• Viés `b`
• Predição `y`

`y = WX + b`

Para que este classificador funcione, `W` e `b` precisam ser treinadas. Para cada rótulo possível, elas devem ser treinadas para que `y` seja maior quando `x` estiver próximo da entrada.

Função Softmax:

`S(y, i) := (exp(y[i])) / (sum_j (exp(y[j])))`

Transforma uma nota em uma probabilidade. Se você multiplicar as notas `y` nesta função por 10, por exemplo, os resultados ficam muito próximos de 1 ou de 0.

Coisas a se perceber:

• One hot encoding: um rótulo é definido como uma matriz em que todos os itens são iguais a 0 menos na posição relevante.
• Cross-entropia: compara as notas obtidas e on hot encoding da seguinte forma:

`D(S,L) := -sum_i L_i ln(S_i)`

Onde `D` é a cross-entropia; `S`, as notas; e `L`, os encodings. Note que `D(S,L) != D(L,S)`.

Até agora, descrevemos o modelo logístico multinomial:

1. Entrada
2. Logit
3. Softmax
4. 1hot

Neste contexto, vamos definir a perda como sendo:

`cr(L) = sum_(i=1)^(N) (D(S(w x_i + b), L_i))/N`

O objetivo, portanto, é minimzar as perdas por meio do ajuste de `W` e de `b`. Este processo pode ser feito por meio da otimização gradiente, que transforma machine learning em um problema de otimização matemática (por meio de análise matemática).

Quando lindando com um problema de otimização, tente normalizar os parâmetros, isto é, torne a média igual a 0 e variância, pequana.

Optimization in a nutshell: lather, rinse, repeat.