<!--
Abstract:

CS 461
Introduction to Deep Learning
Lecture 01: Introduction
-->

# CS 461 - Lecture 01

## Machine Learning Principles

Bernhard Firner

2025-09-08

---

## Contact Information

* My email: `bfirner@cs.rutgers.edu`
* Office: Hill 273
* Office hours: TBD

---

## Canvas

* There is a link to the syllabus on canvas
* I will also upload lecture material to my website, with links on canvas
  * If canvas goes down, it doesn't affect the website
* ProTip: If canvas goes down, everyone emails me
  * Please assume that I'm already aware

---

## Piazza

* Piazza is available through canvas
  * This is where I would prefer for you to ask question
  * Everyone gets to see the answer, and I don't have to answer the same question ten times
* Piazza also remains up if canvas goes down

---

## Syllabus: Book

* Probabilistic Machine Learning: An Introduction by Kevin P. Murphy
  * [probml.github.io/book1](https://probml.github.io/pml-book/book1.html)
* We will stay close to the text so that you have an easy reference
* We will also cover a few readable and interesting academic papers

---

## Syllabus: Tools

* Python, SciPy, and PyTorch
  * [https://pytorch.org/get-started/locally/](https://pytorch.org/get-started/locally/)
  * [https://scipy.org](https://scipy.org)
  * [https://docs.pytorch.org/docs/stable/index.html](https://docs.pytorch.org/docs/stable/index.html)

---

## Resources

* All examples will run on iLab machines (on CPU, but could be slow)
  * [https://resources.cs.rutgers.edu/docs/instructional-lab/](https://resources.cs.rutgers.edu/docs/instructional-lab/)
  * [https://resources.cs.rutgers.edu/docs/using-python-on-cs-linux-machines/](https://resources.cs.rutgers.edu/docs/using-python-on-cs-linux-machines/)
* Slurm will allow GPU access
  * [https://resources.cs.rutgers.edu/docs/scheduler-for-gpu-jobs/](https://resources.cs.rutgers.edu/docs/scheduler-for-gpu-jobs/)
  * [https://resources.cs.rutgers.edu/docs/limitation-enforced-on-cs-linux-machines/](https://resources.cs.rutgers.edu/docs/limitation-enforced-on-cs-linux-machines/)

---

## Structure

* Lectures
  * Introductions to concepts
  * Mostly theoretical
* Recitations
  * Will usually go over example code and sample questions
  * Short quizzes and practice work to keep you honest with yourself

---

## Syllabus: Grading

* 25% Final
* 15% Midterm
* Recitation Work
  * 15% Recitation Quizzes
  * 10% In-recitation Assignments
* 35% Homeworks/Projects

---

## Academic Integrity

* [CS Academic Integrity Policy](https://www.cs.rutgers.edu/academics/undergraduate/academic-integrity-policy)
* Academic Integrity applies to both exams and assignments
* Violating the integrity policy negatively impacts your classmates, and current and future Rutgers students
  * Enforcement will be strict

---

## Assistance on Assignments

* Your work must be your own
  * But you may ask for advice from other students, on canvas, in recitation and in office hours
    * And you can use online material, including LLMs, to clarify any confusion
* Afraid of being punished just because you looked something up?
  * Don't be!

---

## Documenting Work

* Note any assistance in a comment at the top of the file
* If you use an LLM, you must provide a link to the LLM session
  * If you note *no* references, but two students hand in very similar work, I will assume ill-intent
* Plagiarism is different from cases where you arrive at similar solutions because of similar LLM or other references, so just note your source

---

## Absences & Late assignments

* Use the self-reporting tool
  * [https://sims.rutgers.edu/ssra/](https://sims.rutgers.edu/ssra/)
* Late assignments
  * 10% per day, down to 50%
  * Accept assignments up to 7 days late
  * Exceptions for major illnesses
* Missed exams
  * You must have a valid excuse to schedule a make up exam

---

## Exceptions

* Inform me ahead of time of special circumstances
  * Meaning non-emergency situations
* If you have an emergency, please don't stop to email me
  * You can self-report after the fact

---

## Exam and Quiz Absences

* Makeups involve writing new examinations
* I have many students across multiple classes, so you don't get personalized exams and schedules
  * You must have a valid excuse to schedule a make up exam
  * If a makeup cannot be scheduled within an academic week, we may switch to an oral evaluation
* **I will never give an online exam**

---

## Appropriate Conversations

* I can help with problems related to this class
* Can probably help with professional questions
* I'm not a psychologist. I probably can't help with other issues.
  * I am also required to report some topics, so don't assume everything you tell me will remain private

---

## Material

* CS440 is AI
* CS461 is ML, a subset of AI
* CS462 is DL, a subset of ML

---

## Machine Learning

* Important distinctions from other approaches
  * Data-driven
  * Make assumptions about statistics of data
    * About noise, bias, and measurement errors
  * Techniques are formulaic

---

## Isn't Everything DNNs?

* Deep learning (and LLMs) are big, but they are not everything
* Here's something recent from operations research:
  * [Designing Layouts for Sequential Experiences: Application to Cultural Institutions](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2022.02024)

<div class="col">
<img style="width: 50%" class="r-stretch" src="./pictures/AouadEtAl_Fig4.png" />
<p style='font-size:13pt'>See Aouad et al. Figure 4</p>

</div>

---

## Why Not Deep Learning?

* Why do we want to learn non-deep learning approaches?
* Machine learning involves matching a *model* to observed data
* Every model works with different assumptions, called its *inductive bias*
  * An inductive bias could be as simple as an assumption about the shape made when samples are plotted

---

## Models and Bias

* There is no "best" model for every task
  * This is called the *no free lunch* theorem
* It means that we need to learn a lot of models in this class
  * Different models are suitable to different problems
  * An expert in ML will choose good models
  * The novice always uses the same tool with mediocre results

---

## Background Material

* ML requires a lot
  * Probability
  * Linear Algebra
  * Calculus
  * Information Theory
  * Algorithms

---

## Course Outline

* Begin with fundamental concepts
* Then jump to chapter 9 of Murphy's *Probabilistic Machine Learning*
  * The earlier parts of the book are reference (but we will review)
* Parametric models
  * Including probability models, regression models, and some light coverage of Neural Networks
* Non-parametric models
  * Including exemplar methods, kernel methods (SVMs), trees and ensembles, and clustering

---

## Types of Data

* Numbers: continuous numeric values are the simplest form of data
* Tabular: meaning that labels are not continuous numeric values
* Vectors and matrices: these may end up being more complicated than lone values
  * Correlation between elements can make some models inefficient
  * Structure between elements is better captured by some models
* Graphs: graphs can have arbitrary edges, making them complicated

---

## Types of Predictions

* Regression
  * This means trying to predict numbers or groups of numbers
  * Predicting the temperature tomorrow is an example
* Classification
  * Trying to predict the likelihood of different observations
  * Word probabilities is an example

---

## Types of Models

* There are a few ways to divide ML models 
  * Parametric Vs Non-parametric
  * Generative Vs Discriminative
* And when estimating with probabilities
  * MLE Vs MAP
* We will eventually cover the differences

---

## Parametric Models

* As the name implies, these models require parameters
* Let's say we want to estimate a line:
  * $y = mx + b$
  * $y$ is being predicted by our model
  * The parameters are $m$ and $b$
* We will use $\theta$ to represent all of a model's parameters

---

## Non-Parametric Models

* How can we have a model without parameters?
* What if we just use a few examples of different objects
  * If we want to classify something new, we just compare to what we have
  * There will be a metric involved, but no parameters
* An example of this approach is the *K-Nearest Neighbors* algorithm

---

## Probability

* We can't talk about ML without talking probabilities
* Probability is the foundation of machine learning
  * And this will also be our first topic
* First we need to agree on some notation
* This is a good moment to warn you that we'll be using lots of notation

---

## Notation

* $Y$ is the thing we want to predict
  * $Y$ is every example, $y$ is a particular one
* $X$ is the information we use
  * Again, $X$ is every example, $x$ is a particular one
* For now, think of $x_i$ as example number i
  * It could be a single value, multiple values, etc

---

## Models and Parameters

* Our model is a function
* Given x, it predicts y
  * y could be a class, a number, an image, a sentence, etc
* The thing we use to predict is the model
  * $m(x_i) = \hat{y}_i$
  * The hat over $y$ means that it is an estimate

---

## Model Parameters

* Our model is generally dependent upon its parameters
* This leads to the book's notation where the model is referred to as $\hat{\theta}$
* Why is that an estimate?
  * $\theta$ would be the "correct" parameters, based upon all possible X and Y
  * In ML, we only see a subset of data, $\mathcal{D}$
    * So we can only estimate the correct parameters

---

## Probability Review

* $P(A)$ is the probability of A
* $P(A,B)$ is the probability of both A and B
  * If A and B are independent, then $P(A,B) = P(A)P(B)$

---

## Conditional Probability

* $P(B|A)$ is the probability of B given that A is observed
  * $P(B|A) \triangleq \frac{P(A,B)}{P(A)}$
  * $\triangleq$ means equivalence

---

## Conditional Probability

* Consider throwing a dart onto this picture
* If you hit B, what is the probability that A is also hit?
  * $P(B)$ is the fraction of space filled by B

---

## Predictions

* This will lead into our first ML approach
  * Use probability to predict a class or value
* This sounds simple, and it is in comparison to some other ML
* Also gives us the chance to analyze some important qualities
  * So we will stick with probability for a few lectures

---

## Classification Formula

* $p(y = c | x, \theta)$
  * This is the probability that the class is $c$, given observation $x$ and learned parameters $\theta$
* Not rocket science
* We are going to observe a dataset, $\mathcal{D}$
  * From that, we will estimates values in $\theta$

---

## Example

* Let's make this concrete
* We are observing coin flips and want to predict the next flip
  * That implies a Bernoulli random variable
  * $\theta$ will estimate the Bernoulli's statistics
* In this case, $\theta$ could just be the probability of observing heads or tails

---

## Expanded

* Let's expand that equation:
  * $p(y = c | x, \theta) = \frac{p(x|y = c,\theta)p(y=c|\theta)}{\sum\limits_{c'}p(x|y=c',\theta)p(y=c'|\theta)}$
* This is hopefully familiar as Bayes' rule (sec. 2.3 in the book)
  * We want $P(y=c|x)$, and our observations gave us $P(y=c)$ and $P(x|y=c)$

---

## Larger Example

* Let's say that you are working somewhere with a cafeteria
* You've observed that the availability of fries decreases over time
  * p=1.0 at 11AM, p=0.75 at noon, and p=0.25 by 1PM
* If you arrive at the cafeteria and they have fries, what time is it?

---

## $\mathcal{D}$

* $\mathcal{D}$ is our observations, giving:
  * 11AM: fries observed 100 of 100 days
  * 12PM: fries observed 75 of 100 days
  * 1PM: fries observed 25 of 100 days
  * In total, fries are observed in 200 of 300 observations
    * Notice that observations may not be independent, but it is okay
* We want to turn that into $P(\text{time}|\text{fries})$

---

## Bernoulli RV

* The observation has two possible outcomes
  * $p(Y=1) = \theta$
  * $p(Y=0) = 1 - \theta$
* Hopefully you recognize this as a Bernoulli random variable

---

## MLE for Bernoulli

* Observe fries/no fries over many days to get $\mathcal{D}$
* Now we need to solve for the *maximum likelihood estimate* (MLE) of $\theta$
* Find a $\hat\theta$ that maximizes the observations
* For 11AM, fries are observed 100 of 100 days
  * Obviously $\theta = 1$

---

## MLE for Bernoulli

* How about for 12PM, where fires are observed 75 of 100 days?
  * Yes, you can guess 0.75
  * But we are going to need the actual formula later
* The probability of our observations is
  * $p(\mathcal{D}_{12PM}) = \binom{100}{75}\prod\limits_1^{100}\theta^{y_n=1}(1 - \theta)^{y_n=0}$
  * Or $p(\mathcal{D}) = \binom{100}{75}\theta^{75}(1 - \theta)^{25}$

---

## Solving MLE

* Here's the graph of likelihood for different values of $\theta$
  * See 4.2.3 in the book if this loses you

---

## Solving MLE

* We are comparing different values of $\theta$
  * We can remove the constant $\binom{100}{75}$
* How should we solve?

---

## Solving MLE

* Just convert into the negative log likelihood
  * From here, we can take the derivative and solve for 0

---

## Log Likelihoods

* ML algorithms like to work in log space for two reasons
* First, division turns to subtraction, which is more mathematically stable
* Second, many optimization algorithms minimize some function
  * A log converts the probability range from 0 to 1 into $-\infty$ to 0
  * Multiply by -1, and now 0 probability has an error of $\infty$
  * This is called the *negative log likelihood*, or NLL

---

## Solving

* $\frac{\delta}{\delta\theta}NLL(\theta) \propto \frac{-75}{\theta} + \frac{25}{1 - \theta}$
* Solve for $0 = \frac{-75}{\theta} + \frac{25}{1 - \theta}$

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"><mn>25</mn><mi>θ</mi></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mn>75</mn><mrow><mo stretchy="true" form="prefix">(</mo><mn>1</mn><mo>−</mo><mi>θ</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mi>θ</mi></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>75</mn><mn>25</mn></mfrac><mrow><mo stretchy="true" form="prefix">(</mo><mn>1</mn><mo>−</mo><mi>θ</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mi>θ</mi><mo>+</mo><mi>θ</mi><mfrac><mn>75</mn><mn>25</mn></mfrac></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>75</mn><mn>25</mn></mfrac></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mi>θ</mi><mrow><mo stretchy="true" form="prefix">(</mo><mn>1</mn><mo>+</mo><mfrac><mn>75</mn><mn>25</mn></mfrac><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>75</mn><mn>25</mn></mfrac></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mi>θ</mi></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>75</mn><mrow><mn>25</mn><mrow><mo stretchy="true" form="prefix">(</mo><mn>1</mn><mo>+</mo><mfrac><mn>75</mn><mn>25</mn></mfrac><mo stretchy="true" form="postfix">)</mo></mrow></mrow></mfrac></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><mi>θ</mi></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><mfrac><mn>75</mn><mrow><mn>25</mn><mo>+</mo><mn>75</mn></mrow></mfrac></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
25\theta &= 75(1 - \theta) \\
\theta &= \frac{75}{25}(1 - \theta) \\
\theta + \theta\frac{75}{25} &= \frac{75}{25} \\
\theta(1 + \frac{75}{25}) &= \frac{75}{25} \\
\theta &= \frac{75}{25(1 + \frac{75}{25})} \\
\theta &= \frac{75}{25 + 75}
\end{align*}</annotation></semantics></math></p>

---

## Generally

* The general solution, given counts of outcome 0 and 1, is:
  * $\hat{\theta}_{mle} = \frac{N_1}{N_0 + N_1}$
* That is the *most likely estimate* of $\theta$
* For the fries examples, we will estimate 1.0, 0.75, and 0.25
  * If we see fries we guess 11AM, otherwise guess 1PM

---

## A Note on Math

* In general, I won't expect you guys to derive anything complicated in an exam
* However, if you have an equation I will expect you to know how to use it
* You will have chances to practice more in recitations

---

## Applying Bayes

* $p(y = c | x, \theta) = \frac{p(x|y = c,\theta)p(y=c|\theta)}{\sum\limits_{c'}p(x|y=c',\theta)p(y=c'|\theta)}$

* Bayes rule is generally intuitive from a graphical point of view
* Divide $P(\text{fries}|\text{time})$ by $P(\text{fries})$
  * Then multiply by $P(\text{time})$
    * If you forget that, the probabilities will sum > 1

</div>
<div class="col" style="text-align: center;">
<img style="width: 40%" class="r-stretch" src="./figures/bayes_diagram.svg" />

</div>
</div>

---

## Complicated $\mathcal{D}$

* What if we have more columns in $\mathcal{D}$?
  * Perhaps we have observed both fries and ice cream
* Just replace $p(x|y = c,\theta) = \prod\limits_{d=1}^{D}p(x_d|y=c,\theta)$
  * Each $d=1$ is fries and $d=2$ is ice cream
* Sounds good?

---

## Independence

* If you remember your course in probability, you are slamming your foot on the brake
  * "We can't multiply probabilities unless they are independent!" you say
  * Observation are unlikely to be independent
* Sure. But let's assume that they are independent anyway.
* This is the *Naive Bayes* classifier
  * Justification? It works well, usually.

---

## Naive Bayes

* See section 9.3 of the book
* The classifier is not *correct*, but experience shows it works well
  * Approximation and experience are at the heart of machine learning
* We will look at a more complete example next lecture

---

## ML Details

* We are doing ML, not probability
* So what does that mean?
  * Algorithms need to run on computers
  * Expect to see approximations and simplifications

---

## Good?

* Naive Bayes can work surprisingly well
  * For spam email detection, for example
  * Compared to other approaches, this is also lightning fast
* And because this is probability, we can do clever things with priors
  * This is important, and we'll go over it in detail next time

---

## Distributions

* We can use Naive Bayes for any distribution
* Although we will generally stick to either Bernoulli or Gaussian
* We can also mix the two together
  * E.g., whether or not fries or ice cream are present (Bernoulli), and the number of people already sitting down (Gaussian)

---

## MNIST Digits

* As a preview, we'll apply Naive Bayes on the MNIST digits dataset
* The dataset is filled with 60000 handwritten digits from 0 to 9

---

## Naive Bayes Results

* Teaser: Classification accuracy of 84.27%
* Here are the feature densities per class
  * Each pixel is a feature

---

## For Next Class

* Get the book
  * Digital or physical
* It is terse, but very complete
* Lots of examples available in notebooks on github
* Always be ready for a bit of math
  * But remember, learn the concept, don't memorize a formula

---

## Reading

* We are going to cover some statistics
* If this seems unfamiliar, read ahead
  * 4.2.3-4.2.4 MLE for Bernoulli and categorical distributions
  * 4.5.1-4.5.2 MAP estimation for Bernoulli and Guassians
  * 4.6.2.1-4.6.2.10 Bayesian Statistics, Bernoulli Likelihood, priors

---

## Recitation Reminder

* Next Tuesday is a Monday schedule
  * So we miss the recitation next week
* The first recitation will be two Tuesdays from now