23 Neural Nets and Decision Trees

Today we are going to review neural nets

z_i ^(k) = g(sigma_j W_i,j )

g = nonlinear activqation funciton

why does nonlinear matter in this case? we could have done just linear mappings, but that ends up looking like is just a bunch of matrix multiplication

the nonlinearity part allows us to be more expressive with the data which allows us to do more than a single linear mapping

this last layer Z_n is just a set of learned features, if you ignore everything prior, which is just our set of learned features, which we learned by doing this transformation or linear mapping, adn you got these features at the end of it. You end up doing logisital regression, and push it through a softmax to get the probabilities at the end.

for certain complex datastructures, its difficult to write down, like what is the featureset.

we are just doing it in a bit more complicated way.

this specific architecture is a deep neural net with connected layers; every node in one layer connects to every node in the next layer.

when you hear about different architectures, we are thinking about different ways to connect the nodes in oreder to best suit the data we are working iwht

Training the deep neural network is just like logistic regression

max_w ll(w) = max_w sigma_i log(P(y^i|x^i; w))

just w tends to be a much, much larger vector

-> just run gradient ascent + stop when log likelihood of hold-out data starts to decrease

you dont want to use the same data you used for gradient descent

Ultimately, this should give you the weights you can plug into the function above.

as you continue fitting your data, ur log likelyhood will stop increasing

Sometimes it means you're at the maximum, but you could possibly be at a local peak, not the global peak.

doing this optimization for neural nets can be hard. for now for the purposes of this class, its okay

another kinda property of these NN, is the universal approximator theorem, a large network with a large number of neurons can approximate any continuous function to any accuracy

• practical considerations
  • can be seen as learning the features
  • hard to interpret
  • large number of neurons
    • danger of overfitting
    • (hence early stopping)

turn that into a pro con table

We would love it if each neuron could tell us something. etc.

the idea being that if these neurons can give us some information on how it came to the final classification

these neurons end up being a mix of all of the singlas in our data. thats something that is verty active, and figure out how to make these models more interpretable.

another consideration is that these models are really big and because they are really big theyy tend to overfit. there are a couple ways we try to prevent this, bearly stopping where you stop traingn when it stops improving.

and another thing, big means you need a lot of data, so there are a lof of considerations we need to take into account. IN real settings, realapplications

one application has ebee computer. ision. but insluce wy have other types of imager. Maybe trying to detect an object, etc.

if we are trying to do object detection, we want to determane some stuff

manual feature design

you basically run some edge detection algo, to turn an algo into an image, and identify and go from that Example of a HOG image. Pre neural networks, pre imagenet, this what people would do to represenent the features, and run it on a logisitic reg modlle, and they didnt get too far.

the task is object detection. what people do in ml and ai is to create a benchmark dataset. then they compare to other models and methods to test every model on the same data, same task, etc. They created this dataset, which is i called imagenet. Millions of images off the internet which is classify. And they basically pulled over 100m candndiadate image. had them do it over the labels multiple times. once this was created, tis took a lot of time, and a great feat, of this

the reasons a lof of models have survived, etc. there no reason is there?

the main researchers stanford did fei fei lee

now that we have imagenet. Now that everyone is doing the same task at the same time. Before things were leveling off, where we only made some improvement, but now that we have AlexNet by jefferey hitono. created this model adn the erroror rate is signifificanyl move improved.

Another task that people have don in this space is MS COCO (COMMON OBJECTS IN CONTEXT)

its a bit harder in context, where there is not just "cat" and "bird" but "girl in pink dress jumping in air"

again we see that neural nets work the best.

another challege is Visual QA challenge where the input is an image and a question. The model needs to output an asnwer "what uniform is she wearing?" answer: "girl scouts"

and so essentially we see the same thing happen in speech recognition. and you want to output text and we see this steep decline in the error rate since deep learning was produced.

this picture, this infographic for googles machine translation projduct. We want to learn one language, and the input was chainese, and the output was christions. the is one turns each of th einput vectors. We have a set of weights, inout weights, and the director turnes one of those vecors into one of them in the dat. we wont talk about transfomrers today, when we think about mor emodern systems. etc. but todya we are going to talk about decision trees

when you should use a neural net.

• when youre working ith data types where theyre' known or likely to preform well
  • images and text are cononical examples
  • genereally: complex data where its hard to pre-specify features that will do well
  • not simple tabular datasets where few simple features suffice
  • not tiny datasets
• you're willing to safrifice interpretability for performatince
• you can won or can rent to requisite hardware
• these properties often hold and nns are very widely used today.

INductive learning (science)

• simplest formL learn a fuction from examples

  • A target fucntion: g
  • examples; input output pairs
  • eg x in an email and g(x) is spam/ham
  • eg x is a house and g(x) is its selling rpice

• problem

• curve fitting,(regression, function approximation)

  • Why not make h as huge as possible, so g is guaranteed to be inside?
  • we need to weigh between bias and variance
  • we call this tradeoff consistency vs simplicity
• for a linear regression, a line doesn't go through all the points
  • but maybe it generalizes better
• quadratic model is better
• cubic one overfits too much and doesn't fit the training data better.

A rule of thumb is that if there are two models and they fit equally well, use the simpler one. Ockhams razor

algorithms by default already prefer a consistent model

