学习帖， 每天总结今天学习成果

今天准备看推荐系统

Restrictive assumption on linear regression:
First, additive assumption: the effect of changes of x on Y is independent of values of other predictors.
Second, linear assumption: the change of Y due to one unit change of x is constant, regardless of the value of x.

Hierarchical principle:
If we include the interaction term, we need to include the individual term even if they are not statistically significant.

Potential problems for linear regression:
Non linearity of data:
Residual plots (residuals vs fitted values), if residuals show a pattern, there might be a non-linear relationship. To solve this, we can use non-linear transformations on the predictors.

Correlation of error term:
The standard error calculated for the regression coefficients or the fitted values is based on the assumption of uncorrelated error terms. If there is correlation, the calculated standard error term will be smaller than the true standard error. So, the prediction and confidence interval are narrower than they should be. The p-value is smaller than they should be. In short, if the error term is correlated, we will have an unwarranted confidence in our model.
Using residual plots can check whether they are correlated.
An extreme case, if we double our data, the confidence interval will be narrower by a factor of sqrt(2).

Non-constant variance of error terms:
An important assumption: var(epsilon_i) = sigma^2. This assumption can be checked by using residual plots. If the residuals become larger and larger along with fitted values. There might be non-constant variance. This can be solved by transforming the response using a concave function.

Outliers:
Outliers are points which the response is unusual given the predictors. Outliers can be good or bad. It can be detected by the residual plots or studentized residual plots. The studentized residual is residual divided by standard error of residual.

High leverage points:
High leverage points have an unusual value for x. High leverage points tend to have a sizable impact on the estimated regression line.

Collinearity:
Collinearity means predictors are correlated with each other. Collinearity won’t influence the prediction accuracy of the model. But it will be difficult to separate the individual effects of collinear variables.
Rating and Limit are highly correlated with each other, if they are exactly same, this might be a straight line.
Collinearity causes the standard error for beta_j to grow, which means the t statistic will decline, it may fail to reject the null hypothesis.
To detect collinearity, a simple way is to look at the correlation matrix between predictors. But not all collinearity can be detected by this way, because there might be collinearity exist between three or more variables even if no pair of variables has a particularly high correlation. This situation is called multicollinearity.
Instead of inspecting the correlation matrix, a better way is to compute the variation inflation factor(VIF).
The smallest possible value for VIF is one. As a rule of thumb, a VIF value which exceeds 5-10 indicates a problem.

Logistic regression:
P(Y=1|X) = P(X) = exp(beta_0 + beta_1*X)/(1 + exp(beta_0 + beta_1*X))
Logistic regression directly models P(Y=k|X=x) using the logistic function.

In logistic regression, increasing X by one unit changes the log odds by beta_1 or equivalently it multiplies the odds by exp(beta_1). The amount that P(X) changes due to a one-unit change in X will depend on the current value of X.
The coefficients are estimated using the maximus likelihood method.
The likelihood function is:

The estimates are chosen to maximize the likelihood function.

Multiclass logistic regression is possible, but we often choose to use other methods.


Linear discriminant analysis:
The advantages of LDA:
When the classes are well-seperated, the logistic regression is unstable, LDA doesn’t suffer from this problem.
If n is small and the distribution of the predictors X is approximately normal in each of the classes, the LDA is more stable than logistic regression.
LDA is popular when we have more than two response classes.

F_k(x) = P(X=x|Y=k), we assume that f_k(x) is normal
P(Y=k|X=x) = P(X=x|Y=k)*P(Y=k)/P(X=x)
                = (f_k(x)*pi(k)/sum(f_k(x)*pi(k))), posterior probability

LDA assumes the variance of the predictors across the groups are same.

Take the log of P(Y=k|X=x), the result will be as follow:

Log(P(Y=1|X=x)) – log(P(Y=0|X=x)) = c_0 + c_1*x

ROC curve:
ROC (receiver operating characteristics), the y axis is True positive rate(sensitivity), the x axis is False positive rate(1 - specificity). Each point in the curve is a threshold. AUC (area under the curve), the larger the AUC, the better the classifier. AUC = 0.5 is a random guess.

ROC curve is useful to compare different classifiers, since they take into account all possible thresholds.

                        Predicted
                        Null        non-null
        Null                TN        FP                N
