Probability Tidbits 7 - All About Integration As we discussed in tidbit 5 , random variables are actually functions. These functions are non-negative everywhere and importantly measurable . This means for any measurable set in the output measurable space (typically $(\mathbb{R}, \mathcal{B})$), the preimage of the measurable set must also be measurable in the input measurable space(arbitrary…
Probability Tidbits 6 - Kolmogorov’s 0-1 Law In the 4th tidbit we discussed the definition of almost surely and infinitely often . In the discussion of the converse of the second Borel-Cantelli lemma , we referenced the Kolmogorov 0-1 Law , but didn’t prove it or even state the general result. The law states that for independent random variables \(\{X_n\}_n\) its tail $\sigma$-algebra is…
Probability Tidbits 5 - Random Variables Random variables aren’t actually variables. They’re measurable functions (see previous post here ) between a measurable space $(\Omega, \mathcal{F})$ and $(\mathbb{R}, \mathcal{B})$ (I’m going to use $\mathcal{B}$ instead of $\mathcal{B}(\mathbb{R})$ as I’ve done previously as shorthand). Recall that for a measurable function $h: \Omega \to \mathbb{R}$,…
Probability Tidbits 4 - Almost Surely and Infinitely Often Suppose we have a probability space $(\Omega, \mathcal{F}, P)$, an event is some $E \in \mathcal{F}$ and outcomes are $\omega \in \Omega$. It’d be nice to characterize behavior events on uncountably infinite measurable spaces like $(\mathbb{R}, B(\mathbb{R}))$. Let’s roll a six-sided die. The set is \(\Omega = \{1,2,3,4,5,6\}\). An example…
Probability Tidbits 3 - Pi Systems Suppose we have a set $S$, $I$ is a $\pi$-system on $S$ if $I$ is a set of subsets of $S$ satisfying: \(\begin{align} I \neq \emptyset \\ I_1, I_2 \in I \implies I_1 \cap I_2 \in I \end{align}\) or in other words, the subsets of $S$ in $I$ are closed under intersection. This simple system is visually intuitive; we can often work with just an underlying…
Probability Tidbits 2 - Measure Theory Given a set $X$, $\mathcal{A}$ is a $\sigma$-algebra on the set if: \[\begin{align} \emptyset, X \in \mathcal{A} \\ A \in \mathcal{A} \implies A^c \in \mathcal{A} \\ A_i \in \mathcal{A} \implies \bigcup_{i} A_i \in \mathcal{A} \end{align}\] where the union could be potentially countable. The combination of the set and its $\sigma$-algebra $(X, \mathcal{A})$…
Probability Tidbits 1 - Banach Tarski Not all sets are measurable. Within $[0,1]$ there exists unmeasurable sets. We’ll construct one here. First define an equivalence class $x \sim y \iff x - y \in \mathbb{Q}$. The set $[0,1]$ contains many such equivalence classes(which by definition are disjoint from each other). By axiom of choice, we can choose a representative from each equivalence class.…
WIP. The complex numbers are defined as \(\mathbb{C} = \{ a+bi : a, b \in \mathbb{R}\}\) . We look at some basic operations on the field and dive into differentiability. Basic Operations Consider two complex numbers $z = a + bi$ and $w = c + di$ in the following: The conjugation of a complex number \(z\) is defined as \(\bar{z} = a - bi\). This is an isomorphic map of \(\mathbb{C} \to…
This is a very informal set of notes that I’ll be maintaining while taking Terrence Tao’s complex analysis class. Fields, order, sequences $\mathbb{R}, \mathbb{C}$ are fields, which are sets equipped with addition and multiplication. In addition, they exhibit associativity, commutativity, identity, inverses for both addition and multiplication, as well as distributivity of multiplication over…
I interviewed for Google’s Tensorflow, Apple’s MLPT (Machine Learning Platform & Technology), Bytedance’s ad infrastructure, Databrick’s ML team, Citadel Securities as a quantitative research analyst, Hudson River Trading(HRT) as an algorithm engineer, and Jane Street’s research desk as SWE. I received offers from all of the companies except for Jane Street. Here’s my experience interviewing…
At my time at Airbnb, I’ve witnessed the development of the feature store effort on the machine learning infrastructure team. The project’s name is Zipline , and it has been presented at many conferences . As it’s one of the first open-sourced feature engineering platforms, I made sure to cover its implementation details in the query engine sections of the blog. The feature store problem is one of…
When you see the C++ standard’s specification on value categories , it’s likely your eyes gloss over and you think to yourself - “why do I ever need to know this?”. At least that’s what I thought when I first took a glance. Over the years, I’ve ran into issues assuming a simplistic model of value categories, and I regret not taking a long hard look at the standard in the beginning. This is my…
Table of Contents Table of Contents The Setup: Simplest C++ Program Structure of the Executable: ELF Format ELF Headers Program Headers PHDR INTERP LOAD DYNAMIC NOTE GNU_EH_FRAME GNU_STACK GNU_RELRO Recap What does g++ do? Preprocessor ( cpp ) Compiler ( cc1plus ) Front End Middle End Back End Assembler ( as ) Static Linker ( ld ) Disclaimer: Static linker and dynamic linkers are NOT the same…
Table of Contents Table of Contents My Arch Linux Setup Preliminary i3 Installing i3 i3 Container Manipulation i3 Workspaces i3blocks Setting Backgrounds Using a File Manager Reading PDF’s Spotify Program Launcher ( dmenu replacement) Terminal Emulator Solarized Colorscheme Aesthetics Login Manager My Arch Linux Setup I’ve set up my Arch Linux environment for over a year now and I haven’t made…
Apologies for the long delay in posts! I’ve been caught up with some busy work and only recently did I remember to revisit my blog. This time around we’ll be doing some reading for queueing theory , which is one of the most relevant mathematical fields for computer science. For the sake of this blog, I will not get into measure theoretic tools required to answer particularly complicated examples.…
Table of Contents Table of Contents What Do We Care About? Reliability Aside: Fault vs. Failure Aside: Types of Faults Scalability Aside: Statistical Analysis on Response Time Aside: How to Deal With Increasing Load Maintainability Aside: What Operation Teams Do Aside: How to KISS Aside: How to Evolve What Do We Care About? Reliability Definition : Working correctly under faults and errors. We…
Table of Contents Table of Contents Overview Cartesian Products Restricted listcomp List & Tuples & Generic Sequences Generator Expressions (genexp) tuple namedtuple Advanced Slicing Slice Assignment Add Delete No More Magic - Readable Slices Multi-Argument Slices - How? +, * Operators With Sequences Reference Issues with * __iadd__ and __imul__ With Immutable Objects Weirdest Corner Case bisect…
Table of Contents Table of Contents Recap Intuition Construction wip Recap Note: If you haven’t read part 1, this entire blog will make no sense to you. Last time, we set up the notion of Turing reducibility and oracle machines, and asked the question, does there exist recursive enumerable sets \(A,B\) such that \(A \not\leq_T B\) and \(B \not\leq_T A\)? , where \(\leq_T\) is Turing…
Table of Contents Table of Contents Recap Enumeration & Normal Form for Oracle Machines Why The Setup? Basic Construction Diagonalization However… Recap Quick recap : previously, we defined recursive enumerable (r.e.) sets, which are sets that are generated by a computable function. These sets encode a degree of complexity within them. Specifically, the membership \(x \in A \) is a semi-recursive…
Table of Contents Table of Contents Why You Care: $|P(\mathbb{N})| = \aleph_1$ Semirecursive Relations Recursive Sets Recursive Enumerable Sets Reductions and r.e. completeness Post’s Problem From the set of natural numbers, \(\mathbb{N}\), we can generate a lot of subsets \(S \subset \mathbb{N}\). In fact, the number of subsets we can have of \(\mathbb{N}\) is so large that it’s uncountable. This…
Table of Contents Table of Contents Recap of Ackermann and $\mu$-recursive Partial Algebras Expansion to Recursion Compilers Normal Form and Enumeration Theorem $S^m_n$ Theorem The Halting Problem Why Do You Care? Recap of Ackermann and $\mu$-recursive Recall that our previous result was that $A(n,x)$, the Ackermann function, is not primitive recursive, which means it’s not in $\mathcal{R}_p$, but…
I haven’t been writing blogposts as often as I’d like to, but mostly for the reason that I don’t have a lot of time to goof around. Now that I have some free time, Tiff reminded me that I should write something. I will write more about this subject when I have the chance. What is Computability Theory? Computability theory is a branch of mathematics that attempts to analyze and categorize problems…
Manufacturing Process of a CPU Silicon ingot is extracted to the purest form (any impurities will lead to a defect) Ingot is sliced up into wafers (thin disks) wafers are then etched and patterned with a layer of material above it for the circuitry of the chip The wafer is then sliced up into individual CPU dies Bond the die to the package, and ship to customers Usually, the yield of a…
Table of Contents Table of Contents Review of Monte Carlo Temporal Difference Prediction Similarity between TD and DP Similarity between TD and Monte Carlo Optimality of TD(0) On-policy: Sarsa Off-policy: Q-learning Example: Cliff Walking Sarsa Model Q-Learning Model Cliffwalking Maps Learning Curves Temporal difference learning is one of the most central concepts to reinforcement learning. It is…
Table of Contents Table of Contents Introduction Integer 8-bit quantization Details Bitwise quantization Training and Backpropagation of an XNORNet Difficulty of training an XNORNet Training Tips Approaches to Implement XNORNet Forward-inference Framework Linear Algebra Backend Python to C++ Transpiler Custom XNOR BLAS functionalities xnormatmul Floating point packing Vectorized xnors Accumulating…
Table of Contents Table of Contents Introduction First-visit Monte Carlo Monte Carlo Action Values Monte Carlo Control Exploring Starts On-Policy: $\epsilon$-Greedy Policies $\epsilon$-Greedy Convergence Off-policy: Importance Sampling Off-policy Notations Ordinary Importance Sampling Weighted Importance Sampling Incremental Implementation Extra: Discount-aware Importance Sampling Extra:…
Table of Contents Table of Contents Formalizations The Agent-Environment Interface Returns and Episodes Policies and Value Functions Iterative Policy Evaluation Proof of Convergence Policy Improvement Policy Iteration Value Iteration Proof of Convergence See it in action! Visual Results Conclusion Previously, we discussed $k$-armed bandits , and algorithms to find the optimal action-value function…
Table of Contents Table of Contents $k$-armed Bandit Problem Action-value Methods Estimating Action Values Action Selection Rule : Greedy Action Selection Rule : $\epsilon$-Greedy Crux: Nonstationary Action Value 1. Transience 2. Convergence Action Selection Rule: Optimistic Initial Values Action Selection Rule: Upper-Confidence-Bound Selection Gradient Bandit Algorithms Ending Remarks To begin,…
It’s been a while since I wrote anything to the blog , and it’s partially because life has been going real fast that I haven’t had time to really think about jotting down my thoughts. I’ve been chasing a pineapple-pizza-eating, hot-chocolate-drinking someone so that’s another excuse :-). Some habits die hard, and I always think about writing another blog, to learn something new and really remember…
Evaluation Strategy Table of Contents Evaluation Strategy Table of Contents Call By Value Call By Reference Call By Result Call By Value-Result Call By Name Call By Need Call By Value Copies the arguments into the callee. Pros: Immutability via copying. Cons: If values are large, slow copying. If we try to pass by address, leads to unreliable code. Call By Reference Passes arguments as references…
Memory Management And Garbage Collection Table of Contents Memory Management And Garbage Collection Table of Contents Heaps Example: First-fit Quick Lists Heap Links Heap Compaction Garbage Collection Mark-and-sweep GC Copying GC Reference Counting GC Going Meta: Generational GC Comprehensive comparison of GC’s: Heaps Many languages have unordered runtime memory allocation, and usually we hear…
What Are Continuations Table of Contents What Are Continuations Table of Contents What is a Continuation? Using Continuations as Currying Using Continuations as Returns Green Threads and Generators Continuations in scheme are quite tricky. Here we will try to delve deep into how they work. What is a Continuation? A continuation, is “just about to return from call-with-current-continuation”, and it…
Networking Refresher Table of Contents Networking Refresher Table of Contents TCP/IP Protocols HTTP(S) FTP SMTP UDP Protocols DNS P2P Basics Comparison of P2P & Client/Server TCP/IP Protocols HTTP(S) Format of web content Sends content to client without maintaining state information. Considered a “PULL” protocol. HTTP 1.0 is 1 TCP connection, setup/teardown, per object in web page. HTTP 1.1 is 1…
Table of Contents Table of Contents Waiting for an event/condition condition_variable and condition_variable_any Details of wait() An example of safe_queue Before, we talked about the basics of how C++ threads are used, and how threads can protect data by using mutex es, lock_guard s, unique_lock s, recursive_mutex , and once_flag s. Now, we talk about how threads can wait for other threads to…
Table of Contents Table of Contents Inherent Problems std::mutex Hide Your Shared Data from User Deadlock std::unique_lock std::call_once std::recursive_mutex is C++’s ReentrantLock Inherent Problems Every thread is considered a lightweight process . It has its own stack space, but will share heap space with other threads of the same process. When we’re sharing data, the issue arises when the data…
Table of Contents Table of Contents std::thread Syntax and Functions You must join or detach Don’t detach() While Using Locals Transfering ownership of threads std::thread Syntax and Functions #include <thread> #include <iostream> using namespace std ; void hello_world (){ cout << "hello world!" << endl ; } int main (){ thread t ( hello_world ); t . join (); assert ( t . joinable () == false );…
Before we start - why did C++ create templates? Templates were created because we needed containers that could safely contain a multitude of different objects. Now, we realize that templates are turing-complete, and that it can be used for a whole new type of programming called template meta-programming , which basically means a program that runs during compilation and finishes when compilation…
Before we start, here’s the code: Branch with Eigen backend Branch that only supports scalars I worked on this project with Minh Le . Why? You’ve probably heard this phrase “Don’t roll your own ___” thousands of times if you’re a CS major. It can be filled with crypto, standard library, parser, etc. I think nowadays, it should also contain ML library. Regardless of this fact, it’s still an amazing…
Table of Contents Table of Contents Public Inheritance is “is-a” Nitty Gritty: “is-a” is tricky Solution 1: Generalize base class to introduce granular relationships Solution 2: Throw exception Composition is “has-a” Avoid hiding inherited names Why does an error occur? Don’t we want to inherit the overloaded functions? How do we fix it? Differentiate inheritance of interface/implementation…
Table of Contents Table of Contents Postpone Variable Definitions Within Loops Minimize Casting You think you need cast, but you don’t Casts are slow Avoid returning handles Accidentally expose non-constness Strive for exception-safe throw(...) vs noexcept throw() noexcept Which one to choose? What can throw? A strategy for strong exception guarantee - Copy & Swap Inlining Misconception: Inline…
Table of Contents Table of Contents Easy Correct, Hard Incorrect Make Errors Occur Early & Obviously Restrict User Input Space Class Design is Type Design ALWAYS Prefer pass-by- const& to pass-by-value Inefficiency Subtle Incorrectness DON’T Force const& when should return-by-value Try 1 - Stack references Try 2 - Heap references Try 3 - Static references private your Data Members Consistency…
Table of Contents Table of Contents Rvalue and Lvalue Simplified definition: References Small (Confusing) Exception Functions Can Yield Lvalues Rvalue References Small Aside: function overloading ambiguity Move Semantics std::move So what can you std::move efficiently? Rvalue and Lvalue Simplified definition: lvalue - An object that occupies some address in memory. most things are lvalues. int i =…
Table of Contents Table of Contents Use Objects for Resources How To Screw Up How To Unscrew Yourself Decide How to Implement Copy The silent-killer-copy The shared-refcount-copy The unique-move-copy The weak-copy Raw Resource Interface in RAII Explicit Conversion Solution Implicit Conversion Solution Use new / delete or new[] / delete[] Don’t Typedef Arrays/Pointers To Arrays! Dedicate Whole…
Table of Contents Table of Contents Default Implementations Limitations Disallow Unnecessary Functions Uncopyable Uninitializable (Singleton) Declare Destructors virtual in Base Class Common screw-up Aside: public/protected/private inheritance How to Handle Exceptions in Destructor Don’t Call virtual Functions in Constructors/Destructors A Meh Workaround Assignment Operators return *this Handle…
Table of Contents Table of Contents Enums, Consts, Inlines & Macros Pros and Cons Macros Consts Enums Use Const ’s Often const Variables C-Style C++97+ Style Example const Functions Physical/Bitwise const vs. Logical const Initialize Before You Use Initialization vs. Assignments Issue with static & Singleton Design Enums, Consts, Inlines & Macros Pros and Cons Macros (e.g. #define C 1.5 ) pro :…
But for reals I genuinely believe that millions of hours are wasted every year because people don’t read the documentation. Actually - noone reads the documentation, that’s why StackOverflow has billions of page views! If people read the manual, and found an undocumented bug, then sure. But the truth is, people ask questions without googling/man-paging them. I’m a culprit too - I wasted so many…
Previously… Previously, we have defined the notion of a hypothesis set . We also introduced a bound that explains how far the risk of a specific hypothesis in $\mathcal{H}$ is to the optimal hypothesis $f^*$ in $\mathcal{H}$. It explains the bias variance tradeoff by illustrating that: As the complexity of the model class increases, a specific hypothesis in $\mathcal{H}$ could have much worse risk…
Preface If you haven’t seen the previous blog, or not familiar with Hoeffding bounds, I suggest you read about it. This blog goes head first into the continuation of the previous blog here . What is a hypothesis? A hypothesis, can be thought of as a function . However, it’s not necessary. A function maps something to something else, like $f: \Re^n \to \Re$. For every input in the domain, we know…
Why This? I’ve been meaning to get to this topic for a long time. I didn’t really have a strong grasp on the learning theory portion of machine learning, except for the basics taught in CS260. Going through all of this really opened my eyes up to the history of machine learning, and most importantly, why machine learning works . When I was just a practitioner, trying out algorithms and seeing…
Why Docker? Docker is a great containerization technology for running your applications in a stateless manner. This way, all builds have similar behavior. All you need to do is spin up a docker container that runs ubuntu and you’re good to go. There’s no source of confusion by running docker because there’s no uncertainty to whether your system’s architecture or configurations is causing some bug.…