# The Geometry of Linear Programming

### In data science, we will be dealing frequently with optimization problems as our main motivation is to minimize(or maximize) a certain objective we are pursuing. Linear optimization(or linear programming) is a subfield of a much broader optimization field called convex optimization and is a great place to start because of its easiness and intuitiveness.

For you who are interested in studying LP but don’t have any preliminary knowledge about it, I try to explicate it as translucent as possible so that you can study in depth with much more confidence. I follow the book Introduction to Linear Optimization by Dimitris Bertsimas (Author), John N. Tsitsiklis. I intented to do this because some core concepts are so crucial that if you cannot internalize them, you are likely to have lots of headache ahead.

### The Basic Concepts That Everything Else is Built Upon

Think of mathematics as a game that has certain rules to be played. Those rules in math might be axioms, definitions, assumptions, or any other thing that is agreed upon beforehand. So LP is a mathematical game that has certain rules and definitons to be played consistently. Consistent is the key word here because any inconsistency between rules, definitions, theories and realities leads to a pointless, confusing and ambiguous game. Let’s start..

Some Verbal Definitions

In LP, we have some variables which we call decision variables. Using those decision variables, we try to minimize or maximize some objective function we are interested in. In LP this objective function is linear in decision variables, that is why it is called linear optimization. We have also some constraints to be met. A vector x of our decision variables satisfying all of the constraints is called a feasible solution and the set of all feasible solutions is called the feasible region. If we find a feasible solution so that no other feasible solution in the feasible region provides improvement in our objective function further (depending on whether we are minimizing or maximizing), then this solution is called optimal solution, and the corresponding objective function value is called optimal objective.

Hyperplanes and Halfspaces

These are the fundamental concepts and definitions of our LP game that we always use. Formal definition of them is the following:

And a typical hyperplane looks like this:

Pay attention to the formal definition of hyperplane and halfspace. A hyperplane is an equation whereas a halfspace is an inequality. For example a1*x1 + a2*x2 = b is a linear equation in two dimensional space with coordinates x1 and x2. This is also known as line equation. So a hyperplane in 2-dimensional space is line. Similarly, in 3-dimensions a1*x1 + a2*x2 + a3*x3 = b is a linear equation and it is known as plane. In more dimension than 3, the geometric object constructed by a linear equation is called hyperplane.

Halfspace is similar to hyperplane, but it covers the area on the one side of a hyperplane. In the above picture, the side red dots are in is a halfspace, and the side green dots are in is another halfspace and hey are separated by a hyperplane. In other words, a hyperplane is the boundary of a corresponding halfspace.

Polyhedrons

We will play this game with objects called polyhedrons. The formal definition of polyhedron is something like that:

A typical polyhedron looks like these:

What the formal definition actually says is that a ployhedron is a collection of a finite number of inequalities. Every row of matrix multiplied by vector is an inequality that is greater than or equal to the corresponding row of vector b. Since linear inequalities construct halfspaces (the definition of halfspace), a polyhedron is the intersection of a finite number of halfspaces as the picture below illustrates:

So far we have seen how hyperplane, halfspace and polyhedron are related to each other. There are among the most important definitions we need to keep in mind.

Convex Sets

This is another important concept we shoul know. The formal definition is the following:

A typical convex and non-convex set look like this:

A linear combination of any two points in a set with lambda between 0 and 1 (both inclusive) like in the definition is a linear combination of those two point. So this corresponds to a line segment joining the two points. We can go along this line with varying values of lambda. So the definition says that if the line segment joining any two points in a set is also contained in that set, then it is called a convex set. That is why the left plot is convex and the right plot is non-convex.

The convex combination of many vectors (points) with coefficients summing to 1 is called convex combination of those vectors and all convex combinations of those vectors is called the convex hull of them.

With hyperplanehalfspace and polyhedron, convexity is the crucial concept we need to  know to go further. After introducing the most basic, fundamental concepts and definitions of LP, we can go further to define some other things we will encounter.

Extreme Points

Extreme point of a polyhedron is the point which cannot be expressed as a convex combination of two other points in the polyhedron. The following is its formal definition:

The illustration below shows a typical polyhedron with its extreme points marked with blue circles. Those blue circles are extreme points because they cannot be expressed as a convex combination of any two points different from extreme point itself.

Vertex

The lexical meaning of vertex is ‘the highest point of something; apex; summit; top.‘. In this sense, it is the highest point of a polyhedron from a specific perspective. The formal definition is as following:

x is actually a constant point and we can think of c’x as a constant term. So contant < c’y is indeed a halfspace whose boundary line is c’y (non-inclusive) as we have already learned in the previous post. Hence, the formal definition says that if we can find a hyperplane which meets P only at the point x so that any other point in the P resides on one side of that hyperplane, then x is a vertex of P.

Basic and Basic Feasible Solution

This concept includes some fundamental concepts of linear algebra, especially spaces, basis, and linear independence. The typical definition of them is as follows:

With the word “active”, it is meant that all equality costraints are met with x*.

From now on, we can start to play the LP game with those definitions.

### Starting LP Game

First Game: With the definitions above, we can play an LP game to prove the followings:

(a) For example, two convext sets go to a bar to drink some beer and have fun. After a couple of hours they asked for the bill and the bill was \$10. The set A has \$20 with him and the set B has \$30 with her. The intersection of their money is \$20.  \$20 can be thought as a line joining 0 and 20 on number line and \$30 can be thought as a line joining 0 and 30 on number line.

So as long as the bill does not exceed \$20, they can pay the bill with convex combination of their intersection. For example they can pay \$20 with lambda = 0.5. So each one pays 20*0.5 = 10 dollar. But it is not possible to pay \$25 with convex combination of their intersection.

So the proof of a is about playing with convex combination.

(b) The proof relies on the definition of halfspace and convex combination.

(c) and (d) can be easily proven after (a) and (b).

Second Game: We have seen three so-called different concepts which are extreme point, vertex and basic feasible solution. In essence, those three concepts are equivalent:

Vertex => Extreme Point: Their equivalence can be shown with convex combination of two points in a convex set.

Extreme Point => Basic Feasible Solution: Their equivalence can be shown by the help of basis and linear independence concept in linear algebra.

Basic Feasible Solution => Vertex: This can be shown by the help of the definitions of halfspace, basic solution and basic feasible solution.

### The Key Conclusion

The proofs of those can be found on the book. My point here is that if you have difficulty proving these theorems, always remember:

-In order to prove a mathematical concept, we should always pay attention to the definitions, rules, and axioms related to that concept. For example, in order to prove the theorems above, we should know the definitions of polyhedron, convex set, convex combination and convex hull. If we keep in mind those definitions and pay enough attention to them, we can start to establish some relationships that help us prove the theorems.

-Always start from the simplest case .

The concepts discussed in this post is the most crucial ones in LP and everything else is largely built upon those ideas. So mastering those ideas is extremely important to understand furter topics in LP.

### Another Important Point

The surprising fact is that just a few learnable strategies of thinking can make you more effective in the classroom, the boardroom, and the living room. You can personally choose to become more successful by adopting five learnable habits. So when learning LP try these.

The 5 Elements of Effective Thinking:

#### 1: Understand deeply

• Don’t face complex issues head-on; first understand simple ideas deeply. Clear the clutter and expose what is really important. Be brutally honest about what you know and don’t know. Then see what’s missing, identify the gaps, and fill them in. Let go of bias, prejudice, and preconceived notions. There are degrees to understanding (it’s not just a yes-or-no proposition) and you can always heighten yours. Rock solid understanding is the foundation for success.

#### 2: Make mistakes

• Fail to succeed. Intentionally get it wrong to inevitably get it even more right. Mistakes are great teachers—they highlight unforeseen opportunities and holes in your understanding. They also show you which way to turn next and they ignite your imagination.

#### 3: Raise questions

• Constantly create questions to clarify and extend your understanding. What’s the real question? Working on the wrong questions can waste a lifetime. Ideas are in the air—the right questions will bring them out and help you see connections that otherwise would have been invisible.

#### 4: Follow the flow of ideas

• Look back to see where ideas came from and then look ahead to discover where those ideas may lead. A new idea is a beginning, not an end. Ideas are rare—milk them. Following the consequences of small ideas can result in big payoffs.

#### 5: Change

• The unchanging element is change—By mastering the first four elements, you can change the way you think and learn. You can always improve, grow, and extract more out of your education, yourself, and the way you live your life. Change is the universal constant that allows you to get the most out of living and learning.

Resources:
-Introduction to Linear Optimization by Dimitris Bertsimas (Author), John N. Tsitsiklis (Author), John Tsitsiklis (Author)
-https://courses.edx.org/courses/course-v1:UTAustinX+UT.9.10x+3T2016/info

# Linear Programming Notes

Just like MITx: 6.041x – Introduction to Probability – The Science of Uncertainty, this is the kind of post in which I share my notes of a special subject. In this time the subject is Linear Programming(LP) or Linear Optimization. I publish them in the hope of helping toddlers (just like me when I first started 🙂 ) understand the subject by unraveling the logic behind LP. These are the small part of the notes and I am going to share all as I sift through them. If anything strange or nice jumps out at you, please notify me freely.

R.I.P Osman Darcan and Barbaros Tansel 😦

# The Magic Behind The Linear Methods for Regression – Part 1

It is time to expose the oracle! In this journey, everything started with an amazingly simple method: linear regression. Let’s dive into the nitty-gritty of it.

What we will see:
-Univariate linear regression (with OLS)
-Orthogonalization
-Multivariate linear regression(with OLS)
-Gauss-Markov Theorem
-Gram-Schmidt Procedure

## Revision

In the previous post,  we learned that regression is simply
a conditional expectation of the outcome Y given by input variables X=x (E(Y|X)) and least squares fitting can be used to find the coefficients of the linear regression. The linear model either assumes that the regression function E(Y|X) is linear or that the linear model is a reasonable approximation.

As you may remember, what we are trying to do is to find such betas so as to minimize the RSS:

From the previous post, we know that the betas that minimize the RSS can be found by:

For those who are familiar with linear algebra, does it remind you of something which is widely used in linear algebra? Yes, it is orthogonal projection which is something extremely important.

Here is a brief overview of what orthogonal projection is and how it works:
As it can be clearly seen from the picture above, the least squares estimate of the betas is the coefficients requred for the orthogonal projection of response vector y onto the columns space of the input(feature) matrix. Then all we have to do is to multiply input matrix with our vector of estimated betas to find the least squares estimation of the responses:

X*(X^t*X)^-1*X^t part of the equation is called the projection matrix because it projects y onto the columns space of X and produces the orthogonal projections. The least squares estimates are essentially the orthogonal projections because the orthogonal distance between actual value and predicted value is the minimum distance between them. Think: what happens to projection matrix when the input matrix X is singular?

## The Gauss-Markov Theorem

This theorem states that the LSE(least squares estimates) of the betas have the smallest variance among all linear unbiased estimates. But do the unbiased estimates always the best? As we will see later, there may be some biased estimates of betas that give a smaller mean squared error overall. The book gives the following equations:

This estimate is unbiased which means its expectation equals to original betas:

The proof is as below:

As we always keep in mind our assumptions, the proofs are easy as it can be seen. Then the book states that if we have any other linear estimator c’y  (‘ means transpose) that is unbiased for  then the variance of this estimates cannot be smaller than the variance of  , the estimates of ordinay least squares.

Let’s try to prove it.

First: setting the equation:

The expectation of the linear estimator can be calculated as below:

Then the variance of it can be calculated as following:

For the ones who wonder the variance of OLS beta, here is how we calculate it:

As it can be seen, the variance of another linear estimator for the  is greater than or equal to the variance of .

##### Then let’s try to find how well we estimate the betas by calculating the MSE of it:Correction: variance decomposition should be expectation of the second moment minus the squared expectation, not plus.

As it is clear from the picture above, the MSE of our estimates of betas are linearly related to its variance and squared bias. Variance of the estimate is minimum when OLS is used. The Gauss-Markov theorem implies that the least squares estimator has the smallest mean squared error of all linear estimators with no bias: squared bias term is the same for all unbiased estimators but the variance part is the minimum for OLS thus cause OLS to have minimum MSE among all unbiased estimators. But sometimes biased estimates can cause a greater reduction in variance than they cause an increase in squared bias. Thus, it is possible to have a smaller MSE with biased estimates. This is bias-variance tradeof. This (along with preventing overfitting) is actually the main motivation behind biased estimates such as Ridge Regression and the LASSO.

## Multiple Regression and Gram-Schmidt Procedure

