Tag Archives: Google

Baking recipes made by AI | Google Cloud

AI Leave a comment

AI Baking :
“Breakie” = Bread + Cookie
“Cakie” = Cake + Cookie

https://cloud.google.com/blog/topics/developers-practitioners/baking-recipes-made-ai

Remark:

By the way, the 1789 AD French Revolution Queen Marrie Antoinette’s famous quote of “WHY don’t the hungry farmers go eat Brioch ? “

“Brioch” = 50% Bread + 50% Cake

Cake-like “high-class” bread ‘Brioch’ made by my bread machine.
Butter-rich “Brioch”

Big Picture: Linear Algebra 

Modern Math 1 Comment

The Big Picture of Linear Algebra 线性代数 (MIT Open-Courseware by the famous Prof Gilbert Strang)

A.X = B

A(m,n) = \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1}&a_{m2} &\ldots & a_{mn} \end{pmatrix}

A(m, n)  is a matrix of m rows, n columns

4 sub-Vector Spaces:
Column Space {C(A)} , dim = r = rank (A) 
Row Space {C(A^{T})} , dim = r = rank (A)

Nullspace {N(A)}   {\perp C(A^{T})} , dim = n – r

Left Nullspace {N(A^{T})} {\perp C(A)} , dim = m – r

Abstract Vector Spaces ​向量空间

Any object satisfying these 8 axioms belong to the algebraic structure of Vector Space: eg. Vectors, Polynomials, Functions, …

Note: “Vector Space” + “Linear Map” = “Category” Vect_{K}

Eigenvalues & Eigenvectors (valeurs propres et vecteurs propres) 特征值/特征向量

[ Note: “Eigen-” is German for Characteristic 特征.]

Important Trick: (see Monkeys & Coconuts Problem)
If a transformation A is linear, and the “before” state and “after” state of the “vector” v remain the same  (keep the status-quo) , then : Eigenvalue \boxed {\lambda = 1}

\boxed {A.v = \lambda.v = 1.v = v}

Try to compute:
{ \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1}&a_{n2} &\ldots & a_{nn} \end{pmatrix} }^{1000000000}
is more difficult than this diagonalized equivalent matrix:
{ \begin{pmatrix} b_{11} & 0 & \ldots & 0\\ 0 & b_{22} & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 &0 &\ldots & b_{nn} \end{pmatrix} }^{1000000000}

= { \begin{pmatrix} {b_{11}}^{1000000000}&0 &\ldots &0\\ 0 &{b_{22}}^{1000000000} &\ldots & 0\\ \vdots &\vdots & \ddots & \vdots\\ 0 &0 &\ldots &{b_{nn}}^{1000000000} \end{pmatrix}}

Note: This is the secret of the Google computation of diagonalized matrix of billion columns & billion rows, where all the bjk are the “PageRanks” (web links coming into a particular webpage and links going out from that webpage).

The Essence of Determinant (*): (行列式)

(*) Determinant was invented by the ancient Chinese Algebraists 李冶 / 朱世杰 /秦九韶 in 13th century (金 / 南宋 / 元) in《天元术》.The Japanese “和算” mathematician 关孝和 spread it further to Europe before the German mathematician Leibniz named it the “Determinant” in 18th century. The world, however, had to wait till the 19th century to discover the theory of Matrix 矩阵 by JJ Sylvester (Statistical Math private Tutor of Florence Nightingale, the world’s first nurse) closely linked to the application of Determinant.

[NOTE] 金庸 武侠小说 《神雕侠女》里 元朝初年的 黄蓉 破解 大理国王妃 瑛姑 苦思不解的 “行列式”, 大概是求 eigenvalues & eigenvectors ? 🙂

Google PageRanking Algorithm

Modern Math 1 Comment

Google Illustration:

The following Webpages (1) to (n=6) are linked in a network below:
eg.
Page (1) points to (4),
(2) & (3) points to (1)…

image

Let
a_{ij} = Probability (PageRank *) from Page ( i ) linked to Page (j).

(*) PageRank: a measure of how relevant the page’s content to the topic of your query. This value is computed by the proprietary formula designed by the 2 Google Founders Larry Page & Sergey Brin, whose Stanford Math Thesis mentor was Prof Tony Chan (who knows the ‘secret ‘ to put his name always on Google 1st search list.)

The Markov Transition Matrix (A) is :

A = \begin{pmatrix} a_{11} & a_{12}& \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} &\ldots & a_{nn} \end{pmatrix}

Assume we start surfing from Page (1).

We define PageRank Vector x
x = (1 0 0 0…0), the Probability of reaching from Page (1) to itself is 1, to other pages is 0.

First Iteration:

x.A = (1 0 0 0…0).\begin{pmatrix} a_{11} & a_{12}& \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} &\ldots & a_{nn} \end{pmatrix}
x.A = \begin{pmatrix} a_{11} & a_{12}& \ldots & a_{1n} \end{pmatrix} = x_1

2nd Iteration:
x_{1}.A = \begin{pmatrix} a'_{11} & a'_{12}& \ldots & a'_{1n} \end{pmatrix} = x_2
or,
x_{1}.A = (x.A).A = x.A^{2} = x_2

.
.

nth Iteration:
x_{n} = x.A^{n}