actual  non-null        FN        TP                P
                        N*        P*

FP rate                    FP/N(in all the actual negative observation, you misclassified negative as positive)
Also called Type one error, 1 – specificity(TN rate)

TP rate              TP/P(in all the actual positive observation, you misclassified positive as negative)
Also called 1 – Type two error, sensitivity, power, recall

Positive pred value.          TP/P*(in all the predicted positive observation, you correctly predicted positive)
Also called precision, 1 – false discovery proportion

Negative pred value.                 TN/N*

Quadratic discriminant analysis:
LDA assumes the observations in each class come from multivariate normal distribution with a class specific mean vector and a covariance matrix which is common to all K classes.
The only difference between QDA and LDA is QDA assumes each class has a class specific covariance matrix, which will make the decision function a quadratic function.

The choice between LDA and QDA is about bias-variance trade off.

Comparison of different classifiers:
For the binary classification, the decision boundary of logistic regression and LDA is both linear. The only difference is the coefficients of logistic regression come from maximum likelihood method, LDA comes from the estimated mean and covariance from a normal distribution.
The LDA can outperforms if the normal distribution assumption and equal covariance is well met.
KNN dominates when the decision boundary is highly non-linear.
QDA stays between KNN and (logistic regression, LDA).

Lean analytics

Chapter 1 We are all liars
Concierge Minimum Variable Product
The MVP is the product that is the bare minimum needed to test your hypotheses.  The MVP is the smallest thing you can build that will do the same thing you promise to the market. The MVP prevents you from building a product before you have an idea of anyone need it.
The concierge MVP uses human to do the product work.
For example, you are building a dating app. Instead of building a product which automatically match two similar people based on complex algorithms, you can hire people to do the work. Manually collecting information from two people, calculate similarity based on algorithm, send back the result, get the feedback.
During this process, you will learn a ton about the early user and the value of the potential product you are offering.
The beauty of the Concierge MVP is that you can test your hypothesis without building a product at all.
The user know they are interacting with a human.

The wizard of OZ MVP
What if we want the user to think they are interacting with an automated product? We can wrap a technical shell on the humans.
For example, we want to provide a travelling service where user type complicated request, and your company plans the perfect trip for them. After they submit the request in the web, we can give response that the algorithm is dealing with this, human can easily handle different requirements. After human finished the plan, send back the result.
This will make user believe they are interacting with the true product. And it is more related the future behavior of the true product.

Use the C MVP when you are not confident about customer and want more customer interaction.

Use the OZ MVP when you want to evaluate the influence of your product and hide the human.

Book given an example about Airbnb. Airbnb provides a professional photography service for the hosts.
The general procedure is:
First, Airbnb’s team had a hunch that better photos would increase rentals.
They test the idea with C MVP, before launching the service in the app, they manually provide the service for the hosts.
The experiment showed good results, they built the necessary component and provided it to the customer.

Chapter 2 How to keep score
A good metric changes the way you behave.
Quantitative and qualitative metric
Qualitative data usually comes from survey on humans.

Vanity metric
Vanity metric might make you feel good, but it won’t change how you act.
For example, ‘Total sign ups’, ‘Total active users’ are vanity, they will keep growing if you don’t make large mistakes.
‘Percent of users active’ which tells you the engagement of your users. That means you can experiment, learn, and iterate with it.

Leading and lagging metrics
Both leading and lagging metrics are useful, but they serve different purposes. A leading metric tries to predict the future. A lagging metric gives you an indication that there is a problem.
A lagging metric for one group in a company is a leading metric for another. For example, The number of quarterly booking is a lagging metric for salespeople, but for the finance department, they are leading indicator of expected revenue.

Correlated and causal metrics
Correlation is good, causality is great. Sometimes you may have to settle for the former-but you should always be trying to discover the latter.

Segments:
Segments is simply a group that shares some common characteristic.

Cohort analysis:
Comparison similar group along a timeline. For example, track the spending of the customer after they sign up.

A/B test:
Change one thing and measure the result.

Multivariate analysis:
Change several things at once to see which correlated with a result.
                                                        Without data  find some to try
                                                        /
Start  choose a KPI  draw a baseline for KPI 
                                                        \
                                                        With data  find good users who are doing
                                                                                                       
