[SER222] Empirical Analysis (1/8): The Empirical Process

Summary

Este video ofrece una visión general del proceso para construir empíricamente la función de crecimiento de un algoritmo. Se explican los pasos clave: establecer una serie de pruebas con diferentes entradas, medir el tiempo de ejecución, realizar un análisis de regresión para construir un modelo matemático y, finalmente, validar la precisión del modelo con nuevos datos. Se destacan las ventajas y desventajas de este enfoque, incluyendo su independencia de la implementación y la rapidez del proceso, pero también su inexactitud y dependencia del entorno de evaluación.

Takeaways

• 🔍 La meta es analizar un algoritmo como un 'caja negra' observando su comportamiento con diferentes entradas.
• 📊 Para construir una función de crecimiento empírica, se requiere de un conjunto de pruebas con diferentes entradas y sus tamaños asociados.
• ⏱ Se debe medir el tiempo que toma el algoritmo para procesar cada entrada y crear un mapa de tamaño de problema a tiempo de ejecución.
• 📈 Se utiliza análisis de regresión para construir un modelo que relacione el tamaño de entrada con el tiempo de ejecución.
• 🔍 Se busca un modelo empírico que sea una aproximación de la función de crecimiento del algoritmo.
• 🔄 Es necesario validar el modelo con entradas de tamaño no utilizados en la creación del modelo para asegurar su precisión.
• 🔄 Si el modelo no es preciso, se debe regresar a la fase de benchmarking y ajustar el conjunto de pruebas.
• 🌐 La ventaja del enfoque empírico es que no se requiere el código fuente del algoritmo, lo cual es útil para bibliotecas de terceros.
• ⏱ Este método es más rápido que el análisis analítico, ya que no se examina cada línea de código.
• ⚠️ Los desafíos incluyen la inexactitud inherente al modelo, la posibilidad de no capturar casos extremos y la dependencia del entorno de evaluación.
• 🔄 El proceso iterativo de prueba, modelado y validación es similar al método científico de hipótesis y verificación.

Q & A

¿Cuál es el objetivo principal de analizar un algoritmo como si fuera una caja negra?

El objetivo principal es observar cómo actúa el algoritmo con diferentes entradas para modelar o predecir su comportamiento en función del tamaño de las entradas.

¿Qué significa el enfoque empírico para el análisis de un algoritmo?

El enfoque empírico implica realizar pruebas observacionales para modelar el comportamiento del algoritmo basándose en los datos obtenidos, sin necesidad de analizar el código fuente.

¿Cómo se inicia el proceso de análisis empírico de un algoritmo?

Se inicia definiendo un conjunto de entradas diferentes, ejecutando el algoritmo con esas entradas y midiendo el tiempo que toma cada ejecución.

¿Por qué es importante asociar un tamaño de entrada a cada prueba realizada?

Es necesario para crear un mapa del tamaño de la entrada al tiempo de ejecución, lo cual es esencial para construir una función de crecimiento empírica.

¿Qué es la análisis de regresión y cómo se relaciona con el análisis de un algoritmo?

El análisis de regresión es una técnica estadística utilizada para construir un modelo que predice el tiempo de ejecución del algoritmo a partir del tamaño de la entrada.

¿Qué es una función de crecimiento empírica y cómo se obtiene?

Una función de crecimiento empírica es un modelo matemático aproximado que relaciona el tamaño de la entrada con el tiempo de ejecución del algoritmo, obtenida a partir de los datos de pruebas.

¿Por qué es necesario probar el modelo con un tamaño de entrada que no se haya utilizado en la creación del modelo?

Es necesario para evaluar la precisión del modelo y asegurarse de que pueda predecir adecuadamente el tiempo de ejecución para nuevos tamaños de entrada.

¿Cuáles son las ventajas de utilizar el enfoque empírico para analizar un algoritmo?

Las ventajas incluyen no necesitar el código fuente, ser más rápido que el análisis analítico y ser útil para bibliotecas de terceros sin acceso al código fuente.