So far we have seen univariate regression (regression with one input variable). Now we will see what happens when we have many of them which we call multivariate regression. In this case it is very likely to have input variables that are correlated with each other. But correlated variables are bad for regression. Why?

When we have input variables that are not correlated with each other, then it means input variables are orthogonal to each other. Thus, each input variable does not have any effect on the coefficients of other input variables. That means since they are orthogonal to each other, the effect of an input variable cannot be captured by the any other input variables. But when they are not orthogonal (some correlation), then the coefficients of correlated variables become shaky and unstable.

In the picture above, the left plot shows two centered (the mean of the vector is substracted from  each element of it) orthogonal  vectors. Any change along the blue vector axis cannot be captured by the orange vector axis and vice versa: they might change independently. Orthogonality does not necessarily imply uncorrelatedness or independence. It implies uncorrelatedness when the centered vectors have zero inner product because when they are centered their inner product gives the covariance of them. Independence is something related to their joint probability distribution.  For example you can fix a point on the orange line and go freely along with the blue line. The right plot, however, shows two correlated vectors (no orthogonality). In this case the orange vector captures the some of the information provided by the blue line because they go in the similar direction. That means a change along the direction of orange line is somewhat captured by the blue line. So the two vectors say the same thing to some extend.

So we have to orthogonalize input variables with respect to each other so that they do not provide the same information. The book gives the following algorithm for this:

Here, z(i) is the residual vector of x(i) after x(i) is orthogonalized with respect to z(0), z(1), …, z(i-1). We have seen how orthogonalization works in the beginning. Suppose we have the input matrix:

This algorithm says that orthogonalize x1 with respect to x0 which is the first columns of 1s. To do it, we have to find orthogonal projection of x1 onto x0, then substract it from x1. To visualize it:

Here x1 is orthogonally projected onto x2, thereby production green vector x1′. Then when we substract x1′ from the blue vector x1, here is the residual vector z1. In other words: z1 is the orthogonalized vector of x1 with respect to x2.  Then betas are simply calculated as follows:

In this example, the beta of x1 is the orthogonal projection of y(responses) onto the z1 (orthogonalized(or “adjusted”) version of x1 with respect to x2). When the residual vector zp is small, then it means variable p is correlated with some of the other variables. This causes its beta to be large and any small change in the residual would cause large changes in the beta, making the beta unstable and shaky. That is why we try to avoid correlation.

This entire procedure is called Gram-Schmidt procedure for multiple regression. The book says that we can represent the step 2 of the algorithm in matrix form:

where X is the original input matrix, Z has as columns z(j) and the other part is the upper triangular matrix with the coefficients of the residual vectors in the step 2 of the algorithm. Lets see how we can represent this algorithm in this way:

First: matrix Z is constructed like this:

Second: when we left x(s) alone, the equations and the resulting matrix X look like

So we can represent these equations in the matrix form as below:

A simple matrix calculation yields the same equations in the second part. This decomposition looks like QR decomposition, where Z is orthogonal input vectors and the other matrix is an upper triangular matrix. But in order for it to be a real QR decomposition, Z must be orthonormal: vectors must be orthogonal(ortho) and their length must equalt to 1 (normal). So in order to do this, we must divide each column of Z by its corresponding length (a.k.a norm). Here is what normal vector is:

So dividing each column of Z by its corresponding length means multiplying Z with some diagonal matrix:

Let D denote the diagonal matrix on the picture above. Its inverse is simply the same matrix with the diagonal elements 1/a, 1/b, and so on. If the jth diagonal corresponds to the length of z(j) then the following equation gives the QR decomposition:

where Q is orthonormal matrix and R is an upper triangular matrix. If we replace X with QR in our calculation of beta, the equations look like:

This is how they are derived:

Beta estimates are much easier to calculate in this form compared to original algorithm. That is why QR decomposition is used very commonly.

# From Least Squares to KNN, Statistical Models, Supervised Learning and Function Approximation

Infinity returns!

As you know, I follow the book The Elements of Statistical Learning and my main motivation is to help people like me who are suffering from not understanding anything on their first attemp to read the book since the book is not quite appropriate for beginners. This is a little bit tough subject but I will try to simplfy it as much as I can or at least to give some intuition that lays the foundation of the theories we will encounter.

### Starting with Two Simple Methods: Least Squares and Nearest Neighbors

These are the good starting points in this journey because they are the easiest, most basic, and most intuitive approaches that have their origins in the pre-computer era, and the large portions of today’s much fancier methods are the intelligent derivations of these two approaches.

The linear regression with least squares makes a huge assumptions: the model is linear. On the other hand, k-nearest neighbors makes very mild assumption about the structure of the model. The assumption made in linear regression makes it relatively stable but its predictions tend to be inaccurate because the real world is almost never linear. The KNN, on the other hand, tends to give accurate predictions but it can be easily unstable due to its mild assumptions. Let’s dive into them.

### Linear Models and Least Squares

From this point on, the book starts to express every calculation and computation in matrix and vector forms so the understanding of linear algebra would be a huge time and life saver in the remaining of the book. The residual sum of squares is given by:

Here we are trying to find such betas(coefficients) to minimize the RSS. In this example, there is only one input variable X and one output variable Y.  So the alternate representation of this is in vector form:

Consider Y is a vector of outputs and X is a matrix of inputs (1 for every row of the first column, and the value of the random variable X for the second column).  Taking the derivative of it and equating it to zero, we obtain betas as:

This is a basic linear algebra and differentiation job. But why did we include ones for the first columns? Let’s leave it for further subjects.

The result is a two-element vector, the first element is intercept and the other is the slope. Why? Because we include the intercept in X and made it two columns matrix.

This formula requires X transpose * X to be nonsingular so that it has an inverse. What does it mean? In linear algebra, a matrix has an inverse if it is nonsingular or in other words has full-rank. This means that the columns of the matrix have to be linearly independent of each other so that its determinant will be non-zero quantity. Since we use determinant in the denominator to find the inverse of a matrix,  a number / 0 is undefined. That is why it has to be full rank. Fortunately, there are more intelligent ways to calculate betas utilizing matrix decomposition methods such as QR decomposition that does not suffer from ill-conditioned zero determinant case.

### Nearest-Neighbor Methods

This is a more intuitive one than least squares linear regression is. In order to form a prediction for an observation, we find the nearest neighbors of it in terms of some distance measures such as euclidean distance.Then we average the outcomes of the neighbors to predict the outcome of the observation.

This simple method has only one parameter which is k: the number of neighbors. As k goes to infinity the prediction will be less accurate since we average over more observations but this decreases the variance of the predictions. On the other hand, as k goes to 1, the prediction tends to be more accurate because an observation is likely to be very similar to its nearest neighbor but the variance of prediction will be higher. In this case, we cannot use least squares methods to find optimal k because it would always pick 1 for k.

One big disadvantage of this method is that in order to find an observation’s nearest neighbors it needs n*n distance matrix to store each observation’s distance to all other observations. Here, n is the number of observations in the data and as n increases, n*n increases even faster which makes the computation and storage very costly.

### From Least Squares to Neares Neighbors

Least squares linear regression in which linear decision boundary is assumed is the most rigid one and stable to fit. Nearest neighbors, on the other hand, does not assume any stringent assumptions about the decision boundary and can adapt any situation. However, this makes it unstable relative to least squares (hight variance, low bias).

As it is always said, there is no free lunch in this science, so each method has its own advantages and disadvantages depending on data at hand. In some ways, these two methods can be enhanced to develop more advanced methods:

1- In KNN, all k-nearest neighbors of an observation has equal weights in averaging but it doesn’t have to be in this way. We might use some weights that decrease smoothly to zero with distance from the target point. We do this by a function called Kernel.

2- If the space is high dimensional then distance kernels can be modified to emphasize some variables more than others.

3- Rather than fitting a linear regression to entire data globally, we can fit linear models locally by locally weighted least squares.

4- We can expand the original inputs to a basis in which we can develop any complex models. Truncated power basis is an important methods for this.

5- We can non-linearly transform linear models by projection pursuit or neural network.

### Statistical Decision Theory

This section of the book is little bit difficult if you do not know basic probability. The book says than the statistical decision theory requires a loss function L(Y, f(X)) for penalizing errors in prediction. This is intuitive because we can quantify or measure how well our model is only when we have some penalty or loss function and all what we do is to minimize this loss. Squared error loss by far is the most convenient one:

E means expected value of its argument which is also known as mean. The first line might be obvious to you, but in the second line the things become messy. Well, it is the basic properties of probability theory actually. The quantity that we are trying to find its expected value is a continuous jointly distributed random variable. It consists of Y as a one random variable and f(X) as the other random variable and our quantity is the function of the two random variables: Y-f(X). In order to find the expected value of it, we need to integrate it with its joint probability density function. For more information, you can visit my notes of probability course from MIT.

If you revisited the probability then you may remember that a joint pdf of two random variable can be splitted into two parts as:

So when you replace Pr(dx, dy) in the original EPE formula above with this split and rearrange the terms, you can obtain:

here g(x,y) denotes the functions of two random variables which is [y-f(x)]^2. Then it is simply conditioned on X, and EPE can be written as:

This is again from probability theory. This is specifically called total expectation theorem (or more specifically law of iterated expectation, which is an abstract version of total expectation theorem). I cannot go over details of these theorems but you can learn by your self and use my notes of probability. My aim is just to give you some guidance to make you understand what is going on here. Going back to our discussion, EPE can be minimized poinwise. The solution is the conditional expectation which is known as regression function. Then when least squares is used in fitting, the best prediction of Y at any point X=x is the conditional mean of Y.

The nearest-neighbor methods attempt to directly implement this recipe using the training data. The difference is that expectation is approximated by averaging over sample data, and conditioning at a point is relaxed to conditioning on some region close to the target point.

The two methods end up approximating conditional expectations by averages. But where do they differ? The least squares assumes that f(x) is well approximated by a globally linear function whereas knn assumes f(x) is well approximated by a locally constant function. KNN fails in high dimensional space because the neares neighbors need not be close to the target point and can result in large errors. That is why KNN is avoided when the input space is high dimensional.

### Function Approximation

All we try to do is to approximate to the true function (relationship) between inputs and output. What ever you call it machine learning, statistical learning, mathematical modelling, and so on, they all have this aim. The aim is to find a useful approximation to f(x). We can treat supervised learning as a function estimation problem in this sense.

The majority of approximations have associated a set of parameters θ so that we can modify them to suit the data at hand. In linear regression those parameters are betas, β, (the coefficients). Linear basis expansions could be another class of useful approximation and sigmoid transformation common to neural networks could be an example of nonlinear transformation. Least squares methods can be used to estimates such parameters by minimizing the residual sum of squares. Linear models has a closed form solution to the minimization problems but in some models the solution requires either iterative methods or numerical optimization.

In some situations least squares does not make much sense. A more general principle for estimation is maximum likelihood estimation. If we have observations from a density Prθ(y) indexed by some parameters θ, the log probability of the observed sample is

Maximum likelihood estimation says that the probability of observed sample is maximum. The intuition behind it is that we are likely to observe high probability observations more often than we observe low probability observations. So we assume that what we observe must be the most likely one.

Why is maximum likelihood estimation is more general methods than least squares is? How do they related to each other? Well actually under the assumption of normally distributed error terms, least squares methods are derived from maximum likelihood estimation method and hence they are identical:

As you can see the picture above, the least squares and maximum likelihood are closely related.

# MITx: 6.041x – Introduction to Probability – The Science of Uncertainty

I am currently taking a course from MIT called Introduction to Probability – The Science of Uncertainty and this is one of the best courses that I have taken so far. The professor John Tsitsiklis and the other course staffs do great things in this course. How the subjects are studied is quite different than how they are in Turkish education system, hence that makes me realize what our education system lacks: questioning, multiple ways rather than one absolute way to find an answer to a question, developing intuition and application.

Here is some information about content and aim of the course:

The world is full of uncertainty: accidents, storms, unruly financial markets, noisy communications. The world is also full of data. Probabilistic modeling and the related field of statistical inference are the keys to analyzing data and making scientifically sound predictions.

Probabilistic models use the language of mathematics. But instead of relying on the traditional “theorem – proof” format, we develop the material in an intuitive — but still rigorous and mathematically precise — manner. Furthermore, while the applications are multiple and evident, we emphasize the basic concepts and methodologies that are universally applicable.

The course covers all of the basic probability concepts, including:

• multiple discrete or continuous random variables, expectations, and conditional distributions
• laws of large numbers
• the main tools of Bayesian inference methods
• an introduction to random processes (Poisson processes and Markov chains)