things you want them to do  find attribute these users share that’s correlated with the KPI

     just do it, make changes to the business that target the commonality
   /

\
Design A/B test or multivariate experiments  implement the winning solution  measure
                                                              Yes  Done
                                                             /
the effect on the KPI  Did the KPI move past the line?
                                                            \
                                                              No   Talk to customer, draw a new line  how to improve KPI again

今天看了introduction to statistical learning.
Simple linear regression:
F(x) = beta_0 + beta_1 * x         <>         E(Y|x) = beta_0 + beta_1 * x

Parametric methods:
The parametric methods include two step model based approach: First we make an assumption about the function form or shape of f. Second, we create a procedure that uses the training data to fit or train the model.
The advantage of parametric methods is it simplifies the problem. It reduces the problem from estimating f to estimate a set of parameters. And it is more interpretable like linear regression.
The disadvantages are the model we choose usually doesn’t match the true unknow form f. We can use more flexible models, but we need to avoid overfitting problems.

Non Parametric methods:
Non parametric method don’t make explicit assumption on the functional form. It seeks an estimate of f that gets as close to the data points as possible without being wiggly or too rough.
The advantage is by avoiding the assumption of a particular functional form for f, they can fit a wide range shapes of f.
The disadvantage is it doesn’t reduce the problem, so usually it requires a larger amount of data than parametric methods.

Bayes classifier:
If we know the distribution of x given y(y is different classes, x is predictors, almost impossible in real life, p(x|y)), and the proportion of y(p(y), easy access), we can know the joint distribution, then by sum y, get the marginal distribution(p(x)).
Using bayes rule, we can get p(y|x). Every time we choose the max of p(y = i | x)

The curse of dimensionality:
Nearest neighbors can be good for small p, p <= 4 and large N. But if the dimension is very high, the data points become sparse and they will be non-local. It will require more data as the dimension increases.

Bias-Variance trade off:
Assume we can have a lot of training data sets.
Variance is if we change the training data set, how much f_hat will change. In general, more flexible models have higher variance. It comes from different training data sets.
Bias is defined as the difference between the estimator’s expected value and the true value of the parameter. It refers to the error which uses a much simpler model to approximate complicated real-life problem, also uses a much complicated model to approximate simple problem. In general, more flexible models have less bias.
(Here we use flexible, not related to complicated or simple model.)
There are a large number of training sets, we can estimate a different f_hat from each training set. There is one observation(x_0, y_0) in test data set, we will use each f_hat, get the squared error, take an average on all training data sets. This is the left part in (2.7).  The right part has variance of different predictions for this point, the bias of predictions for this point(the mean of prediction from different training data sets – true prediction), the irreducible error term.

Hypothesis testing for linear regression:
t-test
First we use beta_1 and its standard error to compute t statistics which follow t distribution, then you get p-value which is the probability of observing any value equal or larger than |t|.
F-test
Null is all the parameters are 0, alternative is at least one of them is not 0. First, we compute F statistics . If the null hypothesis is true, it will follow a F distribution. And the F statistics will close to 0. Also we will use p-value to decide the significance.

Above is for whole effect of the predictors, we can also calculate the partial effect, we drop one predictor, calculate the RSS_0, F will be ((RSS_0 - RSS)/1)/(RSS/(n-p-1)), the value will be same as the t statistic when you fit the whole model. Why we still use F statistic as we can check t statistics? Because if the number of predictors are large like 100, even if the null hypothesis of F test is true, there is still a 5% of the p values will be below 0.05. So t statistics are not reliable. F statistics adjusted by the number of predictors.

Unbiased parameters:
Let’s see the simplest case. We want to estimate the mean of a population. We can only access a sample data set(y_1, y_2, …, y_n) from the population. We use the average of the data set to estimate the population mean. This estimate may be biased, it might overestimate the population mean, or underestimate. But if we have a lot of data sets, average the mean of them, the result will be unbiased.

R square:
R square is calculated by (total sum of squares – residual sum of squares)/total sum of squares, total sum of squares means if no model, just use mean to predict, what is the error. Residual sum of squares means by using the model, what is the error. The result of minus means how much of variance reduce by using the model.

