Body: <p>Where can I find a machine learning library that implements <code>loss functions</code> measuring the <a href="http://www.scholarpedia.org/article/Algorithmic_information_theory#:%7E:text=Algorithmic%20information%20theory%20(AIT)%20is,computation%2C%20information%2C%20and%20randomness.&amp;text=presumably%20has%20no%20simple%20description%20other%20than%20writing%20down%20the%20string%20itself." rel="nofollow noreferrer">Algorithmic Information Theoretic</a>-friendly quantity &quot;<em>bits of information</em>&quot;?</p>
  <p>To illustrate the difference between <em>entropy</em>, in the <em>Shannon information</em> sense of &quot;bits&quot; and the <em>algorithmic information</em> sense of &quot;bits&quot;, consider the way these two measures treat a 1 million character string representing <span class="math-container">$\pi$</span>:</p>
  <p><em>Shannon entropy</em> &quot;bits&quot; (<span class="math-container">$6$</span> for the '.'):  <span class="math-container">$\lceil 1e6*\log_2(10) \rceil+6$</span></p>
  <p><em>Algorithmic</em> &quot;bits&quot;:  The length, in bits, of the shortest <a href="https://www.angio.net/pi/pi-programs.html" rel="nofollow noreferrer">program that outputs 1e6 digits of <span class="math-container">$\pi$</span> </a>.</p>
  <p>All <em>statistical</em> measures of information, such as <a href="https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence" rel="nofollow noreferrer">KL divergence</a>, are based on <em>Shannon information</em>.  By contrast, <em>algorithmic information</em> permits representations that are fully <em>dynamical</em> as in <a href="https://en.wikipedia.org/wiki/Unrestricted_grammar" rel="nofollow noreferrer">Chomsky type 0</a>, <a href="https://en.wikipedia.org/wiki/Turing_completeness" rel="nofollow noreferrer">Turing Complete</a>, etc. languages.  Since the world in which we live is <em>dynamical</em>, algorithmic models are at least <em>plausibly</em> more valid in many situations than are <em>statistical</em> models.  (I recognize that recursive neural nets can be dynamical and that they can be trained with statistical loss functions.)</p>
  <p>For a more authoritative and formal description of these distinctions see the Hutter Prize FAQ questions <a href="http://www.hutter1.net/prize/hfaq.htm#xvalid" rel="nofollow noreferrer">Why aren't cross-validation or train/test-set used for evaluation?</a> and <a href="http://www.hutter1.net/prize/hfaq.htm#reg" rel="nofollow noreferrer">Why is Compressor Length superior to other Regularizations?</a> For a paper-length exposition on the same see &quot;<a href="https://www.mdpi.com/1099-4300/22/6/612" rel="nofollow noreferrer">A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions</a>&quot;.</p>
  <p>From what I can see, machine learning makes it difficult to relate <code>loss</code> to <em>algorithmic</em> information.  Such an AIT-friendly <code>loss function</code> must, by definition, measure the number of bits required to reconstruct, <em>without loss</em>, the original training dataset.</p>
  <p>Let me explain with examples of what I mean by AIT-friendly <code>loss functions</code>, starting with the baby-step of <code>classification loss</code> (usually measured as <a href="https://ml-cheatsheet.readthedocs.io/en/latest/loss_functions.html" rel="nofollow noreferrer">cross-entropy</a>):</p>
  <p>Let's say your training set consists of <span class="math-container">$P$</span> patterns belonging to <span class="math-container">$C$</span> classes. You can then construct a partial AIT loss function providing the length of the corrections to the model's classifications with a <span class="math-container">$P$</span>-length vector, each element containing a <span class="math-container">$0$</span> if the model was correct for that pattern, or the class if not.  These elements would each have a bit-length of <span class="math-container">$\lceil \log_2(C+1) \rceil$</span>, and be prefixed by a <a href="https://en.wikipedia.org/wiki/Variable-length_quantity" rel="nofollow noreferrer">variable length integer</a> storing <span class="math-container">$P$</span>.  The more <span class="math-container">$0$</span> elements, the more compressible this correction vector until, in the limit, a single <code>run-length code</code> for <span class="math-container">$P$</span> <span class="math-container">$0$</span>'s is stored as the correction, prefixed by <span class="math-container">$P$</span> and the length of the binary for the <code>RLE</code> algorithm itself. The bit-length of these, taken together, would comprise this partial <code>loss function</code>.</p>
  <p>This is a reasonable first cut at an AIT-friendly loss function for <code>classification error</code>.</p>
  <p>So now let's go one step further to outputs that are numeric, the typical approach is a summation of a function of individual error measures, such as squaring or taking their absolute value or whatever -- perhaps taking their mean.  None of these are in units of bits of information.  To provide the correction on the outputs to reproduce the actual training values requires, again, a vector of corrections.  This time it would be deltas, the precision of which must be adequate to the original data being <em>losslessly</em> represented, hence requiring some sort of adaptive variable length quantity representation(s).  These deltas would likely have a non-uniform distribution so they can be arithmetically encoded.  That seems like a reasonable approach to another AIT-friendly loss function.</p>
  <p>But now we get to the &quot;model parameters&quot; and find ourselves in the <em>apparently</em> well-defined but ill-founded notions like &quot;<a href="https://towardsdatascience.com/l1-and-l2-regularization-methods-ce25e7fc831c" rel="nofollow noreferrer">L2 regularization</a>&quot;, which are defined in terms of ill-defined &quot;parameters&quot;, e.g. &quot;parameter counts&quot; aren't given in bits.</p>
  <p>I'll grant that <code>L2 regularization</code> sounds like it is heading in the right direction by squaring the weights and summing them up, but when one looks at what is actually being done, it is:</p>
  <ul>
  <li>applying additional functions to the sum such as mean</li>
  <li>asking for a scaling factor to apply</li>
  <li>applying the regularization on a per-layer basis rather than the entire model</li>
  </ul>
  <p>I'm sure I missed some of the many ways <code>L2 regularization</code> fails to be AIT-friendly.</p>
  <p>Finally, there is the model's pseudo-invariance, measured, not simply in terms of its <code>hyperparameters</code> but in terms of the length of the (compressed archive of the) actual executable binary running on the hardware.  I say 'pseudo' because there is nothing that says one cannot vary, say, the number of neurons in a neural network during learning -- nor even change to another learning paradigm than neural networks during learning (in the most general case).</p>
  <p>So that's pretty much the complete loss function down to the Universal Turing Machine iron, but I'd be happy to see just a reference to an existing TensorFlow or another library that tries to do even a partial <code>loss</code> function for AIT-theoretic learning.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-13T18:38:51.087Z