When n is large,
x_{n} converges to a steady-state vector, ie
x_{n-1} \approx x_{n}
That is,
x.A^{n-1} \approx x.A^{n}
“Cancel off” both sides by A^{n-1} (technically multiply both sides by A^{-(n-1)}
So we get,
x \approx x.A

We say that x is a Left EigenVector of A if
\boxed { x.A = x }

By Perron’s Theorem:
Every real square matrix with entries that are all positive has
■ a unique eigenvector “x” with all positive entries;
■ the x‘s corresponding eigenvalue ” λ” has only one associated eigenvector, and
■ this eigenvalue “λ” is the largest of the eigenvalues.

Applying to A (square matrix with positive real numbers),
=> one and only one (left) eigenvector x which satisfies x.A = x
=> x is unique and has all positive entries (PageRank values).

It guarantees that no matter how much the Web changes or what set of Web pages Google indexes, the PageRank vector (x) can always be found and will be unique !

Example in the above Illustration:
If the unique PageRank vector x is computed after n iterations as follow:

x = \begin{pmatrix} 0.25\\ 0.35\\ 0.63\\ 0.05\\ 0.12\\ 0.47 \end{pmatrix}
Then Google will list the search result in this order:
1st: Page 3 (0.63)
2nd: Page 6 (0.47)
3rd: Page 2 (0.35)
4th: Page 1 (0.25)
5th: Page 5 (0.12)
6th: Page 4 (0.05)

Knowing this trick, some hackers in 2003 initiated a “Google Bomb” attack on President George W. Bush, associated him with Google query “miserable failure“.

Revision:
Linear Algebra (Left & Right Eigenvectors and eigenvalues).

Ref:
《Math Bytes》by Tim Charter
Princeton University Press
[NLB #510 CHA]

Google Patents:
https://www.google.com/patents/US6285999

谷歌背后的数学:

The New Language to Watch : Go

Business Leave a comment

Google’s new language Go is invented to replace Java, hence free from Oracle’s threat of Java license in all Android Smartphones.

Go Language is invented by Ken Thompson, the father of Unix and B language, which was transformed into the famous C language by his Bell Lab’s teammate Dennis Ritchie.

Go impresses me of its concurrency best suitable for parallel programming, given today’s most hardware including smartphones are made of multi-core CPU, yet none of today’s languages is designed inherently to take advantage of it, even Java.

If we can say Cobol is for the 1st generation Mainframe computing, C the 2nd generation Unix-based Minicomputer computing, Java the 3rd generation Client-Server computing, then Go will be the 4th generation Mobile-Cloud computing.

Try the Go simulator here:
http://golang.org

Note 1: Do not confuse with another Agent-based language “Go! “, differs by “!” sign.

Note 2: Review of Go multicore concurrency feature:
http://mobile.eweek.com/developer/google-go-lets-developers-work-more-with-multicore-parallel-computing



Google Linear Algebra

Modern Math 1 Comment

Google Search Engine & Linear Algebra:
1) Let M(nxn) matrix of size n (say 1 billion) web pages:

\begin{pmatrix} m_{11} & m_{12} & \ldots & m_{1n}\\ m_{21} & m_{22} & \ldots & m_{2n}\\ \vdots & \vdots & m_{jk} & \vdots\\ m_{n1} & m_{n2} &\ldots & m_{nn} \end{pmatrix}

m_{jk} = \begin{cases} 1, & \text{if Page }j \text{ linked to Page k} \\ 0, & \text{if } \text{ not} \end{cases}

Note: This PageRank of 0 & 1 is over-simplied. The actual PageRank is a fuzzy number between 0 and 1, based on Larry Page’s patented PageRank formula, taking into accounts of the importance of the pages linked from and to, plus many other factors.

2) Let v(n) eigenvector of n webpages’ PageRank ak:
\begin{pmatrix} a_1 \\ a_2 \\ \vdots\\ a_k \\ \vdots\\ a_n \end{pmatrix} \displaystyle \implies a_k= \sum_{j}m_{jk}
(all Page j pageRanks)
The page k pointed to by all pages j.

3) Let λ eigenvalue: M.v =λ.v

4) Iterate n times: \boxed{(M^{n}).v = \lambda{^n}.v}

=> page k is ranked more important if many important pages j point to it;
& pages j themselves pointed by other important pages, …(iterate n times).
=> highest ranked pages appear first in Search list.

Google PageRank Search

Elementary Math, Modern Math Leave a comment

Google: “A page is good insofar as good pages link to it”
=> PageRank invented by Larry Page while a graduate Math student in Stanford University, under the supervision of Prof Tony Chan (now the President and Professor of Mathematics & Computer Science and Engineering of Hong Kong University of Science and Technology).

Below is a simplified 3 web pages of PageRanks x, y, z respectively.

x page receives link from z :
(x=z)

y page receives 1/2 link from x:
(y= 1/2 x)

z page receives 1/2 link from x and 1 link from y:
(z = 1/2 x + y)

All PageRank scores = 1 (Conservation Law of PageRank):
(x + y + z = 1)

Solve PageRank Simultaneous Equation:
x = z
y = 1/2 x
z = 1/2 x + y
x + y + z = 1

=> x = 2y = z
=> x = 2/5, y = 1/5, z = 2/5

Visually from below, you can see x and z pages have more links than y.

So the search result should return x,z pages in front of y page.

Using Linear Algebra to compute the eigenvalues and the eigenvectors of large matrix of billion variables, Google applies mathematics and the power of clustering 50,000 cheap CPU to search the Internet, making billion dollars.

Computers are powerful only when they are ‘told’ with great algorithm, which is based on Math. The other example is RSA Encryption with big prime number factorization.

20130409-164228.jpg