Notes

Ripasso Prox: 30 Ripasso: June 6, 2023 Ultima modifica: May 14, 2023 6:13 PM Primo Abbozzo: March 13, 2023 9:20 AM Studi Personali: No Elementi di ripasso Teoria dei Tipi Introduzione Definizione 🟩— Un metodo sintattico praticabile per dimostrare l’assenza di determinati comportamenti del programma, fatto classificando le unità sintattiche in base ai tipi di valore che assumono Vogliamo che fosse praticabile nel senso che effettivamente lo possiamo implementare, cioè ci permettono di avere certe tipologie di garanzia. ma ancora è una definizione molto ampia. E di solito si può fare una analisi statica del comportamento del programma. ...

Top-down Algoritmo di parsing 🟩 Slide Questo si potrebbe considerare come algoritmo classico di parsing con non determinismo. (vado avanti, ed esploro tutto, senza look ahead). Esempio di esecuzione Commenti efficienza di sopra 🟩 È molto inefficiente, in particolare si potrebbe trovare una compessità esponenziale del tipo $O(b^{|w|})$, con b il massimo numero di produzioni. (la produzione maggiore la espando sempre!) ...

Espressioni, Comandi, Ricorsione Espressioni Con espressione intendiamo una entità sintattica, che una volta valutata ritornerà un valore, oppure non termina, in questo caso si dice che la espressione è INDEFINITA. Questa è una definizione è leggermente ambigua dato che non abbiamo una definizione precisa di valutazoine, che è fortemente dipendente dalla macchina astratta in cui viene eseguito. Notazioni (sintassi possibili) (3) 🟩 Notazione infissa Questa è la notazione classica matematica, per cose tipo $a -b$, in cui l’operando sta nel mezzo degli operatori. ...

Gaussians are one of the most important family of probability distributions. They arise naturally in the law of large numbers and have some nice properties that we will briefly present and prove here in this note. They are also quite common for Gaussian Processes and the Clustering algorithm. They have also something to say about Maximum Entropy Principle. The best thing if you want to learn this part actually well is section 2.3 of (Bishop 2006), so go there my friend :) ...

Anomaly detection is a problem in machine learning that is of a big interest in industry. For example a bank needs to identify problems in transactions, doctors need it to see illness, or suspicious behaviors for law (no Orwell here). The main difference between this and classification is that here we have no classes. Setting of the problem Let’s say we have a set $X = \left\{ x_{1}, \dots, x_{n} \right\} \subseteq \mathcal{N} \subseteq \mathcal{X} = \mathbb{R}^{d}$ We say this set is the normal set, and $X$ are our samples but it’s quite complex, so we need an approximation to say whether if a set is normal or not. We need a function $\phi : \mathcal{X} \to \left\{ 0, 1 \right\}$ with $\phi(x) = 1 \iff x \not \in \mathcal{N}$. ...

Robbins-Moro Algorithm The Algorithm $$ w_{n+1} = w_{n} - \alpha_{n} \Delta w_{n} $$For example with $\alpha_{0} > \alpha_{1} > \dots > \alpha_{n} \dots$, and $\alpha_{t} = \frac{1}{t}$ they satisfy the condition (in practice we use a constant $\alpha$, but we lose the convergence guarantee by Robbins Moro). More generally, the Robbins-Moro conditions re: $\sum_{n} \alpha_{n} = \infty$ $\sum_{n} \alpha_{n}^{2} < \infty$ Then the algorithm is guaranteed to converge to the best answer. One nice thing about this, is that we don’t need gradients. But often we use gradient versions (stochastic gradient descent and similar), using auto-grad, see Backpropagation. But learning with gradients brings some drawbacks: ...

Here we attempt to answer what is memory, how is it stored and retrieved. Memory is a process by which information is: Encoded Stored Retrieved The brain has different types of memories, and certain brain regions are specialized for this task. Ebbinghaus Curves Other experiments destroy parts of the cortex and correlate this with recall. Types of memory TODO see Kendal67-1 figure. Sensory memory iconic memory (remembering images) 150-500 milliseconds Echoic memory (recognizing some sounds) usually retained for 1 to 2 seconds. This memory is filtered by consciousness/attention to be passed to short term working memory. The register capacity of this memory is considered to be quite large. Short-term memory it has an explicit storage of about 7 +- 2 items (so very small). Depending on attention level, it is retained for 2 to 18 seconds. It seems the representation here is often vocal. ...

Introduzione alla notazione asintotica Cercare di definire il tempo impiegato da una funzione per essere eseguita in termini di DIMENSIONE dell’input. **(il numero di bit a livello basso basso) Ma abbiamo il problema di misura, in quanto dobbiamo considerare delle variabili che siano indipendenti rispetto alla macchina. Caratteristiche della notazione Vogliamo considerare una notazione asintotica (che guarda quanto fa il comportamento verso l’infinito) ### Accesso di memoria Ogni operazione in un processore moderno ha in generale un numero di accessi in memoria constante (solitamente abbiamo sempre un numero fissato di operandi possibile, questo significa che se un certo algoritmo ha una certa complessità, resta di questa complessità anche tenendo in considerazione le operazioni di accesso di memoria). Questo discorso non tiene più se teniamo in considerazione numeri a precisione infinita, che possono avere un numero arbitrario di accessi in memoria per poter essere computato. ...

We have a group of mappers that work on dividing the keys for some reducers that actually work on that same group of data. The bottleneck is the assigning part: when mappers finish and need to handle the data to the reducers. Introduction Common input formats 🟨 You need to know well what Shards Textual input binary, parquet and similars CSV and similars Sharding 🟩 It is a common practice to divide a big dataset into chunks (or shards), smaller parts which recomposed give the original dataset. For example, in Cloud Storage settings we often divide big files into chunks, while in Distributed file systems the system automatically divides big files into native files of maximum 10 GB size. ...

The synaptic connections that define such circuits are typically made in a dense tangle of dendrites, axons terminals, and glial cell processes that together constitute what is called neuropil. Knee-Jerk Response The knee-jerk reflex (also known as the patellar reflex) is a classic example of a mono-synaptic reflex arc, which involves a direct connection between sensory and motor neurons, as well as inhibitory circuits to regulate movement. ...