The contents of this course are essentially the same as those of the corresponding MIT class (Probabilistic Systems Analysis and Applied Probability) — a course that has been offered and continuously refined over more than 50 years. It is a challenging class, but it will enable you to apply the tools of probability theory to real-world applications or your research.

The course covers:

• The basic structure and elements of probabilstic models
• Random variables, their distributions, means, and variances
• Probabilistic calculations
• Inference methods
• Laws of large numbers and their applications
• Random processes

Here is my notes:

1-2 Conditioning and Bayes’ rule
-Independence
-Counting: Permutation, Combination, Partitioning

3-Discrete Random Variables:
-Probability mass functions and expectations
-Variance; Conditioning on an event; Multiple r.v.’s
-Conditioning on a random variable; Independence of r.v.’s

4-Continuous Random Variables:
-Probability density functions
-Conditioning on an event; Multiple r.v.’s
-Conditioning on a random variable; Independence; Bayes’ rule

5- Further topics on random variables
-Derived distributions
-Sums of r.v.’s; Covariance and correlation
-Conditional expectation and variance revisited; Sum of a random number of r.v.’s

6- Bayesian inference
-Introduction to Bayesian inference
-Linear models with normal noise
-Least mean squares (LMS) estimation
-Linear least mean squares (LLMS) estimation

7- Limit theorems and classical statistics
-Inequalities, convergence, and the Weak Law of Large Numbers
-The Central Limit Theorem (CLT)
-An introduction to classical statistics

8- Bernoulli and Poisson processes
-The Bernoulli process
-The Poisson process
-More on the Poisson process

9- Markov chains
-Finite-state Markov chains
-Absorption probabilities and expected time to absorption

# My Self-Taught Data Science Journey

Yes! It is a huge world. A really, really huge world in which you have infinitely many ways to achive a goal unless there are some restrictions which always exist fortunately. You may find it little bit murky, little bit daunting, little bit overwhelming, and a little bit scary in the beginning. You may not understand anything about it, you will probabily stumble over and over again, and you definitely get lost in the way. If, however, you have a passion for it, you will see that all those things will be the underlying force behind your progress, and ultimately your success.

Yes, I am talking about Data Science. From now on, I will write my topics in English and they will cover my journey of data science. I want to write about it because there are ever incresing demand for data science and there are also lots of people like me(in the beginning of my journey) who don’t know where to start the journey! Well, let’s start.

Everything started with the book Elements of Statistical Learning, Data Mining, Inference, and Prediction. During Analytics Edge course on edX from MIT, one of the successful students said that we should read and understand at least the first eight chapters of this book in order to be competent at data science. Then I decided to read the book. At the first glance, the book looked very attractive and fun to read, but all those good thoughts immediately vanished after a copule of pages. That didn’t happen due to the book, but happened due to my lack of basic knowledge about certain subjects. I want to go over them chapter by chapter. Since the first chapter is an introduction, I skip it. All the subjects from chapter 2 to chatper 8 are the building blocks of every statistical and machine learning method.

The second chapter of the book is Overview of Supervised Learning. It starts with basic
terminologies which we will encounter frequently in this journey. It assumes that you have basic knowledge of calculus, statistics, probability theory, and linear algebra. If you don’t, then you are in trouble! Fortunately, we are living in a world where we are just a couple of clicks away from anything we want to learn. There are lots of invaluable sources on the Internet.

– If you want to learn calculus, or refresh your knowledge of calculus, is a perfect place.

– If you want to learn statistics and linear algebra, there are lots of good courses on Coursera and edX. For linear algebra Linear Algebra from MIT given by Prof. Gilbert Strang is an amazing course. It covers all the subjects of linear algebra you need to know for data science. Especially spaces and matrix decompositions are the fundamentals.

– If you learn probability theory, there is a very good course called Introduction to Probability – The Science of Uncertainty. It follows the book Introduction to Probability, 2nd Edition, which I love much.

In order to understand this chapter and the followings, you will need at least basic understanding of those subjects. You will frequently encounter “differentiating w.r.t, integrating, probability distribution, probability density function, least squares, bias, variance”. If you are not familiar with those, then you can get familiar with them using the sources I wrote above. Furthermore, this chapter puts all the statistical and machine learning methods on a spectrum on which traditional least squares regression represents one end and K-Nearest Neighbor represents the other end, and any other algorithms are put in-between. The least squares regression is the most rigid one and has the lowest variance but potentially has higher bias, whereas KNN has the lowest bias but potentially higher variance. All those terms may make no sense for now, but they make sense as we progress.

The third chaper is Linear Methods for Regression. We will encounter regression
problems frequently in which we want to estimate a continuous outcome or response from various inputs. To understand the building blocks of regression, you must have an understanding of linear algebra, or vector algebra, or matrix algebra, all of which are used interchangeably. All of the computation and algorithms are created using linear algebra. It also covers the best subset selection and shrinkage methods, again frequently used in machine learning. For example, it is always said that correlated features are bad for regression. But if I say that “it is bad because the algorithm that minimizes the squared errors need to computer the inverse of feature matrix, and for this feature matrix to be invertable it has to be full rank. In other words, the columns of it have to be linearly independent. If the columns are not linearly independent (two or more features are highly correlated), then it probabily will have no unique inverse.”, doesn’t it make much sense? This sentence includes lots of linear algebra and differentiation. If you do not understand it, you need to go over the source I wrote, if you want to be a real data scientist I guess. Yeah, it comes with a price. Understanding of shrinkage is also very important because it helps prevent overfitting. Ridge Regression, for example, adds a positive constant to the diagonal entries of your input matrix before inversion. This makes the problem nonsingular even if original input matrix is not of full rank. The LASSO(Least Absolute Shrinkage and Subset Selection) is another regularization method that performs both subset selection and shrinkage. If you want to know where and why to use them, you need to get your hands dirty.

The fourt chapter is Linear Methods for Classification. This time, linear models are developed for classification tasks. This chapter includes Linear Discriminant Analysis(LDA), Quadratic Discriminant Analysis(QDA), Logistic Regression, and Separating Hyperplanes(Rosenblatt’s Perceptron and Optimal Separating Hyper Plane). These subjects require at least elementary knowledge of statistics and probability theory. Logistic Regression and LDA have much things in common, but the main difference lies in the way they are fitted. If you want to understand it, you need to know math. And If you understand it, you will know when to use which, which makes you faster and wiser. This covers Bayes Theorem form probability.

Chapters 5, 6, 7, and 8 are build upon these four chapters. I will go over them in the next post. Until then, challenge yourself. Try to understand what those chapters say in essence.

# Olasılık Teorisi – Ayrık Olasılık Dağılımları

Olasılık teorisi serisinde olasılık bakış açısıyla bir çok simülasyon ve deney gerçekleştireceğiz. Genel fikri aslında şu: yapacağımız her bir deney ve/veya simülasyonda o deneyin ve/veya simülasyonun sonucunu temsil edecek rassal değişkenler yer alacak. Bu rassal değişkenlerin alabileceği olası değerlerin hepsine örneklem uzayı(sample space) diyeceğiz. İlk olarak sonlu miktarda sonucu olabilecek deneyleri inceleyerek başlayacağız.

### Rassal Değişkenler ve Örneklem Uzayı

Diyelim ki bir deney yapıyoruz ve bu deneyin sonucu şansa bağlı olarak değişiyor. Deneyin sonucu X  ile gösteriyor olalım. bir rassal değişkendir ve alabileceği her türlü değere bu deneyin örneklem uzayı(sample space) denir. Eğer bu uzay sonlu veya sayılabilir sonsuz elemandan oluşuyorsa ayrık(discrete) olarak adlandırılır.

Bir zar atıldığında örneklem uzayımız şu şekildedir:

Ω = {1, 2, 3, 4, 5, 6}

Zar hileli bir zar olmadığı müddetçe bu uzaydaki her bir elamanın olasılığı eşittir ve 1/(örneklem uzayı boyutu) kadardır ve 1/6’dır.

### Dağılım Fonksiyonu

Diyelim ki bir deneyin sonucunu gösteren rassal bir değişken olsun ve bu deneyin sonlu sayıda sonucu olsun. Bu deneyin tüm sonuçlarını içeren örneklem uzayını da(sample space) Ω işareti ile gösterelim.  O halde için dağılım fonksiyonunu şu şekilde tanımlayabiliriz:

