{"id":363450,"date":"2024-05-21T01:56:09","date_gmt":"2024-05-21T01:56:09","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=363450"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=363450","title":{"rendered":"<span>3. Information theory and ML. Forecast<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p><a href=\"https:\/\/habr.com\/en\/articles\/763090\/\" rel=\"noopener noreferrer nofollow\">Part 1 &#8212; Entropy<\/a><\/p>\n<p><a href=\"https:\/\/habr.com\/en\/articles\/764942\/\" rel=\"noopener noreferrer nofollow\">Part 2 &#8212; Mutual Information<\/a><\/p>\n<p>In this third part, we will discuss Machine Learning, specifically the prediction task in the context of information theory.<\/p>\n<p>The concept of Mutual Information (MI) is related to the prediction task. In fact, the prediction task can be viewed as the problem of extracting information about the signal from the factors. Some part of the information about the signal is contained in the factors. If you write a function that calculates a value close to the signal based on the factors, then this will demonstrate that you have been able to extract MI between the signal and the factors.<\/p>\n<h2>What is Machine Learning?<\/h2>\n<p>To move forward, we need fundamental concepts from Machine Learning (ML), such as factors, target, loss function, training and test sets, overfitting and underfitting and their variations, regularization, and different types of data leakage.<\/p>\n<p><strong>Factors (features)<\/strong> are what you input, and <strong>the signal (target)<\/strong> is what you need to predict using the features. For example, if you need to forecast the temperature <strong>tomorrow at 12:00<\/strong> in a specific city, that&#8217;s the target, while you are given a set of numbers <strong>about today and previous days<\/strong>: temperature, pressure, humidity, wind direction, and wind speed in this and neighboring cities at different times of the day \u2013 these are the features.<\/p>\n<p><strong>Training Data<\/strong> is a set of examples (also known as samples) with known correct answers, meaning rows in a table that contain both the feature fields (features = (f1, f2, &#8230;, fn)) and the target field. Data is commonly divided into two parts \u2013 <strong>the training set<\/strong> and <strong>the test set<\/strong>. It looks something like this:<\/p>\n<p><strong>Training set:<\/strong><\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"left\"><strong><em>id<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>1<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>2<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>&#8230;<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>target<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>predict<\/em><\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">1<\/p>\n<\/td>\n<td>\n<p align=\"left\">1.234<\/p>\n<\/td>\n<td>\n<p align=\"left\">3.678<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">1.23<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">2<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.345<\/p>\n<\/td>\n<td>\n<p align=\"left\">6.123<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.34<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">18987<\/p>\n<\/td>\n<td>\n<p align=\"left\">1.432<\/p>\n<\/td>\n<td>\n<p align=\"left\">3.444<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;.<\/p>\n<\/td>\n<td>\n<p align=\"left\">5.67<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p><strong>Test set:<\/strong><\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"left\"><strong><em>id<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>1<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>2<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>&#8230;<\/strong><\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\"><strong><em>target<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>predict<\/em><\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">18988<\/p>\n<\/td>\n<td>\n<p align=\"left\">6.321<\/p>\n<\/td>\n<td>\n<p align=\"left\">6.545<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">4.987<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">18989<\/p>\n<\/td>\n<td>\n<p align=\"left\">4.123<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.348<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">3.765<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">&#8230;.<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">30756<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.678<\/p>\n<\/td>\n<td>\n<p align=\"left\">3.187<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">2.593<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>In broad terms, the prediction task can be formulated in a Kaggle-style competition:<\/p>\n<p><strong>Prediction Task (ML Task):<\/strong> You are given a training set. Implement a function <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(f_1, \\ldots, f_k)\" alt=\"\\mathcal{P}(f_1, \\ldots, f_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b6a\/99e\/ec0\/b6a99eec0b564a7ca4a879a26f186365.svg\" width=\"109\" height=\"22\"\/> in code that, based on the given features, returns a value as close as possible to the target. The measure of closeness is defined by a loss function, and the value of this function is called the prediction error: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"error = Loss(predict, target)\" alt=\"error = Loss(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2a2\/503\/9c7\/2a25039c70d2454d97c471cff25267db.svg\" width=\"245\" height=\"22\"\/>, where <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict = \\mathcal{P}(f_1, \\ldots, f_k)\" alt=\"predict = \\mathcal{P}(f_1, \\ldots, f_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/374\/373\/0f5\/3743730f5d17023a8112bd4b927763d1.svg\" width=\"195\" height=\"22\"\/>. <strong>The quality of the prediction<\/strong> is determined by the average error during the application of this prediction in real-life scenarios, but in practice, a test set hidden from you is used to evaluate this average error.<\/p>\n<p>The quantity <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi = predict - target\" alt=\"\\xi = predict - target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/161\/5e2\/47c\/1615e247c5274a609fccd357ffb7891c.svg\" width=\"168\" height=\"20\"\/> has a special name &#8212; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Errors_and_residuals\" rel=\"noopener noreferrer nofollow\">the residual<\/a>. Two popular variants of loss functions for predicting real values are:<\/p>\n<ul>\n<li>\n<p>Mean Squared Error (MSE) &#8212; also known as the average squared residual.<\/p>\n<\/li>\n<li>\n<p>Mean Absolute Error (MAE) &#8212; also known as the L1 error.<\/p>\n<\/li>\n<\/ul>\n<p>In practice, the ML task is more general and high-level. Specifically, you need to develop a moderately universal <strong>ML model<\/strong> &#8212; a way to get functions <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(f_1, \\ldots, f_n)\" alt=\"\\mathcal{P}(f_1, \\ldots, f_n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6c4\/7cc\/817\/6c47cc817fcd694e36bad7d3f29667a4.svg\" width=\"110\" height=\"22\"\/> from a given training set and a specified loss function. You also need to perform <em>model evaluation<\/em>: monitor the prediction quality in a working system, be able to update trained models (step by step, creating new versions, or modifying the model&#8217;s internal weights in an online mode), improve the model&#8217;s quality, and control the cleanliness and quality of the features.<\/p>\n<p>The process of getting the function <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(f_1, \\ldots, f_n)\" alt=\"\\mathcal{P}(f_1, \\ldots, f_n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c74\/20d\/3a6\/c7420d3a63f024308d391e7dcf2fa2fd.svg\" width=\"110\" height=\"22\"\/> from the training set is called <strong>training<\/strong>. Popular classes of ML models include:<\/p>\n<ul>\n<li>\n<p><strong>Linear Mode<\/strong>l<strong>:<\/strong> In a linear model, where <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(f_1, \\ldots, f_n) = \\sum_{i} w_i \\cdot f_i\" alt=\"\\mathcal{P}(f_1, \\ldots, f_n) = \\sum_{i} w_i \\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/efc\/c9f\/260\/efcc9f26039c0e426903455ea484804c.svg\" width=\"217\" height=\"45\"\/>, the training process typically involves parameter tuning <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w_1, w_2, ..., w_n)\" alt=\"(w_1, w_2, ..., w_n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b2\/d81\/c7f\/3b2d81c7f4c8cf566a1d66ab9ec26e9f.svg\" width=\"136\" height=\"22\"\/>, usually done through <a href=\"https:\/\/en.wikipedia.org\/wiki\/Gradient_descent\" rel=\"noopener noreferrer nofollow\">gradient descent<\/a>.<\/p>\n<\/li>\n<li>\n<p><strong>Gradient Boosted Trees (GBT):<\/strong> GBT is a model where the function looks like a sum of multiple terms (hundreds or thousands), with each term being <a href=\"https:\/\/en.wikipedia.org\/wiki\/Decision_tree\" rel=\"noopener noreferrer nofollow\">a decision tree<\/a>. In the nodes of these trees, there are conditions based on the features, and in the leaves, specific numbers are assigned. Each term can be thought of as a system of nested if-conditions on feature values, with simple numbers in the final leaves. GBT is not just about the solution being a sum of trees but also a specific algorithm for getting these terms. There are many ready-made programs for training GBT, such as <a href=\"https:\/\/catboost.ai\/\" rel=\"noopener noreferrer nofollow\">CatBoost<\/a> and <a href=\"https:\/\/github.com\/dmlc\/xgboost\" rel=\"noopener noreferrer nofollow\">xgboost<\/a>.<\/p>\n<\/li>\n<li>\n<p><strong>Neural Networks:<\/strong> In its simplest basic form, a neural network model appears as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f}) = W_k\\odot W_{k-1}\\odot \\ldots W_1 \\odot \\vec{f}\" alt=\"\\mathcal{P}(\\vec{f}) = W_k\\odot W_{k-1}\\odot \\ldots W_1 \\odot \\vec{f}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/005\/1db\/606\/0051db60619c1c2c3b2bb1eeed0912c0.svg\" width=\"281\" height=\"27\"\/><\/em>,  , where <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"W_j\" alt=\"W_j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b3\/4dd\/4fb\/3b34dd4fb5bd40cbf2e6281d45b53aee.svg\" width=\"26\" height=\"22\"\/> are matrices, and their sizes are determined by the model developer. The features are represented as a vector <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\vec{f} = |f_1, \\ldots, f_n|^{T}\" alt=\"\\vec{f} = |f_1, \\ldots, f_n|^{T}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/903\/64d\/6ab\/90364d6abd7d152faa315d339b3f952d.svg\" width=\"143\" height=\"26\"\/>, and the operator <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\odot\" alt=\"\\odot\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a75\/e64\/e0b\/a75e64e0bfcee963a5ab8ba4bcf206bc.svg\" width=\"15\" height=\"16\"\/> represents element-wise multiplication of a vector by a matrix followed by setting all negative values in the resulting vector to zero. Operators are applied from right to left, which is important in the case of this zeroing. The matrices are referred to as layers of the neural network, and the number of matrices determines the depth of the network. Instead of zeroing negatives, various other non-linear transformations can be applied. Without non-linear transformations after the matrix multiplication, all matrices could be collapsed into one, and the space of possible functions would not differ from what a linear model defines. I described a linear architecture for a neural network, but more complex architectures are possible. For instance:<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=W_6\\odot(W_1\\odot W_2 \\cdot \\vec{f}  + W_3\\odot W_4 \\odot W_5\\odot W_2\\odot \\vec{f})+W_7\\odot \\vec{f}\" alt=\"\\mathcal{P}(\\vec{f})=W_6\\odot(W_1\\odot W_2 \\cdot \\vec{f}  + W_3\\odot W_4 \\odot W_5\\odot W_2\\odot \\vec{f})+W_7\\odot \\vec{f}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b15\/324\/6b7\/b153246b7a3f25a308908bc4be6a33fa.svg\" width=\"574\" height=\"27\"\/><\/em>.    <\/p>\n<p>In addition to various element-wise non-linear transformations and matrix multiplications, neural networks can use operators for scalar vector products and element-wise maximum operations for two vectors of the same dimension, combining vectors into a longer one, and more. You can think of a general architecture for <strong>the prediction function<\/strong>, where a vector is input, and then the response is constructed using operators <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{+, -, \\cdot, \\max \\}\" alt=\"\\{+, -, \\cdot, \\max \\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/16e\/cab\/630\/16ecab630d42869a7a01535afd369c9b.svg\" width=\"116\" height=\"22\"\/>, non-linear functions <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{\\tanh, \\mathrm{abs}, \\max(0, \\cdot), \\ldots\\}\" alt=\"\\{\\tanh, \\mathrm{abs}, \\max(0, \\cdot), \\ldots\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/948\/15c\/575\/94815c5757876f104027b22b7432dde2.svg\" width=\"209\" height=\"22\"\/>, and weights <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{w_1, w_2, \\ldots\\}\" alt=\"\\{w_1, w_2, \\ldots\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/720\/ef3\/ea5\/720ef3ea54f4a79d52bc9a8094c4d3b9.svg\" width=\"104\" height=\"22\"\/>. In this sense, neural networks can represent functions of quite a general form. In reality, the architecture of the function <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}\" alt=\"\\mathcal{P}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/095\/33f\/322\/09533f322253f47a0c350fc7361fa806.svg\" width=\"14\" height=\"18\"\/> is called a neural network when it contains something resembling a chain like <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"W_k\\odot W_{k-1}\\odot \\ldots W_1 \\odot \\vec{f}\" alt=\"W_k\\odot W_{k-1}\\odot \\ldots W_1 \\odot \\vec{f}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7d4\/22a\/479\/7d422a479dc5fc931024a9ff00e55970.svg\" width=\"209\" height=\"26\"\/>. Essentially, we have a regression problem &#8212; to adjust parameters (weights) in a parametrically defined function to minimize the error. There are numerous methods for training neural networks, most of which are iterative, and the module responsible for weight updates is what programmers refer to as <a href=\"https:\/\/habr.com\/en\/articles\/318970\/\" rel=\"noopener noreferrer nofollow\">an optimizer<\/a>, such as <a href=\"https:\/\/In%20addition%20to%20various%20element-wise%20non-linear%20transformations%20and%20matrix%20multiplications,%20neural%20networks%20can%20use%20operators%20for%20scalar%20vector%20products%20and%20element-wise%20maximum%20operations%20for%20two%20vectors%20of%20the%20same%20dimension,%20combining%20vectors%20into%20a%20longer%20one,%20and%20more.%20You%20can%20think%20of%20a%20general%20architecture%20for%20the%20prediction%20function,%20where%20a%20vector%20is%20input,%20and%20then%20the%20response%20is%20constructed%20using%20operators%20%7B+,%20-,%20%5Ccdot,%20%5Cmax%20%7D,%20non-linear%20functions%20%7B%5Ctanh,%20%5Cmathrm%7Babs%7D,%20%5Cmax(0,%20%5Ccdot),%20%5Cldots%7D,%20and%20weights%20%7Bw_1,%20w_2,%20%5Cldots%7D.%20In%20this%20sense,%20neural%20networks%20can%20represent%20functions%20of%20quite%20a%20general%20form.%20In%20reality,%20the%20architecture%20of%20the%20function%20%5Cmathcal%7BP%7D%20is%20called%20a%20neural%20network%20when%20it%20contains%20something%20resembling%20a%20chain%20like%20W_k%5Codot%20W_%7Bk-1%7D%5Codot%20%5Cldots%20W_1%20%5Codot%20%5Cvec%7Bf%7D.%20Essentially,%20we%20have%20a%20regression%20problem%20-%20to%20adjust%20parameters%20(weights)%20in%20a%20parametrically%20defined%20function%20to%20minimize%20the%20error.%20There%20are%20numerous%20methods%20for%20training%20neural%20networks,%20most%20of%20which%20are%20iterative,%20and%20the%20module%20responsible%20for%20weight%20updates%20is%20what%20programmers%20refer%20to%20as%20an%20optimizer,%20such%20as%20AdamOptimizer,%20for%20example.\" rel=\"noopener noreferrer nofollow\">AdamOptimizer<\/a>, for example.  <\/p>\n<\/li>\n<\/ul>\n<h2>ML Terminology<\/h2>\n<p>In <a href=\"https:\/\/en.wikipedia.org\/wiki\/Regression_analysis\" rel=\"noopener noreferrer nofollow\">regression analysis<\/a>, many important terms have emerged, allowing for a better understanding of the content of prediction tasks and avoiding common mistakes. These terms have been carried over into Machine Learning (ML) with little to no modification. Here, I will present the fundamental concepts, aiming to highlight their connections to information theory.<\/p>\n<h3>Overfitting<\/h3>\n<p><strong>Overfitting (retraining)<\/strong> occurs when the model you have selected is more complex than the actual reality underlying the target, and\/or when there is insufficient data to support training such a complex model. There are two main causes of <strong>overfitting<\/strong>: <\/p>\n<ul>\n<li>\n<p><strong>too complex model:<\/strong> The model&#8217;s structure is significantly more intricate than the reality or does not align with the complexity of the reality it&#8217;s intended to represent. It&#8217;s easier to illustrate this with a one-factor model.<br \/>Let&#8217;s say you have 11 data points in your training set <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(x, y) = (f_i, target_i)\" alt=\"(x, y) = (f_i, target_i)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dfa\/388\/7fd\/dfa3887fd170f32e1e776adf6a59f9c8.svg\" width=\"167\" height=\"22\"\/>, and your model is a 10th-degree polynomial. You can adjust the coefficients in the polynomial in such a way that it &#171;touches&#187; every data point in the training set, but this doesn&#8217;t guarantee good predictive performance.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/cc4\/175\/5ee\/cc41755ee89f94f97537b372cab9f20a.png\" alt=\"The blue line is a 10th-degree polynomial that was able to precisely replicate the training set of 11 points. However, the correct model is likely more linear (the black line), and the deviations from it are either noise or something explained by factors that we don't have.  \" title=\"The blue line is a 10th-degree polynomial that was able to precisely replicate the training set of 11 points. However, the correct model is likely more linear (the black line), and the deviations from it are either noise or something explained by factors that we don't have.  \" width=\"300\" height=\"204\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cc4\/175\/5ee\/cc41755ee89f94f97537b372cab9f20a.png\"\/><\/p>\n<div><figcaption>The blue line is a 10th-degree polynomial <br \/>that was able to precisely replicate the training set of 11 points. <br \/>However, the correct model is likely more linear (the black line), and the deviations from it are either noise or something explained by factors that we don&#8217;t have.  <\/figcaption><\/div>\n<\/figure>\n<\/li>\n<\/ul>\n<p>A polynomial of the 10th degree is an obvious and frequently used example of overfitting. Polynomials of low degrees with many variables can also lead to overfitting. For instance, you can choose a model like predict = a 3rd-degree polynomial of 100 factors (by the way, how many coefficients does it have?), while in reality, the prediction corresponds to a 2nd-degree polynomial of the factors plus random noise.  If you have a sufficient amount of data, classical regression methods can yield an acceptable result, and the coefficients for the 3rd-degree terms will be very small. These 3rd-degree terms will make a small contribution to the prediction for typical factor values (as in the case of interpolation). However, in the extreme values of the factors, where the prediction is more of an extrapolation than interpolation, the high-degree terms will have a noticeable impact and degrade the prediction quality. Moreover, when you have limited data, noise might be mistaken for true information, causing the prediction to try to fit every point in the training data.<\/p>\n<ul>\n<li>\n<p><strong>Insufficient training data:<\/strong> Your model may roughly match reality, but you might not have enough training data. Let&#8217;s use the polynomial example again: suppose both reality and your model are 3rd-degree polynomials of two factors. This polynomial is defined by 10 coefficients, meaning the space of possible predictors is 10-dimensional.  If you have 9 examples in your training pool, writing the equation &#171;polynomial(features<sub>i<\/sub>) = target<sub>i<\/sub>&#187; for each example will give you 9 equations for these coefficients, which is insufficient to uniquely determine the 10 coefficients. In the space of possible predictors, you will get a line, and each point on this line represents a predictor that perfectly replicates what you have in your training pool. You can randomly choose one of them, and there is a high probability that it will be a poor predictor. <\/p>\n<\/li>\n<li>\n<p><strong>Important note about training multi-parameter models. <\/strong>The above example may seem artificial, but the truth is that modern neural network models can contain millions of parameters or even more. For instance, the GPT-3 language model contains 175 billion parameters. <\/p>\n<p>If your model has N = 175 billion parameters, and the size of the training pool is M = 1 billion, you essentially have an infinite set of models that perfectly fit the training data, and this set is essentially a manifold of dimension N &#8212; M = 174 billion. <\/p>\n<p>In the case of deep multi-parameter neural networks, the <strong>&#171;insufficient train data&#187;<\/strong> effect becomes highly pronounced if handled incorrectly. Specifically, <strong>seeking the strict minimum of the error on the training pool results in a poor, overfitted predictor.<\/strong> <strong>This is not how things are done in practice.<\/strong> Various techniques and intuitions have been developed for training a model with <em>N<\/em> parameters on <em>M<\/em> examples, where <em>M<\/em> is significantly smaller than <em>N<\/em>. Regularization terms are added to the loss function (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Regularization_(mathematics)#Tikhonov_regularization\" rel=\"noopener noreferrer nofollow\">L2<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Regularization_(mathematics)#Regularizers_for_sparsity\" rel=\"noopener noreferrer nofollow\">L1<\/a>), <a href=\"https:\/\/en.wikipedia.org\/wiki\/Stochastic_gradient_descent\" rel=\"noopener noreferrer nofollow\">Stochastic Gradient Descent<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Dilution_(neural_networks)\" rel=\"noopener noreferrer nofollow\">Dropout Layers<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Early_stopping\" rel=\"noopener noreferrer nofollow\">Early Stopping<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Decision_tree_pruning\" rel=\"noopener noreferrer nofollow\">pruning<\/a>, and <a href=\"https:\/\/en.wikipedia.org\/wiki\/Regularization_(mathematics)\" rel=\"noopener noreferrer nofollow\">other techniques<\/a> are used. <br \/><strong>IMPORTANT: Understanding these techniques and knowing how to apply them largely defines expertise in machine learning.<\/strong>  <\/p>\n<\/li>\n<\/ul>\n<h3>Underfitting<\/h3>\n<p><strong>Underfitting<\/strong> occurs when the prediction model is simpler than reality. Just like in the case of overfitting, there are two main reasons for underfitting: <\/p>\n<ul>\n<li>\n<p><strong>too simplistic model:<\/strong> Choosing a model that is too simple and overly simplifies what is behind the target in reality. These cases are still encountered in production, and they are usually linear models. Linear models are appealing due to their simplicity and the presence of mathematical theorems that justify and describe their predictive abilities. However, it can be stated with confidence that if you decide to use linear models to predict currency exchange rates, weather, purchase probabilities, or credit repayment probabilities, you will get <strong>under-fitted weak model<\/strong>.<\/p>\n<\/li>\n<li>\n<p><strong>too early stopping:<\/strong> Training processes for models are typically iterative. If too few iterations are performed, an undertrained model results.<\/p>\n<\/li>\n<\/ul>\n<h3>Data leakage<\/h3>\n<p><strong>Data leakage<\/strong> is when, during training, you used information that exists in the test pool or data that is not available or differs from what will be available in practice when applying the model in real-life situations. Models that can take advantage of this leakage will have unreasonably low errors on the test pool and may be selected for real-world use. There are several types of <strong>data leakage<\/strong>:  <\/p>\n<ul>\n<li>\n<p><strong>Target leakage into factors:<\/strong> If, in a temperature prediction task, you add a factor &#8212; the average temperature for the past K days, and during training, some of the K days include the target day for which the prediction should be made, then you will get a flawed or non-functional predictor. More complex leaks can occur through features. In the case of predicting some future event, you must repeatedly ensure that when calculating features for the training pool, data got during or after that event is not used.<\/p>\n<\/li>\n<li>\n<p><strong>Simple test pool leakage:<\/strong> Sometimes it&#8217;s straightforward &#8212; rows from the test pool end up in the training pool.<\/p>\n<\/li>\n<li>\n<p><strong>Leakage through hyperparameter tuning:<\/strong> The rule that only the training pool should be used for training is deceptively simple. It&#8217;s easy to be misled here. A typical example of implicit leakage is hyperparameter tuning during training. Every training algorithm has hyperparameters. For instance, in gradient descent, there are parameters like &#171;learning rate&#187; and a parameter defining the stopping criterion. Moreover, you can add regularization components to the Loss function, like <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R_2=\\lambda_2 \\sum w_i^2\" alt=\"R_2=\\lambda_2 \\sum w_i^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/373\/8aa\/22c\/3738aa22cd539d1fc166f3bb8037329e.svg\" width=\"127\" height=\"30\"\/><\/em>and\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R_1=\\lambda_1 \\sum |w_i|\" alt=\"R_1=\\lambda_1 \\sum |w_i|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/26f\/3b7\/f24\/26f3b7f2496e9c160d2f6fcfdeec38a9.svg\" width=\"136\" height=\"30\"\/><\/em>, and now you have two more hyperparameters <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_1\" alt=\"\\lambda_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8fb\/9e9\/e79\/8fb9e9e7920a489f2be0a5834f8c5e1b.svg\" width=\"20\" height=\"19\"\/><\/em>and\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_2\" alt=\"\\lambda_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2a9\/738\/ed2\/2a9738ed25eb1fb0a4314fd45264e386.svg\" width=\"20\" height=\"19\"\/><\/em>. The prefix &#8216;hyper&#8217; is used to differentiate internal model parameters (weights) from parameters influencing the training process.<\/p>\n<p>So, suppose you decide to iterate through different training hyperparameters and select those hyperparameters that minimize the error on the test set. It&#8217;s important to understand that there&#8217;s a leakage of the test set into the model happening here. The &#8216;trap&#8217; hidden here is easy to understand from the standpoint of information theory. When you ask what the error is on the test set, you&#8217;re extracting information about that test set. Then, when you make decisions based on this information that ultimately affect the weights of your model, bits of this information end up in the model&#8217;s weights.<\/p>\n<p>One can further illustrate the concept of test set leakage by pushing the notion of hyperparameters to the absurd. After all, the distinction between weights (parameters) and hyperparameters (training process parameters) is purely formal. Let&#8217;s name all the model weights, such as the coefficients of a 10-degree polynomial, as hyperparameters, and we&#8217;ll have no training process (the set of internal weights will be empty). Then, let&#8217;s embark on an insane loop to search through all possible combinations of hyperparameter values (each parameter ranging from -1000 to +1000 with a step of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"10^{-6}\" alt=\"10^{-6}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e1f\/922\/8dc\/e1f9228dc5f8f76dd497bda824220cfd.svg\" width=\"39\" height=\"21\"\/><\/em>and compute the error on the test set. Clearly, after billions of years, we&#8217;ll find such a combination of parameters that yields a very small error on the test set, and we could repost the same image above, but with a different captio:<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/944\/479\/704\/944479704e62aa1c0b14dbcf07a87edc.png\" alt=\"The blue line represents a polynomial of the 10th degree that managed to perfectly replicate the test pool of 11 points.  \" title=\"The blue line represents a polynomial of the 10th degree that managed to perfectly replicate the test pool of 11 points.  \" width=\"300\" height=\"204\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/944\/479\/704\/944479704e62aa1c0b14dbcf07a87edc.png\"\/><\/p>\n<div><figcaption>The blue line represents a polynomial of the 10th degree that managed to perfectly replicate the test pool of 11 points.  <\/figcaption><\/div>\n<\/figure>\n<\/li>\n<\/ul>\n<p>This predictor will perform well on the test pool but poorly in real life.<\/p>\n<ul>\n<li>\n<p>In practice, models with thousands or millions of weights are used, and these effects are noticeable in larger datasets, especially with data leakage from the future (see below).<\/p>\n<\/li>\n<li>\n<p>It&#8217;s important to understand that test leakage through hyperparameter tuning always happens one way or another. Even if you&#8217;ve created a separate <strong>validation pool<\/strong> for tuning hyperparameters and haven&#8217;t used the test pool for that purpose, there&#8217;s still a moment when you compute the quality metric on the test pool. Later on, when you have several models evaluated on the test pool, choosing the best model based on the test metric is also considered a form of leakage. However, not all such instances of leakage need to be feared.<\/p>\n<\/li>\n<li>\n<p><strong>An important note is when to be concerned about this kind of leakage.<\/strong> If the <strong>effective complexity of your model<\/strong> (see the definition below) involves hundreds or more bits, you may not need to fear this type of leakage or allocate a special pool for hyperparameter tuning\u2014 <strong>the logarithm of the number of attempts for hyperparameter tuning should be noticeably smaller than the complexity of the model.<\/strong><\/p>\n<\/li>\n<\/ul>\n<ul>\n<li>\n<p><strong>Data leakage from the future:<\/strong> For instance, when training predictors for click-through rates on ads, ideally, the training pool should contain data exclusively available before a specific date, let&#8217;s say date X, which is the minimum date of events in the test pool. Otherwise, sneaky leaks like the following could occur. Suppose we have a set of ad display events labeled with <em>target<\/em> = 1 for clicked events and target = 0 for non-clicked ones. And let&#8217;s assume we split this event set into the training and test pools not based on the date boundary X but randomly, for instance, in a 50:50 ratio. It&#8217;s known that users tend to click on several ads of the same topic in a row within a few minutes, selecting the desired product or service. Consequently, these sequences of multiple clicks might randomly split between the training and test pools. You can artificially create a model with a leak: take the best correct model without a leak and additionally memorize the facts &#171;user U clicked on topic T&#187; from the training log. Then, while using the model, slightly increase the click probability for cases (U, T) from this set. This will improve the model in terms of the test pool error but worsen its practical application on new data. We&#8217;ve described an artificial model, yet it&#8217;s easy to imagine a natural mechanism for memorizing (U, T) pairs and inflating their probabilities in neural networks and other popular ML algorithms. The presence of such leaks from the future exacerbates the issue of leakage through hyperparameters. Models overtuned towards memorizing data will win on such a test pool with leakage. To describe this problem more broadly: <strong>a model can overfit to the test set if the mutual information between an example in the train set and an example in the test set is greater than that between an example in the train set and a real example when using the model in real life.<\/strong><\/p>\n<\/li>\n<\/ul>\n<h2>Tasks<\/h2>\n<p><strong>Task 3.1 <\/strong>Let the reality be such that <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target = w_0 + w_1\\cdot f + w_2\\cdot f^2+ \\nu,\" alt=\"target = w_0 + w_1\\cdot f + w_2\\cdot f^2+ \\nu,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8da\/5a5\/a9a\/8da5a5a9ac0cf75ac02dbd1915ad19f4.svg\" width=\"292\" height=\"25\"\/><\/em>where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu\" alt=\"\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2d3\/735\/b4e\/2d3735b4e5f929609986a9b0402d90cc.svg\" width=\"10\" height=\"12\"\/><\/em>\u2013 is a random number from<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,\\alpha^2),\" alt=\"\\mathcal{N}(0,\\alpha^2),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/09d\/612\/a1b\/09d612a1b218b136abb764ecc899c45f.svg\" width=\"80\" height=\"25\"\/><\/em>\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\alpha=0.2.\" alt=\"\\alpha=0.2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/481\/390\/406\/48139040678f4142e176253165e0f02d.svg\" width=\"69\" height=\"17\"\/><\/em>The factor<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d09\/3ee\/3df\/d093ee3dfadfa7128687b445d18653f4.svg\" width=\"11\" height=\"21\"\/><\/em> is sampled from<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1).\" alt=\"\\mathcal{N}(0,1).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/42f\/5e5\/d9b\/42f5e5d9b7e83daa1e2c1c8f4e3b946f.svg\" width=\"68\" height=\"23\"\/><\/em>On average, how many training data points are needed to get weight estimates that are equal to the true weights within a mean square error of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon=0.01\" alt=\"\\varepsilon=0.01\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8f0\/055\/a96\/8f0055a96060a12cb09884e645f3406b.svg\" width=\"70\" height=\"17\"\/><\/em>, given an appropriate model for reality? <br \/>Consider that the prior distribution of weights is a normal distribution<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,\\sigma^2).\" alt=\"\\mathcal{N}(0,\\sigma^2).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/56d\/2ca\/9aa\/56d2ca9aa6d9833c2351820406d9b2d3.svg\" width=\"79\" height=\"25\"\/><\/em>Express the answer as a function of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\alpha\" alt=\"\\alpha\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/67d\/045\/3cd\/67d0453cd58d52357cf0c0b6bd0d20c3.svg\" width=\"12\" height=\"12\"\/><\/em>,\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/319\/e30\/fa0\/319e30fa092ca8ef1a973b961479416c.svg\" width=\"9\" height=\"12\"\/><\/em>,\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma.\" alt=\"\\sigma.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f8e\/ceb\/ce2\/f8ecebce2f3407ddb25f5cf7f99b6d8a.svg\" width=\"17\" height=\"12\"\/><\/em> How does the prediction error depend on the size of the training dataset?<\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>There&#8217;s a method to get an answer &#171;from physicists.&#187; Let the size of the training dataset be <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/762\/d2d\/207\/762d2d207921ca6c394f2a785dc7949c.svg\" width=\"12\" height=\"12\"\/><\/em>. From <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Task%201.16%3A,number%20of%20measurements%3F\" rel=\"noopener noreferrer nofollow\">problem 1.16<\/a>, we have the intuition that <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon = c \/ \\sqrt{n}\" alt=\"\\varepsilon = c \/ \\sqrt{n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/364\/e22\/3ff\/364e223ff421a8398c317181f1df632c.svg\" width=\"81\" height=\"24\"\/><\/em>. The constant <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"c\" alt=\"c\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c20\/fdf\/aa7\/c20fdfaa7614fe959e00f38d7339542d.svg\" width=\"8\" height=\"12\"\/><\/em> in this problem is a function of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\alpha\" alt=\"\\alpha\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b4b\/977\/1ca\/b4b9771cab73ceb39229796b35b6ba1b.svg\" width=\"12\" height=\"12\"\/><\/em> and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma\" alt=\"\\sigma\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8b8\/4fa\/cbc\/8b84facbc81c25207609678774018bcb.svg\" width=\"11\" height=\"12\"\/><\/em>. But is there a dependency of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"c\" alt=\"c\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c20\/fdf\/aa7\/c20fdfaa7614fe959e00f38d7339542d.svg\" width=\"8\" height=\"12\"\/><\/em> on <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma\" alt=\"\\sigma\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5f7\/dd7\/1f7\/5f7dd71f7254115493e43e89854dffcc.svg\" width=\"11\" height=\"12\"\/><\/em>? In fact, there isn&#8217;t. Indeed, the noise <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\alpha\\cdot \\nu\" alt=\"\\alpha\\cdot \\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/302\/eb6\/849\/302eb68491725e621d2b7e79aa6f06aa.svg\" width=\"37\" height=\"12\"\/><\/em> erases digits in the decimal representation of the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aa6\/417\/af0\/aa6417af0ba16d83724ebdd79e21a857.svg\" width=\"52\" height=\"20\"\/><\/em> value, starting at some point after the decimal. When <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma\" alt=\"\\sigma\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/e28\/f6b\/4e0e28f6bd4e11f401dc7cff777b7c57.svg\" width=\"11\" height=\"12\"\/><\/em> increases, more significant digits remain, and that&#8217;s exactly how much more we learn about the coefficients <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{w_0, w_1, w_2\\}.\" alt=\"\\{w_0, w_1, w_2\\}.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f45\/23e\/5cb\/f4523e5cbc64e8a62035cccfb42345ec.svg\" width=\"111\" height=\"22\"\/><\/em>Thus, with an increase in <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma\" alt=\"\\sigma\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/e28\/f6b\/4e0e28f6bd4e11f401dc7cff777b7c57.svg\" width=\"11\" height=\"12\"\/><\/em>, the position in the decimal representation of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{w_0, w_1, w_2\\}\" alt=\"\\{w_0, w_1, w_2\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/45c\/f49\/f49\/45cf49f49c083e3750a1f99ea7bc921e.svg\" width=\"105\" height=\"22\"\/><\/em>, from which there is uncertainty, remains the same. Due to <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma\" alt=\"\\sigma\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0ec\/091\/1cb\/0ec0911cbe7910e88c72a3f5df6e1425.svg\" width=\"11\" height=\"12\"\/><\/em> not being involved in the formula and considering dimensional considerations, the formula should look like this:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\varepsilon =c_0 \\cdot {\\alpha \\over \\sqrt{n}}\" alt=\"\\varepsilon =c_0 \\cdot {\\alpha \\over \\sqrt{n}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3cb\/92b\/65a\/3cb92b65a08ac9701b7c44568287b548.svg\" width=\"102\" height=\"45\"\/><\/p>\n<p>Where the empirically computed constant <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"c_0\" alt=\"c_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/52b\/1b0\/f4c\/52b1b0f4c73a8b4bd79b208aaa62c78f.svg\" width=\"17\" height=\"15\"\/><\/em>is approximately equal to 0.9. Consequently, we get the answer <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n = 0.8\\cdot \\left({\\alpha \\over \\varepsilon} \\right)^2\" alt=\"n = 0.8\\cdot \\left({\\alpha \\over \\varepsilon} \\right)^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f92\/dcd\/fe7\/f92dcdfe7d28000632af986c1dd5a391.svg\" width=\"128\" height=\"43\"\/><\/em>.<\/p>\n<p>The error of the<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a41\/d48\/3e1\/a41d483e1d1284c2dcc4af86ce3d7c84.svg\" width=\"52\" height=\"20\"\/><\/em>value itself equals:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"mse=\\sqrt{\\varepsilon^2 + \\alpha^2}=\\alpha \\cdot \\sqrt{1+0.8\/n}\" alt=\"mse=\\sqrt{\\varepsilon^2 + \\alpha^2}=\\alpha \\cdot \\sqrt{1+0.8\/n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fa6\/266\/d5c\/fa6266d5c6170160c9c2e98a34928c26.svg\" width=\"296\" height=\"40\"\/><\/p>\n<p>This is a consequence of adding two independent random variables<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w'_0 + w'_1\\cdot f + w'_2\\cdot f^2\" alt=\"w'_0 + w'_1\\cdot f + w'_2\\cdot f^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/12f\/725\/2ee\/12f7252ee9f4f2eae6e28d5b3bc1b920.svg\" width=\"175\" height=\"27\"\/><\/em> and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu\" alt=\"\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e34\/ee5\/8eb\/e34ee58ebb309e7f3de3c097c6769555.svg\" width=\"10\" height=\"12\"\/><\/em> their variances add up. They should be independent in the correct forecast because if they are dependent, the model can be improved by calibrating the forecast in some way.<\/p>\n<p>Thus, in this prediction problem and many practical situations, there&#8217;s an unavoidable error <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\alpha\" alt=\"\\alpha\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bf2\/6dd\/666\/bf26dd66632de2b596a8d3dfac8c3470.svg\" width=\"12\" height=\"12\"\/><\/em>. It determines two things: <br \/>(1) the error you&#8217;ll get for a very large training set (as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\\to \\infty\" alt=\"n\\to \\infty\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a22\/fc9\/81e\/a22fc981e56783dd4ab8347768009005.svg\" width=\"62\" height=\"13\"\/><\/em> , we have \u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mse=\\alpha \\sqrt{1  + \\beta \/n}\\to \\alpha\" alt=\"mse=\\alpha \\sqrt{1  + \\beta \/n}\\to \\alpha\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f94\/010\/562\/f94010562d41263d20a32e7c85d51ede.svg\" width=\"203\" height=\"40\"\/><\/em>) <br \/>(2) the size of the set necessary to achieve a certain specified error in internal parameters, which quadratically depends on this unavoidable error:<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n=\\beta \\cdot (\\alpha\/\\varepsilon)^2\" alt=\"n=\\beta \\cdot (\\alpha\/\\varepsilon)^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eb7\/843\/34d\/eb784334d0faea2388f83c0ea07083c5.svg\" width=\"118\" height=\"25\"\/><\/em><\/p>\n<\/div>\n<\/details>\n<p>The unavoidable error <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\alpha\" alt=\"\\alpha\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ed5\/d83\/9b5\/ed5d839b57cc41baeb76c99cb7db75f8.svg\" width=\"12\" height=\"12\"\/> <\/em>is defined by the amount of information in the signal that is fundamentally absent in your factors. The size of the training set required to get a model of a certain accuracy <em>mse<\/em>, quadratically depends on this error:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"n={\\beta \\over (mse\/\\alpha)^2 -1 }\\approx  \\beta \\cdot (\\alpha \/ mse)^2 \\; \\;\\mathrm{\u043f\u0440\u0438\\;\u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445} \\; \\alpha\/mse\" alt=\"n={\\beta \\over (mse\/\\alpha)^2 -1 }\\approx  \\beta \\cdot (\\alpha \/ mse)^2 \\; \\;\\mathrm{\u043f\u0440\u0438\\;\u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445} \\; \\alpha\/mse\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f95\/ef6\/d23\/f95ef6d23348a1076e2bbb954504ab57.svg\" width=\"470\" height=\"49\"\/><\/p>\n<p>Someone might have the slightly incorrect intuition that reducing this error is crucial and that adding factors where new information about the signal might be hidden is an extremely beneficial move. Sometimes that&#8217;s true. However, in reality, having more factors means having more internal weights, and you need more information to figure out the first significant digits of those weights. Increasing model complexity by adding new factors sometimes nullifies the beneficial effect of new information if you don&#8217;t increase the size of the training set (i.e., increase the number of rows in the training pool), especially when the new factors are less informative than the existing ones.<\/p>\n<p>Moreover, factors are often <em>dependent<\/em> and inherently contain a noisy component. Assessing the utility of new factors and conducting factor selection is a separate and complex topic on its own.<\/p>\n<p><strong>Task 3.2.<\/strong> Let reality be such that the <em>target<\/em> is a second-degree polynomial of 10 factors, where the coefficients in the polynomial are numbers sampled once from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1),\" alt=\"\\mathcal{N}(0,1),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/261\/e78\/c57\/261e78c5727c11ec98fed3751bd0252b.svg\" width=\"68\" height=\"23\"\/><\/em>and the factors are independent random numbers from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/210\/e0e\/936\/210e0e936560868f796908a8ca25bdf1.svg\" width=\"62\" height=\"23\"\/>. <\/em>How much data is needed in the training set to achieve acceptable prediction quality when all factors lie in the range [-1, 1], assuming the model is correct, meaning it is a second-degree polynomial? <br \/>And what if the model is a third-degree polynomial?<\/p>\n<p><strong>Task 3.3.<\/strong> Build a model of users who tend to click more on ads of a particular theme at any given time and ensure that dividing the dataset into a training and test set randomly, rather than by time, leads to <em>data leakage from the future<\/em>. <br \/>You can take, for instance, this model: each user has 10 favorite themes, which we know and store in the user&#8217;s profile. User activity is divided into sessions, each lasting 5 minutes, during which the user sees exactly 10 ads from one of their 10 themes, randomly chosen from their favorites. In each session, the user is particularly interested in one of these 10 themes, and there are no factors allowing us to guess which one specifically. The probability of clicking for this &#171;hot&#187; theme is twice as high as usual. Based on each user&#8217;s click history, we know the click probabilities for their 10 themes well, and if ordered by interest for a specific user, the vector of these probabilities is {0.10, 0.11, 0.12, &#8230;, 0.19}. The user ID and the category number are the available factors. How much can the likelihood of predicting the click probability on the test set increase if we assume that each session was equally divided between the training and test sets (5 events went into one pool and 5 into the other), and the statistics from 5 events in the training set can be used to predict the click probability for 5 others? <br \/>It is suggested to experimentally achieve overfitting due to data leakage from the future by using some ML program like CatBoost.<\/p>\n<p><strong>Definition 3.1.<\/strong> <strong>The implementation<\/strong> <strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/3e4\/8c2\/4e03e48c2a0dd4d7f7b443d537f9ac32.svg\" width=\"9\" height=\"12\"\/><\/em><\/strong> <strong>&#8212;  complexity of a function (<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/3e4\/8c2\/4e03e48c2a0dd4d7f7b443d537f9ac32.svg\" width=\"9\" height=\"12\"\/><\/em><\/strong> <strong>&#8212; IC)<\/strong> is the amount of information about the function that needs to be communicated from one programmer to another, enabling the latter to reproduce it with a mean squared error not exceeding <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/212\/38d\/b70\/21238db701790b6957e9901c8e87324c.svg\" width=\"9\" height=\"12\"\/><\/em> . Two programmers agree in advance on a parametric family of functions and the prior distribution of parameters (weights) within this family. <br \/><strong>The effective complexity of a model<\/strong> is the minimum implementation complexity of a function among all possible functions that provide <em>the same predictive quality<\/em> as the given model.<\/p>\n<p><strong>Task 3.4.<\/strong> What is the average <strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/3e4\/8c2\/4e03e48c2a0dd4d7f7b443d537f9ac32.svg\" width=\"9\" height=\"12\"\/><\/em><\/strong> &#8212; IC of a function of the form<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p(f_1,\\ldots,f_n)=\\sum_{i=1}^n w_i\\cdot f_i\" alt=\"p(f_1,\\ldots,f_n)=\\sum_{i=1}^n w_i\\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aca\/809\/8af\/aca8098af84a8745545c6b051499f510.svg\" width=\"216\" height=\"57\"\/><\/em>\u200b<\/p>\n<p>of\u00a0<em>n<\/em> factors, where the weights are sampled from the distribution <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,\\sigma^2)\" alt=\"\\mathcal{N}(0,\\sigma^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/64c\/09c\/b0c\/64c09cb0c6809399e04eb2f5cf8c1fc4.svg\" width=\"73\" height=\"25\"\/><\/em>, and the factors are sampled from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/af9\/00c\/86c\/af900c86c43f1bdfec385c0bbd5944f8.svg\" width=\"63\" height=\"23\"\/><\/em>?<\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>When the factors are fixed, the function&#8217;s error is determined by the errors in the weights using the formula:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\delta p^2 = \\sum_i \\delta w_i ^2 f_i^2\" alt=\"\\delta p^2 = \\sum_i \\delta w_i ^2 f_i^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6b3\/52a\/644\/6b352a644d8cec0af0459c787f357e61.svg\" width=\"137\" height=\"45\"\/><\/p>\n<p>On average, considering all possible factor values, we get \u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta p^2 = {\\sum}_i \\delta w_i ^2\" alt=\"\\delta p^2 = {\\sum}_i \\delta w_i ^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/612\/010\/20f\/61201020fabe07831753941c8ab79c1f.svg\" width=\"117\" height=\"45\"\/><\/em>\u200b. If we desire <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta p^2 \\le \\varepsilon^2\" alt=\"\\delta p^2 \\le \\varepsilon^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6fa\/61c\/e8e\/6fa61ce8e15587377462efe1f276fd75.svg\" width=\"71\" height=\"24\"\/><\/em>, then the weights need to be transmitted with precision <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta w_i \\le  \\varepsilon^2 \/n\" alt=\"\\delta w_i \\le  \\varepsilon^2 \/n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a03\/c94\/8ea\/a03c948ea28ba791c5a01611454af559.svg\" width=\"95\" height=\"25\"\/><\/em>. <\/p>\n<p>Hence, according to the answer in <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Answer-,Task%201.9,-%3A%20What%20is\" rel=\"noopener noreferrer nofollow\">task 1.9<\/a>, on average, it will be necessary to transmit <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\\cdot \\log(\\sqrt{n}\\cdot \\sigma\/\\varepsilon)\" alt=\"n\\cdot \\log(\\sqrt{n}\\cdot \\sigma\/\\varepsilon)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/494\/a67\/960\/494a67960037c5bf44ae0455d24c603f.svg\" width=\"138\" height=\"24\"\/><\/em>bits. Here lies an important property of very complex models \u2013 determining the complexity of a complex model isn&#8217;t as reliant on the quality or precision of prior knowledge about the weights or the achieved accuracy. The primary component in the IC of the model is<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"0.5 \\cdot n\\cdot \\log n\" alt=\"0.5 \\cdot n\\cdot \\log n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/769\/865\/ce0\/769865ce0e1295581bc8305238c15a29.svg\" width=\"105\" height=\"21\"\/><\/em>, where <em>n<\/em> represents some effective number of weights contributing equally and beneficially to the model.<\/p>\n<\/div>\n<\/details>\n<p><strong>Task 3.5.<\/strong> The function <em>t<\/em>(id) is defined by a table as a function of a single factor \u2013 the category ID. There are <em>N\u00a0<\/em>= 1 million categories with varying proportions in the data, which can be considered as proportions got by sampling 1 million numbers from an exponential distribution, followed by normalization to ensure their sum equals 1 (this sampling corresponds to sampling once from a Dirichlet distribution with parameters {1,1,&#8230;,1} \u2013 1 million ones). The values of the function <em>t<\/em> for these categories are sampled independently from a beta distribution <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"B(\\alpha, \\beta),\" alt=\"B(\\alpha, \\beta),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ae0\/9c5\/410\/ae09c5410fd5b5fa1f5e8ee0a9004a26.svg\" width=\"68\" height=\"22\"\/><br \/>where<\/em>\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\alpha=2,\" alt=\"\\alpha=2,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9be\/61e\/628\/9be61e628b72539fbd3fc53aa9bf910f.svg\" width=\"53\" height=\"19\"\/><\/em> and<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\beta=10\" alt=\"\\beta=10\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/90f\/8b9\/9b8\/90f8b99b8c05bdea4a3ff1fb298c3de6.svg\" width=\"56\" height=\"20\"\/><\/em>.<\/p>\n<p>What is the average <strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/3e4\/8c2\/4e03e48c2a0dd4d7f7b443d537f9ac32.svg\" width=\"9\" height=\"12\"\/><\/em><\/strong>&#8212; IC of such a function?<\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>First, let&#8217;s describe the behavior of this function for very small <strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/3e4\/8c2\/4e03e48c2a0dd4d7f7b443d537f9ac32.svg\" width=\"9\" height=\"12\"\/><\/em><\/strong>. When <strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon \\ll 1\/10^6\" alt=\"\\varepsilon \\ll 1\/10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0be\/d70\/d0e\/0bed70d0efa3485ba6600222d4220c25.svg\" width=\"87\" height=\"25\"\/><\/em><\/strong>, we are forced to store a table function \u2013 1 million values. It&#8217;s possible to numerically or through the formula from Wikipedia calculate the entropy of the beta distribution<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"B(\\alpha, \\beta)\" alt=\"B(\\alpha, \\beta)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/683\/387\/b5f\/683387b5f3dab07c847a3e9c3f9d4c9d.svg\" width=\"62\" height=\"22\"\/><\/em>. Next, assume that we want to convey to another programmer that the value <em>t<\/em>  for a specific category <em>i<\/em>  lies around some fixed value <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t_i\" alt=\"t_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c7e\/c7b\/0fb\/c7ec7b0fbc46d44690ac3258bc62fce8.svg\" width=\"14\" height=\"19\"\/><\/em>with an allowed error of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/55b\/f16\/f35\/55bf16f358304df68eecc1b8d3cc3112.svg\" width=\"9\" height=\"12\"\/><\/em>. This is equivalent to narrowing the &#171;hat&#187; of the distribution<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"B(\\alpha, \\beta)\" alt=\"B(\\alpha, \\beta)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/245\/e2f\/7f0\/245e2f7f0a7a429b14a30b517ff87856.svg\" width=\"62\" height=\"22\"\/><\/em> to, let&#8217;s say, a normal distribution <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(t_i, \\varepsilon^2).\" alt=\"\\mathcal{N}(t_i, \\varepsilon^2).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/870\/96c\/018\/87096c01834ab02003e4c6c959592e37.svg\" width=\"81\" height=\"25\"\/><\/em> The difference in entropy between <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"B(\\alpha, \\beta)\" alt=\"B(\\alpha, \\beta)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/245\/e2f\/7f0\/245e2f7f0a7a429b14a30b517ff87856.svg\" width=\"62\" height=\"22\"\/><\/em>and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(t_i, \\varepsilon^2)\" alt=\"\\mathcal{N}(t_i, \\varepsilon^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aee\/b59\/eff\/aeeb59eff788ae29f37efd46df15abab.svg\" width=\"75\" height=\"25\"\/><\/em> is approximately <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"-2.38 -\\log \\varepsilon\" alt=\"-2.38 -\\log \\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d93\/29f\/5fa\/d9329f5fa5237028d999abfc23084589.svg\" width=\"111\" height=\"21\"\/><\/em>. This needs to be done for 1 million categories, so for very small <strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/3e4\/8c2\/4e03e48c2a0dd4d7f7b443d537f9ac32.svg\" width=\"9\" height=\"12\"\/><\/em><\/strong>, the answer is <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N\\cdot (-2.38 + \\log 1\/\\varepsilon)\" alt=\"N\\cdot (-2.38 + \\log 1\/\\varepsilon)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/086\/a63\/890\/086a63890b7f4838271145f948fe0372.svg\" width=\"177\" height=\"22\"\/><\/em>.<\/p>\n<p>For larger <strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e0\/3e4\/8c2\/4e03e48c2a0dd4d7f7b443d537f9ac32.svg\" width=\"9\" height=\"12\"\/><\/em><\/strong>   (but still noticeably less than 1), another strategy works. Let&#8217;s divide the interval [0,1] into equal segments of length <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta\" alt=\"\\delta\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/56b\/311\/ff3\/56b311ff35a96de09acd93c98bed2082.svg\" width=\"9\" height=\"18\"\/><\/em> , and for each category, transmit the number of the segment in which the function value for this category falls. This information has a volume of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N\\cdot (H_{B(2,10)}+ \\log(1\/\\delta))\" alt=\"N\\cdot (H_{B(2,10)}+ \\log(1\/\\delta))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/212\/815\/b7e\/212815b7e10e32e79ac1fff1d510e4d0.svg\" width=\"203\" height=\"25\"\/><\/em> (see task 1.7). As a result, in each answer, our error will be limited by the length of the segment in which we landed. If we consider the midpoint of the segment as the answer and assume uniformity of the distribution (which is acceptable when the segments are small), then the error within a segment of length <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta\" alt=\"\\delta\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/27f\/20a\/66a\/27f20a66a5437142612581af8383405a.svg\" width=\"9\" height=\"18\"\/><\/em> is <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta\/\\sqrt{12}\" alt=\"\\delta\/\\sqrt{12}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/576\/f40\/9db\/576f409dbd733e72b2857611b942da0a.svg\" width=\"54\" height=\"24\"\/><\/em>. Therefore, to get the specified average error <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/099\/d58\/cb2\/099d58cb2d2c76a0a2a93c7dd1b81a4e.svg\" width=\"9\" height=\"12\"\/><\/em>, the segments should be of length <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta=\\sqrt{12}\\cdot \\varepsilon\" alt=\"\\delta=\\sqrt{12}\\cdot \\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c82\/06b\/b6e\/c8206bb6e2c3b29ac6e761514e37eec6.svg\" width=\"94\" height=\"23\"\/><\/em>. Hence, the overall answer is <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N\\cdot (-2.20487 + \\log 1\/\\varepsilon)\" alt=\"N\\cdot (-2.20487 + \\log 1\/\\varepsilon)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/449\/b45\/14a\/449b4514ab087c67dcd7fb8d8f95d9fc.svg\" width=\"207\" height=\"22\"\/><\/em>.  <\/p>\n<p>Both approaches yield an answer of the form <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N\\cdot (c + \\log 1\/\\varepsilon)\" alt=\"N\\cdot (c + \\log 1\/\\varepsilon)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2f6\/666\/ba6\/2f6666ba65cad032ccafb26b91e9420e.svg\" width=\"136\" height=\"22\"\/><\/em>. The idea of using the Bloom filter to store sets of categories for each segment also provides the same result.<\/p>\n<\/div>\n<\/details>\n<p><strong>Task 3.6. <\/strong>Let&#8217;s say in the previous task, the function represents the probability of clicking on an advertisement. Let&#8217;s renumber all the categories in descending order of their true proportions and denote the ordinal number as order_id, while the original random identifier is denoted as id. We propose considering different machine learning options by coarsening the number (identifier) of the category to a natural number from 1 to 1000. This limitation might be related, for instance, to the need to store statistics on historical data, where you only have the capability to store 1000 pairs (displays, clicks). The options for coarsening the category identifier are: <br \/>(a) Coarsened identifier equals id&#8217; = id \/\/ 1000 (integer division by 1000); <br \/>(b) Coarsened identifier equals id&#8217; = order_id for the top 999 categories by proportion, while assigning identifier 1000 to all the others; <br \/>(c) Some other method of coarsening id&#8217; = G(id), where G is a deterministic function that you can construct based on click statistics from 100 million displays, where each display has a category with an equal probability of categories, and clicks occur based on the click probability for that category. <br \/>Evaluate the error value in these three approaches, where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"error = (LL_0 - LL)\/n,\" alt=\"error = (LL_0 - LL)\/n,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eb3\/4f2\/bbe\/eb34f2bbe64e1859d1713fc03e895e75.svg\" width=\"199\" height=\"22\"\/><\/em> and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"LL=-{\\sum}_{i=1}^n t_i \\log(p_i) + (1-t_i)\\log(1-p_i)\" alt=\"LL=-{\\sum}_{i=1}^n t_i \\log(p_i) + (1-t_i)\\log(1-p_i)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c04\/09f\/068\/c0409f0682e6f6be102e4d34219bc40c.svg\" width=\"374\" height=\"32\"\/><\/em>, and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"LL_0\" alt=\"LL_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b46\/35b\/e41\/b4635be414af4ad9f15463f1d3f31d6b.svg\" width=\"35\" height=\"20\"\/><\/em>is the<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"LL\" alt=\"LL\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1d8\/9c2\/eb7\/1d89c2eb7b85ddf861b98500ee44a510.svg\" width=\"27\" height=\"17\"\/><\/em> value for a perfect forecast where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p_i = t_i\" alt=\"p_i = t_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8a9\/371\/583\/8a93715839dbc105cc5f9c3fc976d49e.svg\" width=\"57\" height=\"19\"\/>.<\/em><\/p>\n<p><strong>Task 3.7.<\/strong> Let reality be such that <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target ={\\sum}_{i=1}^{45} w_i\\cdot f_i +0.02 \\cdot \\nu\" alt=\"target ={\\sum}_{i=1}^{45} w_i\\cdot f_i +0.02 \\cdot \\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0c7\/afe\/7e0\/0c7afe7e079b9c7b4549009695c0e28b.svg\" width=\"264\" height=\"35\"\/><\/em>, where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu\" alt=\"\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2d3\/735\/b4e\/2d3735b4e5f929609986a9b0402d90cc.svg\" width=\"10\" height=\"12\"\/><\/em> is noise, <\/p>\n<p>a random number from<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2f9\/f31\/4dd\/2f9f314dd216825f0bda384fd6bbf5de.svg\" width=\"63\" height=\"23\"\/><\/em>. And your model<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict = {\\sum}_{i=1}^{50} w_i\\cdot f_i +0.02 \\cdot \\nu,\" alt=\"predict = {\\sum}_{i=1}^{50} w_i\\cdot f_i +0.02 \\cdot \\nu,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9f8\/1ae\/3f2\/9f81ae3f21d37e9c5e12caa1cec089b5.svg\" width=\"279\" height=\"35\"\/><\/em> where the weights <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_1,w_2, \\ldots,w_{70}\" alt=\"w_1,w_2, \\ldots,w_{70}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4d6\/195\/842\/4d619584272531ff651b95f948859283.svg\" width=\"128\" height=\"15\"\/><\/em>are unknown to you and have a Laplace prior distribution with a mean of 0 and variance of 1. The last 5 factors of the model are effectively useless for prediction. What should be the size of the training pool to achieve a mean squared prediction error where <\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mse={\\sum}_{i=1}^n(predict_i - target_i)^2 \/ n  \\le 0.04^2\" alt=\"mse={\\sum}_{i=1}^n(predict_i - target_i)^2 \/ n  \\le 0.04^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e80\/fe6\/bbb\/e80fe6bbba9c69348e2a74cb7b2daccf.svg\" width=\"378\" height=\"32\"\/><\/em>.<\/p>\n<p>Generate three pools: \u21161, \u21162, \u21163 with sizes 50, 50, 100000 and find out which action is better &#8212; (a), (b), or (c): <br \/>(a) Merge two pools into one and based on the combined pool, find the best weights minimizing the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mse\" alt=\"mse\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/704\/641\/d20\/704641d2074c26d254ef699550dba9d1.svg\" width=\"35\" height=\"12\"\/><\/em> on this pool. <br \/>(b) For different pairs<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(\\lambda_1, \\lambda_2)\" alt=\"(\\lambda_1, \\lambda_2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/409\/dcd\/10a\/409dcd10a98b21e2bde8e16acbb0d61c.svg\" width=\"64\" height=\"22\"\/><\/em>, find the best weights minimizing <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mse  + \\lambda_1  \\sum |w_i| + \\lambda_2 \\cdot \\sum w_i^2\" alt=\"mse  + \\lambda_1  \\sum |w_i| + \\lambda_2 \\cdot \\sum w_i^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/364\/a51\/6bc\/364a516bcd575de545d70d3117a0322c.svg\" width=\"258\" height=\"30\"\/><\/em> on pool \u21161; from all pairs, choose\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_1\" alt=\"\\lambda_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b7f\/b27\/84a\/b7fb2784adceb50d9bd7001d0df13feb.svg\" width=\"20\" height=\"19\"\/><\/em>,\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_2\" alt=\"\\lambda_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d16\/f99\/044\/d16f990441fb50477c81f2c13bd469de.svg\" width=\"20\" height=\"19\"\/><\/em> that minimizes <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mse\" alt=\"mse\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9c7\/f32\/09a\/9c7f3209a30c4880abda8d132d7f2971.svg\" width=\"35\" height=\"12\"\/><\/em> on pool \u21162; suggested pairs<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(\\lambda_1, \\lambda_2)\" alt=\"(\\lambda_1, \\lambda_2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/409\/dcd\/10a\/409dcd10a98b21e2bde8e16acbb0d61c.svg\" width=\"64\" height=\"22\"\/><\/em> should be taken from sets<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"A \\times B,\" alt=\"A \\times B,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/45a\/b27\/a4a\/45ab27a4a14f4d672e09262d51cc3e63.svg\" width=\"59\" height=\"20\"\/><\/em> where<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"A\" alt=\"A\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a7a\/8ff\/3eb\/a7a8ff3eb51da99e6e61631bf61ca1da.svg\" width=\"15\" height=\"17\"\/><\/em> and<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"B\" alt=\"B\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/831\/5be\/fa0\/8315befa098995a5eecbbbf27456d5bb.svg\" width=\"15\" height=\"17\"\/><\/em>  are geometric progressions with<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"q=1.2\" alt=\"q=1.2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2eb\/dfc\/61e\/2ebdfc61e34575cb827b59c09bb7a2b6.svg\" width=\"60\" height=\"20\"\/><\/em> from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"1\/10^3\" alt=\"1\/10^3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/483\/ff2\/334\/483ff2334a446c61082bb594f0b2188a.svg\" width=\"48\" height=\"25\"\/><\/em> to 1. Draw a plot of the error as a function of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_1\" alt=\"\\lambda_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b7f\/b27\/84a\/b7fb2784adceb50d9bd7001d0df13feb.svg\" width=\"20\" height=\"19\"\/><\/em> with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_2 = 0\" alt=\"\\lambda_2 = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e74\/8bc\/119\/e748bc119d04801e134f7f05253da486.svg\" width=\"56\" height=\"19\"\/><\/em>.<br \/>(c) Merge two pools into one and based on the combined pool, find the best weights minimizing <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mse  + \\lambda_1  \\sum |w_i| + \\lambda_2 \\cdot \\sum w_i^2\" alt=\"mse  + \\lambda_1  \\sum |w_i| + \\lambda_2 \\cdot \\sum w_i^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/364\/a51\/6bc\/364a516bcd575de545d70d3117a0322c.svg\" width=\"258\" height=\"30\"\/><\/em>  on this pool; take the values of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_1\" alt=\"\\lambda_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b7f\/b27\/84a\/b7fb2784adceb50d9bd7001d0df13feb.svg\" width=\"20\" height=\"19\"\/><\/em>,\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lambda_2\" alt=\"\\lambda_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d16\/f99\/044\/d16f990441fb50477c81f2c13bd469de.svg\" width=\"20\" height=\"19\"\/><\/em> from step (b).<\/p>\n<p>The method is better the smaller the error on pool \u21163, which corresponds to the model&#8217;s application in reality. Is the winner stable when generating new pools? Draw a 3&#215;3 table of mse errors on the three pools using these three methods. How does the error on pool \u21163 decrease with the increase in sizes of pools \u21161 and \u21162?<\/p>\n<p><strong>Task 3.8.<\/strong> Let reality be defined by <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target =l_1(\\vec{f})+ l_2(\\vec{f}) +l_3(\\vec{f})+\\nu\" alt=\"target =l_1(\\vec{f})+ l_2(\\vec{f}) +l_3(\\vec{f})+\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/71f\/421\/99e\/71f42199e3381cc1276e49559ab2c3fe.svg\" width=\"291\" height=\"27\"\/>,<\/em> where <\/p>\n<ul>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu\" alt=\"\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2d3\/735\/b4e\/2d3735b4e5f929609986a9b0402d90cc.svg\" width=\"10\" height=\"12\"\/><\/em> is noise, a random namber from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,\\delta^2)\" alt=\"\\mathcal{N}(0,\\delta^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/19b\/200\/73a\/19b20073a052201ffc567be914c86b14.svg\" width=\"71\" height=\"25\"\/><\/em>,<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta=0.02\" alt=\"\\delta=0.02\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/026\/4d6\/50b\/0264d650be21ef1bd453d1f97b17bf57.svg\" width=\"70\" height=\"18\"\/><\/em>.<\/p>\n<\/li>\n<li>\n<p>The factors <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\vec{f}=\\|f_1,\\ldots,f_{m}\\|^t\" alt=\"\\vec{f}=\\|f_1,\\ldots,f_{m}\\|^t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5a7\/c75\/192\/5a7c7519218ae24dc1528f97abd6e9b2.svg\" width=\"152\" height=\"27\"\/><\/em>\u00a0are independent random variables with a uniform distribution on the interval <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"[-1,1]\" alt=\"[-1,1]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a15\/6f2\/102\/a156f2102b618df870a3f80617fa74e9.svg\" width=\"54\" height=\"22\"\/><\/em>,\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m=10\" alt=\"m=10\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/315\/4cf\/07f\/3154cf07f6a6a956b1316ef9f4540a5f.svg\" width=\"63\" height=\"17\"\/><\/em>.<\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"l_1(\\vec{f})=w_0+\\sum w_{i}\\cdot f_i\" alt=\"l_1(\\vec{f})=w_0+\\sum w_{i}\\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/254\/652\/2bc\/2546522bcdbfed37a12fbffc368a642d.svg\" width=\"199\" height=\"31\"\/><\/em> is a linear function with coefficients from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/40a\/965\/ea2\/40a965ea2a0681e22474b357f3ec8813.svg\" width=\"63\" height=\"23\"\/><\/em>.<\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"l_2(\\vec{f})={1 \\over 2}\\sum w_{ij}\\cdot f_i\\cdot f_j\" alt=\"l_2(\\vec{f})={1 \\over 2}\\sum w_{ij}\\cdot f_i\\cdot f_j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c34\/7fa\/a39\/c347faa390cdc39c3f051ad3cc1b8699.svg\" width=\"209\" height=\"43\"\/><\/em> is a quadratic homogeneous function where most coefficients <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_{ij}\" alt=\"w_{ij}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/690\/4d6\/f76\/6904d6f763f60907bd4446372be3a227.svg\" width=\"26\" height=\"17\"\/><\/em> are zero, except for random<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m_2=20\" alt=\"m_2=20\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/518\/1c9\/fe4\/5181c9fe4e59cedf751c0d50c6c0a214.svg\" width=\"72\" height=\"19\"\/><\/em>coefficients generated from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/40a\/965\/ea2\/40a965ea2a0681e22474b357f3ec8813.svg\" width=\"63\" height=\"23\"\/><\/em>.<\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"l_3(\\vec{f})={1 \\over 6}\\sum w_{ijk}\\cdot f_i\\cdot f_j\\cdot f_j\" alt=\"l_3(\\vec{f})={1 \\over 6}\\sum w_{ijk}\\cdot f_i\\cdot f_j\\cdot f_j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/765\/d91\/240\/765d9124039645132ce7c86f48f59a40.svg\" width=\"248\" height=\"43\"\/><\/em> is a cubic homogeneous function where most coefficients <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_{ijk}\" alt=\"w_{ijk}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2cf\/134\/526\/2cf1345267cc57739dafe8addd2f2745.svg\" width=\"34\" height=\"17\"\/><\/em> are zero, except for random \u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m_3=20,\" alt=\"m_3=20,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/417\/507\/b7e\/417507b7eb17f46a11e6a6f24dc36208.svg\" width=\"77\" height=\"20\"\/><\/em> coefficients generated from<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/40a\/965\/ea2\/40a965ea2a0681e22474b357f3ec8813.svg\" width=\"63\" height=\"23\"\/><\/em>.<\/p>\n<\/li>\n<\/ul>\n<p>What will be the mean squared error (mse) of prediction on <em>sufficiently large<\/em> test and training pools for different variations of the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target(\\vec{f})\" alt=\"target(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1e2\/ca6\/a1b\/1e2ca6a1b1d508dcc2b9f7b47ac311c9.svg\" width=\"81\" height=\"27\"\/><\/em>function (that is, for different samplings of coefficients <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i, \\; w_{ij},\\; w_{ijk}\" alt=\"w_i, \\; w_{ij},\\; w_{ijk}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/834\/64a\/20a\/83464a20a1823a4e94b5a86f6d93c530.svg\" width=\"109\" height=\"17\"\/>) <\/em>in the case when your model is:<\/p>\n<ul>\n<li>\n<p>(a0) \u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/956\/0e3\/546\/9560e354659a96a46987e4fc61cdbbe4.svg\" width=\"113\" height=\"27\"\/><\/em> with true coefficient values. <\/p>\n<\/li>\n<li>\n<p>(b0) <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/509\/0e6\/55a\/5090e655a2844c3a8c812350168b7e67.svg\" width=\"181\" height=\"27\"\/><\/em> with true coefficient values. <\/p>\n<\/li>\n<li>\n<p>(c0) <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})+l_3(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})+l_3(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9c9\/43a\/5ba\/9c943a5ba23017386f58a951bcb91e8f.svg\" width=\"249\" height=\"27\"\/><\/em>\u00a0with true coefficient values. <\/p>\n<\/li>\n<li>\n<p>(a1) <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/449\/e13\/fee\/449e13fee6bf254be0a26d6ae749474d.svg\" width=\"113\" height=\"27\"\/><\/em> with training (i.e., coefficients got by regression). <\/p>\n<\/li>\n<li>\n<p>(b1) <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/509\/0e6\/55a\/5090e655a2844c3a8c812350168b7e67.svg\" width=\"181\" height=\"27\"\/><\/em>with training, without knowing which coefficients are zero. <\/p>\n<\/li>\n<li>\n<p>(c1) <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})+l_3(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})+l_3(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9c9\/43a\/5ba\/9c943a5ba23017386f58a951bcb91e8f.svg\" width=\"249\" height=\"27\"\/><\/em> with training, without knowing which coefficients are zero. <\/p>\n<\/li>\n<li>\n<p>(c2) <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})+l_3(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})=l_1(\\vec{f})+l_2(\\vec{f})+l_3(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9c9\/43a\/5ba\/9c943a5ba23017386f58a951bcb91e8f.svg\" width=\"249\" height=\"27\"\/><\/em> with training, knowing which coefficients are zero. <\/p>\n<\/li>\n<li>\n<p>(d1) <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\\vec{f})\" alt=\"\\mathcal{P}(\\vec{f})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/806\/f78\/ca9\/806f78ca9011fb2171ae88ffca49cc47.svg\" width=\"43\" height=\"27\"\/><\/em>is a neural network with a depth of d = 5 and internal layer size <em>h<\/em>=5 (internal matrices have a size of <em>h<\/em>\u00a0x\u00a0<em>h<\/em>).<\/p>\n<\/li>\n<\/ul>\n<p><strong>A sufficiently large training pool<\/strong> is one where doubling it doesn&#8217;t notably reduce the error on the test set.<\/p>\n<p><strong>A sufficiently large test pool<\/strong> is one where its finite size doesn&#8217;t introduce an error comparable to the model&#8217;s error. In other words, a sufficiently large test pool won&#8217;t allow critical ranking errors among models. The discriminative capacity of the test pool is the difference in model qualities that the test pool confidently allows you to assess. In our task, it&#8217;s crucial to correctly rank the listed 6 models.<\/p>\n<p>Observe <em>overfitting<\/em> in these models (except the first two) by reducing the size of the training pool to a certain value for each model. Try to mitigate overfitting by:<\/p>\n<ol>\n<li>\n<p>Adding regularization terms to the Loss function: <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R_1=\\lambda_1\\cdot \\sum |w|,\" alt=\"R_1=\\lambda_1\\cdot \\sum |w|,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4f1\/119\/a5f\/4f1119a5f2fb1c08337dc36dbb052147.svg\" width=\"146\" height=\"30\"\/><\/em>\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R_2=\\lambda_2 \\cdot \\sum w^2\" alt=\"R_2=\\lambda_2 \\cdot \\sum w^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/be4\/1e0\/ea5\/be41e0ea5c817d332b327377087f26bf.svg\" width=\"138\" height=\"30\"\/><\/em>; <\/p>\n<\/li>\n<li>\n<p>Using early stopping.<\/p>\n<\/li>\n<li>\n<p>Employing SGD (Stochastic Gradient Descent).<\/p>\n<\/li>\n<li>\n<p>Modifying the architecture of the neural network.<\/p>\n<\/li>\n<li>\n<p>Adding Dropout.<\/p>\n<\/li>\n<li>\n<p>A combination of these methods.<\/p>\n<\/li>\n<\/ol>\n<p>It&#8217;s also interesting in this task to study how the degree of overfitting increases and the model&#8217;s quality decreases with the increase in the number of (extra) parameters. For model (c1), initially, you can consider only those coefficients that are actually non-zero. Then, explore several options by adding some randomly selected extra coefficients to the model. Plot the model&#8217;s error growth against the logarithm of the number of coefficients in the model. Additionally, create a graph illustrating the change in error for the neural network model (d1) as a function of the number of internal layers and their sizes.<\/p>\n<p><strong>Task 3.9.<\/strong> Let reality be defined as:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"target =w_0+\\sum_{i=1}^{m} w_i\\cdot f_i+\\nu,\" alt=\"target =w_0+\\sum_{i=1}^{m} w_i\\cdot f_i+\\nu,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/106\/651\/189\/10665118901f6e91545dbc1c266055a5.svg\" width=\"244\" height=\"57\"\/><\/p>\n<p>Where:<\/p>\n<ul>\n<li>\n<p>The weights <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\" alt=\"w_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9a2\/234\/25a\/9a223425acdb564e3ac2666b166d6f83.svg\" width=\"21\" height=\"15\"\/><\/em>are sampled from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,\\sigma^2)\" alt=\"\\mathcal{N}(0,\\sigma^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/83c\/6b3\/955\/83c6b3955cbab5ed8d172dc5fb8c781a.svg\" width=\"73\" height=\"25\"\/><\/em>; <\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu\" alt=\"\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a09\/7a7\/431\/a097a74316e2857004e44b9a7515f22b.svg\" width=\"10\" height=\"12\"\/><\/em> is noise, a random number from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,\\delta^2)\" alt=\"\\mathcal{N}(0,\\delta^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/19b\/200\/73a\/19b20073a052201ffc567be914c86b14.svg\" width=\"71\" height=\"25\"\/><\/em>,\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta=0.5\" alt=\"\\delta=0.5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/437\/968\/9cd\/4379689cd4b402872f6f778f5747a126.svg\" width=\"60\" height=\"18\"\/><\/em>.<\/p>\n<\/li>\n<li>\n<p>The values <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_1,\\ldots,f_{m}\" alt=\"f_1,\\ldots,f_{m}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/883\/b59\/bf7\/883b59bf7ae0a2dc475bddcef09693f8.svg\" width=\"85\" height=\"20\"\/><\/em>are independent random variables with a normal distribution <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/462\/a87\/de5\/462a87de5cbc6ad2c727e58ffb1090be.svg\" width=\"63\" height=\"23\"\/><\/em>;<\/p>\n<\/li>\n<\/ul>\n<p>How does the error in determining the weights <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\" alt=\"w_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/156\/66e\/906\/15666e9063dee0b7110a4a63c417e106.svg\" width=\"21\" height=\"15\"\/><\/em>depend on the size of the training data <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/809\/66d\/da7\/80966dda77639347529e3639ca196f27.svg\" width=\"12\" height=\"12\"\/><\/em> and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m, \\; \\delta?\" alt=\"m, \\; \\delta?\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f97\/385\/14b\/f9738514bc4f662564959f8298cca117.svg\" width=\"49\" height=\"21\"\/><\/em><\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>In the first approximation, the answer is<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"mse(w_i) = {\\delta \\over \\sqrt{n}}.\\;\\;\\;\\;\\;(1)\" alt=\"mse(w_i) = {\\delta \\over \\sqrt{n}}.\\;\\;\\;\\;\\;(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d33\/ffd\/42e\/d33ffd42e262b833ba60fef154acefce.svg\" width=\"193\" height=\"51\"\/><\/p>\n<p>And this is a good approximation for the case where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n \\gg m\" alt=\"n \\gg m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/19f\/c3b\/116\/19fc3b116357e003d8fbd95b318a64ab.svg\" width=\"59\" height=\"16\"\/><\/em> (when<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4d8\/805\/b00\/4d8805b0068e04e96223f606b32f132e.svg\" width=\"12\" height=\"12\"\/><\/em>\u00a0is significantly larger than\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/458\/586\/69d\/45858669dc20939006a194bd8ea6f547.svg\" width=\"17\" height=\"12\"\/><\/em>).  <\/p>\n<p>For <em>n<\/em>\u00a0= 0, the best estimate of weights is 0, and the error of this estimation is 1. This error slowly decreases as <em>n<\/em> increases up to the number <em>m<\/em>. Then, the error drops significantly faster and as n increases, it approaches the asymptote (1). Through numerical experiments, you can get a graph:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/34a\/032\/cb5\/34a032cb51e591556b04a6bee858aa09.png\" alt=\"Average squared error of weights, normalized by \u03b4^2 for m=50. The X-axis is normalized by m, meaning X=1 corresponds to n = m. The red line corresponds to the function 1\/n\u200b.  \" title=\"Average squared error of weights, normalized by \u03b4^2 for m=50. The X-axis is normalized by m, meaning X=1 corresponds to n = m. The red line corresponds to the function 1\/n\u200b.  \" width=\"1144\" height=\"714\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/34a\/032\/cb5\/34a032cb51e591556b04a6bee858aa09.png\"\/><\/p>\n<div><figcaption>Average squared error of weights, normalized by \u03b4^2 for m=50. <br \/>The X-axis is normalized by <em>m<\/em>, meaning <em>X<\/em>=1 corresponds to <em>n <\/em>= <em>m<\/em>. <br \/>The red line corresponds to the function 1\/n\u200b.  <\/figcaption><\/div>\n<\/figure>\n<p>If anyone has a good analytical approximation for the vicinity of n ~ m, feel free to send it via private message.  <\/p>\n<\/div>\n<\/details>\n<p><strong>Task 3.10.<\/strong> Let reality be defined as:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"target =\\sum_{i=1}^{11} w_i\\cdot g_i+\\nu,\" alt=\"target =\\sum_{i=1}^{11} w_i\\cdot g_i+\\nu,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/825\/c5f\/ca4\/825c5fca4f539e6cdbcfd3fa24046fc7.svg\" width=\"200\" height=\"60\"\/><\/p>\n<p>Where:<\/p>\n<ul>\n<li>\n<p>The weights <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\" alt=\"w_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9a2\/234\/25a\/9a223425acdb564e3ac2666b166d6f83.svg\" width=\"21\" height=\"15\"\/><\/em>are sampled from<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/462\/a87\/de5\/462a87de5cbc6ad2c727e58ffb1090be.svg\" width=\"63\" height=\"23\"\/><\/em>;<\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu\" alt=\"\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a09\/7a7\/431\/a097a74316e2857004e44b9a7515f22b.svg\" width=\"10\" height=\"12\"\/><\/em> is noise, a random number from<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,\\delta^2)\" alt=\"\\mathcal{N}(0,\\delta^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/19b\/200\/73a\/19b20073a052201ffc567be914c86b14.svg\" width=\"71\" height=\"25\"\/><\/em>,\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\delta=0.5\" alt=\"\\delta=0.5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/437\/968\/9cd\/4379689cd4b402872f6f778f5747a126.svg\" width=\"60\" height=\"18\"\/><\/em>.<\/p>\n<\/li>\n<li>\n<p>The values <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"g_1,\\ldots,g_{m}\" alt=\"g_1,\\ldots,g_{m}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2c0\/498\/17d\/2c049817d1f28c59daf6aac0d1f4e66c.svg\" width=\"85\" height=\"16\"\/><\/em> are independent random variables with a normal distribution <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/462\/a87\/de5\/462a87de5cbc6ad2c727e58ffb1090be.svg\" width=\"63\" height=\"23\"\/><\/em>;<\/p>\n<\/li>\n<li>\n<p>You are given factors with noise: <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_i = g_i + \\zeta_i\" alt=\"f_i = g_i + \\zeta_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/09b\/4b1\/87e\/09b4b187ea6b5cfdcf223e112c4c596a.svg\" width=\"97\" height=\"21\"\/><\/em>, where the random noise <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\zeta_i\" alt=\"\\zeta_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1f0\/f20\/60f\/1f0f2060fbb3ce965d96d0159f6d57cc.svg\" width=\"15\" height=\"20\"\/><\/em>\u00a0in each example is sampled from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0, z_i^2)\" alt=\"\\mathcal{N}(0, z_i^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/25f\/d63\/4c6\/25fd634c6c0dc0fd7b7c3b11d600ccbb.svg\" width=\"71\" height=\"25\"\/><\/em>(represented as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\zeta_i\\sim\\mathcal{N}(0,z_i^2)),\" alt=\"\\zeta_i\\sim\\mathcal{N}(0,z_i^2)),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cad\/c31\/978\/cadc319784d142963e5aec1b2f5cc025.svg\" width=\"125\" height=\"25\"\/><\/em>and the noise sizes are known and equal to <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"z_i=0.01 \\cdot 2^i\" alt=\"z_i=0.01 \\cdot 2^i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/10f\/289\/d1f\/10f289d1f86881d397f786dcc8907ec0.svg\" width=\"107\" height=\"24\"\/><\/em>.<\/p>\n<\/li>\n<\/ul>\n<p>What will be the best forecast if you know the exact values of weights <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i?\" alt=\"w_i?\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3c6\/e4a\/20a\/3c6e4a20a53bfe0e045b563b76ae7226.svg\" width=\"30\" height=\"20\"\/><\/em>How can you best implement learning in this task (when the weights are unknown and need to be &#171;learned&#187;)?<\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>Let&#8217;s consider a specific problem regarding adding a new factor <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_1\" alt=\"f_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/20e\/920\/aef\/20e920aefe080af1ff276ee03009d21c.svg\" width=\"18\" height=\"21\"\/><\/em> to an existing forecast\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"F_0\" alt=\"F_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/225\/48c\/2da\/22548c2da8515b4e14f1a374ef1a3cae.svg\" width=\"21\" height=\"20\"\/><\/em>\u200b. Suppose:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"target =  F_0 + w_1\\cdot g_1 + \\nu_1,\\; \\\\ \\nu_1 \\sim \\mathcal{N}(0, \\delta_1^2), \\; g_1\\sim \\mathcal{N}(0,1), \\\\ predict_0 = F_0, \\\\ f_1 = g_1 + \\zeta_1, \\; \\;  \\zeta_1\\sim  \\mathcal{N}(0,z_1^2)\" alt=\"target =  F_0 + w_1\\cdot g_1 + \\nu_1,\\; \\\\ \\nu_1 \\sim \\mathcal{N}(0, \\delta_1^2), \\; g_1\\sim \\mathcal{N}(0,1), \\\\ predict_0 = F_0, \\\\ f_1 = g_1 + \\zeta_1, \\; \\;  \\zeta_1\\sim  \\mathcal{N}(0,z_1^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a8a\/df8\/4e9\/a8adf84e956abe315fd1c00d949051a7.svg\" width=\"615\" height=\"107\"\/><\/p>\n<p>Can we reduce the mean squared error (mse) by taking a new forecast:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"predict_1 = predict_0 + w_1\\cdot f_1?\" alt=\"predict_1 = predict_0 + w_1\\cdot f_1?\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b37\/9b7\/8b0\/b379b78b0e22e2f9e77bcaf3a5df7ab8.svg\" width=\"253\" height=\"21\"\/><\/p>\n<p>The current error is equal to the variance <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"D(target - predict_0) =  w_1^2 + \\delta_1^2.\" alt=\"D(target - predict_0) =  w_1^2 + \\delta_1^2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d90\/c39\/383\/d90c393836e9fdade5013f71f6a8ec0d.svg\" width=\"272\" height=\"25\"\/><\/em> The error of the new forecast will be <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"D(target - predict_1) = w_1^2 \\cdot z_1^2+\\delta_1^2,\" alt=\"D(target - predict_1) = w_1^2 \\cdot z_1^2+\\delta_1^2,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/af5\/afe\/b91\/af5afeb9169c374ce189807c5c56040c.svg\" width=\"304\" height=\"25\"\/><\/em> which is smaller than the old error if <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"z_1 &lt; 1.\" alt=\"z_1 &lt; 1.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/286\/6ba\/4ea\/2866ba4eaeca55637fc2f31801b81b74.svg\" width=\"59\" height=\"19\"\/><\/em><\/p>\n<p>Let&#8217;s construct a sequence of forecast improvements:<\/p>\n<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict_0 = 0,\\\\ predict_1 = predict_0 + t_1 \\cdot w_1 \\cdot f_1, \\\\ predict_2=predict_1 + t_2\\cdot w_2\\cdot f_2, \\\\ \\ldots \\\\ predict_{m} = predict_{m-1} + t_{m}\\cdot w_{m}\\cdot f_{m}\" alt=\"predict_0 = 0,\\\\ predict_1 = predict_0 + t_1 \\cdot w_1 \\cdot f_1, \\\\ predict_2=predict_1 + t_2\\cdot w_2\\cdot f_2, \\\\ \\ldots \\\\ predict_{m} = predict_{m-1} + t_{m}\\cdot w_{m}\\cdot f_{m}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/533\/93c\/2a8\/53393c2a8d59217127999696745fa02a.svg\" width=\"611\" height=\"120\"\/><\/em>  \u200b<\/p>\n<\/p>\n<p>The numbers\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t_i\" alt=\"t_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/754\/30c\/908\/75430c908636be8cabcbc5217b7ab967.svg\" width=\"14\" height=\"19\"\/><\/em> are equal to 0 or 1 \u2013 these are indicators of whether we include the factor<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_i\" alt=\"f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/357\/52e\/0f1\/35752e0f1056ba645ae8b04c459090f3.svg\" width=\"16\" height=\"21\"\/><\/em> in the linear forecast or not. <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"D(target - predict_0) =  \\sigma_0^2 = w_1^2 +  \\delta_1^2\" alt=\"D(target - predict_0) =  \\sigma_0^2 = w_1^2 +  \\delta_1^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/655\/493\/feb\/655493febcaaa3eba07b24394187290c.svg\" width=\"312\" height=\"25\"\/><\/em>, where <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\delta_1^2 = \\sum_{i=2}^{m} w_i^2 + \\delta^2\" alt=\"\\delta_1^2 = \\sum_{i=2}^{m} w_i^2 + \\delta^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/63b\/fee\/004\/63bfee004a6fb2fe2128535cb91cbca4.svg\" width=\"140\" height=\"57\"\/><\/p>\n<p>Then, if we take the first factor, the error will be:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"D(target - predict_1) =\\sigma_1^2=  w_1\\cdot z_1^2 + \\delta_1^2\" alt=\"D(target - predict_1) =\\sigma_1^2=  w_1\\cdot z_1^2 + \\delta_1^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a60\/e03\/615\/a60e03615b82d9732cf2eaa255496fcf.svg\" width=\"345\" height=\"25\"\/><\/p>\n<p>It&#8217;s logical to include a new factor <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_i\" alt=\"f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aca\/9be\/fdc\/aca9befdcd1740be7f1aa85f1b8a3d0f.svg\" width=\"16\" height=\"21\"\/><\/em> in the linear forecast when <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"z_i &lt;1.\" alt=\"z_i &lt;1.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f77\/898\/a1f\/f77898a1fa2c8d9250cd6089aa2aa8ba.svg\" width=\"57\" height=\"20\"\/><\/em><\/p>\n<p>Ultimately, the error of the final forecast is:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"D(target - predict_{m}) = \\sigma_m^2=\\sum_{i=1}^m \\min(1, z_i^2)\\cdot w_i^2+\\delta^2\" alt=\"D(target - predict_{m}) = \\sigma_m^2=\\sum_{i=1}^m \\min(1, z_i^2)\\cdot w_i^2+\\delta^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c3a\/896\/4a3\/c3a8964a3bb64e40f68e4eefe7b66317.svg\" width=\"453\" height=\"57\"\/><\/p>\n<p>So, in the case of a linear forecast and known weights <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\" alt=\"w_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ccd\/3bf\/1a1\/ccd3bf1a1d2e26327bdb6f57aa15ce14.svg\" width=\"21\" height=\"15\"\/><\/em>\u200b, we can either include or exclude terms. It&#8217;s logical to include terms <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\\cdot f_i\" alt=\"w_i\\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bec\/217\/072\/bec2170729e5ed7841426c0168015fb9.svg\" width=\"51\" height=\"21\"\/><\/em> with those factors <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_i,\" alt=\"f_i,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/338\/970\/d1d\/338970d1d4c6d95e9ed13d9355ac75ee.svg\" width=\"22\" height=\"21\"\/><\/em> where the noise variance is smaller than the variance of the least noisy factor <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"g_i\" alt=\"g_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9fe\/b5a\/032\/9feb5a032efdf6bd5285fe28cd45b88c.svg\" width=\"16\" height=\"16\"\/><\/em>. However, apart from the options of &#171;including&#187; or &#171;excluding&#187;, there&#8217;s also the option of including with a different, smaller weight in magnitude. Additionally, the forecasting model doesn&#8217;t necessarily have to be linear. The correct solution to the problem appears more intricate; in reality, we can always extract some benefit from a factor if it holds new information, even if it&#8217;s highly noisy.<\/p>\n<p>Let&#8217;s consider having two unbiased forecasts <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict_0\" alt=\"predict_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/160\/89d\/26d\/16089d26d47367aa02a33cd94d9df316.svg\" width=\"70\" height=\"20\"\/><\/em>and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict_1\" alt=\"predict_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/255\/dfa\/aee\/255dfaaee36b086b8693f0c381620740.svg\" width=\"70\" height=\"20\"\/><\/em>with errors:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\; mse_0 = D(target - predict_0) = \\sigma_0^2,\\\\ mse_1=D(target - predict_1) = \\sigma_1^2.\" alt=\"\\; mse_0 = D(target - predict_0) = \\sigma_0^2,\\\\ mse_1=D(target - predict_1) = \\sigma_1^2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ce\/1d0\/3fa\/1ce1d03fa8a383d7e860fdff2c3ee154.svg\" width=\"615\" height=\"55\"\/><\/p>\n<p>Then, if they were completely independent, a new, more accurate forecast could be constructed from them as:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"predict_c = {m_0 \\cdot predict_0 + m_1 \\cdot predict_1 \\over  m_0 + m_1},\\\\  m_0 = 1\/\\sigma_0^2,\\; m_1 = 1\/\\sigma_1^2.\" alt=\"predict_c = {m_0 \\cdot predict_0 + m_1 \\cdot predict_1 \\over  m_0 + m_1},\\\\  m_0 = 1\/\\sigma_0^2,\\; m_1 = 1\/\\sigma_1^2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8c4\/766\/b21\/8c4766b21b3bb89c941c422b85b6eb8b.svg\" width=\"615\" height=\"77\"\/><\/p>\n<p>The error of this forecast would be:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sigma_c^2 = {1 \\over 1\/\\sigma_0^2 + 1\/\\sigma_1^2}\" alt=\"\\sigma_c^2 = {1 \\over 1\/\\sigma_0^2 + 1\/\\sigma_1^2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b50\/3f7\/db2\/b503f7db2d4bf5c4c0c956d299c46aee.svg\" width=\"156\" height=\"51\"\/><\/p>\n<p>That is, <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m_c = 1\/\\sigma_c^2 = m_0 + m_1.\" alt=\"m_c = 1\/\\sigma_c^2 = m_0 + m_1.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a8b\/864\/da1\/a8b864da13cdde880e342a002d9f1d93.svg\" width=\"198\" height=\"23\"\/><\/em><\/p>\n<p>Why this holds true for independent forecasts is suggested for self-exploration. This scenario resembles, for instance, two independent groups of researchers providing their estimations of the Higgs boson&#8217;s mass with uncertainties, and the need arises to combine them.<\/p>\n<p>In our case, the estimations are dependent, and in the errors:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"target - predict_0 = -w_1\\cdot g_1 + \\nu_1, \\\\ target - predict_1= - w_1\\cdot  \\zeta_i + \\nu_1\" alt=\"target - predict_0 = -w_1\\cdot g_1 + \\nu_1, \\\\ target - predict_1= - w_1\\cdot  \\zeta_i + \\nu_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dfb\/2e3\/b39\/dfb2e3b39c10328a0758f3bd6e522583.svg\" width=\"615\" height=\"47\"\/><\/p>\n<p>There&#8217;s a common part\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu_1\" alt=\"\\nu_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4d4\/fbd\/ca4\/4d4fbdca4b8f026eb310ee6863b7eab3.svg\" width=\"19\" height=\"14\"\/><\/em>\u200b &#8212;  the common irreducible error for these two forecasts. When combining, we essentially combine only two independent parts\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"-w_1\\cdot g_1\" alt=\"-w_1\\cdot g_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/333\/ec4\/159\/333ec41599e3cd84e0ff04712a7dfb40.svg\" width=\"70\" height=\"19\"\/><\/em> and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"-w_1 \\cdot \\zeta_1\" alt=\"-w_1 \\cdot \\zeta_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/29e\/5eb\/9b1\/29e5eb9b1f969e0f28eb0b5d251a1a2a.svg\" width=\"70\" height=\"20\"\/><\/em>\u200b, yielding the result:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"predict_c= F_0 + {m_0\\cdot 0 + m_1\\cdot (w_1 \\cdot f_i) \\over m_0 + m_1}=\\\\=F_0 + {1\\over m_0\/m_1+1}\\cdot w_1\\cdot f_1\" alt=\"predict_c= F_0 + {m_0\\cdot 0 + m_1\\cdot (w_1 \\cdot f_i) \\over m_0 + m_1}=\\\\=F_0 + {1\\over m_0\/m_1+1}\\cdot w_1\\cdot f_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/317\/9f9\/021\/3179f90210b0674d9c7ff74d9553833d.svg\" width=\"615\" height=\"102\"\/><\/p>\n<p>Where<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"m_0 = 1\/w_1^2,\\; m_1= 1\/(w_1^2\\cdot z_1^2).\" alt=\"m_0 = 1\/w_1^2,\\; m_1= 1\/(w_1^2\\cdot z_1^2).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/210\/b44\/e70\/210b44e704e1f3c8a88c6e4f15a4d22e.svg\" width=\"256\" height=\"25\"\/><\/p>\n<p>Thus:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"predict_c = F_0 + {1 \\over z_1^2+1}\\cdot w_1\\cdot f_1\" alt=\"predict_c = F_0 + {1 \\over z_1^2+1}\\cdot w_1\\cdot f_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5ab\/ea6\/a8b\/5abea6a8b7eb567204e7228d2966c30e.svg\" width=\"268\" height=\"51\"\/><\/p>\n<p>And the error of such a forecast will be:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sigma_c^2 = w_1^2 {z_1^2\\over z_1^2 + 1} +   \\delta_1^2\" alt=\"\\sigma_c^2 = w_1^2 {z_1^2\\over z_1^2 + 1} +   \\delta_1^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/435\/33f\/66b\/43533f66bf42290bb222d05cb5468249.svg\" width=\"169\" height=\"56\"\/><\/p>\n<p>This is less than the errors \u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma_0^2=w_1^2 + \\delta_1^2\" alt=\"\\sigma_0^2=w_1^2 + \\delta_1^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fb6\/27c\/c65\/fb627cc653d3e84159344eecfd43e78c.svg\" width=\"110\" height=\"25\"\/><\/em>\u00a0and\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma_1^2=w_1\\cdot z_1^2 + \\delta_1^2\" alt=\"\\sigma_1^2=w_1\\cdot z_1^2 + \\delta_1^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bc8\/856\/96e\/bc885696eee17e2919924ccb2e7998d8.svg\" width=\"143\" height=\"25\"\/><\/em> of both forecasts, <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict_0\" alt=\"predict_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/160\/89d\/26d\/16089d26d47367aa02a33cd94d9df316.svg\" width=\"70\" height=\"20\"\/><\/em> and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict_1.\" alt=\"predict_1.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0ef\/c4e\/f28\/0efc4ef28d78d1e9df1e855021704f58.svg\" width=\"75\" height=\"20\"\/><\/em><\/p>\n<p>The final formula for the best linear forecast looks like this:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"predict = \\sum_{i=1}^m {1\\over z_i^2 + 1} \\cdot w_i \\cdot f_i\" alt=\"predict = \\sum_{i=1}^m {1\\over z_i^2 + 1} \\cdot w_i \\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e2c\/6b6\/fd6\/e2c6b6fd603ac5619248ee78c41d4a39.svg\" width=\"242\" height=\"57\"\/><\/p>\n<p>And the error of this forecast is:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"D(target - predict) = \\sigma^2=\\sum_{i=1}^m {z_i^2\\over z_i^2+1} \\cdot w_i^2+\\delta^2\" alt=\"D(target - predict) = \\sigma^2=\\sum_{i=1}^m {z_i^2\\over z_i^2+1} \\cdot w_i^2+\\delta^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/549\/8c5\/04c\/5498c504cebe3aa63f6b1d744232403b.svg\" width=\"408\" height=\"58\"\/><\/p>\n<p>So, with known weights, all factors are useful. But when weights are unknown and the training pool is not sufficiently large, some factors need to be discarded.<\/p>\n<p>Weights can be estimated by the formula:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"w'_i= \\mathrm{avg}(target \\cdot f_i)\/\\mathrm{avg}(f_i^2)\" alt=\"w'_i= \\mathrm{avg}(target \\cdot f_i)\/\\mathrm{avg}(f_i^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/91a\/758\/824\/91a7588241d452232ba40ae010cb8870.svg\" width=\"249\" height=\"25\"\/><\/p>\n<p>Let&#8217;s see what this expression equals in the limit when the training log is large, and the average can be replaced with the mathematical expectation. If all factors are initially normalized so that their mean is zero:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"M(target \\cdot f_i) =\\\\= M((\\ldots + w_i\\cdot g_i)\\cdot (g_i + \\zeta_i)) =\\\\= M(w_i\\cdot g_i^2) = w_i\" alt=\"M(target \\cdot f_i) =\\\\= M((\\ldots + w_i\\cdot g_i)\\cdot (g_i + \\zeta_i)) =\\\\= M(w_i\\cdot g_i^2) = w_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/99c\/14e\/8e9\/99c14e8e9c37b8733076e16dbf7cd34b.svg\" width=\"615\" height=\"81\"\/><\/p>\n<p>And the mean square of the factor is:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"M((g_i + \\zeta_i)^2) = M(g_i^2 + \\zeta_i^2) = 1 + z_i^2\" alt=\"M((g_i + \\zeta_i)^2) = M(g_i^2 + \\zeta_i^2) = 1 + z_i^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/088\/ced\/6ec\/088ced6ec86655b458185322c9ceadb6.svg\" width=\"315\" height=\"27\"\/><\/p>\n<p>Thus, the expression <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w'_i = \\mathrm{avg}(target \\cdot f_i)\/\\mathrm{avg}(f_i^2)\" alt=\"w'_i = \\mathrm{avg}(target \\cdot f_i)\/\\mathrm{avg}(f_i^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a68\/709\/1f3\/a687091f3c64fab67de59e004948bdd4.svg\" width=\"249\" height=\"25\"\/><\/em> in the limit equals <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i \/ (1+z_i^2)\" alt=\"w_i \/ (1+z_i^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/27b\/349\/424\/27b34942488b160489945b82b704dfbd.svg\" width=\"97\" height=\"25\"\/><\/em>, precisely what needs to be substituted into the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/659\/ac8\/b03\/659ac8b03263b0a745a80732c94b78a4.svg\" width=\"61\" height=\"20\"\/><\/em> formula. The value<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w'_i\" alt=\"w'_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/84c\/e78\/fa9\/84ce78fa9c09ceabf091c5d94e5ed5c7.svg\" width=\"21\" height=\"23\"\/><\/em> will be calculated with an error, deviating from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i \/ (1+z_i^2)\" alt=\"w_i \/ (1+z_i^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/27b\/349\/424\/27b34942488b160489945b82b704dfbd.svg\" width=\"97\" height=\"25\"\/><\/em> &#8212; due to the finiteness of the training pool (the normalization won&#8217;t be perfect, and the sample averages will differ from the true mathematical expectations). Let an estimate of the mean square of the relative error be given:<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\epsilon_i=\\left( { w'_i \\over  w_i \/ (1+z_i^2)}-1\\right),\\;\\; d^2_i=M(\\epsilon_i^2).\" alt=\"\\epsilon_i=\\left( { w'_i \\over  w_i \/ (1+z_i^2)}-1\\right),\\;\\; d^2_i=M(\\epsilon_i^2).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/212\/4b0\/fb3\/2124b0fb3250e1cbe2cff9bbd515a768.svg\" width=\"335\" height=\"62\"\/><\/em>  <\/p>\n<p>If we don&#8217;t include the term <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w'_i\\cdot f_i\" alt=\"w'_i\\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/00e\/060\/e91\/00e060e910449ec8e3e8745c0de3ddca.svg\" width=\"51\" height=\"23\"\/><\/em> in the forecast, the additional term to the error square (from losing the true term <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\\cdot g_i\" alt=\"w_i\\cdot g_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e66\/dd9\/634\/e66dd96346d30f51d2973152b6b33dce.svg\" width=\"51\" height=\"16\"\/><\/em>) equals <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i^2.\" alt=\"w_i^2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4f1\/645\/d2e\/4f1645d2e03d7e2b65330c9aeabc1b86.svg\" width=\"28\" height=\"25\"\/><\/em> If instead of\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\\cdot  g_i\" alt=\"w_i\\cdot  g_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/80e\/ae4\/068\/80eae4068e15a4cab13e1339df903f7f.svg\" width=\"51\" height=\"16\"\/><\/em>, we include <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w'_i\\cdot f_i\" alt=\"w'_i\\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d7b\/f6b\/e0d\/d7bf6be0d71b4ca3142737557643ac61.svg\" width=\"51\" height=\"23\"\/><\/em>\u200b, the additional term to the error square equals:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"M((w'_i\\cdot f_i - w_i\\cdot g_i)^2) =\\\\=M\\left(\\left({w_i \\over 1+z_i^2}\\cdot (1 + \\epsilon_i)\\cdot(g_i + \\zeta_i) - w_i\\cdot g_i\\right)^2\\right) = \\\\ = w_i^2\\cdot M\\left(\\left(\\left({1 + \\epsilon_i\\over 1+z_i^2} - 1\\right)\\cdot g_i + \\left({1 + \\epsilon_i\\over 1+z_i^2}\\right)\\cdot \\zeta_i \\right)^2 \\right)\" alt=\"M((w'_i\\cdot f_i - w_i\\cdot g_i)^2) =\\\\=M\\left(\\left({w_i \\over 1+z_i^2}\\cdot (1 + \\epsilon_i)\\cdot(g_i + \\zeta_i) - w_i\\cdot g_i\\right)^2\\right) = \\\\ = w_i^2\\cdot M\\left(\\left(\\left({1 + \\epsilon_i\\over 1+z_i^2} - 1\\right)\\cdot g_i + \\left({1 + \\epsilon_i\\over 1+z_i^2}\\right)\\cdot \\zeta_i \\right)^2 \\right)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cda\/a59\/8d1\/cdaa598d1a664c9cff164d7cdc287a86.svg\" width=\"615\" height=\"176\"\/><\/p>\n<p>Here we:<\/p>\n<ul>\n<li>\n<p>pulled out <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i\" alt=\"w_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/287\/2c0\/69e\/2872c069e0a63c241f29d077a9645a70.svg\" width=\"21\" height=\"15\"\/><\/em>\u200b<\/p>\n<\/li>\n<li>\n<p>divided the expression in brackets into two parts, which are independent random variables with a mean of 0.<\/p>\n<\/li>\n<\/ul>\n<p>If this expression is greater than <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_i^2,\" alt=\"w_i^2,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/698\/2cc\/2ae\/6982cc2ae470f70ac7ddf4945d1af808.svg\" width=\"28\" height=\"25\"\/><\/em> it&#8217;s better to discard the factor. The final expression simplifies to:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"w_i^2 \\cdot\\left({1  + d_i^2 \\over (1 + z_i^2)^2} - {2 \\over 1 + z_i^2}+1 + {1+d_i^2 \\over (1+z_i^2)^2} z_i^2   \\right) = \\\\ =  w_i^2 \\cdot\\left({d_i^2 + z_i^2  \\over 1 + z_i^2}   \\right)\" alt=\"w_i^2 \\cdot\\left({1  + d_i^2 \\over (1 + z_i^2)^2} - {2 \\over 1 + z_i^2}+1 + {1+d_i^2 \\over (1+z_i^2)^2} z_i^2   \\right) = \\\\ =  w_i^2 \\cdot\\left({d_i^2 + z_i^2  \\over 1 + z_i^2}   \\right)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/48e\/a5a\/011\/48ea5a011407b64c499c6999ff723c0e.svg\" width=\"615\" height=\"129\"\/><\/p>\n<p>Therefore, if the relative error\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"d_i^2\" alt=\"d_i^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/650\/91d\/36f\/65091d36f9eaa77571eb27b9b555e167.svg\" width=\"19\" height=\"25\"\/><\/em> of the estimate <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w'_i\" alt=\"w'_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e1e\/f9a\/a27\/e1ef9aa27e3e4b71f3bc14cc493d0592.svg\" width=\"21\" height=\"23\"\/><\/em> is greater than 1, the factor is better off discarded. The error of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w'_i\" alt=\"w'_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e1e\/f9a\/a27\/e1ef9aa27e3e4b71f3bc14cc493d0592.svg\" width=\"21\" height=\"23\"\/><\/em> can be estimated, for instance, by the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bootstrapping_(statistics)\" rel=\"noopener noreferrer nofollow\">bootstrap <\/a>method.<\/p>\n<p>From this answer, we can derive the following intuitive idea &#8212; if during gradient descent (regular or stochastic) at the last iterations, a weight in the model changes its sign, it&#8217;s better to set it to 0.<\/p>\n<\/div>\n<\/details>\n<h2>Quadratic Loss Function and Mutual Information  <\/h2>\n<p>Usually, the prediction task is formulated as minimizing the error:<\/p>\n<p><strong>ML-task \u21163.1:<\/strong> Based on the given training pool, train a model\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict=\\mathcal{P}(f_1, \\ldots)\" alt=\"predict=\\mathcal{P}(f_1, \\ldots)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a63\/262\/e18\/a63262e186f91a4a9ebfce004fdf8458.svg\" width=\"166\" height=\"22\"\/><\/em> that minimizes the average error<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Loss(predict, target)\" alt=\"Loss(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cd0\/34f\/a16\/cd034fa16f180d795b9629a3af6b127f.svg\" width=\"177\" height=\"22\"\/><\/em>. The quality of the prediction will be measured by the average error on the hidden test pool.<\/p>\n<p>But it&#8217;s possible to try formulating the prediction task as a maximization of MI.<\/p>\n<p><strong>ML-task \u21163.2:<\/strong> Based on the given training pool, train a model <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(f_1, \\ldots)\" alt=\"\\mathcal{P}(f_1, \\ldots)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/96f\/d15\/405\/96fd15405c5a2cde0971a5730db881cb.svg\" width=\"79\" height=\"22\"\/><\/em> such that<\/p>\n<ul>\n<li>\n<p>the value predict has the maximum possible mutual information with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target,\" alt=\"target,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7fd\/8d5\/b23\/7fd8d5b236c113fcf777eb47a43eb718.svg\" width=\"57\" height=\"20\"\/><\/em> <br \/>i.e. <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target)\\to \\mathrm{max}\" alt=\"\\mathrm{MI}(predict, target)\\to \\mathrm{max}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bf7\/aad\/cff\/bf7aadcff3473a5927d94a9e637a85c7.svg\" width=\"227\" height=\"22\"\/><\/em>; <\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bf4\/708\/095\/bf4708095dfc51310253bd0a822d17eb.svg\" width=\"61\" height=\"20\"\/><\/em> is an unbiased forecast of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0b5\/108\/b20\/0b5108b2039a50bff8740369afeeb663.svg\" width=\"52\" height=\"20\"\/><\/em>, meaning the expectation of the discrepancy <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi = predict - target\" alt=\"\\xi = predict - target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/893\/0ec\/8b1\/8930ec8b188f8443508639ebd62591a9.svg\" width=\"170\" height=\"21\"\/><\/em> equals 0 under the condition <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict = x\" alt=\"predict = x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c3b\/8fb\/5f7\/c3b8fb5f7d3ae401a3d9cb35361c165f.svg\" width=\"98\" height=\"20\"\/><\/em> for any <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x\" alt=\"x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ae6\/670\/86a\/ae667086a59d3dbbf33101120e842d6b.svg\" width=\"11\" height=\"12\"\/><\/em>.<\/p>\n<\/li>\n<\/ul>\n<p>This is a brief but not entirely correct formulation, requiring some clarifications. Specifically, the following points need clarification:<\/p>\n<ul>\n<li>\n<p>In what sense can the pair<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(predict, target)\" alt=\"(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e6d\/001\/7e2\/e6d0017e23deecfa70a60861fbb2b694.svg\" width=\"136\" height=\"22\"\/><\/em> be interpreted as a pair of dependent random variables?<\/p>\n<\/li>\n<li>\n<p>The requirement of unbiasedness seems unattainable if the dataset on which we train and test is finite and fixed.<\/p>\n<\/li>\n<\/ul>\n<p>These points can be resolved straightforwardly. During testing, we sample an example from a potentially infinite pool and get a pair of random variables<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(predict, target).\" alt=\"(predict, target).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/636\/fd4\/584\/636fd4584df08197f8d9edc4918d27ee.svg\" width=\"141\" height=\"22\"\/> <\/em>And unbiasedness should be understood in the way it&#8217;s commonly done in mathematical statistics in regression problems &#8212; unbiasedness on average over all possible training and test pools, not on specific pool data.<\/p>\n<details class=\"spoiler\">\n<summary>More details<\/summary>\n<div class=\"spoiler__content\">\n<p>The deterministic function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(f_1, \\ldots, f_k)\" alt=\"\\mathcal{P}(f_1, \\ldots, f_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c14\/acc\/7af\/c14acc7af4609465a9efb466e87a65a8.svg\" width=\"110\" height=\"22\"\/><\/em>is interpreted as a random variable as follows: we sample a row from the test pool, extract a set of factors<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(f_1, \\ldots, f_k)\" alt=\"(f_1, \\ldots, f_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0c0\/e23\/03f\/0c0e2303ffdcf2f86fb0198a7558e33a.svg\" width=\"96\" height=\"22\"\/><\/em>, and the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/929\/c71\/c7c\/929c71c7c1fedf1efac5dd60e7779c87.svg\" width=\"52\" height=\"20\"\/><\/em>. Then we substitute these factors into the function and get the value <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e9a\/d2c\/582\/e9ad2c5824a71cddb194483090f6656f.svg\" width=\"61\" height=\"20\"\/><\/em> and a pair of dependent random variables <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(predict, target)\" alt=\"(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/884\/407\/c0f\/884407c0feb058ee9dbbab6160193a8a.svg\" width=\"136\" height=\"22\"\/><\/em>.<\/p>\n<p>The requirement of unbiasedness should be understood as an average unbiasedness when considering the training and test pools as random variables. That means a specific finite training pool will certainly yield a model with a biased forecast &#8212; the average value of the difference<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict - target\" alt=\"predict - target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ba4\/747\/9a9\/ba47479a9872a446ee43152973bf95b7.svg\" width=\"136\" height=\"21\"\/><\/em> will not be zero on average for a random example from a potentially infinite test pool. However, one can consider the difference <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"avg(predict) - target\" alt=\"avg(predict) - target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f8c\/6ca\/cbe\/f8c6cacbe64914df28fc34452d9b81a4.svg\" width=\"180\" height=\"22\"\/><\/em>, where the average is taken over all possible models that could be obtained by training on hypothetical training pools and testing on hypothetical test pools. Another way to justify unbiasedness is by requiring it in the limit, as the size of the training pool tends to infinity. These interpretations of unbiasedness give a chance for the existence of a solution to ML-task \u21163.2.2. However, to be honest, neither engineers nor ML theorists pay much attention to the bias issue, as is commonly done in methods of mathematical statistics. ML practitioners acknowledge this and openly prefer to test and evaluate their methods on artificial or real problems using error metrics, without analyzing their bias.<\/p>\n<p>But I needed the requirement of unbiasedness to reformulate the prediction task in terms of maximizing MI.<\/p>\n<\/div>\n<\/details>\n<p>So, we&#8217;ll allow ourselves to perceive the test pool as a source of random examples and use the terminology of probability theory.<\/p>\n<p><strong>Definition 3.2:<\/strong> A loss function equal to the expected value of the squared error<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"M_{\\xi^2}\" alt=\"M_{\\xi^2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4b9\/095\/ca1\/4b9095ca10f2c615198607a86edc428f.svg\" width=\"33\" height=\"25\"\/><\/em> will be referred to as<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_2\" alt=\"L_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bdd\/a4c\/6a7\/bdda4c6a7f5e1e523c5f8653d5223ab9.svg\" width=\"22\" height=\"19\"\/><\/em><strong>\u2013 \u043e\u0448\u0438\u0431\u043a\u043e\u0439<\/strong> or <strong>squared error<\/strong> or <strong>MSE<\/strong> (Mean Squared Error). And a loss function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"M_{|\\xi|^p}\" alt=\"M_{|\\xi|^p}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/182\/6df\/7d6\/1826df7d6f605c30c089af16ff1eff0b.svg\" width=\"41\" height=\"24\"\/><\/em>will be referred to as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_p\" alt=\"L_p\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6da\/39d\/450\/6da39d450ed99e4741b764c05570aa45.svg\" width=\"22\" height=\"22\"\/><\/em><strong>\u2013 \u043e\u0448\u0438\u0431\u043a\u043e\u0439<\/strong>.<\/p>\n<p><strong>Statement 3.1:<\/strong> Suppose your model in the ML-task \u21163.2.2 or ML-task \u21163.2.1 has the discrepancy <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi = predict - target\" alt=\"\\xi = predict - target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a63\/4b7\/737\/a634b7737ca578e2e128c2e6f558218e.svg\" width=\"170\" height=\"21\"\/><\/em> possessing two properties:<\/p>\n<ol>\n<li>\n<p>It is a normal variable with a zero mean (meaning the forecast is unbiased) for any fixed value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d45\/8cb\/d6d\/d458cbd6d4cfc7ea80ec4580f6e60771.svg\" width=\"61\" height=\"20\"\/><\/em>.<\/p>\n<\/li>\n<li>\n<p>It has a variance that is independent of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d29\/dee\/7b3\/d29dee7b302454ac45e9f69f88a3c8b4.svg\" width=\"61\" height=\"20\"\/><\/em>.<\/p>\n<\/li>\n<\/ol>\n<p>Then the ML-task \u21163.1 and ML-task \u21163.2 problems are equivalent for Loss = MSE, meaning the &#171;maximize MI&#187; task provides the same solution as the &#171;minimize MSE-error&#187; task.<\/p>\n<p>Of course, these properties described in the statement are rarely encountered in practice, but nonetheless, this fact is interesting. <\/p>\n<p>First, these properties are attainable when the vector of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/709\/fb1\/31d\/709fb131ddb81f4cb28bd51c2da3e9cf.svg\" width=\"12\" height=\"12\"\/><\/em> factors and the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/18d\/1f8\/401\/18d1f84010fd673e6ddb595b4f45c08a.svg\" width=\"52\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(f_1, f_2, \\ldots, f_n, target)\" alt=\"(f_1, f_2, \\ldots, f_n, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/50e\/3f8\/c6c\/50e3f8c6c4be81f8bc1aff5c9a2b2af3.svg\" width=\"184\" height=\"22\"\/><\/em>constitutes a measurement of a multivariate normal variable. This occurs specifically when the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/515\/677\/3b0\/5156773b00b60438b813cd5006c6f43c.svg\" width=\"52\" height=\"20\"\/><\/em> is a linear combination of several independent Gaussian variables, some of which are known and provided as factors. In this case, seeking the forecast as a linear combination of these given factors is natural.<\/p>\n<p>In this case,<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(target, predict) = \\log({\\sigma_t^2 \/ \\sigma_e^2})\" alt=\"\\mathrm{MI}(target, predict) = \\log({\\sigma_t^2 \/ \\sigma_e^2})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8f8\/f71\/870\/8f8f718705b05d6165d256df3c52aec1.svg\" width=\"277\" height=\"24\"\/><\/em>,  <\/p>\n<p>where\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma_e^2\" alt=\"\\sigma_e^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9b9\/c87\/c56\/9b9c87c56cffb5e3e0313987b1821137.svg\" width=\"20\" height=\"22\"\/><\/em> is the average value of the squared forecast error, that is <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"M_{\\xi^2} = M_{{(target - predict)}^2}\" alt=\"M_{\\xi^2} = M_{{(target - predict)}^2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/20f\/bf6\/664\/20fbf666437ac40a5563af7aa096b817.svg\" width=\"187\" height=\"26\"\/><\/em>, and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma_t^2\" alt=\"\\sigma_t^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8dc\/36e\/e8c\/8dc36ee8c15367c9dd029d78f77b0ade.svg\" width=\"20\" height=\"24\"\/><\/em> is the variance of the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5ac\/77e\/413\/5ac77e4136fd2383f4cd28c3478f1870.svg\" width=\"52\" height=\"20\"\/> <\/em>(see task 2.8 about the mutual information of two dependent normal variables). Clearly, in this scenario, maximizing <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}\" alt=\"\\mathrm{MI}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/230\/84f\/9a7\/23084f9a7baeb4dd9285f76be5c8317b.svg\" width=\"25\" height=\"17\"\/><\/em> is equivalent to minimizing <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"M_{\\xi^2}=\\sigma_e^2\" alt=\"M_{\\xi^2}=\\sigma_e^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/de2\/3b4\/6c8\/de23b46c89bc800f9ebd4710f4027a3d.svg\" width=\"79\" height=\"27\"\/><\/em>.<\/p>\n<p>It should be understood that while a pure, unbiased Gaussian for the error <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi\" alt=\"\\xi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dde\/48a\/881\/dde48a88145c2e4ee9600cfa26ff7a8e.svg\" width=\"9\" height=\"21\"\/><\/em> that does not depend on <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/97f\/772\/2b2\/97f7722b20607025d5a95294983d871b.svg\" width=\"61\" height=\"20\"\/><\/em> is not encountered in practice, the distribution of the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a5b\/297\/417\/a5b297417445e9f3a61a6351d65e4ecc.svg\" width=\"52\" height=\"20\"\/> <\/em>given a fixed <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8c3\/57a\/7f1\/8c357a7f14c93d117af6cf426e760e9e.svg\" width=\"61\" height=\"20\"\/><\/em> often resembles a Gaussian &#171;bell curve&#187; centered at <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fda\/5b3\/30f\/fda5b330f9340dc1334dce3c2cb58c8e.svg\" width=\"61\" height=\"20\"\/><\/em>. The statement about equivalence is almost true in such cases. Specifically, the task of maximizing MI is equivalent to the task of minimizing the error in an <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_2\" alt=\"L_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7c2\/03c\/86f\/7c203c86f79d3f930a84e69780994a69.svg\" width=\"22\" height=\"19\"\/><\/em>-like metric, where the averaging is weighted and somehow dependent on <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a2a\/060\/283\/a2a06028300bb188abe64c0a11b75b84.svg\" width=\"61\" height=\"20\"\/><\/em>.<\/p>\n<p>To be precise, if the bell curve of the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\rho_\\xi\" alt=\"\\rho_\\xi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a6f\/727\/dce\/a6f727dce353942abb409d41f84fdc45.svg\" width=\"18\" height=\"17\"\/> <\/em>distribution is unimodal, symmetric, and with a quadratic peak, then an equivalent task regarding the maximization of MI can be formulated. We&#8217;ll discuss this below.<\/p>\n<p>For now, let&#8217;s attempt to prove the statement about the equivalence of the &#171;maximize MI&#187; and &#171;minimize L2&#187; tasks for the case described in Statement 3.1.<\/p>\n<p>Let&#8217;s introduce the abbreviations: <strong><em>t<\/em><\/strong>\u00a0=\u00a0<strong><em>target<\/em><\/strong>,\u00a0<strong><em>p<\/em><\/strong>\u00a0=\u00a0<strong><em>predict<\/em><\/strong>.<\/p>\n<p>The proof is based on simply expressing the value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}\" alt=\"\\mathrm{MI}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ac0\/51b\/6de\/ac051b6debbbcd95dae1e4d553cf22ce.svg\" width=\"25\" height=\"17\"\/> <\/em>in the following form:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(p, t) = H(t) - \\int H(t | p = x) \\rho_{p}(x) dx\" alt=\"\\mathrm{MI}(p, t) = H(t) - \\int H(t | p = x) \\rho_{p}(x) dx\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c78\/92e\/7cf\/c7892e7cfabba1c4880135eb311f6eb4.svg\" width=\"336\" height=\"46\"\/><\/p>\n<p>The value <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(t)\" alt=\"H(t)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a00\/895\/c82\/a00895c82ac649429c37ddc2d718f729.svg\" width=\"40\" height=\"22\"\/><\/em>is independent of the forecast and is <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"C + 0.5\\cdot \\log(D(t)).\" alt=\"C + 0.5\\cdot \\log(D(t)).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f0c\/3f4\/f05\/f0c3f4f05a002af2ee6617a964e1d00b.svg\" width=\"162\" height=\"22\"\/><\/em> The value <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(t | p = x)\" alt=\"H(t | p = x)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7ec\/892\/812\/7ec892812961bc5d838fcd7d0dc41f6d.svg\" width=\"92\" height=\"22\"\/><\/em>is <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"C + 0.5\\cdot \\log(D(t|p=x)),\" alt=\"C + 0.5\\cdot \\log(D(t|p=x)),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1b2\/a6a\/4c1\/1b2a6a4c16b4c638384b8106987e1968.svg\" width=\"214\" height=\"22\"\/><\/em> where<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"D(t|p=x)\" alt=\"D(t|p=x)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b94\/cc8\/6da\/b94cc86daa55d7d29338a99d2dd15f5e.svg\" width=\"91\" height=\"22\"\/><\/em>represents the variance of the predicted quantity given a particular prediction. According to the second condition of the statement, it is constant. In the case of an unbiased forecast, this is <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"M_{\\xi^2}\" alt=\"M_{\\xi^2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e19\/3c1\/e2a\/e193c1e2a1fb4f1c85275525f6c53ca6.svg\" width=\"33\" height=\"25\"\/><\/em>(i.e., precisely the squared error) given <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p=x.\" alt=\"p=x.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2ac\/986\/f59\/2ac986f590e4a17fdf28d2dcc0a25701.svg\" width=\"53\" height=\"15\"\/><\/em><\/p>\n<p>The expression<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\int \\ldots \\rho_{p}(x) dx\" alt=\"\\int \\ldots \\rho_{p}(x) dx\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/97b\/cf9\/27f\/97bcf927f63d3ed02f47cf7415a5fbcb.svg\" width=\"115\" height=\"46\"\/><\/em>  essentially represents averaging over the pool.<\/p>\n<p>If <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"M_{\\xi^2}\" alt=\"M_{\\xi^2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e50\/368\/3f7\/e503683f78d53efe33adb534083832a4.svg\" width=\"33\" height=\"25\"\/><\/em>is independent of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p=x,\" alt=\"p=x,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a80\/10e\/e15\/a8010ee155d331ed81938e17da73e644.svg\" width=\"53\" height=\"15\"\/><\/em> then we get the required statement. Indeed,<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(p, t) = \u0421 +  0.5\\cdot \\log(D(t)) - \\int (C +  0.5 \\log(\\mathrm{mse})) \\rho_{p}(x) dx = \\\\ = 0.5 \\cdot \\log(D(t) \/ \\mathrm{mse})\" alt=\"\\mathrm{MI}(p, t) = \u0421 +  0.5\\cdot \\log(D(t)) - \\int (C +  0.5 \\log(\\mathrm{mse})) \\rho_{p}(x) dx = \\\\ = 0.5 \\cdot \\log(D(t) \/ \\mathrm{mse})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4d1\/96a\/d46\/4d196ad469d6fdff8b032f1c97de337e.svg\" width=\"697\" height=\"74\"\/><\/p>\n<p>Maximizing this expression is equivalent to minimizing the MSE. End of proof.<\/p>\n<p>For a better understanding, let&#8217;s elaborate further on the expression:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(p, t) =\\\\= H(t) - \\int H(t | p = x) \\rho_{p}(x) dx =\\\\=  H(t) - \\int \\rho_{t}(y | p = x) \\log(1\/\\rho_{t}(y | p = x)) \\rho_{p}(x) dx dy =\\\\  = H(t) - \\int \\log(1\/\\rho_{t}(y | p = x)) \\cdot \\rho_{t,p}(x, y) dx dy\" alt=\"\\mathrm{MI}(p, t) =\\\\= H(t) - \\int H(t | p = x) \\rho_{p}(x) dx =\\\\=  H(t) - \\int \\rho_{t}(y | p = x) \\log(1\/\\rho_{t}(y | p = x)) \\rho_{p}(x) dx dy =\\\\  = H(t) - \\int \\log(1\/\\rho_{t}(y | p = x)) \\cdot \\rho_{t,p}(x, y) dx dy\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5a8\/2f5\/a13\/5a82f5a131aa09e61ecd26ea25ccc201.svg\" width=\"697\" height=\"178\"\/><\/p>\n<p>The integration <\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\int \\ldots (\\rho_{t,p}(x, y) dx dy\" alt=\"\\int \\ldots (\\rho_{t,p}(x, y) dx dy\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a58\/042\/0e2\/a580420e243dca5f30e63e91a014e106.svg\" width=\"169\" height=\"46\"\/><\/em>  <\/p>\n<p>again corresponds to simply averaging over the pool, and the expression <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/\\rho_{t}(y | p = x))\" alt=\"\\log(1\/\\rho_{t}(y | p = x))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/78b\/531\/521\/78b53152142148e444b83d9dd24d52e5.svg\" width=\"154\" height=\"22\"\/><\/em> is what should be interpreted as the error value. If we transition to the discretized case and recall Huffman encoding, <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/P(t= y | p = x))\" alt=\"\\log(1\/P(t= y | p = x))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d75\/097\/b34\/d75097b3486a9aefcc45e338b90acbf6.svg\" width=\"185\" height=\"22\"\/><\/em>is the number of bits required to write the code for the value <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t=y\" alt=\"t=y\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8de\/922\/29c\/8de92229c2917ddeda5d58c9b9f41f89.svg\" width=\"43\" height=\"20\"\/><\/em> (with some precision <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/003\/9d2\/ecd\/0039d2ecda82e325f0ecd1953b4698a7.svg\" width=\"9\" height=\"12\"\/><\/em>) given the value <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p=x\" alt=\"p=x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/be8\/4dc\/da4\/be84dcda4f829b7dd993eb82c3ece8bf.svg\" width=\"48\" height=\"15\"\/><\/em>. If the forecast is unbiased and it is given to us, to encode <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cf7\/58e\/8b2\/cf758e8b2c9599914e1eda3447f412de.svg\" width=\"7\" height=\"16\"\/><\/em> with a certain precision, it is simpler to write the code for the discrepancy <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi=t- p\" alt=\"\\xi=t- p\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2cd\/25b\/bb7\/2cd25bbb79045c66c7026a0bd5d444d9.svg\" width=\"75\" height=\"21\"\/><\/em>, which is a random variable with a zero mean and a smaller variance than the variance of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7e5\/31b\/b91\/7e531bb9197631c54fba2455c1152eb2.svg\" width=\"7\" height=\"16\"\/><\/em>. These considerations lead to another formulation of the forecasting problem as a maximization of MI:<\/p>\n<p><strong>ML-task \u21163.3:<\/strong> Train a model <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict(f_1, \\ldots, f_k)\" alt=\"predict(f_1, \\ldots, f_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/80f\/614\/29a\/80f61429a0e539590123b76fd43a3be8.svg\" width=\"157\" height=\"22\"\/><\/em> based on the given training pool, such that encoding the discrepancy <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target-predict\" alt=\"target-predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b1c\/61f\/c79\/b1c61fc790777ba755f0269ba6140c8e.svg\" width=\"136\" height=\"21\"\/><\/em> within an accuracy of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cae\/ee3\/e61\/caeee3e6100a7a82fa6f88733aecfbba.svg\" width=\"9\" height=\"12\"\/><\/em> requires the minimum number of bits.<\/p>\n<p>In this task, the implication is the naive encoding of numbers, where all significant digits are recorded. For instance, assuming a fixed precision of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon = 0.000001\" alt=\"\\varepsilon = 0.000001\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/42d\/f76\/a3d\/42df76a3db4361c5ab61abf1cc02b2ce.svg\" width=\"109\" height=\"17\"\/><\/em>, a number like <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"-0.000123456789\\pm 0.000001\" alt=\"-0.000123456789\\pm 0.000001\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dd7\/70d\/73b\/dd770d73b52ecc6d4bf1c556b1cd47ee.svg\" width=\"245\" height=\"18\"\/><\/em> is logically encoded as &#171;-123&#187;. Here, one bit is spent on the sign (+ or &#8212; at the beginning), and we disregard all digits starting from the seventh place after the decimal point. We only record the significant figures without listing leading zeros. The last digit in the code is understood to be at the sixth place after the decimal point. In this encoding, the smaller the average error, the fewer bits are needed to encode all errors in the test pool. The value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon\" alt=\"\\varepsilon\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cae\/ee3\/e61\/caeee3e6100a7a82fa6f88733aecfbba.svg\" width=\"9\" height=\"12\"\/><\/em> must be sufficiently small. Beyond this naive encoding, it&#8217;s crucial to apply Huffman encoding to further compress the data based on differences in the probabilities of various errors.<\/p>\n<p>In this formulation, we are, in a sense, forced to define our own Loss function. Some tend to view this as a criterion for choosing the right Loss function: if you minimize mse, it&#8217;s good when <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/P(t= y | p = x))\" alt=\"\\log(1\/P(t= y | p = x))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d75\/097\/b34\/d75097b3486a9aefcc45e338b90acbf6.svg\" width=\"185\" height=\"22\"\/><\/em> tends towards <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"A \\cdot (y  - x)^2 + B\" alt=\"A \\cdot (y  - x)^2 + B\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e41\/948\/5f2\/e419485f2e97fcf18f10074b54a5a8bc.svg\" width=\"136\" height=\"25\"\/><\/em> as the training and test pools grow, meaning the discrepancy distribution approximates normality. When minimizing L1-error, it&#8217;s favorable if <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/P(t= y | p = x))\" alt=\"\\log(1\/P(t= y | p = x))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d75\/097\/b34\/d75097b3486a9aefcc45e338b90acbf6.svg\" width=\"185\" height=\"22\"\/><\/em>tends towards <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"A\\cdot |y  - x| + B\" alt=\"A\\cdot |y  - x| + B\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/255\/0e1\/99e\/2550e199e7ce388e63d2a6a6a5e89866.svg\" width=\"123\" height=\"22\"\/><\/em>, indicating the discrepancy distribution approximates the Laplace distribution. In general, approximate equality <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P(t = y| p=x) \\approx e^{-A \\cdot Loss(y,x) + B}\" alt=\"P(t = y| p=x) \\approx e^{-A \\cdot Loss(y,x) + B}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/14a\/ddc\/0af\/14addc0af9d13866f32651bd696ab2d7.svg\" width=\"267\" height=\"26\"\/><\/em> is expected. If not, either you haven&#8217;t completed the ML task, or your problem doesn&#8217;t fall into the category of good problems.<\/p>\n<p>Apparently, under certain conditions, these arguments hold in the other direction as well. If you have an ideal solution to ML-task \u21163.3, studying the discrepancy distribution for its solution reveals the Loss function that should be used to extract the maximum information from the signal.<\/p>\n<h2>Log-Likelihood and Mutual Information<\/h2>\n<p><strong>An example from real life:<\/strong> Implement a deterministic function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(\u043f\u043e\u043b, \u0432\u043e\u0437\u0440\u0430\u0441\u0442, \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435\\ 10\\ \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0445\\ \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432, \\ldots)\" alt=\"\\mathcal{P}(\u043f\u043e\u043b, \u0432\u043e\u0437\u0440\u0430\u0441\u0442, \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435\\ 10\\ \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0445\\ \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432, \\ldots)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/973\/ddf\/389\/973ddf38902da93a1aa88c717da52216.svg\" width=\"395\" height=\"27\"\/><\/em> predicting the probability, <em>p<\/em> , that a user will click on a given advertisement.<\/p>\n<p>Tasks of this type, where you need to forecast a Boolean variable (a variable that takes &#171;Yes&#187; or &#171;No&#187; values), are referred to as binary classification problems. <br \/>To solve them, the maximum likelihood method is typically used. Specifically, it is assumed that the prediction, <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict\" alt=\"predict\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2e0\/32f\/f54\/2e032ff5467ec845b67aefd94915b36d.svg\" width=\"61\" height=\"20\"\/><\/em>, should return a real number from 0 to 1, corresponding to the probability that the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target = 1\" alt=\"target = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/347\/2da\/b96\/3472dab9661c723990ef458101fb3daf.svg\" width=\"87\" height=\"21\"\/><\/em> (user clicks on the ad). When training the predictor on the training set, internal model parameters (also known as weights) can be adjusted to maximize the probability of observing what is in the training set.<\/p>\n<p>Usually, it&#8217;s not just the probability that&#8217;s maximized but a combination of this probability and a regularization component. There are no restrictions on how developers design this regularization component. Moreover, the training algorithm can be anything; what matters are just two things:<\/p>\n<ul>\n<li>\n<p>During training, the algorithm doesn&#8217;t &#171;see&#187; data from the test pool.<\/p>\n<\/li>\n<li>\n<p>Predictors are compared based on the probability estimates of events in the test pool.<\/p>\n<\/li>\n<\/ul>\n<p>The probability of observing what we see in the pool, when applied to the model, is referred to as <strong>the model likelihood<\/strong>. In other words, we talk about the &#8216;probability of an event&#8217; and &#8216;model likelihood,&#8217; but we don&#8217;t talk about the &#8216;probability of a model&#8217; or &#8216;event likelihood.&#8217;<\/p>\n<p>Here&#8217;s an example test pool consisting of three rows:<\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">i<\/p>\n<\/td>\n<td>\n<p align=\"left\"><em>f<\/em><sub>1<\/sub><\/p>\n<\/td>\n<td>\n<p align=\"left\"><em>f<\/em><sub>1<\/sub><\/p>\n<\/td>\n<td>\n<p align=\"left\"><em>f<\/em><sub>1<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">target<\/p>\n<\/td>\n<td>\n<p align=\"left\">predict=<br \/>P(target=1)<\/p>\n<\/td>\n<td>\n<p align=\"left\">P(target=0)<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">1<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">0<\/p>\n<\/td>\n<td>\n<p align=\"left\"><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p_1\" alt=\"p_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ed2\/5c8\/f94\/ed25c8f9454703708e61cf52ffbc9f91.svg\" width=\"19\" height=\"15\"\/><\/em><\/p>\n<\/td>\n<td>\n<p align=\"left\"><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"1 - p_1\" alt=\"1 - p_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/797\/664\/1da\/7976641daed543c7f5643c456d262cd3.svg\" width=\"52\" height=\"20\"\/><\/em><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">2<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">1<\/p>\n<\/td>\n<td>\n<p align=\"left\"><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p_2\" alt=\"p_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/58a\/d8e\/3a2\/58ad8e3a23ea5019e59dc622ce868e09.svg\" width=\"19\" height=\"15\"\/><\/em><\/p>\n<\/td>\n<td>\n<p align=\"left\"><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"1-p_2\" alt=\"1-p_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d03\/f04\/e57\/d03f04e575fc1b8b8ee3ddade2995072.svg\" width=\"52\" height=\"20\"\/><\/em><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">3<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">0<\/p>\n<\/td>\n<td>\n<p align=\"left\"><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p_3\" alt=\"p_3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bca\/820\/de8\/bca820de8b4152ca81b7f18b03127ffc.svg\" width=\"19\" height=\"15\"\/><\/em><\/p>\n<\/td>\n<td>\n<p align=\"left\"><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"1-p_3\" alt=\"1-p_3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7fe\/041\/867\/7fe041867e4440e2aa4f283179d91bcd.svg\" width=\"52\" height=\"20\"\/><\/em><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td data-colwidth=\"100\" width=\"100\">\n<p align=\"left\">\n<\/td>\n<td>\n<p align=\"left\">\n<\/td>\n<td>\n<p align=\"left\">\n<\/td>\n<td colspan=\"4\" data-colwidth=\"0,100,0,0\" width=\"0\">\n<p align=\"left\"><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{Likelihood}=(1-p_1)\\cdot p_2\\cdot(1-p_3)\" alt=\"\\mathrm{Likelihood}=(1-p_1)\\cdot p_2\\cdot(1-p_3)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/674\/c34\/eae\/674c34eae33f3c07d8a125bd4fc82d06.svg\" width=\"297\" height=\"22\"\/><\/em><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>It&#8217;s more convenient to work with the LogLikelihood value:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{LogLikelihood} = \\log((1 - p_1)\\cdot p_2\\cdot (1 - p_3)) = \\log(1 - p_1) + \\log (p_2) + \\log(1 - p_3)\" alt=\"\\mathrm{LogLikelihood} = \\log((1 - p_1)\\cdot p_2\\cdot (1 - p_3)) = \\log(1 - p_1) + \\log (p_2) + \\log(1 - p_3)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/828\/1e0\/e7b\/8281e0e7bf50b7ad453f9802c479f238.svg\" width=\"686\" height=\"22\"\/><\/p>\n<p>Rows with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target=1\" alt=\"target=1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/14b\/007\/527\/14b0075275bc5f0461349cd42a47ef64.svg\" width=\"87\" height=\"21\"\/><\/em> contribute to the total Log-Likelihood as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(predict)\" alt=\"\\log(predict)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c67\/34b\/c5b\/c6734bc5b6c9c800e9ad851f520f69a9.svg\" width=\"100\" height=\"22\"\/><\/em>, and rows with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target = 0\" alt=\"target = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e93\/46e\/032\/e9346e032d4e67591b65ba872b8e29a0.svg\" width=\"87\" height=\"21\"\/><\/em> contribute as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1 - predict)\" alt=\"\\log(1 - predict)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c15\/9fc\/c0e\/c159fcc0e590465f37adeed36efddcdb.svg\" width=\"134\" height=\"22\"\/><\/em>.<\/p>\n<p>In a simplified form, the binary classification problem looks like this:<\/p>\n<p>ML-task \u21163.4: Given a training log. Find a deterministic function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict(f_1,f_2,\\ldots),\" alt=\"predict(f_1,f_2,\\ldots),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f79\/b29\/1ff\/f79b291ff135bfc09207749b5e9f356d.svg\" width=\"159\" height=\"22\"\/><\/em> so that the value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{LogLikelihood}(predict, target)\" alt=\"\\mathrm{LogLikelihood}(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f81\/a90\/baf\/f81a90bafb12323f34e214a6c1d2c42f.svg\" width=\"256\" height=\"22\"\/><\/em>on the test pool is maximized.<\/p>\n<p>Let&#8217;s formulate a similar task in terms of maximizing MI.<\/p>\n<p><strong>ML-task \u21163.5:<\/strong> Find a deterministic function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p=predict(f_1,f_2,\\ldots),\" alt=\"p=predict(f_1,f_2,\\ldots),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d65\/954\/ee7\/d65954ee7b049b47c8219bcfbccfa4bb.svg\" width=\"194\" height=\"22\"\/><\/em> such that a random discrete variable <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi\" alt=\"\\xi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2c9\/cb7\/6e9\/2c9cb76e93e212ab8cbb8bd92b70add0.svg\" width=\"9\" height=\"21\"\/><\/em>  taking values 0 and 1 with probabilities <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{p,\\; 1 - p\\},\" alt=\"\\{p,\\; 1 - p\\},\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7ce\/cb7\/9fe\/7cecb79fe0db0b759e6a721cbca82ee0.svg\" width=\"92\" height=\"22\"\/><\/em> has the maximum possible value of mutual information <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(\\xi, target)\" alt=\"\\mathrm{MI}(\\xi, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f08\/7ab\/7ff\/f087ab7ffbc9179e0e7ce1c7945c3266.svg\" width=\"109\" height=\"22\"\/><\/em> with the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/930\/2e5\/7c4\/9302e57c48dd94c93c32044ed5cdf631.svg\" width=\"52\" height=\"20\"\/><\/em> variable.  <\/p>\n<p><strong>Statement 3.2:<\/strong> If your model is such that <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi = predict - target\" alt=\"\\xi = predict - target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/395\/507\/416\/3955074167526886dc46bee42e79a58d.svg\" width=\"170\" height=\"21\"\/><\/em>\u00a0is a random variable with a zero mean (in other words, the prediction is unbiased), then ML-task \u21163.2.2 and ML-task \u21163.2.1 are equivalent. That is, the task &#171;maximize MI(target, predict)&#187; gives the same answer as the task &#171;maximize LogLikelihood.&#187;<\/p>\n<p>The requirement that the prediction is unbiased, or in other words, doesn&#8217;t require calibration, isn&#8217;t a complex demand. In classification tasks, if you&#8217;re using Gradient Boosted Trees or neural networks with appropriate hyperparameters (learning rate, number of iterations), the prediction becomes unbiased. Specifically, if you take events with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict \\in [x - \\varepsilon, x + \\varepsilon],\" alt=\"predict \\in [x - \\varepsilon, x + \\varepsilon],\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7ff\/bcc\/251\/7ffbcc251020a20865b3798702bf07e3.svg\" width=\"198\" height=\"22\"\/><\/em>\u00a0you get a set of events where:<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p_{fact} = { \\mathrm{number\\_of\\_lines\\_with\\_target\\_1} \\over  \\mathrm{number\\_of\\_lines}} = {\\mathrm{clicks} \\over  \\mathrm{impressions}}\\approx x\" alt=\"p_{fact} = { \\mathrm{number\\_of\\_lines\\_with\\_target\\_1} \\over  \\mathrm{number\\_of\\_lines}} = {\\mathrm{clicks} \\over  \\mathrm{impressions}}\\approx x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eaf\/f29\/638\/eaff29638644399b4dcac6f9e732370f.svg\" width=\"508\" height=\"47\"\/><\/em>  <\/p>\n<p>In classification tasks, I&#8217;m accustomed to calling rows where the <em>target = 1<\/em> as clicks and rows with <em>target = 0<\/em> as non-clicks. Clicks plus non-clicks constitute the set of all events, termed impressions. The actual ratio of clicks to impressions is called <a href=\"https:\/\/en.wikipedia.org\/wiki\/Click-through_rate\" rel=\"noopener noreferrer nofollow\">CTR<\/a> \u2014 Click Through Rate.<\/p>\n<p>To prove Statement 3.2, let&#8217;s utilize the solution to the problem.<\/p>\n<p><strong>Task 3.10.<\/strong> How can the value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(\\xi,\\; \\mu)\" alt=\"\\mathrm{MI}(\\xi,\\; \\mu)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6aa\/b13\/b25\/6aab13b25e7711d1f91d80eab406d62f.svg\" width=\"75\" height=\"22\"\/><\/em>be estimated based on N measurements of two random variables &#8212; a discrete variable <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi\" alt=\"\\xi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d54\/5a7\/232\/d545a7232cc9f9116cb6c8bb7f4ac989.svg\" width=\"9\" height=\"21\"\/><\/em> taking values from 1 to M, and a boolean random variable <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mu\" alt=\"\\mu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4a4\/d78\/235\/4a4d782359c2312c27082d9c66b0c519.svg\" width=\"12\" height=\"16\"\/><\/em>?<\/p>\n<p>One way to think about this task: <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi\" alt=\"\\xi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b17\/e21\/f66\/b17e21f667224bd1f3fd557cdec00aea.svg\" width=\"9\" height=\"21\"\/><\/em>\u00a0is a categorical variable related to an advertising announcement; its values can be interpreted as class identifiers, while <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mu = \\mathrm{IsClick}\" alt=\"\\mu = \\mathrm{IsClick}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f51\/6d5\/6ee\/f516d56eec62195a305b4d504a697609.svg\" width=\"96\" height=\"21\"\/><\/em>indicates whether a click occurred. The data regarding the measurements of pairs<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(\\xi, \\mu)\" alt=\"(\\xi, \\mu)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/14d\/c7a\/2b3\/14dc7a2b39c051a68a5a5345bde4dbeb.svg\" width=\"44\" height=\"22\"\/><\/em>represents a log of clicks and non-clicks.<\/p>\n<p>To solve this problem, it&#8217;s convenient to use the formula:<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(\\xi,\\mu) = H(\\mu) - H(\\mu | \\xi)=H(\\mu)-{\\sum}_i P(\\xi=i)\\cdot H(\\mu|\\xi=i)\" alt=\"\\mathrm{MI}(\\xi,\\mu) = H(\\mu) - H(\\mu | \\xi)=H(\\mu)-{\\sum}_i P(\\xi=i)\\cdot H(\\mu|\\xi=i)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/467\/044\/7cd\/4670447cd6b7bd488100bedbbba49eb8.svg\" width=\"527\" height=\"31\"\/><\/em><\/p>\n<p>Value <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(\\mu)=H(\\mathrm{ctr}_{0})\" alt=\"H(\\mu)=H(\\mathrm{ctr}_{0})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4cf\/c3d\/863\/4cfc3d863c3a5bc13ca5f6b96327230c.svg\" width=\"136\" height=\"22\"\/><\/em>, where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_{0} = \\mathrm{ctr}_{total} = \\mathrm{clicks}_{total} \/ \\mathrm{impressions}_{total}\" alt=\"\\mathrm{ctr}_{0} = \\mathrm{ctr}_{total} = \\mathrm{clicks}_{total} \/ \\mathrm{impressions}_{total}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/369\/3a0\/572\/3693a05721cc25a1507545dd2f9e3778.svg\" width=\"353\" height=\"22\"\/><\/em> &#8212; the average CTR over the entire log.<\/p>\n<p>And <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(\\mu | \\xi = i) = H(\\mathrm{ctr}_i)\" alt=\"H(\\mu | \\xi = i) = H(\\mathrm{ctr}_i)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1f0\/e8c\/72c\/1f0e8c72cab60c8fa1bdf5b0617b5f48.svg\" width=\"180\" height=\"22\"\/><\/em>, where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_{i} = \\mathrm{clicks}_{i} \/ \\mathrm{impressions}_{i}\" alt=\"\\mathrm{ctr}_{i} = \\mathrm{clicks}_{i} \/ \\mathrm{impressions}_{i}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6f5\/0ca\/05f\/6f50ca05f722801cb4486de4ac981ef9.svg\" width=\"224\" height=\"22\"\/><\/em> &#8212; CTR for events where \u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\xi = i\" alt=\"\\xi = i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ab\/0f8\/818\/1ab0f8818b26808611b4650533c06295.svg\" width=\"41\" height=\"21\"\/><\/em>, naturally called CTR in class i. Substituting these into the formula and we get:<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(\\mu, \\xi) = H(\\mu) - H(\\mu | \\xi) = \\\\ = H(\\mathrm{ctr}_{0}) - \\displaystyle\\sum_{i\\in classes} { \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total} } \\cdot H(\\mathrm{ctr}_i) = \\\\  = - (\\mathrm{ctr}_{0}\\cdot \\log(\\mathrm{ctr}_{0}) + (1 - \\mathrm{ctr}_{0})\\cdot \\log(1 - \\mathrm{ctr}_{0})) +\\\\  +  \\displaystyle\\sum_{i\\in classes} {\\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\cdot ( \\mathrm{ctr}_{i}\\cdot \\log(\\mathrm{ctr}_{i}) + (1 - \\mathrm{ctr}_{i})\\cdot \\log(1 - \\mathrm{ctr}_{i}))\" alt=\"\\mathrm{MI}(\\mu, \\xi) = H(\\mu) - H(\\mu | \\xi) = \\\\ = H(\\mathrm{ctr}_{0}) - \\displaystyle\\sum_{i\\in classes} { \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total} } \\cdot H(\\mathrm{ctr}_i) = \\\\  = - (\\mathrm{ctr}_{0}\\cdot \\log(\\mathrm{ctr}_{0}) + (1 - \\mathrm{ctr}_{0})\\cdot \\log(1 - \\mathrm{ctr}_{0})) +\\\\  +  \\displaystyle\\sum_{i\\in classes} {\\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\cdot ( \\mathrm{ctr}_{i}\\cdot \\log(\\mathrm{ctr}_{i}) + (1 - \\mathrm{ctr}_{i})\\cdot \\log(1 - \\mathrm{ctr}_{i}))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/521\/8db\/80c\/5218db80c46aa29610ee22678d8ea8fa.svg\" width=\"693\" height=\"169\"\/><\/em>  <\/p>\n<p>Let&#8217;s focus on the first term and express it as a sum over classes: <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"H(\\mu) =  - \\left(\\displaystyle{\\mathrm{clicks}_{total} \\over \\mathrm{impressions}_{total}} \\log(\\mathrm{ctr}_{0}) + \\displaystyle{\\mathrm{notclicks}_{total} \\over \\mathrm{impressions}_{total}}\\cdot \\log(1 - \\mathrm{ctr}_{0})\\right)  = \\\\\" alt=\"H(\\mu) =  - \\left(\\displaystyle{\\mathrm{clicks}_{total} \\over \\mathrm{impressions}_{total}} \\log(\\mathrm{ctr}_{0}) + \\displaystyle{\\mathrm{notclicks}_{total} \\over \\mathrm{impressions}_{total}}\\cdot \\log(1 - \\mathrm{ctr}_{0})\\right)  = \\\\\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5c9\/fa9\/7df\/5c9fa97df8cc80a0bf79d5b4e41ad674.svg\" width=\"697\" height=\"58\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"= - \\displaystyle\\sum_{i \\in classes}\\left({\\mathrm{clicks}_i \\over \\mathrm{impressions}_{total}} \\log(\\mathrm{ctr}_{0}) + {\\mathrm{notclicks}_i \\over \\mathrm{impressions}_{total}}\\cdot \\log(1 - \\mathrm{ctr}_{0})\\right) =\" alt=\"= - \\displaystyle\\sum_{i \\in classes}\\left({\\mathrm{clicks}_i \\over \\mathrm{impressions}_{total}} \\log(\\mathrm{ctr}_{0}) + {\\mathrm{notclicks}_i \\over \\mathrm{impressions}_{total}}\\cdot \\log(1 - \\mathrm{ctr}_{0})\\right) =\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a7a\/138\/780\/a7a13878028ddc1cb51461e8dd180b65.svg\" width=\"640\" height=\"56\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"- \\displaystyle\\sum_{i \\in classes}\\left({\\mathrm{ctr}_i \\cdot \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\log(\\mathrm{ctr}_{0}) + {(1 - \\mathrm{ctr}_i)\\cdot \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\log(1 - \\mathrm{ctr}_{0})\\right).\" alt=\"- \\displaystyle\\sum_{i \\in classes}\\left({\\mathrm{ctr}_i \\cdot \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\log(\\mathrm{ctr}_{0}) + {(1 - \\mathrm{ctr}_i)\\cdot \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\log(1 - \\mathrm{ctr}_{0})\\right).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c22\/251\/39f\/c2225139f2e298d4247c95fbe4f556f5.svg\" width=\"688\" height=\"56\"\/><\/p>\n<p>Substituting this into the expression for MI, and combining both parts into one sum over classes, we get <strong>the final expression for MI<\/strong>:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\displaystyle\\sum_{i \\in classes} { \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\cdot \\left(\\mathrm{ctr}_{i}\\cdot \\log\\left({\\mathrm{ctr}_{i} \\over \\mathrm{ctr}_{0}}\\right) + (1 - \\mathrm{ctr}_{i})\\cdot \\log\\left({1 - \\mathrm{ctr}_{i} \\over 1 - \\mathrm{ctr}_{0}}\\right)\\right) = \\\\ = \\displaystyle{1 \\over \\mathrm{impressions}_{total}} \\displaystyle\\sum_{e \\in \\mathrm{impressions}} \\mathrm{ctr}_{i(e)}\\cdot \\log{\\left({\\mathrm{ctr}_{i(e)} \\over \\mathrm{ctr}_{0}}\\right)} + (1 - \\mathrm{ctr}_{i(e)})\\cdot \\log{\\left({1 - \\mathrm{ctr}_{i(e)} \\over 1 - \\mathrm{ctr}_{0}}\\right)}\" alt=\"\\displaystyle\\sum_{i \\in classes} { \\mathrm{impressions}_i \\over \\mathrm{impressions}_{total}} \\cdot \\left(\\mathrm{ctr}_{i}\\cdot \\log\\left({\\mathrm{ctr}_{i} \\over \\mathrm{ctr}_{0}}\\right) + (1 - \\mathrm{ctr}_{i})\\cdot \\log\\left({1 - \\mathrm{ctr}_{i} \\over 1 - \\mathrm{ctr}_{0}}\\right)\\right) = \\\\ = \\displaystyle{1 \\over \\mathrm{impressions}_{total}} \\displaystyle\\sum_{e \\in \\mathrm{impressions}} \\mathrm{ctr}_{i(e)}\\cdot \\log{\\left({\\mathrm{ctr}_{i(e)} \\over \\mathrm{ctr}_{0}}\\right)} + (1 - \\mathrm{ctr}_{i(e)})\\cdot \\log{\\left({1 - \\mathrm{ctr}_{i(e)} \\over 1 - \\mathrm{ctr}_{0}}\\right)}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/efb\/39f\/e71\/efb39fe71d9301236df20f4ec6b453a0.svg\" width=\"701\" height=\"119\"\/><\/p>\n<p>In the last equality, we replaced summation over classes with summation over log entries to show the similarity of the formula to the LogLikelihood formula.<\/p>\n<p>When the classes are merely <em>prediction bins<\/em> and the prediction is unbiased (meaning the average prediction in a bin matches the real <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}\" alt=\"\\mathrm{ctr}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/321\/0f0\/f76\/3210f0f7640a98972e82f2962e95248f.svg\" width=\"24\" height=\"16\"\/><\/em> in that bin), we have:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{LogLikelihood(predict)}=\\\\ = \\sum_{e\\in \\mathrm{impressions}}\\mathrm{ctr}_{i(e)}\\cdot \\log(\\mathrm{ctr}_{i(e)}) + (1-\\mathrm{ctr}_{i(e)})\\cdot\\log(1-\\mathrm{ctr}_{i(e)})\" alt=\"\\mathrm{LogLikelihood(predict)}=\\\\ = \\sum_{e\\in \\mathrm{impressions}}\\mathrm{ctr}_{i(e)}\\cdot \\log(\\mathrm{ctr}_{i(e)}) + (1-\\mathrm{ctr}_{i(e)})\\cdot\\log(1-\\mathrm{ctr}_{i(e)})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9bc\/034\/68f\/9bc03468f3033da5895f2ecaf2f5b983.svg\" width=\"697\" height=\"75\"\/><\/p>\n<p>And if the prediction equals a constant <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_0\" alt=\"\\mathrm{ctr}_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e02\/ad1\/160\/e02ad116042d99b391e34af623e1970e.svg\" width=\"33\" height=\"19\"\/><\/em>\u200b, the likelihood expression becomes:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{LogLikelihood}(\\mathrm{predict}=\\mathrm{ctr}_0)=\\\\ = \\sum_{e\\in \\mathrm{impressions}}\\mathrm{ctr}_{0}\\cdot \\log(\\mathrm{ctr}_{0}) + (1-\\mathrm{ctr}_{0})\\cdot\\log(1-\\mathrm{ctr}_{0})=\\\\= \\sum_{e\\in \\mathrm{impressions}}\\mathrm{ctr}_{i(e)}\\cdot \\log(\\mathrm{ctr}_{0}) + (1-\\mathrm{ctr}_{i(0)})\\cdot\\log(1-\\mathrm{ctr}_{0})\" alt=\"\\mathrm{LogLikelihood}(\\mathrm{predict}=\\mathrm{ctr}_0)=\\\\ = \\sum_{e\\in \\mathrm{impressions}}\\mathrm{ctr}_{0}\\cdot \\log(\\mathrm{ctr}_{0}) + (1-\\mathrm{ctr}_{0})\\cdot\\log(1-\\mathrm{ctr}_{0})=\\\\= \\sum_{e\\in \\mathrm{impressions}}\\mathrm{ctr}_{i(e)}\\cdot \\log(\\mathrm{ctr}_{0}) + (1-\\mathrm{ctr}_{i(0)})\\cdot\\log(1-\\mathrm{ctr}_{0})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/868\/363\/bb2\/868363bb2a7fc8d4f6e5ae5e4536e034.svg\" width=\"697\" height=\"128\"\/><\/p>\n<p>Replacing <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_0\" alt=\"\\mathrm{ctr}_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6e9\/298\/ef0\/6e9298ef0566b45936b58ec7dafeffc6.svg\" width=\"33\" height=\"19\"\/><\/em> with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_{i(e)}\" alt=\"\\mathrm{ctr}_{i(e)}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8c6\/f5b\/cf6\/8c6f5bcf6f911d4cfaf0cc2e5af653ce.svg\" width=\"48\" height=\"23\"\/><\/em> is valid since the expressions with logarithms are constant, and the average value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_{i(e)}\" alt=\"\\mathrm{ctr}_{i(e)}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8c6\/f5b\/cf6\/8c6f5bcf6f911d4cfaf0cc2e5af653ce.svg\" width=\"48\" height=\"23\"\/><\/em>over all impressions equals <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_0\" alt=\"\\mathrm{ctr}_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6e9\/298\/ef0\/6e9298ef0566b45936b58ec7dafeffc6.svg\" width=\"33\" height=\"19\"\/><\/em>.<\/p>\n<p>Here, we see that <em>the final expression<\/em> <em>for MI<\/em> is simply the normalized difference between two expressions for LogLikelihood:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(\\xi, \\mu) = \\ \\mathrm{MI}(predict, \\mu) =\\\\ \\ {1 \\over \\mathrm{impressions}_{total}}\\cdot (\\mathrm{LogLikelihood}(predict) - \\mathrm{LogLikelihood}(predict = \\mathrm{ctr}_{0})\" alt=\"\\mathrm{MI}(\\xi, \\mu) = \\ \\mathrm{MI}(predict, \\mu) =\\\\ \\ {1 \\over \\mathrm{impressions}_{total}}\\cdot (\\mathrm{LogLikelihood}(predict) - \\mathrm{LogLikelihood}(predict = \\mathrm{ctr}_{0})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/98f\/de4\/1f1\/98fde41f1cc10740cdaa962b6fff29da.svg\" width=\"697\" height=\"75\"\/><\/p>\n<p>Therefore, in the case of an unbiased prediction, the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target)\" alt=\"\\mathrm{MI}(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/920\/59a\/ba5\/92059aba5181aabf026c76b1444ee026.svg\" width=\"161\" height=\"22\"\/><\/em>is a linear function of the LogLikelihood.<\/p>\n<p>By the way, the quantity <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{LogLikelihood}(predict_1) - \\mathrm{LogLikelihood}(predict_2)\" alt=\"\\mathrm{LogLikelihood}(predict_1) - \\mathrm{LogLikelihood}(predict_2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6de\/5d4\/986\/6de5d4986c737fbd375ce40438f70f8a.svg\" width=\"433\" height=\"22\"\/><\/em> is called the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Likelihood-ratio_test\" rel=\"noopener noreferrer nofollow\">Log Likelihood Ratio<\/a> of two predictors, and it&#8217;s naturally normalized by the number of events (impressions). <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict_2\" alt=\"predict_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6c2\/2ef\/177\/6c22ef177ea24dc32354585fed072dbc.svg\" width=\"70\" height=\"20\"\/><\/em>often represents a basic prediction, in our case, a constant prediction. It&#8217;s often worthwhile to monitor the graph of LogLikelihoodRatio \/ impressions, rather than LogLikelihood \/ impressions, using a <em>robust<\/em> (simple, reliable, not easily broken) prediction based on a few factors as the <em>baseline<\/em> <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict_2\" alt=\"predict_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bb2\/6d1\/16f\/bb26d116fabf2ec89f71e5bbf29beae0.svg\" width=\"70\" height=\"20\"\/><\/em>. Sometimes, using <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{LogLikelihoodRatio} \/ \\mathrm{impressions} \\cdot \\mathrm{ctr}_0^{\\gamma}\" alt=\"\\mathrm{LogLikelihoodRatio} \/ \\mathrm{impressions} \\cdot \\mathrm{ctr}_0^{\\gamma}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/74d\/087\/07d\/74d08707db649bfa3319757a6d7dc02f.svg\" width=\"323\" height=\"25\"\/><\/em> for some <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\gamma\" alt=\"\\gamma\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2b7\/51d\/93d\/2b751d93d17ba63f8be41c9d51bc3fc6.svg\" width=\"11\" height=\"16\"\/><\/em> can eliminate correlation or anti-correlation with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{ctr}_0\" alt=\"\\mathrm{ctr}_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/094\/008\/c1f\/094008c1fe407cdcc084407f5951d673.svg\" width=\"33\" height=\"19\"\/><\/em> and better visualize prediction break points.<\/p>\n<p>Thus, for an unbiased prediction, the MI between the prediction and the signal equals the normalized Log Likelihood Ratio of your prediction and the best constant prediction.<\/p>\n<h2>Evaluation of Mutual Information = Machine Learning<\/h2>\n<p>Two statements \u2014 <strong>3.1<\/strong> and <strong>3.2<\/strong> \u2014 assert that <strong>Mutual Information is a quality metric<\/strong> that, under certain assumptions, corresponds to two metrics in prediction tasks \u2014 the mean squared error in predicting a real value with a normal distribution and LogLikelihood in binary classification tasks.<\/p>\n<p><strong>The Mutual Information (MI)<\/strong> itself cannot be used as a loss function because it&#8217;s not a metric on data, i.e., it doesn&#8217;t represent the sum of loss function values across elements in a pool. The notion of &#171;correspondence&#187; can be clarified as follows: practically, almost all loss functions ultimately aim to maximize <strong>the Mutual Information<\/strong> between the predict and target, albeit with different additional terms.<\/p>\n<p>Perhaps the following two statements (again, without proof) shed light on this:<\/p>\n<p><strong>Statement 3.3:<\/strong> If you have a prediction based on factors <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_1,\\ldots,f_k\" alt=\"f_1,\\ldots,f_k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cca\/cc4\/e76\/ccacc4e762930c2eb60c639a47be07c1.svg\" width=\"81\" height=\"21\"\/><\/em>, and there&#8217;s a new factor <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_{k+1},\" alt=\"f_{k+1},\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4e1\/3ee\/f13\/4e13eef1377d04bf4b83119d7734841a.svg\" width=\"42\" height=\"21\"\/><\/em> such that <em><img class=\"formula inline\" source=\"\\mathrm{MI}(\\{f_{k+1}, predict\\}, target) > \\mathrm{MI}(predict, target),&#187; alt=&#187;\\mathrm{MI}(\\{f_{k+1}, predict\\}, target) > \\mathrm{MI}(predict, target),&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d47\/3d6\/b7f\/d473d6b7fe60d18101641c17a87d7c93.svg&#187; width=&#187;417&#8243; height=&#187;22&#8243;\/><\/em> then with a sufficiently large training pool, this factor will reduce your loss function if it&#8217;s normal. <strong>A Loss-function is considered normal<\/strong> if it decreases when, in any element of the pool, the predict value approaches the target. Mean squared error (MSE), <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_p\" alt=\"L_p\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4f2\/7a3\/29d\/4f27a329d7e11fc1470e75e3405348f9.svg\" width=\"22\" height=\"22\"\/><\/em>&#8212; error, LogLikelihood \u2014 they all represent normal Loss-functions. Going forward, let&#8217;s assume the loss function is normal.<\/p>\n<p>Any monotonic transformation of the prediction will be referred to as <strong>the calibration of the prediction.<\/strong><\/p>\n<p><strong>Statement 3.4 (requires specification of conditions):<\/strong> If you find a change in weights (or internal parameters) of your model that increases<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target),\" alt=\"\\mathrm{MI}(predict, target),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dd7\/e23\/8a5\/dd7e238a5760b6a4d9957e9320519a05.svg\" width=\"166\" height=\"22\"\/><\/em>then after proper calibration of the prediction, your Loss-function will increase.<\/p>\n<p>In these statements, MI cannot be replaced with any loss function. For instance, if you make weight changes in your model that decrease the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_1\" alt=\"L_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a33\/c84\/236\/a33c84236a353c2bce2429ed821b6325.svg\" width=\"22\" height=\"19\"\/><\/em>&#8212; error, it doesn&#8217;t imply that the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_2\" alt=\"L_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/556\/65f\/2dd\/55665f2dd4bc130eb4694d03a013f6d5.svg\" width=\"22\" height=\"19\"\/><\/em>&#8212; error will decrease even after proper calibration of the prediction to fit <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_2\" alt=\"L_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/225\/528\/c7c\/225528c7cf735d9106c04e60f7352183.svg\" width=\"22\" height=\"19\"\/><\/em>. The distinctness of MI is associated with the fact that, as mentioned earlier, it&#8217;s not exactly a loss function and inherently allows any calibration (meaning it doesn&#8217;t change under arbitrary strictly monotonic calibration of the prediction).<\/p>\n<p><strong>Task 3.11:<\/strong> Prove that in the case where the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target=\\mathcal{P}(f_1,f_2,\\ldots,w_1,w_2,\\ldots) + \\nu\" alt=\"target=\\mathcal{P}(f_1,f_2,\\ldots,w_1,w_2,\\ldots) + \\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/467\/a06\/cb9\/467a06cb9c4ba45873a1c47086fb8628.svg\" width=\"316\" height=\"22\"\/><\/em>, where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\nu\" alt=\"\\nu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/209\/a52\/597\/209a52597c48507dc7ba531e25a27c7c.svg\" width=\"10\" height=\"12\"\/><\/em> is random noise, and the model matches reality, as the training pool size increases, the weights tend toward the correct values for both <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_1\" alt=\"L_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a33\/c84\/236\/a33c84236a353c2bce2429ed821b6325.svg\" width=\"22\" height=\"19\"\/><\/em>and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_2\" alt=\"L_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0ae\/24b\/cc0\/0ae24bcc0785061f1bdd0e4c13286821.svg\" width=\"22\" height=\"19\"\/><\/em>Loss-functions. Additionally, if the noise has a symmetric distribution, both Loss-functions provide an unbiased prediction.<\/p>\n<p><strong>Task 3.12:<\/strong> Provide an example of a model and a real target where the <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_1\" alt=\"L_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a33\/c84\/236\/a33c84236a353c2bce2429ed821b6325.svg\" width=\"22\" height=\"19\"\/><\/em>and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"L_2\" alt=\"L_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e3c\/a15\/0a9\/e3ca150a9694eb89931f07311e4630a0.svg\" width=\"22\" height=\"19\"\/><\/em>loss functions yield different predictions even on a very large training pool, such that one cannot be transformed into the other by any monotonic transformation (i.e., the calibration of one prediction cannot be achieved from the other).<\/p>\n<p><strong>Statement 3.5:<\/strong> The task of estimating <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mi = \\mathrm{MI}(\\{f_1,\\ldots, f_k\\}, target)\" alt=\"mi = \\mathrm{MI}(\\{f_1,\\ldots, f_k\\}, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e1c\/7b8\/c04\/e1c7b8c045f12ad0892e2927fdb6ed85.svg\" width=\"251\" height=\"22\"\/><\/em>is equivalent to the task of constructing a prediction <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"predict=\\mathcal{P}(f_1,\\ldots, f_k)\" alt=\"predict=\\mathcal{P}(f_1,\\ldots, f_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/30c\/c81\/16c\/30cc8116cd7fa019794a525fbba51d73.svg\" width=\"197\" height=\"22\"\/><\/em> in some Loss-function.<\/p>\n<p>This statement suggests that the true value of mi is approximately equal to the supremum of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target)\" alt=\"\\mathrm{MI}(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cf6\/a82\/a23\/cf6a82a2397463cd384ee1100c8a0c18.svg\" width=\"161\" height=\"22\"\/><\/em>for all pairs (ML method, Loss-function), where ML method ::= (&#171;model structure&#187;, &#171;method of getting model weights&#187;), &#171;method of getting model weights&#187; ::= (&#171;algorithm&#187;, &#171;algorithm hyperparameters&#187;), and the equality is more accurate the larger the training pool.<\/p>\n<p>Essentially, the pair (ML method, loss function) that yields the highest value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target)\" alt=\"\\mathrm{MI}(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0b1\/3d8\/d30\/0b13d8d3077e65e11440ff83bba5f7e8.svg\" width=\"161\" height=\"22\"\/><\/em>close to mi is the model closest to reality, that is, how <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f_1,\\ldots,f_k\" alt=\"f_1,\\ldots,f_k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f5d\/24e\/d34\/f5d24ed34c59143571006d97ca4b6bf5.svg\" width=\"81\" height=\"21\"\/><\/em> and target are actually related.<\/p>\n<p><strong>In summary: we&#8217;ve formulated two profound connections between prediction tasks and MI:<\/strong><\/p>\n<ul>\n<li>\n<p><strong>Firstly, maximizing MI somewhat corresponds to minimizing a certain loss function.<\/strong><\/p>\n<\/li>\n<li>\n<p><strong>Secondly, &#171;MI estimation&#187; = &#171;ML&#187;, namely, estimating <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(\\{f_1,\\ldots, f_k\\}, target)\" alt=\"\\mathrm{MI}(\\{f_1,\\ldots, f_k\\}, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/406\/712\/0a0\/4067120a069f33dec7fe92c94183f3e4.svg\" width=\"201\" height=\"22\"\/><\/em> is equivalent to constructing a prediction <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{P}(f_1,\\ldots, f_k)\" alt=\"\\mathcal{P}(f_1,\\ldots, f_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/045\/986\/efb\/045986efb25aac5498722d8dbc9c1a6c.svg\" width=\"110\" height=\"22\"\/><\/em> for some Loss-function. The ML method and Loss-function that yield the maximum <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target)\" alt=\"\\mathrm{MI}(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aa3\/6a1\/16b\/aa36a116bb5c8819f19e757272e50d2a.svg\" width=\"161\" height=\"22\"\/><\/em>represent the most plausible model.<\/strong><\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/781874\/\"> https:\/\/habr.com\/ru\/articles\/781874\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p><a href=\"https:\/\/habr.com\/en\/articles\/763090\/\" rel=\"noopener noreferrer nofollow\">Part 1 &#8212; Entropy<\/a><\/p>\n<p><a href=\"https:\/\/habr.com\/en\/articles\/764942\/\" rel=\"noopener noreferrer nofollow\">Part 2 &#8212; Mutual Information<\/a><\/p>\n<p>In this third part, we will discuss Machine Learning, specifically the prediction task in the context of information theory.<\/p>\n<p>The concept of Mutual Information (MI) is related to the prediction task. In fact, the prediction task can be viewed as the problem of extracting information about the signal from the factors. Some part of the information about the signal is contained in the factors. If you write a function that calculates a value close to the signal based on the factors, then this will demonstrate that you have been able to extract MI between the signal and the factors.<\/p>\n<h2>What is Machine Learning?<\/h2>\n<p>To move forward, we need fundamental concepts from Machine Learning (ML), such as factors, target, loss function, training and test sets, overfitting and underfitting and their variations, regularization, and different types of data leakage.<\/p>\n<p><strong>Factors (features)<\/strong> are what you input, and <strong>the signal (target)<\/strong> is what you need to predict using the features. For example, if you need to forecast the temperature <strong>tomorrow at 12:00<\/strong> in a specific city, that&#8217;s the target, while you are given a set of numbers <strong>about today and previous days<\/strong>: temperature, pressure, humidity, wind direction, and wind speed in this and neighboring cities at different times of the day \u2013 these are the features.<\/p>\n<p><strong>Training Data<\/strong> is a set of examples (also known as samples) with known correct answers, meaning rows in a table that contain both the feature fields (features = (f1, f2, &#8230;, fn)) and the target field. Data is commonly divided into two parts \u2013 <strong>the training set<\/strong> and <strong>the test set<\/strong>. It looks something like this:<\/p>\n<p><strong>Training set:<\/strong><\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"left\"><strong><em>id<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>1<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>2<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>&#8230;<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>target<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>predict<\/em><\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">1<\/p>\n<\/td>\n<td>\n<p align=\"left\">1.234<\/p>\n<\/td>\n<td>\n<p align=\"left\">3.678<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">1.23<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">2<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.345<\/p>\n<\/td>\n<td>\n<p align=\"left\">6.123<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.34<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">18987<\/p>\n<\/td>\n<td>\n<p align=\"left\">1.432<\/p>\n<\/td>\n<td>\n<p align=\"left\">3.444<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;.<\/p>\n<\/td>\n<td>\n<p align=\"left\">5.67<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p><strong>Test set:<\/strong><\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"left\"><strong><em>id<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>1<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>f<\/em><sub>2<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>&#8230;<\/strong><\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\"><strong><em>target<\/em><\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong><em>predict<\/em><\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">18988<\/p>\n<\/td>\n<td>\n<p align=\"left\">6.321<\/p>\n<\/td>\n<td>\n<p align=\"left\">6.545<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">4.987<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">18989<\/p>\n<\/td>\n<td>\n<p align=\"left\">4.123<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.348<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">3.765<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">&#8230;.<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">30756<\/p>\n<\/td>\n<td>\n<p align=\"left\">2.678<\/p>\n<\/td>\n<td>\n<p align=\"left\">3.187<\/p>\n<\/td>\n<td>\n<p align=\"left\">&#8230;<\/p>\n<\/td>\n<td data-colwidth=\"117\" width=\"117\">\n<p align=\"left\">2.593<\/p>\n<\/td>\n<td>\n<p align=\"left\">?<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>In broad terms, the prediction task can be formulated in a Kaggle-style competition:<\/p>\n<p><strong>Prediction Task (ML Task):<\/strong> You are given a training set. Implement a function  in code that, based on the given features, returns a value as close as possible to the target. The measure of closeness is defined by a loss function, and the value of this function is called the prediction error: , where . <strong>The quality of the prediction<\/strong> is determined by the average error during the application of this prediction in real-life scenarios, but in practice, a test set hidden from you is used to evaluate this average error.<\/p>\n<p>The quantity  has a special name &#8212; <a href=\"https:\/\/en.wikipedia.org\/wiki\/Errors_and_residuals\" rel=\"noopener noreferrer nofollow\">the residual<\/a>. Two popular variants of loss functions for predicting real values are:<\/p>\n<ul>\n<li>\n<p>Mean Squared Error (MSE) &#8212; also known as the average squared residual.<\/p>\n<\/li>\n<li>\n<p>Mean Absolute Error (MAE) &#8212; also known as the L1 error.<\/p>\n<\/li>\n<\/ul>\n<p>In practice, the ML task is more general and high-level. Specifically, you need to develop a moderately universal <strong>ML model<\/strong> &#8212; a way to get functions  from a given training set and a specified loss function. You also need to perform <em>model evaluation<\/em>: monitor the prediction quality in a working system, be able to update trained models (step by step, creating new versions, or modifying the model&#8217;s internal weights in an online mode), improve the model&#8217;s quality, and control the cleanliness and quality of the features.<\/p>\n<p>The process of getting the function  from the training set is called <strong>training<\/strong>. Popular classes of ML models include:<\/p>\n<ul>\n<li>\n<p><strong>Linear Mode<\/strong>l<strong>:<\/strong> In a linear model, where , the training process typically involves parameter tuning , usually done through <a href=\"https:\/\/en.wikipedia.org\/wiki\/Gradient_descent\" rel=\"noopener noreferrer nofollow\">gradient descent<\/a>.<\/p>\n<\/li>\n<li>\n<p><strong>Gradient Boosted Trees (GBT):<\/strong> GBT is a model where the function looks like a sum of multiple terms (hundreds or thousands), with each term being <a href=\"https:\/\/en.wikipedia.org\/wiki\/Decision_tree\" rel=\"noopener noreferrer nofollow\">a decision tree<\/a>. In the nodes of these trees, there are conditions based on the features, and in the leaves, specific numbers are assigned. Each term can be thought of as a system of nested if-conditions on feature values, with simple numbers in the final leaves. GBT is not just about the solution being a sum of trees but also a specific algorithm for getting these terms. There are many ready-made programs for training GBT, such as <a href=\"https:\/\/catboost.ai\/\" rel=\"noopener noreferrer nofollow\">CatBoost<\/a> and <a href=\"https:\/\/github.com\/dmlc\/xgboost\" rel=\"noopener noreferrer nofollow\">xgboost<\/a>.<\/p>\n<\/li>\n<li>\n<p><strong>Neural Networks:<\/strong> In its simplest basic form, a neural network model appears as <em><\/em>,  , where  are matrices, and their sizes are determined by the model developer. The features are represented as a vector , and the operator  represents element-wise multiplication of a vector by a matrix followed by setting all negative values in the resulting vector to zero. Operators are applied from right to left, which is important in the case of this zeroing. The matrices are referred to as layers of the neural network, and the number of matrices determines the depth of the network. Instead of zeroing negatives, various other non-linear transformations can be applied. Without non-linear transformations after the matrix multiplication, all matrices could be collapsed into one, and the space of possible functions would not differ from what a linear model defines. I described a linear architecture for a neural network, but more complex architectures are possible. For instance:<\/p>\n<p><em><\/em>.    <\/p>\n<p>In addition to various element-wise non-linear transformations and matrix multiplications, neural networks can use operators for scalar vector products and element-wise maximum operations for two vectors of the same dimension, combining vectors into a longer one, and more. You can think of a general architecture for <strong>the prediction function<\/strong>, where a vector is input, and then the response is constructed using operators , non-linear functions , and weights . In this sense, neural networks can represent functions of quite a general form. In reality, the architecture of the function  is called a neural network when it contains something resembling a chain like . Essentially, we have a regression problem &#8212; to adjust parameters (weights) in a parametrically defined function to minimize the error. There are numerous methods for training neural networks, most of which are iterative, and the module responsible for weight updates is what programmers refer to as <a href=\"https:\/\/habr.com\/en\/articles\/318970\/\" rel=\"noopener noreferrer nofollow\">an optimizer<\/a>, such as <a href=\"https:\/\/In%20addition%20to%20various%20element-wise%20non-linear%20transformations%20and%20matrix%20multiplications,%20neural%20networks%20can%20use%20operators%20for%20scalar%20vector%20products%20and%20element-wise%20maximum%20operations%20for%20two%20vectors%20of%20the%20same%20dimension,%20combining%20vectors%20into%20a%20longer%20one,%20and%20more.%20You%20can%20think%20of%20a%20general%20architecture%20for%20the%20prediction%20function,%20where%20a%20vector%20is%20input,%20and%20then%20the%20response%20is%20constructed%20using%20operators%20%7B+,%20-,%20%5Ccdot,%20%5Cmax%20%7D,%20non-linear%20functions%20%7B%5Ctanh,%20%5Cmathrm%7Babs%7D,%20%5Cmax(0,%20%5Ccdot),%20%5Cldots%7D,%20and%20weights%20%7Bw_1,%20w_2,%20%5Cldots%7D.%20In%20this%20sense,%20neural%20networks%20can%20represent%20functions%20of%20quite%20a%20general%20form.%20In%20reality,%20the%20architecture%20of%20the%20function%20%5Cmathcal%7BP%7D%20is%20called%20a%20neural%20network%20when%20it%20contains%20something%20resembling%20a%20chain%20like%20W_k%5Codot%20W_%7Bk-1%7D%5Codot%20%5Cldots%20W_1%20%5Codot%20%5Cvec%7Bf%7D.%20Essentially,%20we%20have%20a%20regression%20problem%20-%20to%20adjust%20parameters%20(weights)%20in%20a%20parametrically%20defined%20function%20to%20minimize%20the%20error.%20There%20are%20numerous%20methods%20for%20training%20neural%20networks,%20most%20of%20which%20are%20iterative,%20and%20the%20module%20responsible%20for%20weight%20updates%20is%20what%20programmers%20refer%20to%20as%20an%20optimizer,%20such%20as%20AdamOptimizer,%20for%20example.\" rel=\"noopener noreferrer nofollow\">AdamOptimizer<\/a>, for example.  <\/p>\n<\/li>\n<\/ul>\n<h2>ML Terminology<\/h2>\n<p>In <a href=\"https:\/\/en.wikipedia.org\/wiki\/Regression_analysis\" rel=\"noopener noreferrer nofollow\">regression analysis<\/a>, many important terms have emerged, allowing for a better understanding of the content of prediction tasks and avoiding common mistakes. These terms have been carried over into Machine Learning (ML) with little to no modification. Here, I will present the fundamental concepts, aiming to highlight their connections to information theory.<\/p>\n<h3>Overfitting<\/h3>\n<p><strong>Overfitting (retraining)<\/strong> occurs when the model you have selected is more complex than the actual reality underlying the target, and\/or when there is insufficient data to support training such a complex model. There are two main causes of <strong>overfitting<\/strong>: <\/p>\n<ul>\n<li>\n<p><strong>too complex model:<\/strong> The model&#8217;s structure is significantly more intricate than the reality or does not align with the complexity of the reality it&#8217;s intended to represent. It&#8217;s easier to illustrate this with a one-factor model.<br \/>Let&#8217;s say you have 11 data points in your training set , and your model is a 10th-degree polynomial. You can adjust the coefficients in the polynomial in such a way that it &#171;touches&#187; every data point in the training set, but this doesn&#8217;t guarantee good predictive performance.<\/p>\n<figure class=\"\">\n<div><figcaption>The blue line is a 10th-degree polynomial <br \/>that was able to precisely replicate the training set of 11 points. <br \/>However, the correct model is likely more linear (the black line), and the deviations from it are either noise or something explained by factors that we don&#8217;t have.  <\/figcaption><\/div>\n<\/figure>\n<\/li>\n<\/ul>\n<p>A polynomial of the 10th degree is an obvious and frequently used example of overfitting. Polynomials of low degrees with many variables can also lead to overfitting. For instance, you can choose a model like predict = a 3rd-degree polynomial of 100 factors (by the way, how many coefficients does it have?), while in reality, the prediction corresponds to a 2nd-degree polynomial of the factors plus random noise.  If you have a sufficient amount of data, classical regression methods can yield an acceptable result, and the coefficients for the 3rd-degree terms will be very small. These 3rd-degree terms will make a small contribution to the prediction for typical factor values (as in the case of interpolation). However, in the extreme values of the factors, where the prediction is more of an extrapolation than interpolation, the high-degree terms will have a noticeable impact and degrade the prediction quality. Moreover, when you have limited data, noise might be mistaken for true information, causing the prediction to try to fit every point in the training data.<\/p>\n<ul>\n<li>\n<p><strong>Insufficient training data:<\/strong> Your model may roughly match reality, but you might not have enough training data. Let&#8217;s use the polynomial example again: suppose both reality and your model are 3rd-degree polynomials of two factors. This polynomial is defined by 10 coefficients, meaning the space of possible predictors is 10-dimensional.  If you have 9 examples in your training pool, writing the equation &#171;polynomial(features<sub>i<\/sub>) = target<sub>i<\/sub>&#187; for each example will give you 9 equations for these coefficients, which is insufficient to uniquely determine the 10 coefficients. In the space of possible predictors, you will get a line, and each point on this line represents a predictor that perfectly replicates what you have in your training pool. You can randomly choose one of them, and there is a high probability that it will be a poor predictor. <\/p>\n<\/li>\n<li>\n<p><strong>Important note about training multi-parameter models. <\/strong>The above example may seem artificial, but the truth is that modern neural network models can contain millions of parameters or even more. For instance, the GPT-3 language model contains 175 billion parameters. <\/p>\n<p>If your model has N = 175 billion parameters, and the size of the training pool is M = 1 billion, you essentially have an infinite set of models that perfectly fit the training data, and this set is essentially a manifold of dimension N &#8212; M = 174 billion. <\/p>\n<p>In the case of deep multi-parameter<\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-363450","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/363450","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=363450"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/363450\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=363450"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=363450"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=363450"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}