<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Copyright 2021 Google LLC
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https
Step1:  Check Point
What is the dimension of the ascii character vector space?
What is the support of 'pizza'?
Step2:  The dot product and the norm
Convince yourself that this dot product here corresponds to dotting vectors.
With numpy arrays, that is numpy.dot.
Step3:  An Example
Step4:  The angles between vectors
This function finds the cosine_similarity in character-space between two char2vec vectors.
Step5:  How far are our examples from one another?
Step6:  Totally Optional Exercises
If the cosine_similarity=0, what do you know about the words?
If the cosine_similarity=1, are the words the same?
Can the cosine_similarity be negative?
Is the cosine_similarity symmetric?
In the definition of dot, above, why are these three definitions of the variable domain equivalent?
domain = string.ascii_letters
domain = support(v).union(w)
domain = support(v).intersection(w)
Define a distance by taking the inverse cosine of cosine_similarity.
Show this now actually computes the angle.
Given 3 words, does this notion of distance satisfy the triangle inequality? Modify the code above to show these three words do.
Advanced
Find a sequence of words w_1, w_2, ..., for which the sequence norm(w_1), norm(w_2), ... is unbounded.
Find two sequences of words whose pair-wise cosine_similarity is arbitrarily close to 1. i.e. Find word sequences a=a_1,a_2,... and b=b_1,b_2,... so that a_n and b_n make arbitrarily tiny angles.
This means that our vector space (with this distance) is not topologically discrete.
State a reasonable condition so that the vector space is discrete.
Step7:  Forget about sparsity! (a dense implementation)
The above example used a Python Counter, which is a defaultdict(int) to implement sparse vectors. That is critically important if your domain is e.g. the English Language. However in our case here our domain is just characters, so the sparseity is unnecessary. Here is a non-sparse, i.e. dense, implementation.
Step8:  More exercises
Hey, vector-spaces are over a field. What is the field in which this vector-space is over?
Pick a unicode encoding. What is its dimension?
Find an alternative basis for ascii character space. Can you think of a situation where it might be more useful than string.ascii_letters? (*)
Implement cosine_similarity_dense. It looks an awful lot like cosine_similarity, doesn't it?
Re-implement cosine_similarity using sklearn.CountVectorizer.
What is an advantage of the sparse implementation?
What is an advantage of the dense implementation?
<ASSISTANT_TASK:>
Python Code:
from collections import Counter
import math
def char2vec(word):
  # Counts each of the the characters in word.
  # We use a dictionary instead of a sparse matrix to describe the characters,
  # however the concept is identical.
  return Counter(word)
def support(v):
  # The support of a vector over a basis is the subset of basis elements with
  # non-zero components.
  return set(v)
# Note: We could have written this simpler: char2vec = Counter; support = set;
Explanation: Copyright 2021 Google LLC
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Character Space - The ascii_letters vector space
Inspired by the char2vec colab.
The character vector space
We begin by defining the character vector space which has the ascii_letters as its basis.  Why ascii? It's arbitrary and having only __ dimesions keeps things simple. We could have taken any of the unicode variations, but depending on the size of the character space we may want to pursue some optional optimizations which are also discussed below.
There are 2 functions which compute: <br>
1) the vector representation of the word, i.e. the counts of the characters in the word <br>
2) the support: the set of unique characters
End of explanation
import string
vector_space = string.ascii_letters
print(f"1. The dimension of vector_space is {len(vector_space)}, since there is one \n   independent vector per character and that's all of them.\n")
print(f'2. The support of pizza is {support(char2vec("pizza"))}.')
Explanation: Check Point
What is the dimension of the ascii character vector space?
What is the support of 'pizza'?
End of explanation
import string
def dot(v, w):
  domain = string.ascii_letters
  # Note that this computation is equivalent to each of the following
  # optimizations. Exercise: Why?
  #   domain = support(v).union(w)
  #   domain = support(v).intersection(w)
  #
  # This domain here bears a passing resemblance to integration doesn't it.
  return sum(v[ch] * w[ch] for ch in domain) 
def norm(v):
  return math.sqrt(dot(v, v))