Multicollinearity problem:
If x1, x2, …, xp are orthogonal to each other, which means they are independent, then the parameter estimates will only rely on that predictor. This is ideal case, which means we can change the predictor while holding other vectors. However, in real life, this can never happen.

If there are multicollinearity predictors, the variance of the coefficients will be larger(which is a little complicated computation, but it relates to project one predictor to another predictor, if they are identical, the projection length will be small, and it is on the denominator, so the variance will be large), then it will influence the hypothesis test, because the denominator is the variance of the coefficients, it will also influence the confidence interval. So the explanation of the coefficient, because change one predictor, other predictors change.

Recommend systems use a number of different technologies. We can classify these systems into two broad groups.

Content based systems:

This method requires to define the features of the item. First, each item is represented by a d dimensional vector. For each user, it has a user profile which average or weighted average the item profile. We will recommend items which is close to the user. For instance, if a Netflix user has watched many cowboy movies, then you can recommend him movies which have ‘cowboy’ genre.

Utility matrix is the user-item matrix, the value can be a Boolean value or a rating value. If it is the Boolean value, simply aggregate the item profile which the user like and take an average. If it is the rating value, first normalize the rating then do a weight average on the item profile.

This method has some advantages: First, you don’t need other user’s data to start recommendation. Second, it can recommend new and unpopular items. Third, it can find users’ unique taste. Fourth, it is easy to understand.

It also has some disadvantages: First, it is hard to define the features of the item and it costs time. Second, it can’t jump outside of the user’s profile. Third, it provides substitutes instead of complements.

Discovering Features of Documents:

For a bunch of documents, first, we remove stop words; Second, we compute the TF.IDF score for each word in the document.

TF.IDF: term frequency inverse document frequency. Term frequency (tf) is the frequency of the word in this document. Inverse document frequency (idf) is the total number of documents divided by the the number of documents which have this word.

The formula is: TF.IDF = tf * log(N/df), N is the number of all documents.

AB testing:

Do we need to use AB testing for every change?
AB testing can help you climb the mountain. But it won’t help if you want to move from one peak to another peak.

AB testing can be useful in many areas, but what is AB testing can’t do?
AB testing can’t be used for testing new user experience.
AB testing should be used in short amount volume situation, like google, amazon, wayfair. But not useful for apartment rental, because the react can be slow, even to week or month.
AB testing can’t tell you the weakness or missing.

Example:
An online course website wants to change the button from orange to pink.
The null hypothesis is changing the button will not increase the metric.
Potential metric:
Total number courses completed. (Complete a course take a long time, it might not help)
Number of clicks.
Number of clicks/Number of page views. (click through rate)
Unique visitors who click/unique visitors to page. (click through probability)

A: click 0 time; B: click 5 times.
CTR = 5/2 = 2.5
CTP = ½ = 0.5

Rate measures the usability of the site. For example, the usability of that button.
Probability measures the total impact. For example, how many users enter the next page.
Depending on how to technique you used, the metric can be further extended to :
Cookie probability: For a time interval, number of cookies click divided by number of cookies
Pageview probability: For a time interval, number of page views with a click divided by number of page views

Hypothesis testing:
Null: P_control = P_experiment  Alternative: P_controal != P_experiment
D = P_control – P_experiment, D_hat = P_control_hat – P_experiement_hat
D_hat ~ N(0, SE(D_hat)),  SE(D_hat) = sqrt(D_hat*(1 – D_hat)/N)
For 95% confidence, which means alpha = 5%, if D_hat < -1.96*SE(D_hat) or D_hat > 1.96*SE(D_hat): we reject the null hypothesis.

Alpha = P(reject null|null true)  (False positive) | significance level
Beta = P(not reject null|null false) (False negative)
1 – Beta = P(reject null|null false) (True positive)  | Statistical power | sensitivity
1 – Alpha = P(not reject null | null true) (True negative) | confidence level

                        Predicted
                        Null True                null False
Actual Null True        1 - alpha                alpha
         Null False        Beta                        1 - Beta
If the sample size is small, alpha is small, but beta is large.

If the sample size is large, the alpha stays same, but beta will be small.


By increasing the sample size, the statistical power will increase.

