Lecture Week 2 Introduction, Vectors and Matricies.pdf

Introduction to Data Science and Systems Lecture 2: Introduction of Vectors and Matrices Dr Zaiqiao Meng  Intended Learning Outcomes what a vector is and what a vector space is the standard operations on vectors: addition and multiplication what a norm is and how...

Introduction to Data Science and Systems Lecture 2: Introduction of Vectors and Matrices Dr Zaiqiao Meng  Intended Learning Outcomes what a vector is and what a vector space is the standard operations on vectors: addition and multiplication what a norm is and how it can be used to measure vectors what an inner product is and how it gives rise to geometry of vectors how mathematical vectors map onto numerical arrays the different p-norms and their uses important computational uses of vector representations how to characterise vector data with a mean vector and a covariance matrix the properties of high-dimensional vector spaces the basic notation for matrices the view of matrices as linear maps how basic geometric transforms are implemented using matrices how matrix multiplication is defined and its algebraic properties the basic anatomy of matrices  Example: Text and translation Text, as represented by strings in memory, has weak structure. There are comparison functions for strings (e.g. edit distance, Hamming distance), but only character-level semantics String operations are character-level operations like concatenation or reversal, but not useful for machine translation system  Words aren't enough Original "The craft held fast to the bank of the burn." (the vessel stayed moored to the edge of the stream) Dictionary lookup (naiive) French: "L'artisanat tenu rapide à la Banque de la brûlure." (the artisanal skill held quickly to the financial institution of the burn wounds) Danish: "Håndværket holdt fast til banken af brænden" (The craftmanship held fast to the bank [financial institution] of fire) Correct(ish) French: "Le bateau se tenait fermement à la rive du ruisseau." (the boat was firmly attached to the riverbank) Danish: "Farttøjet holdt fast i bredden af åen" (The vessel held fast at the bank of the river)  Solution -- to place them in a vector space Imbue text fragments with additional mathematical structure -- to place them in a vector space Fragments might be words, partial words or whole sentences  The structure of a (topological) vector space What words are like salamander? Distance/metric functions: norm E.g. the neighbourhood of the vector corresponding to salamander, which might include words like axolotl or waterdog What is the equivalent of a king, but with a woman instead of a man? Operation functions: subtraction, mean Famously, the original word2vec paper should that on their test data, the equation King − Man + Woman = Queen  Vector spaces Vectors to be ordered tuples of real numbers A vector has a fixed dimension n Each element of the vector as representing a distance in a direction orthogonal to all the other elements. Orthogonal just means "independent", or, geometrically speaking "at 90 degrees". We write vectors with a bold lower case letter:  Vector spaces A vector space is a set whose vectors. For example, a length-3 vector might be used to represent a spatial position in Cartesian coordinates, with three orthogonal measurements for each vector. Consider the 3D vector [5, 7, 3] Each of these vectors [1,0,0], [0,1,0], [0,0,1] is pointing in a independent direction (orthogonal direction) and has length one.  Points in space Notation: ℝ means the set of real numbers. ℝ!" means the set of non-negative reals. ℝ# means the set of tuples of exactly 𝑛 real numbers (vector). ℝ#×% means the set of 2D arrays (matrix) of real numbers with exactly 𝑛 rows of 𝑚 elements. The notation ℝ# , ℝ# → ℝ says that the operation defines a map from a pair of 𝑛 dimensional vectors to a real number.  Points in space Vector spaces Any vector of given dimension n lies in a vector space, called ℝ# , along with the operations of: scalar multiplication so that 𝑎𝐱 is defined for any scalar 𝑎. For real vectors, 𝑎𝐱 = 𝑎𝑥&, 𝑎𝑥', … 𝑎𝑥# , elementwise scaling. ℝ, ℝ# → ℝ# vector addition so that 𝐱 + 𝐲 vectors 𝐱, 𝐲 of equal dimension. For real vectors, 𝐱 + 𝐲 = 𝑥& + 𝑦&, 𝑥' + 𝑦', … 𝑥( + 𝑦( the elementwise sum ℝ# , ℝ# → ℝ#  Points in space Two additional operations A norm ∥ 𝐱 ∥ which allows the length of vectors to be measured. ℝ# → ℝ!" An inner product 𝐱 𝐲 , ⟨x,y⟩ or 𝐱 3 𝐲 which allows the angles of two vectors to be compared. The inner product of two orthogonal vectors is 0. For real vectors 𝐱 3 𝐲 = 𝑥&𝑦& + 𝑥'𝑦' + 𝑥)𝑦) … 𝑥( 𝑦( ℝ# , ℝ# → ℝ  Topological and inner product spaces With a norm a vector space is a normed vector space/topological vector space. With an inner product, a vector space is an inner product space, and we can talk about the angle between two vectors. Topological/geometrical space: a set whose elements are called points Metric space: define distance between points, e.g. norm Vector space Normed vector space: a vector space with norm defined  Topological and inner product spaces With a norm a vector space is a normed vector space. With an inner product, a vector space is an inner product space Relationship between Inner Product and Norm: If you have an inner product on a vector space, you can derive a norm from it: 𝐱 = ⟨𝐱|𝐱⟩ However, not all norms come from an inner product.  Vectors Points in space Arrows pointing from the origin Tuples of numbers These are all valid ways of thinking about vectors. The "points in space" mental model is probably the most useful vectors to represent data; data lies in space matrices to represent operations on data; matrices warp space.  Relation to arrays 1D floating point arrays are we called "vectors" floating point numbers are NOT real numbers  Uses of vectors They are a lingua franca for data. Because vectors can be composed (via addition), compared (via norms/inner products) and weighted (by scaling), In Numpy, they map onto the efficient ndarray data structure, so we can operate on them efficiently and concisely.  Vector data Datasets are commonly stored as 2D tables. Observations one element of the vector (feature) Each row can be seen as a vector in ℝ!  Geometric operations Use vectors in 3D space Transformations in 3D space include: scaling rotation flipping (mirroring) translation (shifting) The Cobra Mk. III spaceship model above is defined by these vectors specifying the vertices in 3D space  Machine learning applications Machine learning relies heavily on vector representation. A typical machine learning process involves: transforming some data onto feature vectors creating a function that transforms feature vectors to a prediction (e.g. a class label) Most machine learning algorithms can be seen as doing geometric operations: comparing distances, warping space, computing angles, and so on. E.g. k nearest neighbours  Example: irises classification The irises classification task: The measurements of the dimensions of the sepals and petals of irises allows classification of species Training data: [sepal, petal] Labels: species of irises k nearest neighbours Using a norm to compute distances The output prediction is the class label that occurs most times among these k neighbours  Example: irises classification k nearest neighbours Calculate distance between training examples and the target using norm Finding the closest k neighbors (e.g. 3, 5, 10), voting for the most majority  Example: irises classification The choice of k might significantly affect the prediction result The distance function (norm or cosine similarity) is something need to be considered  Example: Image compression Images can be represented as 2D arrays of brightness Groups of pixels -- for example, rectangular patches -- can be unraveled into a vector. E.g. An 8x8 image patch would be unraveled to a 64-dimensional vector. Splitting images into patches, and treating each patch as a vector x_1,…,x_n The vectors are clustered to find a small number of vectors y_1,…,y_m, mO(N2) but