¿Cuáles son las desventajas del enfoque empírico en el análisis de algoritmos?

Las desventajas incluyen la imprecisión de las predicciones, la dependencia del entorno de evaluación y la posibilidad de no capturar todos los comportamientos del algoritmo debido a casos extremos no probados.

¿Cómo se relaciona el proceso de análisis empírico con el método científico?

El proceso de análisis empírico sigue el método científico al hacer predicciones basadas en pruebas, evaluar esas predicciones y actualizar el modelo en base a los resultados.

¿Qué sucede si el modelo no es capaz de predecir adecuadamente el tiempo de ejecución para una nueva entrada?

Si el modelo no predice adecuadamente, se debe volver a la fase de benchmarking para incluir más entradas en el conjunto de pruebas y construir un nuevo modelo.

Outlines

00:00

🔍 Análisis empírico del crecimiento de un algoritmo

El video ofrece una visión general del proceso para construir de manera empírica la función de crecimiento de un algoritmo. Se destacan cuatro pasos principales para analizar un algoritmo como si fuera un cuadro negro, observando su comportamiento con diferentes entradas. Se menciona la necesidad de realizar un conjunto de pruebas para diferentes tamaños de entrada y calcular el tiempo que toma el algoritmo para ejecutarse. A partir de estos datos, se realiza un análisis de regresión para construir un modelo que relacione el tamaño de la entrada con el tiempo de ejecución. Finalmente, se sugiere probar el modelo con nuevos tamaños de entrada para evaluar su precisión y, si es necesario, ajustar el modelo con más pruebas.

05:02

🔧 Ventajas y desventajas del análisis empírico

El video también discute las ventajas y desventajas del enfoque empírico. Entre las ventajas, se destaca la independencia de la implementación y la rapidez del proceso, lo cual es especialmente útil para bibliotecas de terceros que no proporcionan el código fuente. Sin embargo, los desafíos incluyen la imprecisión inherente al enfoque empírico, ya que siempre hay un margen de error en las predicciones. Además, existe la posibilidad de que ciertos casos extremos no sean capturados por el conjunto de pruebas y, por lo tanto, no se tomen en cuenta al construir el modelo. También se señala que los resultados pueden variar según el entorno de evaluación, aunque los patrones generales, como la relación N o N cuadrado, son consistentes entre diferentes computadoras.

Keywords

💡Algoritmo

Un algoritmo es una serie de instrucciones claras y ordenadas que se utilizan para resolver un problema o ejecutar una tarea. En el vídeo, el algoritmo es el objeto de estudio, donde se busca entender cómo se comporta al aplicarle diferentes entradas, sin necesidad de conocer los detalles de su implementación.

💡Función de crecimiento

La función de crecimiento de un algoritmo describe cómo el tiempo de ejecución o la cantidad de recursos necesarios crece a medida que aumenta la entrada. En el vídeo, esta función es el objetivo principal de estudio, ya que se busca modelar cómo se comporta el algoritmo en función del tamaño de la entrada.

💡Enfoque empírico

El enfoque empírico es una técnica de análisis donde se observa y se mide el comportamiento de un algoritmo sin analizar su código fuente. En el vídeo, este método se utiliza para construir una función de crecimiento basada en la observación de cómo el algoritmo maneja diferentes entradas.

💡Benchmarking

Benchmarking es el proceso de evaluar el rendimiento de un sistema a través de pruebas estándar. En el contexto del vídeo, se utiliza para medir el tiempo que toma un algoritmo para procesar diferentes conjuntos de entradas, proporcionando datos para construir la función de crecimiento.

💡Entrada

La entrada es la información que se proporciona a un programa o algoritmo para su procesamiento. En el vídeo, las entradas son usadas para evaluar el comportamiento del algoritmo y para generar datos que se utilizan en el análisis empírico.

💡Tamaño de la entrada