Comments.Text: Ok, I understand that you are interested in a measure that returns the number of bits of the shortest program that outputs something. But how do you want to use this as a loss function? Meanwhile, if you haven't found it yet, have a look at https://pypi.org/project/pybdm/.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-14T03:06:13.410Z
Comments.Text: Yes, that's in the right direction.  What I'm more interested in is something that works with existing ML frameworks like Keras, etc.  Of course it is always possible to write custom loss functions, but there is enough going on in the ML field and AIT has been understood by the theorists for 50 years, that I was hoping to avoid doing that.
Comments.UserDisplayName: James Bowery
Tags: <objective-functions><information-theory>
Title: Loss Function In Units Of Bits?
UserDisplayName: James Bowery
ThreadText: # Loss Function In Units Of Bits?
  
  (Asked by: username_0 on 2020-07-12)
  
  Where can I find a machine learning library that implements `loss functions` measuring the [Algorithmic Information Theoretic](http://www.scholarpedia.org/article/Algorithmic_information_theory#:%7E:text=Algorithmic%20information%20theory%20(AIT)%20is,computation%2C%20information%2C%20and%20randomness.&text=presumably%20has%20no%20simple%20description%20other%20than%20writing%20down%20the%20string%20itself.)-friendly quantity "*bits of information*"?
  
  To illustrate the difference between *entropy*, in the *Shannon information* sense of "bits" and the *algorithmic information* sense of "bits", consider the way these two measures treat a 1 million character string representing $\pi$:
  
  *Shannon entropy* "bits" ($6$ for the '.'): $\lceil 1e6\*\log\_2(10) \rceil+6$
  
  *Algorithmic* "bits": The length, in bits, of the shortest [program that outputs 1e6 digits of $\pi$](https://www.angio.net/pi/pi-programs.html) .
  
  All *statistical* measures of information, such as [KL divergence](https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence), are based on *Shannon information*. By contrast, *algorithmic information* permits representations that are fully *dynamical* as in [Chomsky type 0](https://en.wikipedia.org/wiki/Unrestricted_grammar), [Turing Complete](https://en.wikipedia.org/wiki/Turing_completeness), etc. languages. Since the world in which we live is *dynamical*, algorithmic models are at least *plausibly* more valid in many situations than are *statistical* models. (I recognize that recursive neural nets can be dynamical and that they can be trained with statistical loss functions.)
  
  For a more authoritative and formal description of these distinctions see the Hutter Prize FAQ questions [Why aren't cross-validation or train/test-set used for evaluation?](http://www.hutter1.net/prize/hfaq.htm#xvalid) and [Why is Compressor Length superior to other Regularizations?](http://www.hutter1.net/prize/hfaq.htm#reg) For a paper-length exposition on the same see "[A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions](https://www.mdpi.com/1099-4300/22/6/612)".
  
  From what I can see, machine learning makes it difficult to relate `loss` to *algorithmic* information. Such an AIT-friendly `loss function` must, by definition, measure the number of bits required to reconstruct, *without loss*, the original training dataset.
  
  Let me explain with examples of what I mean by AIT-friendly `loss functions`, starting with the baby-step of `classification loss` (usually measured as [cross-entropy](https://ml-cheatsheet.readthedocs.io/en/latest/loss_functions.html)):
  
  Let's say your training set consists of $P$ patterns belonging to $C$ classes. You can then construct a partial AIT loss function providing the length of the corrections to the model's classifications with a $P$-length vector, each element containing a $0$ if the model was correct for that pattern, or the class if not. These elements would each have a bit-length of $\lceil \log\_2(C+1) \rceil$, and be prefixed by a [variable length integer](https://en.wikipedia.org/wiki/Variable-length_quantity) storing $P$. The more $0$ elements, the more compressible this correction vector until, in the limit, a single `run-length code` for $P$ $0$'s is stored as the correction, prefixed by $P$ and the length of the binary for the `RLE` algorithm itself. The bit-length of these, taken together, would comprise this partial `loss function`.
  
  This is a reasonable first cut at an AIT-friendly loss function for `classification error`.
  
  So now let's go one step further to outputs that are numeric, the typical approach is a summation of a function of individual error measures, such as squaring or taking their absolute value or whatever -- perhaps taking their mean. None of these are in units of bits of information. To provide the correction on the outputs to reproduce the actual training values requires, again, a vector of corrections. This time it would be deltas, the precision of which must be adequate to the original data being *losslessly* represented, hence requiring some sort of adaptive variable length quantity representation(s). These deltas would likely have a non-uniform distribution so they can be arithmetically encoded. That seems like a reasonable approach to another AIT-friendly loss function.
  
  But now we get to the "model parameters" and find ourselves in the *apparently* well-defined but ill-founded notions like "[L2 regularization](https://towardsdatascience.com/l1-and-l2-regularization-methods-ce25e7fc831c)", which are defined in terms of ill-defined "parameters", e.g. "parameter counts" aren't given in bits.
  
  I'll grant that `L2 regularization` sounds like it is heading in the right direction by squaring the weights and summing them up, but when one looks at what is actually being done, it is:
  
  * applying additional functions to the sum such as mean
  * asking for a scaling factor to apply
  * applying the regularization on a per-layer basis rather than the entire model
  
  I'm sure I missed some of the many ways `L2 regularization` fails to be AIT-friendly.
  
  Finally, there is the model's pseudo-invariance, measured, not simply in terms of its `hyperparameters` but in terms of the length of the (compressed archive of the) actual executable binary running on the hardware. I say 'pseudo' because there is nothing that says one cannot vary, say, the number of neurons in a neural network during learning -- nor even change to another learning paradigm than neural networks during learning (in the most general case).
  
  So that's pretty much the complete loss function down to the Universal Turing Machine iron, but I'd be happy to see just a reference to an existing TensorFlow or another library that tries to do even a partial `loss` function for AIT-theoretic learning.
  
  **Tags:** objective-functions, information-theory
  
  > **Comments:**
  > **username_1**: Ok, I understand that you are interested in a measure that returns the number of bits of the shortest program that outputs something. But how do you want to use this as a loss function? Meanwhile, if you haven't found it yet, have a look at https://pypi.org/project/pybdm/.  
  > **username_0**: Yes, that's in the right direction.  What I'm more interested in is something that works with existing ML frameworks like Keras, etc.  Of course it is always possible to write custom loss functions, but there is enough going on in the ML field and AIT has been understood by the theorists for 50 years, that I was hoping to avoid doing that.  
  
  ---
  
  ## 0 answers
  
  