What we need to decide the sample size?
The base line target without changing anything.
The minimum detectable effect: The Minimum Detectable Effect is the smallest effect that will be detected (1-beta) % of the time. (practical significance level)
The statistic power 1 - beta and the significance level alpha.

For click through rate:
The control group: N_c page views, n_c clicks the product
The experiment group: N_e page views, n_e clicks the product
The practical significance level: 2%
Confidence level: 95%  | significant level: 5% | Z score 1.96
General probability: P = (n_c + n_e)/(N_c + N_e)
Standard error: SE = sqrt (P*(1 - P)/N)
Click through rate difference: diff_hat = abs (n_c/N_c – n_e/N_e)
Confidence interval: [p – 1.96*SE, p + 1.96*SE]

Resampling methods:
Two main resampling methods: cross validation and bootstrap.
Leave one out cross validation (LOOCV):
N samples in the data set, each time using N-1 samples as training data set, 1 sample as validation data set. Train the model on training data set, test the result on testing data set. Repeat this process N times, each observation in data set will be tested once, average the results, get the final validation error.
Advantages of this method:
First, less bias, using more data in the training data tends not to overestimate the test error rate.
Second, won’t have the problem due to random splitting, because each observation will be excluded once.
Disadvantages of this method:
Expensive to implement, but for the least squares linear or polynomial regression, there is a shortcut to make the cost of LOOCV the same as a single model fit.

The bias and variance trade off between LOOCV and K fold validation:
LOOCV uses N-1 data points to train the model, so the bias is lower than K fold validation. However, the training data sets of LOOCV are more correlated than K fold validation. The mean of many highly correlated quantities has larger variance than does the mean of many quantities that are not as highly correlated. So, the test error estimate from LOOCV tends to have higher variance than K fold CV.

Bootstrap:
For simulated data, we can simulate infinite amount of data sets. But the real world data is finite. So, if we want to quantify the uncertainty of an estimator or statistical learning method. The bootstrap method can be used. It resamples from the data set with replacement.

Imbalance classification response
The response of the data may have majority class and minority class.
There are several methods which can solve this problem:
First, undersampling:
It reduces the number of observations from majority class to make the data set balanced. There are two types: random and informative.
The disadvantage of this method is losing information contained in majority class.
Second, oversampling:
It replicates the observations from minority class. There are two types: random and informative.
The advantage of this method is there is not information loss. The disadvantage is it may lead to overfitting problem. The accuracy of training data may be high, but the accuracy of testing data may be low.
Third, synthetic data generation:
Instead of adding or removing the observations, it creates artificial data. It is also an oversampling technique. Synthetic minority oversampling technique (SMOTE) is a powerful and widely used method.
Fourth, cost sensitive learning:
We can adjust the cost metric to fit for the different needs. Like add different penalty for false positive, or false negative.

今天刷sqlzoo, 刷到了join结束

今天刷完了sqlzoo

今天刷完了leetcode 上的sql 题
看了 lean analytics
Chapter 3: Deciding what to do with your life

Chapter 4: Data-driven versus data-informed
10 things to avoid as a data scientist:
1 assuming the data is clean
2 Not normalizing
3 excluding outliers
4 including outliers
5 ignoring seasonality
6 ignoring size when reporting growth
7 data vomit
8 metrics that cry wolf
9 The ‘Not collected Here’ syndrome
10 focusing on noise

Chapter 5: Analytics frameworks
Dave McClure’s Pirate Metrics:
Acquisition, activation, retention, revenue, referral – AARRR
Element                function                        relevant metrics
Acquisition                generate attention through        traffic, mentions, cost per click, search
(获得)                        a variety of means                results, cost of acquisition, open rate

Activation                turn the resulting drive-by        enrollments, signups, completed
                        Visitors into users who are         on boarding process, used the service
                        Enrolled                        at least once, subscriptions

Retention                convince users to come        engagement, time since last visit, daily
(保留)                        back repeatedly, exhibit        and monthly active use, churns
                        Sticky behavior

Revenue                 business outcome (which        customer lifetime value, conversion rate,
Vary by your business model        shopping cart size, click through revenue
Purchases, ad clicks, content
Creation, subscriptions)
       
Referral                 viral and word-of-mouth        invites sent, viral coefficient, viral cycle time
                        Invitations to other potential
                        Users

Chapter 6: The discipline of one metric that matters