El tamaño de la entrada hace referencia a la cantidad o complejidad de la información que se introduce en un algoritmo. Es un factor clave en el análisis de funciones de crecimiento, ya que se relaciona directamente con el tiempo de ejecución y la cantidad de recursos utilizados, como se discute en el vídeo.

💡Regresión

La regresión es una técnica estadística utilizada para modelar la relación entre una variable dependiente y una o más variables independientes. En el vídeo, se menciona el uso de regresión para construir un modelo que relacione el tamaño de la entrada con el tiempo de ejecución del algoritmo.

💡Modelo

Un modelo es una representación simplificada de una situación real que se utiliza para entender o predecir comportamientos. En el vídeo, el modelo se refiere a la función de crecimiento que se construye a partir de los datos de benchmarking y que se usa para predecir el comportamiento del algoritmo.

💡Predicción

Una predicción es una estimación o proyección basada en información disponible. En el vídeo, las predicciones se hacen usando el modelo de crecimiento empírico para estimar el tiempo de ejecución del algoritmo para entradas de tamaño no testeadas.

💡Validación

La validación es el proceso de confirmar la precisión y la fiabilidad de un modelo o hipótesis. En el vídeo, la validación implica comparar los tiempos de ejecución predichos por el modelo con los tiempos reales medidos para entradas no testeadas, para asegurar que el modelo es preciso.

💡Método científico

El método científico es un enfoque para investigar y comprender el mundo natural a través de la observación y la experimentación. En el vídeo, el proceso de análisis empírico del algoritmo se compara con el método científico, ya que implica hacer predicciones, testear hipótesis y actualizar el modelo basado en los resultados.

Highlights

Empirical approach to constructing an algorithm's growth function

Four main steps for empirical analysis of an algorithm

Analyzing algorithms as a black box to observe behavior with different inputs

Benchmarking an algorithm with a set of different inputs

Importance of associating input size with each test

Timing the algorithm's execution for each input size

Using regression analysis to build a model of the algorithm's runtime

Creating an empirical growth function from the model

The necessity of testing the model with new, unseen input sizes

Evaluating the model's prediction against actual runtime

Iterating the process to improve model accuracy

Advantages of the empirical approach over analytical methods

Disadvantages such as in-exact predictions and dependence on the evaluation environment

The empirical process resembling the scientific method

How the empirical approach can be applied to benchmark a sample program

The impact of different hardware on the empirical results

The generalizability of variables in empirical growth functions across different computers

Transcripts

- In this video, I'm going to give an overview

of the process for constructing

an algorithm's growth function empirically.

So, on the left here, I have four main steps,

and we'll go through those one by one.

As kind of a reminder, our goal is the following.

We're in the section, right, talking

about different ways to analyze an algorithm

and one way you can have, right, instead

of looking at every single line of code

in a program is to actually take a look at that algorithm

out of that program in terms of a black box.

Basically, you just observe how it acts

when put in different inputs.

From that, we can basically try to model, right,

or guess, how that algorithm will act, right,

when I give it different size inputs

or I can do it purely based on observation

and that's what called the Empirical Approach.

So how do I do that?

Well, let's assume for a moment

that we already have an algorithm

or a method, let's say I'll be listing a method

that I want to analyze, right,

I wanna find out it's growth function.

First thing I need to do is I need to benchmark it.

So what I'll do is I'll come up

with an entire set of different inputs, right,

and sometimes, right, maybe you run it

on two different inputs, sometimes you run it

on a hundred different inputs.

Whatever you think is appropriate

for determining how the thing grows, right, how that thing,

how much time or how much work it takes

for that algorithm to run or that method to run.

All right, so if it's something really simple,

maybe you can get away with just a few inputs,

but if you're looking at a thousand lines of code

and their's all sorts of different variations

of the inputs you could probably put into that thing,

well, then that means you just have a bunch

of different tests for it, right,

and so all this little suite here,