Explanation: The dot product and the norm
Convince yourself that this dot product here corresponds to dotting vectors.
With numpy arrays, that is numpy.dot.
End of explanation
# Our sample "words"
wordlist = [
  'TheQuickBrownFoxJumpsOverTheLazyDog',
  'TheQuickWhiteFoxJumpsOverTheLazyDog',
  'SupermanJumpsOverTheTallBuilding',
]
# For each of our words, print its vector and some information about it.
for word in wordlist:
  print(word)
  print("  vector: ", char2vec(word))
  print("  support: ", support(char2vec(word)))
  print("  norm:", norm(char2vec(word)), end="\n\n")
Explanation: An Example
End of explanation
def cosine_similarity(v, w):
  return dot(v, w) / norm(v) / norm(w)
Explanation: The angles between vectors
This function finds the cosine_similarity in character-space between two char2vec vectors.
End of explanation
from itertools import combinations
# Find the cosine similarity between each of the 3 vectors created above
# Similar senteces will have higher scores, ranging from 0-1.
for x, y in combinations(wordlist, 2):
  print ("Cosine Similarity between", x, "and", y,"=",
         cosine_similarity(char2vec(x),char2vec(y)), end="\n\n")
Explanation: How far are our examples from one another?
End of explanation
def similarity(x,y):
  return cosine_similarity(char2vec(x), char2vec(y))
print("similarity of", "able", "elba", ": ", similarity("able", "elba"))
print("similarity of", "gabe", "juno", ": ", similarity("gabe", "juno"))
print("similarity of", "piz...za", "piz...zza", ": ", similarity("pi" + "z"*10**3 + "a", "pi" + "z"*(10**3 +1) + "a"))
Explanation: Totally Optional Exercises
If the cosine_similarity=0, what do you know about the words?
If the cosine_similarity=1, are the words the same?
Can the cosine_similarity be negative?
Is the cosine_similarity symmetric?
In the definition of dot, above, why are these three definitions of the variable domain equivalent?
domain = string.ascii_letters
domain = support(v).union(w)
domain = support(v).intersection(w)
Define a distance by taking the inverse cosine of cosine_similarity.
Show this now actually computes the angle.
Given 3 words, does this notion of distance satisfy the triangle inequality? Modify the code above to show these three words do.
Advanced
Find a sequence of words w_1, w_2, ..., for which the sequence norm(w_1), norm(w_2), ... is unbounded.
Find two sequences of words whose pair-wise cosine_similarity is arbitrarily close to 1. i.e. Find word sequences a=a_1,a_2,... and b=b_1,b_2,... so that a_n and b_n make arbitrarily tiny angles.
This means that our vector space (with this distance) is not topologically discrete.
State a reasonable condition so that the vector space is discrete.
End of explanation
import string
import numpy as np
vector_space = string.ascii_letters
def char2index(ch):
  return vector_space.index(ch)
def index2char(index):
  return vector_space[index]
def char2vec_dense(word):
  out = np.zeros(len(vector_space))
  for ch in word:
    out[char2index(ch)] += 1
  return out
def support_dense(v):
  return "".join(index2char(i) for i in v.nonzero()[0])
# Now the dot, really is np.dot
def dot_dense(v, w):
  return v.dot(w)
def norm_dense(v):
  return dot_dense(v)**.5
# For each of our words, print its vector and some information about it.
for word in wordlist:
  print(word)
  print("  vector: ", char2vec_dense(word))
  print("  support: ", support_dense(char2vec_dense(word)))
  print("  norm:", norm_dense(char2vec_dense(word)), end="\n\n")
Explanation: Forget about sparsity! (a dense implementation)
The above example used a Python Counter, which is a defaultdict(int) to implement sparse vectors. That is critically important if your domain is e.g. the English Language. However in our case here our domain is just characters, so the sparseity is unnecessary. Here is a non-sparse, i.e. dense, implementation.
End of explanation
# This function looks an awful lot like cosine_distance, doesn't it.
def cosine_similarity_dense(v, w):
  return dot_dense(v, w) / norm_dense(v) / norm_dense(w)
Explanation: More exercises
Hey, vector-spaces are over a field. What is the field in which this vector-space is over?
Pick a unicode encoding. What is its dimension?
Find an alternative basis for ascii character space. Can you think of a situation where it might be more useful than string.ascii_letters? (*)
Implement cosine_similarity_dense. It looks an awful lot like cosine_similarity, doesn't it?
Re-implement cosine_similarity using sklearn.CountVectorizer.
What is an advantage of the sparse implementation?
What is an advantage of the dense implementation?
End of explanation
<END_TASK>