Astrazione sul controllo

Significato di astrazione L’astrazione è una cosa fondamentale nell’informatica, l’abbiamo visto anche nella prima lezione in assoluto per architettura, il sistema a strati di Architettura e livelli 1, 2 reti e simili. Il principali metodi sono astrazioni sul controllo e sui dati sui dati stiamo cominciando a parlarne in Teoria dei Tipi. Le astrazioni sono utili a nascondere dettagli per qualche fenomeno o simile (ricorda l’esempio della mappa, che non è il territorio è una astrazione su essa, che contiene ancora informazioni utili). Vogliamo quindi concentrarci su quanto ci interessa ...

Reading Time: 4 minutes ·  By Xuanqiang 'Angelo' Huang

Logica Proposizionale

Con la logica proposizionale studiamo le denotazioni che hanno un valore di verità, ovvero deve essere una sentenza assertiva. Studio solamente le connotazioni che hanno una capacità denotativa, in quanto è solo quello ch emi importa. 6.1 La sintassi Vengono qui definite le produzioni che valgono in ogni singolo mondo. $$ F ::= \top|\bot|A|B|...|\not F| F \wedge F| F \vee F| F \implies F $$Questa è la BNF della nostra sintassi. ...

Reading Time: 9 minutes ·  By Xuanqiang 'Angelo' Huang

Fast Linear Algebra

Many problems in scientific computing include: Solving linear equations Eigenvalue computations Singular value decomposition LU/Cholesky/QR decompositions etc… And the userbase is quite large for this types of computation (number of scientists in the world is growing exponentially ) Quick History of Performance Computing Early seventies it was EISPACK and LINPACK. Then In similar years Matlab was invented, which simplified a lot compared to previous systems. LAPACK redesigned the algorithms in previous libraries to have better block-based locality. BLAS are kernel functions for each computer, while LAPACK are the higher level functions build on top of BLAS (1, 2,3). Then another innovation was ATLAS, which automatically generates the code for BLAS for each architecture. This is called autotuning because it does a search of possible enumerations and chooses the fastest one. Now autotuning has been done a lot for NN systems. ...

Reading Time: 5 minutes ·  By Xuanqiang 'Angelo' Huang

Clustering

Gaussian Mixture Models This set takes inspiration from chapter 9.2 of (Bishop 2006). We assume that the reader already knows quite well what is a Gaussian Mixture Model and we will just restate the models here. We will discuss the problem of estimating the best possible parameters (so, this is a density estimation problem) when the data is generated by a mixture of Gaussians. $$ \mathcal{N}(x \mid \mu, \Sigma) = \frac{1}{\sqrt{ 2\pi }} \frac{1}{\lvert \Sigma \rvert^{1/2} } \exp \left( -\frac{1}{2} (x - \mu)^{T} \Sigma^{-1}(x - \mu) \right) $$Problem statement $$ p(z) = \prod_{i = 1}^{k} \pi_{i}^{z_{i}} $$ Because we know that $z$ is a $k$ dimensional vector that has a single digit indicating which Gaussian was chosen. ...

Reading Time: 6 minutes ·  By Xuanqiang 'Angelo' Huang

Markov Chains

Introduzione alle catene di Markov La proprietà di Markov Una sequenza di variabili aleatorie $X_{1}, X_{2}, X_{3}, \dots$ gode della proprietà di Markov se vale: $$ P(X_{n}| X_{n - 1}, X_{n - 2}, \dots, X_{1}) = P(X_{n}|X_{n-1}) $$ Ossia posso scordarmi tutta la storia precedente, mi interessa solamente lo stato precedente per sapere la probabilità attuale. Da un punto di vista filosofico/fisico, ha senso perché mi sta dicendo che posso predire lo stato successivo se ho una conoscenza (completa, (lo dico io completo, originariamente non esiste)) del presente. ...

Reading Time: 7 minutes ·  By Xuanqiang 'Angelo' Huang

HTTP e REST

HTTP is the acronym for HyperText Transfer Protocol. Caratteristiche principali (3) Comunicazioni fra client e server, e quanto sono comunicate le cose si chiude la connessione e ci sono politiche di caching molto bone (tipo con i proxy) Generico: perché è un protocollo utilizzato per caricare moltissime tipologie di risorse! Stateless, ossia non vengono mantenute informazioni su scambi vecchi, in un certo modo ne abbiamo parlato in Sicurezza delle reti quando abbiamo parlato di firewall stateless. Solitamente possiamo intendere questo protocollo come utile per scambiare risorse di cui abbiamo parlato in Uniform Resource Identifier. ...

Reading Time: 6 minutes ·  By Xuanqiang 'Angelo' Huang

Compiler Limitations

On Compiler Adding compilation flags to gcc not always makes it faster, it just enables a specific set of optimization methods. It’s also good to turn on platform specific flags to turn on some specific optimization methods to that architecture. Remember that compilers are conservative, meaning they do not apply that optimization if they think it does not always apply. What are they good at Compilers are good at: mapping program to machine ▪ register allocation ▪ instruction scheduling ▪ dead code elimination ▪ eliminating minor inefficiencies ...

Reading Time: 3 minutes ·  By Xuanqiang 'Angelo' Huang

Diffusion Models

Diffusion is a physical process that models random motion, first analyzed by Brown when studying pollen grains in water. In this section, we will first analyze a simplified 1-dimensional version, and then delve into diffusion models for images, the ones closest to (Ho et al. 2020). The Diffusion Process This note follows original Einstein’s presentation, here we have a simplified version. Let’s suppose we have a particle at $t = 0$ at some position $i$. We have a probability of jumping to the left of $p$ to right of $q$, the rest is staying at the same position. ...

Reading Time: 13 minutes ·  By Xuanqiang 'Angelo' Huang

Fast Fourier Transforms

The algorithm has been the same, some ideas are in Fourier Series, but architectures change, which means there are new ways to make this algorithm even faster. Example of transforms We have learned in Algebra lineare numerica, Cambio di Base that linear transforms are usually a change of basis. They are matrix vector multiplications (additions and multiplications by constants). The optimizations are based on what sorts of transforms we have (e.g. Sparse Matrix Vector Multiplication, or dense versions). The same idea applies also for Fourier transforms. ...

Reading Time: 5 minutes ·  By Xuanqiang 'Angelo' Huang

RL Function Approximation

These algorithms are good for scaling state spaces, but not actions spaces. The Gradient Idea Recall Temporal difference learning and Q-Learning, two model free policy evaluation techniques explored in Tabular Reinforcement Learning. A simple parametrization The idea here is to parametrize the value estimation function so that similar inputs gets similar values akin to Parametric Modeling estimation we have done in the other courses. In this manner, we don’t need to explicitly explore every single state in the state space. ...

Reading Time: 14 minutes ·  By Xuanqiang 'Angelo' Huang