basically you have a suite of tests, right?

Maybe, so let's say you have a dozen

just for sake of argument.

Take all those different possible inputs,

they all should have associated

with them an input size, right?

So there's always the size N, right,

am I gonna test my certain algorithm

I'll assume it has a hundred elements in it.

Of course then it has one element in it,

ten elements in it, whatever, right?

Every single one of my tests has

to have a problem size associated with it.

The reason, is that, at the end of the day, we want a map

from problem size to how long it takes to run.

All right, so we have all our different inputs.

Feed them all into the method one by one,

and time how long it takes, right?

So all of a sudden we have is these parings,

is they say, "okay, for this size input,

this is how long it took, for this size input,

this is how long it took" and so on and so forth.

Given that we have all those different pairs of data,

what we can next think about doing is some sort

of regression analysis, right?

We can build a model that somehow calculates the run time,

from the size of the input, right?

So we can picture, go back to basic algebra,

you have maybe a graph, right,

and you have your scatter plot of the different pairs

of how long something took to run based

on what its input size is, and we have that, right,

and we could think about doing something like a regression,

and it usually won't be that simple, but, you know,

for sake of argument, we could say it's a regression,

right, and you found, you know,

a linear function for a quadratic function.

Whatever it is, right, we can discover that for that input

and so what that gives us is a potential mathematical model

that relates the size of the input

to how long it takes to run.

Basically what we have is an empirical growth function.

Keep it mind that it will be an approximate.

Now, at that point, we're not done

and it might seem that we are,

because we have a growth function for us,

but that's not really good enough for us.

What we wanna do is the following.

What we wanna do is you wanna pick a problem size,

that's not in one of our input tests, right?

Not something we use to create the model,

we wanna pick something new.

So if we use sizes a hundred, ten,

I want to check how well my sort algorithm works,

or maybe I'll try something else, like two hundred,

I don't know.

It can just be something that's outside of the input set,

and we want to take that input size, feed it

to our mathematical model, right,

our approximate growth function, and figure out how long

that growth function thinks our algorithm will run for

or our method will run for, right?

So we have basically a prediction being made from our model.

Then we can evaluate that prediction, right?

We can go to our basic code, and we can feed it

this new test input or the new size, right?

Size two hundred, or whatever,

and then see how closely the run time

that it actually gives us in practice is to the input,

well, is to the result that was calculated

by our potential growth function, right?

What we wanna do is you wanna check

that our model is accurate, right,

or we wanna basically assess the accuracy

of our model, right?

If our model is not able to predict

how long it takes for this new input to run,

well then it's worthless, right?

We want a model that, when I give it an input size,

has a decent shot at computing

for me how long that method will take.

Now, if I run into a situation where,

maybe I get a good result, right,

it looks pretty close, I'm not done yet.

Probably, I'm gonna check in on a couple more results,

maybe I check on three hundred,

maybe I take on five, now if those also look good,

well, then I'm good to go, right?

That first function that I got from my regression,

that first model, right, that I got

from my regression stuff is good to go.

I can use that.

Otherwise, what I have to think about is, "Oh, hey,

this, you know, maybe there's something not being captured

by the set of input I have to that regression test."

So I'm gonna return to my benchmarking faze, right?

Maybe come up with a different, a couple more inputs,

right, that have different sizes, feed that to that,

you know, that method that benchmark,

figure how long it takes to run,

and then, right, build a new model

that's now inclusive of that data.

Right, so I've basically updated my tests,

say, I get a new model, now I can repeat the process, right?

So then I make a new prediction

from my new model, and then I check that prediction again,

see what the method actually does, right, and I'll need

to repeat this until my model is accurately

predicting my sample inputs to it, right?

Once I have that, then I'm pretty sure

that I have a decent level of accuracy.

I mean, there will always be the case

that there was something that's not really captured

in our inputs sets, but that's basically just one

of the risks we run with doing this.

Now I'm gonna talk about advantages,