w ∈ Ω (örneklem uzayındaki her bir eleman(w) için, m(w) >= 0 ve
∑ m(w) = 1

olan bir m fonksiyonu. Yani bu öyle bir fonksiyon olmalı ki örneklem uzayındaki her bir elemanın olasılığı sıfır veya sıfırdan büyük olmalı ve her elemanın olasılığının toplamı 1’e eşit olmalı. Bu örneklem uzayındaki herhangi bir alt küme için olasılık değeri ise şu şekilde hesaplanabilir:

P(E) = ∑ m(w), w ∈ E.

Yani E alt kümesinin tüm elemanlarının örneklem uzayındaki olasılıklarının toplamı. Kafanız karıştı mı? Hemen bir örnekle olaya açıklık getirelim.

İki kere yazı tura attığınızı düşünün. Bu deneyin sonucunu X ile gösterelim. Deneydeki amacımıza göre deneyin örneklem uzayı farklılık gösterir. Örneğin birinci ve ikinci atıştaki sonuçları sırayla kaybettiğimizi düşünelim. Bu durumda Ω = {YY, YT, TY, TT} olacaktır. Eğer amacımız deneyde yazı gelme sayısını gözlemlemek ise bu durumda Ω = {0, 1, 2} olacaktır.

Diyelim ki bizim amacımız birincisini gerçekleştirmek. Örneklem uzayındaki bütün olası sonuçların olasılığının eşit olduğunu var sayarsak dağılım fonksiyonumuzu, yani m()‘yi, şu şekilde tanımlarız:

m(YY) = m(YT) = m(TY) = m(TT) = 1 / 4 = 0.25

Amacımız en az bir kez yazı gelme olasılığını hesaplamaksa bunu şu şekilde hesaplarız:

P(E) = m(YY) + m(YT) + m(TY) = 0.25 + 0.25 + 0.25 = 0.75

Eğer amacımız ilk atışta yazı gelme olasılığını hesaplamaksa bu sefer şu şekilde hesaplarız:

P(E) = m(YY) + m(YT) = 0.25 + 0.25 = 0.5

Başka bir örnek olarak da bir zar atışını düşünelim. Bu durumda Ω = {1, 2, 3, 4, 5, 6} olur. Eğer zar hilesiz bir zar ise bu durumda dağılım fonksiyonu şu şekilde tanımlanır:

m(i) = 1 / 6,  i = 1, ……, 6.

Eğer amacımız çift bir rakamın gelme olasılığını bulmak ise şu şekilde hesaplayabiliriz:

P(E) = m(2) + m(4) + m(6) = 1/6 + 1/6 + 1/6 = 3/6 = 1/2

Gene başka bir örnekte ise aynı işi kapmaya çalışan A, B, ve C adında 3 adayımız olsun ve bunlardan yalnızca biri işe alınacak olsun. Bu durumda Ω = {A, B, C) olur; yani bu 3 adaydan yalnızca biri işi kapabilir. Diyelim ki A ve B’nin işi kapma olasılığı birbirine eşit; fakat C’nin kapma olasılığı diğerlerininkinin yarısı kadar. O zaman:

m(A) = m(B) = 2*m(C)

m(A) + m(B) + m(C) = 1 olması gerektiğinden:

m(A) + m(B) + 2*m(C) = 1‘dir.

Bu denklemi çözdüğümüzde olasılıkların şu şekilde olduğunu görürüz:

m(A) = 2/5, m(B) = 2/5, m(C) = 1/5

Eğer amacımız A veya C’nin işi kapma olasılığını hesaplamaksa bunu şu şekilde hesaplarız:

P(E) = m(A) + m(C) = 2/5 + 1/5 = 3/5

Aşağıdaki şemadan temel küme özelliklerini hatırlayabiliriz:

### Tekdüze Dağılım (Uniform Distribution)

Bir n boyutlu örneklem uzayındaki tekdüze dağılım şu şekilde tanımlanır:

Örneklem uzayındaki her w için: m(w) = 1/n

Burada fark etmemiz gereken önemli bir şey gerçekleştirdiğimiz deneyin mutlak tek bir örneklem uzayının olmaması. Örneğin iki kere yazı tura atma olayında örneklem uzayımız dört elemandan oluşuyordu ve bu elemanların her biri eşit olasılığa sahipti(tekdüze dağılım). Eğer ilgilendiğimiz olay en az bir kere yazı gelme olasılıklarıysa o zaman örneklem uzayımız üç elemandan oluşur Ω = {0, 1, 2}. Burada 0 hiç yazı gelmemesini; 1 bir kere yazı gelmesini; 2 ise iki kere yazı gelmesini belirtiyor. Bu durumda YY, YT, TY, TT sonuçlarından hiç yazı gelmemesi deneyin TT ile; bir keze yazı gelmesi YT veya TY ile; iki kez yazı gelmesi ise YY ile gerçekleşebilir. Dolayısıyla bu olayların olasılıkları şu şekildedir:

m(0) = 1/4,   m(1) = 1/2,   m(2) = 1/4

### Olasılıkların Belirlenmesi

Pratikte olasılık dağılımlarının belirlenmesindeki yöntemleri incelememiz gerekir. Bu yöntemlerden biri simetri (symmetry). Yazı tura deneyinde yazı ve tura tarafı arasında yazı veya tura gelme olasılığını değiştirecek fiziksel bir fark bulunmamakta. Benzer şekilde hileli olmayan bir zarda zarın her yüzü birbiri ile özdeştir ve simetriden dolayı zarın her yüzüne eşit olasılık değerini atarız. Genellikle simetri olan yerlerde tekdüze dağılım vardır. Fakat dikkatli olmamız gerekiyor: Bir sonucun olasılığının diğer bir sonucun olasılığından farklı olduğunu iddia edebileceğimiz bir sebebimiz yoksa her zaman bu olaylara eşit olasılık atayamayız. Örneğin, yeni doğan bir bebeğin cinsiyetini düşünelim. Yeni doğan bebeklerden erkek bebeklerin oranı 0.513. Bu yüzden yeni doğan bir bebeğin erkek olma olasılığına 0.513, kız olma olasılığına 0.487 değerini atamalıyız. Bu aslında istatistiksel gözlemleri kullanarak olasılıkları belirleyebileceğimiz durumlara örnektir. Ancak bu olasılıklar çalışmadan çalışmaya, ülkeden ülkeye, ve ırktan ırka değişebilir. Hatta genetik mühendislikle bu olasılıkları ciddi biçimde değiştirmek bile mümkün olabilir.

### Odds

Bir deney eğer benzer şartlar altında çok sayıda kez tekrarlanabiliyorsa o zaman istatistiksel hesaplamalarla olasılığı bulmak güzeldir. Ancak diyelim ki yeni başlayan bir futbol sezonunda Fenerbahçe‘nin Galatasaray‘ı yenmesine bir olasılık atamak istiyoruz. Bu durumda söz konusu sezona ait veri henüz elinizde yok. Fakat ne tür bir bahis yapmak istediğinize bağlı olarak kendi kişisel olasılık değerlerinizi atayabilirsiniz. Örneğin 2:1 odds Fenerbahçe’nin kazanmasına 1 TL bahse giriyorsunuz. O zaman Fenerbahçe’nin kaybetmesi durumunda 2 TL vermeye razısınız. Bu demek oluyor ki Fenerbahçe’nin kazanmasına verdiğiniz olasılık 2/3.

Şimdi odds ile bu olasılık değeri arasındaki ilişkiye daha dikkatlice bakalım. Diyelim ki E bir olayına 1:r odds ile bahse giriyorsunuz. Bu demek oluyor ki E olayının olması olmamasından r kere daha fazladır. O zaman bu durumda E olayının olma olasılığı r / (r+1) olmalıdır çünkü

P(E) = r * P(˜E)  ve  P(E) + P(˜E) = 1

olmalı. Genel olarak odd’lar E olayının lehine r:s ise:

Eğer E olayının olma olasılığı P(E) = p ise, r/s’nin oranı p cinsinden şu şekilde ifade edilir:

### Sonsuz Örneklem Uzayları (Infinite Sample Spaces)

Eğer bir örneklem uzayı sonsuz sayıda elemana sahipse bu uzayın dağılım fonksiyonunun tanımı uzaydaki elemanların sayılabilir olup olmadığına bağlıdır. Bir örneklem uzayının elemanları sayılabilir ise, örneğin pozitif tam sayılarla sıralanabiliyorsa, bu örnemklem uzayı sayılabilir sonsuz (countably infinite)  uzaydır; eğer elemanları sayılamıyorsa o zaman sayılamayan sonsuz (uncountably infinite) uzaydır. Sonsuz örneklem uzayları daha sonraki yazılarda ele alacağımız yeni bir konsepti gerektirir ancak sayılabilir sonsuz uzayları şu anki bilgilerimizde açıklayabiliriz. Eğer

Ω = {w1, w2, w3, …}

örneklem uzayı sayılabilir sonsuz uzaysa o zaman dağılım fonksiyonu her bir olaya 0 veya 0’dan büyük bir olasılık verecek ve bu olasılıkların toplamı bire eşit olacaktır. Ancak bu sefer bu toplamlar yakınsayan bir sonsuz toplam olmalı. Sonlu uzaylarda yapıp bu tarz uzaylarda yapamadığımız tek şey tekdüze bir dağılım fonksiyonu tanımlamak.

Örneğin yazı gelene kadar yazı tura attığımızı düşünelim. İlk kez yazı gelme sayısını w ile gösterelim. Bu durumda deneyimizin olası sonuçları şu şekildedir:

Ω = {1, 2, 3, . . .}

Bozuk para her seferinde tura da gelebilir ancak bu olasılığa izin vermiyoruz. Nedenini birazdan göreceksiniz. İlk atışta yazı gelme olasılığı 0.5’tir. İlk atışta tura gelip ikinci atışta yazı gelme olasılığı 0.25’tir. İlk iki atışta tura gelip üçüncü atışta yazı gelme olasılığı 1/8’dir. Bu bize her bir atış sayısı için(n) bir kere yazı gelme olasılıklarını şu şekilde ifade edebileceğimizi gösteriyor:

m(n) = 1 / 2^n

Bunun bir dağılım fonksiyonu olduğunu görmemiz için şu şart sağlamamız gerekiyor:

Bu toplamın 1’e eşit olacağını geometrik serilerinin (geometric series) toplam formülüyle gösterecek olursak:

Bu formül r -1 ve 1 arasındaysa geçerlidir. r yerine 1/2 koyacak olursak o zaman bu toplamın 1’e eşit olacağını yani eninde sonunda en az bir kere yazı geleceğini görebilirsiniz. Her atışta tura gelme olasılığına 0 değeri atanması gerektiğinden örneklem uzayımıza 0 sonucunu eklemedik.

Şimdi örneklerle bütün bu kavramları açıklayalım.

Bir iskambil destesinden rastgele bir kart çekersek bunun birli olma
olayına odds’unuz ne olur? Toplam 52 adet kart olduğuna göre ve bunlardan 4 tanesinin birli olduğuna göre odd’u birli olma olasılığı’nın birli olmama olasılığına oranı olarak tanımlarız:

(4/52) / (48/52) = 4 / 48 = 1 / 12

Bu demek oluyor ki her 12 kartta bir, bir adet birli olmasını bekleriz. Peki iki tane bozuk para attığımızda ikisinin de yazı gelme olayına odds’unuz ne olur? Gene aynı mantıkla ikisinin yazı gelme olasılığının ikisinin yazı gelmeme olasılığına oranı olarak buluruz:

(1/4) / (3/4) = 1/3

yani her 3 başarısız atıştan sonra  ikisinin de bir kere yazı gelmesini bekleriz.

Diyelim ki bir at yarışında X adlı atın kazanma odds’u  2:3, Y adlı atın kazanma odds’u da 1:2. X ya da Y’nin kazanma olayına ne odds verilmelidir?

X’in kazanma olasılığı / X’in kazanamama olasılığı = 2/3
Y’nin kazanma olasılığı / Y’nin kazanamama olasılığı = 1/2

2*X + 3*X = 1 ==> 5*X = 1 ==> X = 0.2 ==> 2/5 kazanma, 3/5 kaybetme

1*Y + 2*Y = 1 ==> 3*Y = 1 —> Y = 1/3 —> 1/3 kazama, 2/3 kaybetme

İkisinden birinin kazanma olasılığı = 2/5 + 1/3 = 11/15. Bu durumda bu olayın odds’u:

(11/15) / (4/15) = 11/4. Yani bu olayın 11 kere gerçekleşmesine karşı 4 kere gerçekleşmemesini bekleriz.

# Olasılık Teorisi: Ayrık Olasılık Simülasyonu

### Olasılık (Probability)

Bu yazıya sonlu sayıda sonucu olan deneylerdeki şans faktörünü işleyerek başlayacağım. Örneğin bir zar attığımızda sonuç kümemiz sonlu sayıdadır ve şu şekildedir: 1, 2, 3, 4, 5 ve 6. Aynı şekilde yazı tura attığımızda sonuç sonludur: yazı veya tura.

Örneğin bir zarı dört defa atarak gelen sayıların toplamını matematiksel olarak ifade etmeye çalışalım:

X1 + X2 + X3 + X4

Burada X‘lerin her biri birer rassal değişkendir (random variable). Bunlar belirli bir deneyin sonucunu ifade eder. Tıpkı matematikteki diğer değişkenler gibi bu değişkenler de adından anlaşılacağı üzere farklı değerler alabilirler.

Örneğin bir zar attığımızı düşünelim ve sonucu X rassal değişkeniyle gösterelim. Bu deneyin olabilecek altı sonucunun her birine bir olasılık değeri atayabiliriz:

m(w1) + m(w2) + · · · + m(w6) = 1

Burada m(), her bir w için atanan olasılık değerini ifade ediyor ve bu olasılıkların toplamı 1’e eşit olmak zorunda. m()’ X rassal değişkeninin dağılım fonksiyonu (distribution function) olarak adlandırılır. Zar atma örneğinde her bir sonuca eşit olasılık değerini veririz: 1/6. Bu şekilde olasılık ataması yaptığımızda attığımız bir zarın 4’ü aşmama olasılığını şu şekilde ifade edebiliriz:

Diyelim ki Y bozuk paranın gelen yüzünü temsil eden bir rassal değişken olsun. Bu durumda Y‘nin alabileceği iki değer vardır: Y(yazı) ve T(tura). Bozuk paranın adilliğinden şüphelenmemizi gerektirecek bir durum olmadığı müddetçe bu iki sonuca eşit olasılıklar olan 1/2‘yi atayabiliriz.

Yukarıdaki hem zar hem de bozuk para örneğinde her bir olası sonuca eşit olasılık değerleri atadık. Fakat genellikle bu tarz eşit olasılık ataması yapacağımız çok az durum vardır. Örneğin bir ilacın kullanıldığı zamanların %30’unda efektif olduğu tespit edilmişse bu ilacın bir sonraki kullanımında efektif olma olasılığına 0.3, efektif olmama olasılığında ise 0.7 değerini atayabiliriz. Bu örnek olasılığın sıklık konseptine (frequency concept of probability)  bir örnek. Yani, bir olayın A ile sonuçlanma olasılığı p ise, bu deneyi çok kere tekrarladığımızda A ile sonuçlanan olayların tüm olaylara oranının yaklaşık olarak p’ye eşit olduğunu görürüz. Bu fikirleri doğrulamak için bu tarz problemlere deneysel olarak yaklaşmamız gerekiyor. Örneğin bozuk para deneyini binlerce kez tekrarladığımızda yazıların oranının 1/2’ye yaklaştığını görebiliriz. Ama neyseki bizi gerçek hayatta böylesine bir deney yapmaktan kurtaracak bir çözüm var: bilgisayar simülasyonu.

### Simülasyon

Bu yazının devamında göreceğimiz simülasyonlarda sonucu şansa bağlı olan deneylerin özellikle çok sayıda tekrar edilmesi sonucu neler olacağını göreceğiz. Bilgisayarlar çok kısa bir zamanda milyonlarca kez deneyi tekrar edebildiklerinden bu iş için onları kullanmak gayet mantıklı.

### Rassal Sayı (Random Number)

Bir zar atma deneyini bilgisayar dilinde nasıl ifade edebiliriz? Çok basit: rastgele sayı üreteciyle (random number generator). Bir bilgisayara 0 ve 1 arasında rastgele bir sayı ürettirebilir veya 1’den 6’ya kadar olan tam sayılardan bir tanesini rastgele seçmesini söyleyebiliriz.

### Simülasyon – 1

n kere bozuk para deneyini gerçekleştiren ve her 100. adımda yazıların oranını hesaplayan bir program yazalım. Bunun için ilk olarak aşağıdaki fonksiyon yazılabilir.

```tossCoin <- function(q){
return(sum(sample(c(0,1), q, replace = TRUE)))
}```

Bu fonksiyon 0 ve 1’den oluşan kümeden parametre olarak gönderilen q sayısı kadar rastgele eleman seçer. Burada 0 ve 1 çekme olasılıkları eşittir ve 0.5’tir. Şimdi de n kez q boyutlu deney gerçekleştirip ortalamalarını veren bir fonksiyon yazalım:

```simulateToss <- function(n, q){
plt <- c()
plts <- c()
for(i in 1:n){
plt <- c(plt, tossCoin(q))
plts <- c(plts, mean(plt))
}
return(plts)
}```

Şimdi bu fonksiyonları istediğimiz kadar çağırarak sonuçlarını grafiğe dökelim. İlk olarak 100 kez para atma deneyini 10000 kez tekrarlayalım. Yani toplamda 10000*100=1.000.000 kez para atma işlemini gerçekleştirelim ve 100 ve katlarındaki yazı oranlarını grafikleştirelim:

Yukarıdaki grafikte görüldüğü üzere deney sayısı 0’dan 10000’e doğru gittikçe yazı oranları 0.5’e yaklaşıyor.

### Simülasyon – 2

Elimizde üç adet zar olsun. Bu zarları aynı anda atıp gelen rakamları topladığımızda sonucun 9 olabileceği kombinasyon sayısıyla 10 olabileceği kombinasyon sayısı birbirine eşittir. Ancak bu tarz oyunları sıklıkla oynayan kumarbazlar toplamın 9 olmasına 10 olmasından biraz daha az rastladıklarını söylüyorlar. Sizce bu doğru olabilir mi? Hemen bir simülasyon yapalım.

Aşağıdaki kodla 1’den 6’ya kadar olan rakamlar kümesinden çekileni bir daha çekebilme şartıyla 3 eleman seçip toplamını döndürüyoruz. Yani 3 zarı aynı anda atıp gelen rakamları topluyoruz.

```calculateSum <- function(x){
return(sum(sample(1:6, 3, replace=TRUE)))
}```

Şimdi bunu 100.000 kez gerçekleştirip neler olacağına bakalım:

```results <- sapply(1:100000, calculateSum)
> sum(results==9)/length(results)
[1] 0.11652
> sum(results==10)/length(results)
[1] 0.12364
> hist(results, breaks = 50)```

Burada ilginç yapıyı gözlemleyebildiniz mi? Bu üç zarın toplamının normal dağılıma (normal distribution) çok benzer bir dağılım sergilediğini görüyoruz. Çok benzer dedim çünkü normal dağılım daha sonraki yazılarda ele alacağım sürekli değişkenlere (continuous variable) özgü bir dağılım türüdür. Üç zarın toplamının sonucu minimum 3 ve maksimum 18 olabilir. Kırmızıyla gösterilen 11’in sıklığı, mavi ile gösterilen 10’un ve yeşil ile gösterilen de 9’un sıklığı. Dağılımdan görebileceğiniz üzere 9’un sıklığı 10’un sıklığından biraz daha az. Hemen yukarıdaki koddan görebileceğimiz üzere 100.000’lik denemede 10 gelme olasılığı 0.12364 iken 9 gelme olasılığı 0.11652. Yani aslında kumarbazlar haklıymış!

### Simülasyon – 3

Diyelim ki DeMoivre’yle çok yakın bir dostsunuz ve iddiaya girdiniz. 3 tane zarı aynı anda attığında toplamlarının en az bir kere 18 olması için ortalama en az 150 kere atış yapmanız gerektiğini söylüyor. Sizce bu doğru mu?

Aşağıdaki kodu inceleyin:

```calculateDieSums <- function(x){
return(sum(sample(1:6, 3, replace=TRUE)))
}```
```n = 0
cutoff = 0
while(abs(n-0.5)>0.01){
alls = 0
cutoff <- cutoff + 30
for(i in 1:10000){
total = 0
result <- sapply(1:cutoff, calculateDieSums)
if(sum(result==18)>0)
total <- total + 1
alls <- alls + total
}
n <- alls / 10000
print(paste(n,"-",cutoff))
}```

Bu kod 3 zar atma olayını cutoff değeri kadar gerçekleştiriyor. Sonuçların içinden en az bir tane 18 varsa ilgili değişkeni bir artırıyor ve bunları toplamda 10.000 kez tekrarlıyor. Sonuçlar şu şekilde:

```[1] "0.1307 - 30"
[1] "0.2464 - 60"
[1] "0.3453 - 90"
[1] "0.4204 - 120"
[1] "0.501 - 150"```

Program cutoff değeri 150 olduğunda duruyor. Bu demek oluyor ki 150 atış civarlarında zarlarının toplamlarının en az bir kere 18 olması olasılığı 0.501, yani neredeyse yarı yarıya. Yani arkadaşınız haklı! En az bir kere 18 gelme ihtimali 150 ve daha büyük denemeler için yüksek.

### Simülasyon – 4

Hepimiz ruleti duymuşuzdur. Rulet oyununda çarkta 38 tane bölüm bulunur: 0, 00, 1, 2, 3, …. ,36. Bunlarda 0 ve 00’ın rengi yeşil, geri kalan 36’sının da yarısı kırmızı yarısı siyah. Diyelim ki kırmızı renkler için bahse girdiniz. Çarkı çevirip topu attığınızda top eğer kırmızı renkli sayılardan birinde durursa 1 TL kazanacaksınız; eğer kırmızı renkte durmazsa 1 TL kaybedeceksiniz. Bu, oyunu oynama yöntemlerinden biri. Bir diğeriyse belirli bir sayıya bahis yapmak. Diyelim ki 17 sayısına bahis yaptınız. Eğer top 17 numarada durursa 1 TL ve buna ek olarak 35TL kazanacaksınız. Eğer 17’de durmazsa 1 TL kaybedeceksiniz. Sizce hangisi daha az riskli?

İki oyun türünü de 500’er kez tekrarlayacak bir simülasyon yazıp kazançlara bakalım.

`sets <- c(0, 0, rep(1,times = 18), rep(2, times=18))`
```betForRed <- function(x){
balance <- 0
for(i in 1:500){
res <- sample(sets,1)
if(res == 1)
balance <- balance + 1
else
balance <- balance - 1
}
return(balance)
}```
```betFor17 <- function(x){
balance <- 0
for(i in 1:500){
res <- sample(1:38,1)
if(res == 17)
balance <- balance + 36
else
balance <- balance - 1
}
return(balance)
}```
```a <- sapply(1:1000,betFor17)
b <- sapply(1:1000,betForRed)
sum(a>0)
sum(b>0)```

Yukarıdaki grafikte her bir oyun türü için 500’er kez oynamayı 1000 kez tekrar ediyor. Yeşil noktalar 17’ye bahsi, mavi noktalar ise kırmızılara bahsin sonuçlarını gösteriyor. Buradan çıkaracağımız sonuç şu: her bir oyunu 500’er kez oynadığımızda 17’ye bahis yaptığımızda kazancımız kırmızılara bahis yaptığımızdakinden çok daha fazla değişkenlik gösterir ve buna paralel olarak kazancı ya da kaybı daha fazla olabilir. Kırmızılara bahis yaptığımızda kazancımız ya da kaybımız daha az değişkenlik gösteriyor ancak negatif bakiyeyle oyunu bitirmemiz pozitif bir bakiyeyle bitirmemizden daha yüksek bir olasılığa sahip! Seçim sizin.

### Simülasyon – 5

Psikoloji dünyasında aşağıdaki soruya her 5 kişiden 4’ünün yanlış cevap verdiği gözlemlenmiş:

Bir köy düşünelim ve bu köyde sadece iki tane hastane olsun. Büyük olan hastanede günde yaklaşık 45 bebek doğarken küçük olan hastanede günde yaklaşık 15 bebek doğuyor olsun. Erkek bebeklerin genel proporsiyonu %50 olsa da bu hastanelerdeki herhangi bir günde doğan bebeklerin erkek oranı %50’den az ya da fazla olabilir. Bir yılın sonunda bir günde doğan bebeklerin %60’dan fazlasının erkek olduğu gün sayısı hangi hastanede daha fazladır ? Büyük olan da mı? Yoksa küçük olan mı acaba?

Bunu anlamanın en iyi yolu simülasyon gerçekleştirmek. Cinsiyetlerin eşit olasılıkta olduğunu var sayarak aşağıdaki gibi bir kod yazabiliriz:

```calculateMaleBabyPercent <- function(x,n){
return(sum(sample(c(0,1), size = n, replace = TRUE))/n)
}```
```small <- 0
big <- 0
for(i in 1:1000){
smallHospital <- sapply(1:365, calculateMaleBabyPercent, 15)
bigHospital <- sapply(1:365, calculateMaleBabyPercent, 45)

small <- small + sum(smallHospital>0.6)/length(smallHospital)*365
big <- big + sum(bigHospital>0.6)/length(bigHospital)*365
}
small/1000
[1] 55.284
big/1000
24.706```

Yukarıdaki kod söz konusu olayı 1000 kez tekrarlar. Sonuçta küçük hastanede ilgili gün sayısı yaklaşık 55 iken büyük hastanede 25. Peki bunun sebebi ne olabilir? Cevap aslında çok basit: örneklem boyutu arttıkça gözlemlenen olasılık değerleri gerçek olasılık değerlerine yaklaşır ve buna paralel olarak da değişkenlik (standard error) azalır. Yani 45’lik bir örneklemde erkek bebeklerin oranı 15’lik bir örneklemdeki erkek bebeklerinin oranından daha az değişkendir. Eğer en baştan böyle düşündüyseniz, tebrikler!

# Basit Doğrusal Regresyon (Simple Linear Regression)

Linear Regression, en basit supervised learning algoritmalarından biridir. Tahmin etmeye çalıştığımız Y değişkeni ile tahminleyici değişkenlerimiz X1,X2,…,Xn arasında doğrusal bir ilişki olduğunu var sayar. Ancak bir önceki yazıda da belirttiğimiz üzere gerçek regresyon fonksiyonu azaltılamaz hatalar yüzünden hiçbir zaman doğrusal bir metotla tam olarak modellenemez. Aşağıdaki grafikte mavi çizgi linear regression metodu sonucunda tahminlediğimiz fonksiyonu gösteriyor. Kırmızı eğri ise gerçek fonksiyonu gösteriyor. Biz X ve Y değişkeni arasında doğrusal bir ilişki olduğunu var sayarken gerçekte X ve Y arasında düzgün doğrusal bir ilişki olmadığını görüyoruz. Ancak yine de doğrusal bir metotla gerçek fonksiyona oldukça yaklaşabiliyoruz.

Bu metot aşırı derecede basitmiş gibi gözükse de hem kavramsal olarak hem de pratiklik açısından son derece yararlı bir metottur.

Aşağıdaki görsele bakıp biraz düşünelim ve şu soruları yanıtlamaya çalışalım:

• Reklam bütçesiyle satışlar arasında bir ilişki var mı?
• Reklam bütçesiyle satışlar arasındaki ilişki ne kadar güçlü?
• Hangi medya satışlara katkıda bulunuyor?
• Gelecek satışları ne kadar net ve doğru tahminleyebiliyoruz?
• Reklam mecraları arasında bir sinerji var mı?

### Basit Doğrusal Regresyon (Simple Linear Regression)

Şöyle bir modelimiz olduğunu var sayalım:

Burada olduğu gibi bir cevap değişkenini (Y) tek bir tahminleyici değişken ile (X) hesaplamaya çalıştığımız modeller basit doğrusal regresyon olarak adlandırılır. Cevap değişkenini birden fazla tahminleyici değişken kullanarak tahminlemeye çalıştığımız doğrusal regresyona ise çoklu doğrusal regresyon (multiple linear regression) denir. Bunu bir sonraki yazıda inceleyeceğiz. Bu yazıdaki ana konumuz basit doğrusal fonksiyon. Bu formülde  ve  bilinmeyen sabitlerdir ve sırasıyla intercept ve slope‘u temsil ediyor. Aynı zamanda bunlar regresyon katsayıları/parametreleri (regression coefficients/parameters) olarak da adlandırılır.  ise hata terimini temsil ediyor. Normalde  ve ‘i bilmeyiz. Linear regression metodunu kullanarak bunları tahminlemeye çalışırız. Diyelim ki metodu uyguladık ve gerçek katsayılar için tahminimiz olan  ve ‘i hesapladık. O zaman satışları şu şekilde tahminleyebiliriz:

Burada ,  X=x iken gerçek Y değeri için tahminimizi gösteriyor. Üzerinde şapka olan miktarlar bizim tahminimizi temsil ediyor.

#### Peki bu katsayıları nasıl hesaplayacağız?

Diyelim ki  Y’nin i.ci x değeri için tahmini değeri olsun. O zaman  i.ci artığı (residual) göstersin.

O zaman residual sum of squares (RSS)‘i şu şekilde tanımlarız:

veya e terimlerini açacak olursak:

Least squares yaklaşımı RSS‘i minimize edecek  ve  katsayılarını seçer. RSS denkleminin sırasıyla   ve  için ayrı ayrı kısmi türevlerini (partial derivative) alıp sıfıra eşitlersek RSS‘i minizime eden değerlerin şunlar olduğunu görürüz:

Burada  ve  ; yani sırasıyla y ve x nin ortalama değerlerini temsil ediyor.

Aşağıdaki grafik least squares uydurması(fitting) ile satışların TV reklam bütçesi üzerinden regresyonunu gösteriyor. Kırmızı noktalar gerçek satışları gösterirken mavi çizgi tahminimiz olan satışları gösteriyor. Herhangi bir nokta için gerçek değer olan kırmızı nokta ile tahminimiz olan mavi çizgi arasındaki dik uzaklık(gri çizgiler) ‘yi veriyor. Dolayısıyla bu dik uzaklıkların karelerinin toplamını minimize etmek hatayı minimize etmek anlamına geliyor.

#### Hesaplanan Katsayıların Netliğini ve Kesinliğini Belirleme

Bir tahminleyicinin (estimator) standart hatası (standard error or SE), farklı örneklemeler (sampling) için o tahminleyicinin ne kadar değişiklik göstereceğini söyler.

Bunu anlamak için Merkezi Limit Teoremi (Central Limit Theorem)‘i bilmemiz gerekir. Bu teorem der ki, bir değişkenin dağılımı normal bir dağılım sergilemese bile bu değişkenden elde edilecek örneklemlerin ortalamalarının (veya oranlarının) dağılımları normal dağılıma yaklaşır. Bu şu anlama geliyor:

Bir veri setinden yeteri kadar veri içeren, çok sayıda örneklem (sample) oluşturuyoruz. İlgili değişkenin her bir örneklemdeki ortalamasını buluyoruz. Bu ortalamalar ilgili değişkenin gerçek dağılımından bağımsız olarak her zaman normal bir dağılım (normal distribution) sergiler. Daha sonra bu bulduğumuz ortalamaların ortalamasını alıyoruz. Ortalamalar normal dağıldığından bu bulduğumuz ortalama veri setinin bilmediğimiz gerçek ortalamasına çok yakın olması yani az miktarda sapması beklenir.

Bu sapmanın ne kadar olacağını hesaplamak için standart hata (standard error) formülünü kullanırız:

SE bize, hesapladığımız ortalama değerin gerçek değerden ne derece sapacağını söyler. Yukarıdaki formülden de görebileceğimiz üzere n arttıkça SE düşecektir. Yani ne kadar çok örneklem üretirsek SE düşer, sapma azalır, dolayısıyla tahminimiz gerçek değere daha çok yaklaşır.

Bu mantığı hesapladığımız regresyon katsayılarına uygulayacak olursak katsayılarımızın SE’lerinin şu şekilde olduğunu görürüz:

Burada   yani hatanın varyansını gösteriyor. Bu standart hatalar güven aralıklarını (confidence intervals) hesaplamak için kullanılabilir. En yaygın kullanılan güven aralığı %95’tir. %95 güven aralığını şu şekilde hesaplıyoruz:

Peki bu ne demek oluyor? Aynı popülasyondan farklı veri setleri (yani örneklemleri) alıp her bir veri seti için  regresyon katsayısını ve standart hatasını hesapladığımızda, yukarıdaki formülle her bir veri seti için elde ettiğimiz güven aralıklarının %95’i gerçek  katsayısını içerir. Burada tek bir güven aralığının %95 olasılıkla gerçek katsayıyı içerdiği kanısına varmaktır en sık yapılan hatalardan biridir. Güven aralığı veri setiyle değil örnekleme(sampling) ile ilgili bir hesaplamadır. Örneğin elimizdeki Satışlar ve TV Reklam bütçeleri verisinden yeteri kadar büyüklükte 100 örneklem ürettiğimizi varsayalım ve diyelim ki bu örneklemlerin her biri için ‘in güven aralığını hesapladık. %95 güven aralığı demek oluyor ki bu 100 güven aralığından 95’i gerçek  katsayısını içeriyor. Dolayısıyla gerçek katsayıyı içermeyen bir güven aralığı oluşturma ihtimalimiz %5.

#### Hipotez Testi (Hypothesis Testing)

Standart hata aynı zamanda katsayıların hipotez testinde de kullanılabilir. En yaygın hipotez testi null hipotez testidir:

H0:    X ve Y değişeki arasında bir ilişki yoktur. (null hypothesis)

HA:    X ve Y değişkeni arasında bir ilişki vardır.(alternative hypothesis)

Bunu matematiksel olarak şöyle ifade edebiliriz:

H0 : β1 = 0

vs

HA : β1 <> 0,

Böyle ifade ediyoruz çünkü eğer  = 0 ise model Y =  +  ‘ye indirgenir ve bu da X ile Y arasında ilişki olmadığı anlamına gelir.

Null hipotezi test etmek için bir t-statistic hesaplarız:

Bu t-statistic null hipotezin doğru olduğu varsayılarak hesaplanır. Yani X ve Y değişkeni arasında bir ilişki olmadığını, diğer bir deyişle ‘in 0 olduğunu varsayıyoruz. Bu varsayımlar altında  katsayısının 0’dan ne kadar saptığını hesaplıyoruz. Bu hesaplama n-2 serbestlik dereceli(degree of freedom) t-dağılımına (t-distribution) sahiptir. Herhangi bir istatistiksel yazılımı kullanarak hesapladığımız t değerine eşit veya bundan büyük bir değer elde etme olasılığının kaç olduğunu bulabiliriz. Bu olasılığı p-value olarak adlandırırız. p-value t-statistic üzerinden hesaplandığı için t-statistic için varsayımlarımızın hepsi p-value için de geçerli. Yani bu iki değer null hipotezin doğru olduğu varsayılarak hesaplanır.

Yukarıdaki tabloda TV’yi kullanarak Satışları tahmin etmeye çalıştığımızda linear regression‘ın ürettiği sonuçları görüyoruz. Coefficient kolonuna baktığımızda regresyonun TV’ye 0.0475 katsayısını() atadığını görüyoruz. TV’nin SE‘si de 0.0027 olarak hesaplanmış. Bu değerin küçük olması gerçek katsayında sapmanın az olduğu anlamına gelir. t-statistic değeri ise coefficient’ın SE’ye bölünmesiyle elde edilir. Bu durumda TV için t-statistic 0.0475/0.0027 = 17.67 olarak hesaplanır. Bu da p-value değerinin çok düşük olduğunu söylüyor. Yani bu t-statistic değerini gözlemlemek o kadar düşük bir olasılığa sahip ki böyle bir değer elde ettiğimizde TV ve Satışlar arasında bir ilişki olmadığı hipotezini (null) TV ve Satışlar arasında bir ilişki olduğu hipotezininin (alternatif) lehine olacak şekilde reddederiz. Hipotez testindeki amacımız null hipotezi reddetmeye çalışmaktır. Elimizdeki veriler eşliğinde null hipotezi ya reddedemeyiz ya da reddederiz. Veriler null hipotezi reddetmemizi söylemiyorsa alternatif hipotezimizin bir önemi kalmaz; anca null hipotezi reddebiliyorsak alternatif hipotezimizin geçerli olduğunu varsayarız. Yani bir hipotezi ya reddedebiliriz ya da reddedemeyiz; hipotezi kabul etmek diye bir şey yoktur.

#### Modelin Genel Netliğini ve Kesinliğini Belirleme

Null hipotezi alternatif hipotezin lehine reddettiğimizde, modelimizin elimizdeki veriye ne kadar uyduğunu(fit) ölçümlememiz gerekir.

Aşağıdaki tabloda TV reklam bütçesini kullanarak Satışları hesaplmaya çalışan linear regression fonksiyonunun ürettiği bazı değerleri görüyoruz.

Şimdi bunları teker teker açıklayalım.

Residual Standard Error (RSE)

Her gözlem için bir hata terimi her zaman mevcuttur. Bu hataların varlığından dolayı, X ve Y arasındaki gerçek regresyon fonksiyonunu bilsek bile X’i kullarak Y’yi mükemmel bir şekilde tahminleyemeyiz. RSE hataların standard sapmasının bir hesaplamasıdır. Yani cevap değişkeninin gerçek regresyon fonksiyonundan ortalama olarak ne kadar sapacağını söyler.  RSE aşağıdaki formülle hesaplanır:

Yukarıdaki tabloda RSE değerinin 3.26 olduğunu görüyoruz. Bu demek oluyor ki her pazardaki gerçek satış adetleri gerçek regresyon fonksiyonundan yaklaşık olarak 3,260 adet sapıyor. Diğer bir deyişte, ürettiğimiz model doğru olsa ve  ve gerçek katsayıları bilinse bile TV reklamları üzerinden hesaplanan satış adetlerinde ortalama olarak 3,260 adet sapma olacaktır. Sapma miktarının kabul edilebilir olup olmadığı elimizdeki probleme göre değişiklik gösterebilir.

RSE modelin veriye uyum eksikliğinin (lack of fit) bir ölçümüdür aslında. Bu değer ne kadar küçükse model veriye o kadar iyi uyum sağlamıştır, ya da bu değer ne kadar büyükse model veriye o kadar az uyum sağlamıştır.

R-squared Statistic

RSE modelimizin veriye mutlak olarak uyum eksikliğinin bir ölçümüdür. Fakat RSE değeri Y’nin birim değerinde ölçüldüğünden iyi bir RSE değerinin ne olduğunu her zaman net değildir. R-squared statistic uyum için alternatif bir ölçümdür.  Her zaman bir oranı(proporsiyonu) temsil eder. Bu proporsiyon X kullanılarak Y’de açıklanabilen varyansın proporsiyonudur ve Y’nin biriminden bağımsız olarak her zaman 0 ile 1 arasında bir değer alır.

R-squared‘i hesaplamak için şu formülü kullanırız:

Burada TSS (total sum of squares)  formülüyle hesaplanır. Buradaki  bütün y değerlerinin ortalamasıdır. Bu hesaplama bize şunu veriyor: eğer regresyon metoduyla y’yi tahminlemeye çalışmasayıp her bir değer için tahmini değer olarak ortalama değeri verseydik hatalarımızın karelerinin toplamı bu olacaktı.

RSS ise regresyon metoduyla hesapladığımız Y değişkenlerinin gerçek değerlerden farkının karelerinin toplamıydı.

TSS ile RSS arasındaki fark ne kadar büyükse regresyondan o kadar fayda sağlarız. RSS hiçbir zaman TSS’ten büyük olamaz. Bu durumda RSS‘in TSS‘den mümkün olduğunca küçük olması gerekir. Yani regresyon sonucu elde ettiğimiz hataların karelerinin toplamının daha düşük olması gerekir. Bu durumda r-square 1’e ne kadar yakınsa regresyon o kadar iyi sonuç vermiştir. Basit doğrusal regresyonda R-square X ve Y değişkenleri arasındaki korelasyona (correlation) eşittir. Ancak sonraki yazılarda ele alacağımız çoklu doğrusal regresyon (multiple linear regression) durumunda R-square’in çok daha dikkatli yorumlanması ve buna bağlı olarak bazı düzeltmelerin yapılması gerektiğini göreceğiz. Bu durumda model uyumunu ölçümlerken tek başına R-square’e bakmak yerine başka göstergelere de bakmamız gerektiğini göreceğiz.

Yukarıdaki tabloda bu örnek için R-square değerinin  0.612 olduğunu görüyoruz. Bu da demek oluyor ki satış değerindeki değişikliğin üçte ikisini TV değişkenini kullanarak açıklayabiliyoruz. Ancak R-squared 1’e yakın olmadığından tek başına TV değişkeninin satışlardaki değişikliği iyi derecede açıklayabildiğini söyleyemeyiz.

Kaynaklar:

# İstatistiksel Öğrenme II – Modelin Netliğini Değerlendirme

statistik ne yazık ki kesin kuralları olan bir disiplin değil. Herhangi bir metot bir veri setinde çok iyi sonuçlar üretebilirken başka bir veri seti üzerinde çok kötü sonuçlar üretebilir. Bu yüzden belirli bir veri seti üzerinde en iyi performansı veren metodu bulabilmek çok önemli bir konu. Pratikte istatistiksel öğrenmenin en çetrefilli olayı da tam olarak budur: doğru yaklaşımı ve metodu belirlemek. Bu yazıda, belirli bir veri seti için en iyi sonucu üreten istatistiksel öğrenme prosedürünü seçmemizde bize yol gösterecek birkaç önemli konsepti inceleyeceğiz.

#### Uyum Kalitesinin Ölçümü

Bir istatistiksel öğrenme metodunun belirli bir veri seti üzerindeki performansını değerlendirmek için metodun ürettiği tahminlerin gerçek sonuçlarla ne kadar örtüştüğünü ölçümlememize yarayacak yöntemlere ihtiyacımız var. Yani, belirli bir gözlem için tahmin edilen cevap(reponse) değerin o gözlemin gerçek cevap(reponse) değerine ne kadar yakın olduğunu sayısallaştırmamız gerekiyor. Regresyon için, en yaygın olarak kullanılan ölçüm Ortalama Karesel Hata (Mean Squared Error-MSE)‘dır ve şu şekilde ifade edilir:

Burada (xi) ‘in i numaralı gözlem için ürettiği tahmini gösteriyor. Tahmin edilen değerler gerçek değerlere ne kadar yakınsa MSE o kadar küçük olur; gerçek değerlerden ne kadar uzaklaşırsa MSE o kadar büyük olur. Yukarıda MSE, modeli uydurmak(model fitting) için kullanılan training veri seti kullanılarak hesaplanır ve training MSE olarak ifade edilmelidir. Fakat genellikle, metodumuzun training veri seti üzerinde ne kadar iyi sonuçlar ürettiğiyle ilgilenmeyiz. Bilakis training veri seti dışındaki verilerde(test) modelin ne kadar kesin sonuçlar ürettiğiyle ilgileniriz. Peki neden durum böyle?

###### Örnek 1

Yukarıdaki grafiği inceleyerek bu durumu açıklayalım. Sol taraftaki grafikte siyah ile çizilmiş eğri bizim gerçek  fonksiyonumuzu gösteriyor. Turuncu çizgi ile mavi ve yeşil eğriler ise bizim gerçek  fonksiyonu için tahminlerimizi göstersin ve bunların esnekliği(flexibility) sırasıyla artıyor olsun; yani mavi turuncudan, yeşil de maviden daha esnek olsun. Turuncu çizgi “linear regression” metodu ile elde edilen tahmindir; yani esnekliği görece azdır. Mavi ve yeşil eğriler ise ilerideki konularda ayrıntılı ele alacağımız “smoothing splines” metodu kullanılarak elde edilen tahminlerdir ve bu eğriler farklı düzleme seviyeleri (level of smoothing) kullanılarak üretilmişlerdir. Grafiğe dikkatli baktığımızda göreceğimiz üzere esneklik seviyesi arttıkça eğri gözlemlenen veriye daha çok uyum sağlar (fit). Yeşil eğri en esnek olan eğridir ve gözlemlenen veriye en çok uyumu sağlamıştır. Fakat, bu eğrinin gerçek  eğrisine çok da benzemediğini görüyoruz; çünkü gereğinden fazla kıvrımlı. Smoothing spline fit metodunun esneklik seviyesini değiştirerek aynı veriye bir çok farklı eğri uydurabiliriz.

Sağ taraftaki grafikte gri eğri ortalama training MSE değerini esnekliğin  bir fonksiyonu olarak göstermekte. Burada esneklik kavramı istatistiki jargonda serbestlik derecesi(degree of freedom) olarak adlandırılır. Turuncu, mavi ve yeşil kareler sol taraftaki ilgili eğrinin MSE değerlerini belirtmekte. Daha kısıtlayıcı ve dolayısıyla daha düz(smooth) eğriler daha kıvrımlı olanlara nazaran daha az serbestlik derecesine (degree of freedom) sahiptir. Training MSE değeri esneklik arttıkça monoton olarak azalır. Bu örnekte gerçek  doğrusal değil, ve bu yüzden turuncu çizgi gerçek ‘i yeterince iyi tahminleyecek esnekliğe sahip değil. Yeşil eğri en düşük training MSE değerine sahip çünkü içlerinden en esnek olanı o. Bu örnekte gerçek  fonksiyonunu biliyoruz ve böylece test MSE değerlerini çeşitli esneklik seviyeleri için hesaplayabiliyoruz. (Elbette pratikte gerçek  fonksiyonu genellikle bilinmez; dolayısıyla bu örnekte yapacağımız hesaplamayı yapmak mümkün olmaz). Test MSE değeri sağ tarafta kırmızı eğri ile gösterilmekte. Esneklik seviyesi arttıkça training MSE değerine paralel olarak test MSE değeri en başta azalmakta, belli bir noktada test MSE değeri minimum olmakta ve o noktadan sonra test MSE değeri tekrar artmakta. Bu nedenle, turuncu ve yeşil eğriler yüksek test MSE değerine sahip. Mavi eğri test MSE değerini minimize etmekte ve sol taraftaki görselde de görülebileceği üzere zaten görsel olarak gerçek ‘i en iyi tahmin eden de bu. Yatay kesikli çizgi azaltılamayan hatayı (irreducible error) Var(e) gösteriyor ve bu da bütün metotların ulaşabileceği minimum test MSE değeri anlamına geliyor. Dolayısıyla, mavi eğri ile gösterilen smoothing spline tahmini optimuma yakın bir tahmin.

Yukarıdaki görselin sağ tarafındaki grafikte görebileceğiniz üzere istatistiksel öğrenme metodunun esnekliği arttıkça training MSE değerinde monoton bir azalma gözlemlerken test MSE değerinde U şekli gözlemliyoruz. Bu durum, eldeki veriden ve kullanılan istatistiksel metottan bağımsız olarak istatistiksel öğrenmenin temel bir özelliğidir. Model esnekliği arttıkça, training MSE hep azalır ancak test MSE hep azalmayabilir. Bir metot düşük training MSE değeri üretirken yüksek test MSE değeri üretiyorsa, bu durum elimizdeki veriye “aşırı uydurma” veya tam adıyla “overfitting” yapıyoruz demektir. Bunun sebebi elimizdeki istatistiksel öğrenme prosedürünün training veri setindeki örüntüyü (pattern) çok yakından takip etmesidir ve bu örüntülerden bazıları gerçek  fonksiyonunun özelliğinden kaynaklanmayıp tamamıyla şans eseri oluşan örüntülerdir. Training verisine “aşırı uydurma” yaptığımızda, test MSE değeri çok büyük olacaktır çünkü training verisinde bulduğumuzu sandığımız örüntüler(rastgele hatalardan kaynaklanan) test verisinde bulunmayacaktır. Şunu da not etmek gerekiyor ki aşırı uydurma yapalım ya da yapmayalım, neredeyse her zaman training MSE değerinin test MSE değerinden düşük olmasını bekleriz çünkü çoğu istatistiksel öğrenme metodu direkt ya da dolaylı olarak training MSE değerini minimize etmek için tasarlanmıştır.

###### Örnek 2

Yukarıdaki grafik gerçek ‘in yaklaşık olarak doğrusal olduğu başka bir örneği gösteriyor. Gene esneklik arttıkça, training MSE değerinin monoton olarak azaldığını, test MSE değerinin ise U şekli çizdiğini görüyoruz. Fakat, gerçek  fonksiyonu doğrusala yakın bir fonksiyon olduğundan, test MSE artmadan önce çok az bir miktarda azalıyor; dolayısıyla turuncu least square fit yüksek miktarda esnek olan yeşil eğriden daha iyi tahminleme yapıyor.

Aşağıdaki figür ise gerçek  fonksiyonunun doğrusal olmadığı bir örneği gösteriyor. Training ve test MSE eğrileri aynı davranışı(yani training azalırken test MSE değeri U şekli çiziyor) gösteriyor fakat bu sefer test MSE değeri artmaya başlamadan önce her iki eğride de hızlı bir düşüş gözlemleniyor.

###### Örnek 3

Pratikte genellikle sadece training MSE değerini hesaplayabiliriz; test MSE değerini hesaplamak çok daha zordur çünkü genellikle test verisi elimizde yoktur. Yukarıdaki üç örnekten görebileceğiniz üzere, minimum test MSE değerini üreten modelin esneklik seviyesi veri setinden veri setine ciddi derecede farklılık gösterebiliyor. Bu minimum test MSE noktasını hesaplamak için bir çok yöntem var. Bunlardan en yaygını cross-validation. İleriki yazılarda ayrıntılı olarak inceleyeceğimiz için şimdilik burada duralım.

Test MSE değerinde gözlemlediğimiz U şekli istatistiksel öğrenme metotlarının birbirleriyle rekabet içinde olan iki özelliğinden kaynaklanıyor. Matematiksel kanıtlamayı burada yapmaya kalkarsak yazının amacını çok aşmış oluruz, fakat beklenen(expected) test MSE değerinin her zaman üç temel miktarın toplamına eşit olduğunu söyleyelim:

Burada   beklenen(expected) test MSE değerini gösteriyor ve bu da bir sürü farklı training veri seti kullanılarak hesaplanan ‘erin test setleri üzerindeki MSE değerlerinin ortalamasına tekabül ediyor.

Bu denklem bize şunu diyor aslında: beklenen test hatasını minimize etmek için, aynı anda hem düşük varyansa hem de düşük taraflılığa(bias) erişebilen bir istatistiksel öğrenme metodu seçmemiz gerekiyor. Dikkat edilmesi gereken konu şu ki varyans yapısı gereği her zaman sıfıra eşit ya da pozitiftir ve karesi alınmış taraflılık(bias) da hiçbir zaman negatif olamaz. Bu yüzden, beklenen test MSE değeri asla ‘nin yani azaltılamaz hatanın (irreducible error) altına inemez.

Bir istatistiksel öğrenme metodunun taraflılığı ve varyansı derken tam olarak neden bahsediyoruz? Varyans ‘in farklı training veri setleri kullanılarak hesaplandığında ne kadar değiştiği ile ilgilidir. Training veri seti istatistiksel öğrenme metodunu uydurmak(fit) için kullanıldığından, farklı training veri setleri farklı ‘ler üretecektir. Fakat ideal olarak gerçek  için olan tahminimizin farklı training veri seti kullandığımızda çok fazla değişmemesi gerekir. Eğer bir metot yüksek varyansa sahipse o zaman training veri setindeki küçük değişiklikler bile tahminimiz olan ‘te büyük değişikliklere sebep olur. Genel olarak, daha esnek istatistiksel metotlar daha yüksek varyanslara sahiptir. Örnek 1‘deki yeşil ve turuncu eğrileri gözlemleyin. Esnek yeşil eğri gözlemleri çok yakından takip ediyor. Bu eğri yüksek bir varyansa sahip çünkü gözlemlerden herhangi birini değiştirdiğimizde hesapladığımız  fonksiyonu ciddi derecede değişir. Diğer yandan, turuncu “least squares” çizgisi ise göreceli olarak daha az esnektir ve dolayısıyla daha düşük varyansa sahiptir çünkü herhangi bir gözlemi değiştirdiğimizde bu değişiklik fonksiyonumuzda çok çok ufak bir değişikliğe neden olacaktır.

Taraflılık(bias) ise gerçek hayattaki bir problemi yaklaşık olarak olarak modellediğimizde modelimizin sebep olduğu hatadır. Bu hata seçtiğimiz model basitleştikçe artış gösterir. Örneğin, linear regression Y ve X1,X2, . . . , Xp arasında doğrusal bir ilişki olduğunu var sayar. Gerçek hayatta karşılaştığımız herhangi bir problemin böylesine basit bir doğrusal ilişkiye sahip olması çok az rastlanılan bir durumdur. Dolayısıyla linear regression ‘i tahminlemede şüphesiz bir biçimde bir miktar taraflılığa sebep olacaktır. Örnek 3‘te gerçek  doğrusal değildir, bu yüzden ne kadar training verisine sahip olursak olalım linear regression kullanarak net bir tahmin yapmamız mümkün değil. Diğer bir deyişle linear regression bu örnekte yüksek taraflılığa sebep oluyor. Fakat Örnek 2‘de gerçek  doğrusala çok yakın ve dolayısıyla elimizde yeterince veri olduğunda linear regression kullanarak net bir tahmin elde etmemiz mümkün. Genel olarak, daha esnek metotlar daha az taraflılığa sebep olur.

Genel bir kural olarak, daha esnek metotlar kullandığımızda varyans artarken taraflılık azalacaktır. Test MSE değerinin artmasını ya da azalmasını belirleyen etmen bu iki miktarın göreceli değişimidir. Esnekliği artırdığımızda taraflılık en başlarda varyansın artış hızından daha hızlı bir şekilde düşecektir. Sonuç olarak beklenen test MSE değeri de düşecektir. Ancak, belirli bir noktadan sonra esnekliği artırmak taraflılık üzerinde çok düşük miktarda etki gösterecektir ve varyansı ciddi derecede artırmaya başlayacaktır. Bu olduğunda test MSE değeri artış gösterir. Bu olay yukarıdaki 3 örneğin sağ tarafındaki grafiklerde gösteriliyor.

Yukarıdaki görseldeki üç grafik 1.,2. ve 3. örneklerimiz için beklenen test MSE değeri denklemimiz için sonuçlarını gösteriyor. Mavi eğri çeşitli esneklik seviyeleri için karesel taraflılığı (squared-bias), turuncu eğri de varyansı gösteriyor. Kesikli yatay çizgi ise azaltılamaz hatayı, gösteriyor. Kırmızı eğri ise bu üç miktarın toplamını yani beklenen test MSE değerini gösteriyor. Her üç örnekte de metodun esnekliği arttıkça varyans artıyor ve taraflılık azalıyor. Fakat, minimum test MSE değerine karşılık gelen esneklik seviyesi her örnek için ciddi derecede farklılık gösteriyor çünkü karesel taraflılık ve varyans hepsinde farklı hızlarlarla değişiklik gösteriyor. Soldaki grafikte en başlarda taraflılık varyansın değişim hızına kıyasla çok hızlı bir şekilde azalıyor ve dolayısıyla test MSE değerinde düşüşe sebep oluyor. Fakat ortadaki grafikte gerçek  doğrusala yakın olduğundan esneklik arttıkça taraflılıkta çok az bir azalmaya neden oluyor ve test MSE değeri çok az miktarda azalıyor ve sonrasında varyans arttığı için hızla artmaya başlıyor. Ve sağ taraftaki grafikte ise esneklik arttıkça taraflılıkta çok ciddi bir azalma oluyor çüknü gerçek  bu örnekte doğrusal olmaktan çok uzak. Ayrıca esneklik arttıkça varyansta da çok az bir artış gözlemleniyor. Sonuç olarak, test MSE değeri çok ciddi miktarda azalıyor ve belirli bir noktadan sonra çok az artış gösteriyor.

Bu durum taraflılık-varyans dengesi (bias-variance trade-off) olarak adlandırılıyor. Bir istatistiksel öğrenme metodunun düşük test MSE değeri üretebilmesi için hem düşük varyansa hem de düşük karesel taraflılığa sahip olması gerekiyor. Bu denge olarak ifade ediliyor çünkü son derece düşük taraflılığı olup son derece yüksek varyansa sahip bir metot veya tam tersini elde etmek kolay. Buradaki zorlayıcı nokta hem varyansı hem de karesel taraflılığı düşük olan bir metot bulmak.

Gerçek hayatta gerçek ‘i genellikle bilmeyiz. Bu yüzden bir istatistiksel öğrenme metodunun test MSE değerini, taraflılığını ve varyansını hesaplamak çoğu zaman mümkün değildir. Yine de taraflılık-varyansa dengesini göz önünde bulundurmamız gerekiyor. Bunları nasıl hesaplayacağımıza dair metotları sonraki yazılarda ele alacağız.

#### Sınıflandırma (Classification) Olayı

Şimdiye kadar model netliğini tartışırken hep regresyona odaklandık. Fakat karşılaştığımız konseptlerin çoğu, mesela taraflılık-varyans dengesi, sınıflandırma metotları için de geçerli. Buradaki tek değişiklik tahmin etmeye çalıştığımız değişkenin artık sayısal bir değişken olmaması. Diyelim ki elimizdeki veri şöyle olsun: {(x1, y1), . . . , (xn, yn)} ve gerçek ‘i hesaplamaya çalışalım. Burada y değişkeni kalitatiftir. Tahminimizin, , netliğini ölçmedeki en yaygın yaklaşım training hata oranıdır (training error rate) ve bu da tahmin ettiğimiz ‘i training veri setine uyguladığımızda elde ettiğimiz hatalı tahminlerin tüm tahminlere oranıdır.

Üzerinde şapka olan y i.’ci gözlem için tahminimizi temsil ediyor. I fonksiyonu ise içindeki ifade doğru ise 1 değil ise 0 üretiyor. Dolayısıyla yukarıdaki fonksiyon bize yanlış sınıflandırılan gözlemlerin yüzdesini veriyor.

Burada da gene tahminimizin training veri seti üzerinde ne kadar iyi sonuçlar ürettiğinden ziyade test veri seti üzerinde ne kadar iyi sonuçlar ürettiğiyle ilgileniriz. İyi bir sınıflandırıcı(classifier) test MSE değeri minimum yapandır.

##### Bayes Sınıflandırıcısı (Bayes Classifier)

Test MSE değeri her bir gözlemi tahmin değişkenlerine bakarak en yüksek olasılıktaki sınıfa atayarak minimize edilir. Diğer bir deyişle x0 tahminleyici değişken vektörüne (yani X1,X2,…,Xp) sahip bir test gözlemini öyle bir j sınıfına atamalıyız ki

Pr(Y = j|X = x0)

değeri maksimum olsun. Bu ifade bir koşullu olasılık (conditional probability)‘dır ve şu şekilde ifade edilir: x0 verildiğinde Y’nin j’ye eşit olma olasılığı. Bu son derece basit sınıflandırıcı Bayes Sınıflandırıcısı(Bayes Classifier) olarak adlandırılır. Yalnızca iki sınıftan(sınıf1, sınıf2) oluşan problemlerde Bayes Sınıflandırıcısı bir gözlemi Pr(Y = 1|X = x0) > 0.5 ise birinci sınıfa değilse ikinci sınıfa atar.

Yukarıdaki grafik X1 ve X2 tahminleyici değişkenlerinden oluşan iki boyutlu bir uzaydaki bir örneği gösteriyor. Turuncu ve mavi halkalar iki farklı sınıfa ait olan training veri seti gözlemlerini gösteriyor. X1 ve X2‘nin her bir değeri için, cevap (response) değişkeninin turuncu veya mavi olma olasılığı farklılık gösteriyor. Bu örnek yapay olarak yaratıldığından verinin nasıl oluşturulduğunu biliyoruz ve X1 ve X2’nin her bir değeri için koşullu olasılık değerlerini hesaplayabiliyoruz. Turuncu alan Pr(Y = orange| X) > 0.5 olduğu alanı, mavi alan ise bu değerin 0.5’ten küçük olduğu alanı gösteriyor. Kesikli mor çizgi ise olasılığın tam olarak 0.5 olduğu yerleri gösteriyor. Bu çizgi Bayes Karar Sınırı (Bayes decision boundary) olarak adlandırılıyor. Bayes Sınıflandırıcısının tahminleri bu sınır tarafından belirleniyor: eğer bir gözlem bu çizginin turuncu tarafına düşerse turuncu sınıfa, mavi tarafında düşerse mavi sınıfa atanıyor.

Bayes Sınıflandırıcısı mümkün olabilecek en düşük test hata oranını üretiyor ve bu da Bayes hata oranı (Bayes error rate) olarak adlandırılıyor. Bu örnekte Bayes hata oranı 0.1304. Sıfırdan büyük çünkü sınıflar birbirleriyle bazı noktalarda çakışıyor. Bayes hata oranı regresyon ortamındaki azaltılamaz hataya denk geliyor.

##### K-Nearest Neighbors

Teoride her zaman Bayes sınıflandırıcısını kullanmak isteriz. Ancak gerçek veriler için Y’nin X değerlerine bağlı koşullu olasılık dağılımını bilmeyiz; bu nedenle Bayes sınıflandırıcısını kullanmak imkansızdır. Bu yüzden, Bayes sınıflandırıcısı ulaşılamaz bir altın standarttır ve diğer metotlar bununla kıyaslanarak değerlendirilir. Y‘nin X‘e bağlı koşullu olasılık dağılımını hesaplamaya yönelik birçok yaklaşım var. Bunlardan biri de En Yakın K Komşu Sınıflandırıcısı(K-Nearest Neighbors or KNN)‘dır. Elimizde training ve test veri setleri olsun. Test verisetindeki bir gözlemin hangi sınıfa ait olacağını hesaplamak için KNN algoritması ilk olarak bu test gözlemine training veri setindeki  en yakın K gözlemi  (N0) bulur. Sonrasında bu en yakın K gözlemin sınıf dağılımını hesaplar.

Hesapladıktan sonra KNN sınıflandırıcısı Bayes kuralını uygular ve test gözlemini (x0) en yüksek olasılık değerine sahip sınıfa atar.

Yukarıdaki görselle birlikte KNN metodunu açıklamaya çalışalım. Sol tarafta 6 mavi ve 6 turuncu gözlemden oluşan küçük bir training veri seti gösteriliyor. Amacımız x ile gösterilen gözlem için sınıf tahminlemek. Diyelim ki K değerini 3 olarak seçtik. KNN ilk olarak bu gözleme en yakın 3 gözlemi bulacaktır. En yakın üç gözlemden ikisi mavi biri ise turuncu sınıfa ait gözüküyor ve bu gözlem için tahminimiz 2/3 olasılıkla mavi sınıf 1/3 olasılıkla turuncu sınıf olarak hesaplanıyor. Dolayısıyla KNN bu gözlem için mavi sınıf tahminliyor. Sağ tarafta ise KNN metodunu K=3 ile mümkün olan bütün X1 ve X2 değerleri için uyguladık ve KNN karar sınırını (KNN decision boundary) belirledik.

Çok basit bir yöntem olmasına rağmen KNN şaşırtıcı bir şekilde çoğu zaman optimal Bayes Sınıflandırıcısına yakın sınıflandırıcı üretiyor.

Aşağıdaki figür KNN‘in K=10 ile 100 adet gözleme uygulandığında elde edilen karar sınırını gösteriyor. Gerçek dağılım KNN sınıflandırıcısı tarafından bilinmemesine rağmen, KNN karar sınırı Bayes karar sınırına çok yakın. Test  hata oranı KNN ile 0.1363. Bu oran Bayes hata oranı olan 0.1304’e son derece yakın!

K’nin seçimi KNN sınıflandırıcısı üzerinde son derece önemli etkilere sahip. Aşağıdaki görselde K = 1 ve K = 100 iken elde edilen KNN karar sınırını görebilirsiniz. K=1 iken karar sınırı son derece esnek ve Bayes karar sınırında olmayan bazı örüntüler bulmuş. Bu düşük taraflılığa fakat son derece yüksek varyansa sahip bir sınıflandırıcıya denk geliyor. K arttıkça, metot daha az esnek olmaya başlıyor ve doğrusala yakın karar sınırları üretmeye başlıyor. Bu düşük  varyanslı fakat yüksek taraflılıklı sınıflandırıcıya denk geliyor.

Tıpkı regresyonda olduğu gibi, sınıflandırmada da training ve test hata oranları arasında güçlü bir ilişki yok.  K=1 olduğunda KNN training hata oranı 0 oluyor fakat test hata oranı oldukça fazla olabilir. Genel olarak, daha esnek sınıflandırma metotları kullandığımızda training hata oranı azalacaktır ancak test hata oranı azalmayabilir. Aşağıdaki figürde KNN test ve training hataları 1/K‘nin bir fonksiyonu olarak gösteriliyor.  1/K arttıkça yani K azaldıkça, metot daha çok esnekleşiyor. Regresyonda olduğu gibi, tranining hata oranı esneklik arttıkça hep azalıyor. Fakat test hata oranı gene U şeklini gösteriyor: en başta azalıyor(K=10 iken minimum oluyor) fakat belirli bir esneklik noktasından sonra tekrar artmaya başlıyor ve veriye aşırı uydurma (overfitting) gerçekleşiyor.

Hem regresyonda hem de sınıflandırmada, esneklik seviyesini doğru seçmek herhangi bir istatistiksel öğrenme metodunun başarısı için kritik derecede önemli. Taraflılık-varyans dengesi, ve bunun sonucunda oluşan U şeklinde test hata oranı bu seçimi zor bir işe dönüştürüyor. Test hata oranını hesaplamak ve optimum esneklik seviyesini seçmek için oluşturulan metotları ileriki yazılarda ayrıntılı olarak ele alacağız.