• fundamental tradeoff: bias vs variance
• usually algorithms perfer consisitency
• several ways to operationalize simplicity
  • reduce hypothesis space
    • assume more: independence assumptions, as in naieve bayes
    • have fewer, ebtter features, attributeies: feature selection
    • other structureal limiations (Descision lists vs trees)
  • regularization
    • smoothing: cautious use of small counts
    • many other generalization params(pruning cutoffs today)
    • hypothesis stays big but harder to get to the outskirs

Decision Trees

think of them as another classificationa lgo

we are literally just doing the same thing, trying to classify data this is just another way of doing that which is kinda fun

Reminder: Features

• features: aka attributies

  • sometimes type=french
  • sometimes f_type=French(X) = 1

• compact representation of a function

  • truth table
  • conditional probabilty rule
  • regression values
• true function shown at the right
  • realizable: yes it is in H

sitting down at a restaurant as a decision tree

Patrons? None, Some FULL Full-> waitEstimate? >60, 30-60, 10-30, now etc...

make a full tree, as ascii

can express any function of the features.

A	B	A xor B
F	F	F
F	T	T
T	F	T
T	T	F

draw this decision tree, as ASCII. How does this relate to perceptrons? We took a linear combination of some features, so the perceptron cannot encode any sort of interaction between features

if i want to say, i'll wait longer if its french vs an italian restaurant> cant do that in a perceptron unless i add another singlular joint feature for interations between features.

in the DT each of the steps is based on the previous ones, and we go back and woah,. how do we make that tree a bit more direct to avoid overfitting?

this main idea is that with a perceptron algo, it was less flexible and the decision trees were able to learn non-linear features of all interaction

in this case the DT are more similar to neural nets in terms of performance.

all of this is different ways to lok at our data

Hypothesis spaces

• how many distinct trees with n boolean attributes?
• we can get the total number of decision trees that can be coded across all attributes
• a dt can encode any function over those n attributes
• We can start by computing the number of distinct combinations of input attributes.
  • if all booleans and n attributes: 2^n possible attribute combinations
  • we have to make this binary choice, 2^n times, so our total number of possible trees is 2^(2^n)
  • eg with 6 boolean attributes there are 18466744073709551616 possible trees
  • yeouch
• how many trees of depth 1 (decision stumps)
  • number of boolean function over 1 attribute
  • number of truth tables with 2 rows, times n
  • 4n
    • with 6 boolean attrs, there are 24 decision stumps
• more expressive hypothesis space
  • increases chance that targe funciton can be expressed (good)
  • increases the number of hypoethese consisten wih the training set (bad, why?)
  • means we can get better preditiocns (lower bias)

Whats the learning algo for a decision tree. the goal is to find a small enough tree that is consistent with the training data, by learning the row etc. idea: recursively choose "most significant" attribute as root of the subtree

finish this pseudocode

function DTL(examples, attributes, default) returns a decision tree
    if examples is empty then return refault
    else if all examples have the same classification, then return the classification
    else if attributes is empty then return Mode(examples)
    else
        best <- Choose_Attribute(attribute, example)
        ...

the whole point is to pcik a good attribute or feature to split on

mos of the are considered positive, where we have a very clean and even split

so we want to chose one that is the best among all possibkle splits

if we split on patron, then we have a class, that gets us a sub dataset that one is all negative, one is positive, and one is kinda mixed, but we can evaluate a classitication on both of those other branches

lets find a measure to figure out how good our split is. which one gave us more information on how to classify our samples

from there we do our process again

how do we classify this?

we need a way of determining which split is better

we need some numerical meausre, so we can classify which split is better than another split

we have this concept of entropy and information gain, is inoortation, oog of math and comuer scinec

the ideas is in principle, the more uncertain you areoe about a question, the more information you stand to gain by asking it.

• information answers questions
  • scale: bits
    • answer to boolean question with prior <1/2, 1/2>
    • answer to 4 way boolean question with prior <1/4, 1/4, 1/4, 1/4>
    • anseer to 4 way wyestion with prior <0, 0, 0, 1>
    • answer to 3 way question with prior <1/2, 1/4, 1/4>
• more generally:
  • optimal: use a code of length log 1/p for events tha occur with proability p (not obvious this should be true, but follows the same logic)

Entropy

• Eneral Answer: if prior is
  • information is the expected code length
    • H( ) = E_p log_2 (1/p_i)
    • =sigma_i=1^n = p_i log_2(p_i)

how do we apply that to our decision trees? we have to compare the entropy between our things - difference is the highest information gain

Splitting on Patrons

None	NN
Some	YYYY
Full	YYNNNN

compute the entropy

Cuisine

french	YN
italian	YYNN
Thai	YN
Burger	YYNN

this is a very reasonable tree its kinda wrong in some place because these 12 examples dont rly pull down a possible function g what we have been trying to ge. the point of this could be wrong and we want to try to how long this tree this tree generalizes better than people who have never treated this tree before. we are trying to predict a cars mpg where the hp of the car has the wiehg model and year.

that like a typical classic case of overfitting

what would the first split be? on all of our attrs? we can compute the informaiton gain on each attr? based on the information game, the feature we mgiht choose to do this might be cylinders. thats our first split. we get a D1 tree split on cylinders. and choose the besxt attr that might move on that set adta

we have the next example, where we have each cylinder