disadvantages in a second, but just to draw your attention

to this little note in the right-hand side,

there's a note that says "seem familiar?"

Hopefully, this does seem familiar.

Basically, what this is is the scientific method,

right, of making predictions, of hypothesis,

and checking them, right?

Maybe using those to update our views,

our understanding of the situation,

making a new prediction, right, a new hypothesis.

So this is very much a scientific approach in my opinion.

So let's talk a little more of the advantages

and disadvantages of doing analysis this way.

So, advantages.

First big thing, right, is that we don't really have

to worry about the implementation.

In fact, I don't even need the code

for that function because I don't care.

All I care about is that I can invoke

that function or that method, right,

because I need to give it some input,

time how long it takes, right, and then, you know,

make a note of that somewhere,

but what happens inside is none of my business.

I don't need to worry about the different operations

that are in there; I don't need to have the source code.

So this is great for something like a third party library.

Third party library typically don't give you source code,

so, well, you can still benchmark it, right?

In that case, right, the analytical approach,

looking line by line, doesn't even apply,

because we don't have the original code.

Here, if we're just doing it as a black box,

well, then, we're good to go, right?

We can take a look of their function

that they gave us in the library,

run a DLL, run it, see how long it takes.

No problem for us.

It's fast, right, this is another advantage.

We already said there was issues in analytical

where we have to look at every line, it just takes forever.

Here maybe you can hope to do this in an hour, right?

It's mostly plug-and-chug, as long as you can

have a good way of coming up with your test sets,

right, and then collect your data,

I mean, regression is really easy.

So it's generally a much faster process

than doing it the analytical way.

So, disadvantages, some of these,

right, are a little bit related.

First of the disadvantages is in-exact, right?

So there's always going to be some margin

of error in our prediction.

So, even if my model, right, is generally matching,

you know, what I expected to give,

right, when I do an arbitrary test, you know,

the model can correctly predict the run time

or how long it takes, right, to run

on that particular input.

There will always be, right, some sort

of little margin of error.

Just because you don't really know what's happening, right?

There could always be, you know, some little if branch

that just gets run, you know, one in a thousand times,

you don't really know that and so there will always be

these little fluctuations in your data

and in your predictions, and that's kind of,

really, the second bullet point there

which is the black box, right?

There's always the chance that there is some code

in my function that maybe takes a lot more time

than what, you know, how long it typically takes,

right, and in my test cases I'm just not seeing it

for whatever reason, right?

There's some sort of edge case, you know,

that changes how this thing acts.

Well, with an empirical approach,

if there's something that's not seen by that test suite,

well, then it's not going to be taken into account

when we create our model, right, using regression.

So we just have this chance, right,

that all of a sudden the function is completely different

than what we expect just because

we are taking a black box approach

and we can't guarantee that we've looked

at all the different ways it can behave.

Last note here is that it depends on evaluation environment.

So if we're writing a function, or if we're trying

to determine the growth function, right,

in terms of time, right, it's very exact hopefully,

well, it's gonna be approximate

but maybe it can give us at least down to the second,

right, maybe millisecond's off

but second's fine, how long something takes,

well, there's the issue in that

whatever results we get will be specific to the computer

that we did the tests on, right?

So, if I have different hardware,

it's gonna take a different amount of time, right?

Obviously.

I have different programs running in the background,

well, then it's gonna take a different amount of time.

There are a thousand factors that influence

how long it takes your program or your method to run.

So these results we get really only apply

to the machine that we run then on.

That said, what will generalize is somehow,

like the variables in there.

So, the part that tends to vary is somehow the constants

and the expression recover, maybe are not so useful

because they are depending on the machine,

but in there they'll be saying like,

you know, N or N squared.

Generally those things are depending on variables,

those will be the same between different computers

and so that is going to be valuable for us.

All right, so there we have it,

that's an overview of The Empirical Process,

now we're going to take a look at how we're to apply

this to benchmark a sample program.