{"posts":[{"id":5,"date":"2022-05-16","title":"Average entropy of a discrete probability distribution (part 1)","subtitle":"with respect to its dimensionality","content":"\n\n\n

In this blogpost I will present my own little research in maths: the search for an expression of the expected value of an n-dimensional discrete probability distribution.

Average entropy

The story begins while I was learning Information Theory at my uni. We talked about the entropy of a binary random variable. A binary random variable is a variable which only ever has two outcomes, 0 or 1.¹. The pmf of a Bernoulli variable is\n

$\n\\begin{pmatrix}\n0 & 1 \\\\\n1-p & p\n\\end{pmatrix}\n$

\nwhich reads as “the probability of a random variable to have a value of 1 is $p$ and to have a value of 0 is $1-p$ ”.

The entropy of a Bernoulli variable is then²\n

$\nE\\left[X\\right] = -p\\ln\\left(p\\right) - \\left(1-p\\right)\\ln\\left(1-p\\right)\n$

\nwhich looks like this:\n

Figure 1: The entropy of a Bernoulli random variable with respect to the probability parameter $p$ . It resembles a parabola as it’s symmetric around $p=\\frac12$ .

Now for the question: what is the average entropy of a Bernoulli variable? If we were to pick a lot of random $p$ , calculated the entropy and averaged all of them, what number would we get as a result?\nWe could just integrate over all $p$ ’s, and divide by the size of the space of $p$ . To borrow some physics intuition, to calculate the average density of an object, you first calculate the mass of an object by integration, and then divide by the size of the object (i.e. its volume). Here the “size” of the space happens to be $1$ . Anyways:

$\n\\begin{align*}\n\\overline{E_2} &= \\frac1{1-0}\\int_{0}^{1}{E(p)\\mathrm{d}p} =\\\\\n &= -\\int_{0}^{1}{p\\ln\\left(p\\right) + \\left(1-p\\right)\\ln\\left(1-p\\right) \\mathrm{d}p} =\\\\\n &= ... \\mathrm{use\\ photomath\\ or\\ sth} ...\\\\\n &= \\frac12\n\\end{align*}\n$

\nSo the average entropy turns out to be

\\frac12

. If we were to pick

p

at random afew times and calculate the average, we should get something in the vicinity of

0.5

. Cute.

Two’s a company, three’s a crowd

Let’s move a step up. What if we picked a random 3-dimensional “Bernoulli” and calculated it’s entropy. What is the average (or expected) entropy of a random 3-dimensional variable?

First, let’s define some stuff. 3-d Bernoulli variable does not exists, as the term Bernoulli is reserved for 2-dimensional case excusively. Higher dimensional random variables are caled Multinoulli, presumably because someone was feeling particularly creative that day. It’s entropy is calculated with:

$\nE[X] = -\\sum_{i=1}^{N}{p_i\\ln(p_i)}\n$

\nThere is constraint that

\\sum_i{p_i} =

and

p_i \\le 0, \\forall 0 \\le i \\le N

. Particular instance of this formula for the 3-dimensional case is:\n

$\nE_3(p, q) = -p\\ln(p) - q\\ln(q) - (1-p-q)\\ln(1-p-q)\n$

\nwhich looks like this:\n

Figure 2: 3d graph of the entropy of all multinoulli variables. It is similar to a parabolloid, but slanted. This function has a maximum at $(p, q) = (\\frac13, \\frac13)$ .

How do we calculate the average entropy of this? Using the same process as above: integrate the function and divide by the “size” of the function’s domain. Here, the domain is a 2D triangle⁴ determined by the lines $p \\ge 0$ , $q \\ge 0$ , $p+q \\le 1$ . This triangle is exactly one half of the unit square, so it has to have an area of $\\frac12$ . The average entropy of a 3-dimensional multinoulli variable is:\n

$\n\\begin{align*}\n\\overline{E_3} &= \\frac1{\\frac12}\\int_{0}^{1}{\\int_0^{1-p}{E(p, q)}{\\mathrm{d}q}}{\\mathrm{d}p} =\\\\\n &= \\frac1{\\frac12}\\int_{0}^{1}{\\int_0^{1-p}{-p\\ln(p) - q\\ln(q) - (1-p-q)\\ln(1-p-q)}{\\mathrm{d}q}}{\\mathrm{d}p} =\\\\\n &= ... \\mathrm{use\\ wolfram\\ alpha\\ or\\ sth} ...\\\\\n &= \\frac5{12}\n\\end{align*}\n$

Okay, no visible pattern so far. To quote data scientists, “More data is needed!”. To dimension no.4 $\"🚀\"$

Three is a crowd, four is unthinkable. Literally

Let’s try to find out what happens if we calculate the average entropy of a random 4-dimensional multinoulli variable. This is something we usually cannot even imagine, however it’s quite feasible due to maths. The recipe is the same: integrate and divide by the volume of the domain.

First, we’ll have to add one more variable to the calculation of entropy:\n

$\nE_4(p, q, w) = -p\\ln(p) - q\\ln(q) - w\\ln(w) - (1-p-q-w)\\ln(1-p-q-w)\n$

\nThen, we calculate the volume of the domain. We are now in the 3D so we have planes instead of lines. The domain is a pyramid between these 4 planes:

$p \\ge 0$
$q \\ge 0$
$w \\ge 0$
$p+q+w \\le 1$

and its volume is $\\frac16$ . (This is a good exercise for the reader btw)

And now for the integral…\n

$\n\\begin{align*}\n\\overline{E_3} &= \\frac1{\\frac16}\\int_{0}^{1}{\\int_0^{1-p}{\\int_0^{1-p-q}{E(p, q)}{\\mathrm{d}w}}{\\mathrm{d}q}}{\\mathrm{d}p} =\\\\\n &= \\frac1{\\frac16}\\int_{0}^{1}{\\int_0^{1-p}{\\int_0^{1-p-q}{-p\\ln(p) - q\\ln(q) - w\\ln(w) - (1-p-q-w)\\ln(1-p-q-w)}{\\mathrm{d}w}}{\\mathrm{d}q}}{\\mathrm{d}p} =\\\\\n &= ... \\mathrm{? ? ? ? ?}\n\\end{align*}\n$

\nWolframAlpha doesn’t really help anymore. $\"😢\"$ \nBut some other symbollic computing tools come to rescue, namely Sympy\n

>>> from sympy import symbols, integrate, ln, simplify\n>>> p, q, w = symbols('p q w', real=True)\n>>> E = -p*ln(p)-q*ln(q)-w*ln(w)-(1-p-q-w)*ln(1-p-q-w)\n>>> domain_volume = 1/6\n>>> res = integrate(f, (w,0,1-p-q), (q,0,1-p), (p,0,1))\n>>> # seven hungry years later\n>>> print(result.real / domain_volume)\n13/12\n

The result is $\\frac{13}{12}$ .⁵ No obvious pattern yet.

And also, these integral solving functions take progressively more and more time. Running it for 2-dimensional case took ~4sec, for 3-dimensional case took ~20 sec, and for 4-dimensional case it took a whooping 163 sec to get an anwser. If we assume it’s a factorial growth, we’re looking forward to ~10 minutes for 5-dimensional case and ~2h for 6 dimensions.

I could, in theory, buy a better laptop but it won’t help me much. Therefore, we’ll need to look for other methods that trade computation speed for absolute precision. See you in the next part.

\n
While this is not entirely true, I’ll leave it at that for brevity’s sake ↩
\n
\n
$\\ln()$ is a so-called natural logarithm, logarithm with a base $e$ .³ ↩
\n
\n
Usually, the entropy is defined using $\\log_2()$ and not $\\ln()$ . However, using base e will be beneficial for the end result $\"😄\"$ . The only difference anyways is just the scaling factor of $\\ln(2)$ .\nThe volume of the domain is the easier part: it is now ↩
\n
\n
It is a general pattern that the entropy of an $d$ -dimensional variable is a function of $d-1$ variables. This stems from the fact that $\\sum{p} = 1$ ; you always need one variable less because you can calculate it from all the others. ↩
\n
\n
An astute reader might be wondering why is there a .real attribute acess. The truth is - I don’t really know haha while solving these integrals, Sympy would always return some dubious complex numbers, but the result I needed was always the real part. I’m not sure why this keeps happening, bit it seems to be working $\"😄\"$ ↩
\n

","show":1},{"id":4,"date":"2022-05-01","title":"My deployment setup (Part 2)","subtitle":"The details of the system architecture of this website","content":"

This is a second of two posts in a series of “My deployment setup” posts. You can find the other one here.

The last blog post ended with an infrastructure support for HTTP requests to arrive at my loaned cloud computer. Those requests should be responded to, though, and this is the topic of this post.

Software support

My first deployment used “raw” NGINX. “Raw” here means not using any containerization technologies such as Docker. It was mostly apt install nginx followed by systemctl start nginx.service. The hardest part was writing a .conf file because it was the first time in my life so I had to learn all about NGINX configuration from scratch.

However, this deployment, while working (almost) flawlessly, had one major weakness: it is hard to serve multiple sites from a server in this way. If the sites are static, I should write more .conf files which are all same for the most part (something which can be automated). If the sites are somewhat dynamic, like this blog, this means I should be forwarding the request to another server process, with all the necessary headers etc. Also, nothing was containerized which meant any change in an environment, such as a package update or environment variable change, could result with the deployment failing.

I knew I wanted to deploy multiple containerized sites from the same machine so an archtectural change was inevitable.

Reverse proxy

My requirements were as follows:

I wanted to deploy multiple sites from the same machine. This meant multiple DNS A-records should point to the same IP address, which is trivial, however there should be a software support for correct dispatching
I also wanted all the sites to be containerized because it’s easier to update the sites this way, and also the containers are all isolated by design.
Requirement #2 somewhat implies the dispatch software should also be in a container, as it’s easier for two containers to communicate with each other than a container and a process.
Ideally, the software dispatch support should be “config, run, and leave it alone”. There should be minimum overhead for every new site to be deployed.
My final requirement was that it’s possible to collect some metrics (the number of requests in a day for a particular site, status codes etc).

All of these problems are solved by putting a piece of software in front of every site, the so-called reverse proxy.¹ I actually contemplated writing my own, thinking “surely it can’t be that difficult”. Luckily, I stumbled upon a piece of software which mstches all the requirements above and much more (and a lot better than I would have). It’s called Traefik.

Traefik

The plan is to put all my sites in a Docker container and to connect them to the Traefik container which will then make them available to the entirety of the Internet.

But, how does the Traefik knows how to forward the correct requests? Do I need to update Traefik for every new container?

Fortunately, no, because that would defeat the purpose. Traefik is configured once at the start and then it autodiscovers the services and the services are responsible for the correct configuration (which is minimal). This means publishing a new site requires only the container and several container labels Traefik reads for the configuration generation. Marvellous.

Figure 1: The original architecture. All requests coming to my cloud instance at ports 80/443 are first greeted by Trafik reverse proxy. It forwards the requests to one of the site containers, and forwards back the response.

As for the Traefik’s configuration, it’s really minimal: most of the lines go to the SSL certificate provider configuration² and Prometheus configuration.

Monitoring

I monitor my deployments with Grafana and Prometheus, which are also Docker containers.

Prometheus collects the metrics about the sites deployed from Traefik itself (RPS, latencies, IP adresses, status codes etc)
It collects the metrics about the performance of the site containers, such as RAM usage, CPU usage etc from cAdvisor container
Prometheus collects the metrics about my cloud computer from a node_exporter container
Grafana then asks Prometheus for the metrics and shows them in a graphical way.

There is a secret middle step here: these graphs aren’t publicly available to anyone but me. To ensure that, I had to setup an authentication middlestep using Authelia, which asks for the username and password³ and then asks for a 2nd factor authentication with Google Authenticator.⁴.

The full architecture is as shown in Figure 2:

Figure 2: the full architechture of my deployment. To monitor my deployment, I use grafana which reads from Prometheus, which in turn reads from cAdvisor, node_exporter and Traefik itself. However, access should first be allowed by Authelia, which asks Google for authorization. If successful I can see graphs of requests and errors, RAM consumption etc

Final thoughts

In retrospect, my deployment turned out to be more complex than I imagined when I started my architecture redesign. I hadn’t anticipated this as some of requirements changed over time, but luckily, my architecture supported those changes. This taught me what good software architecture should be: it does not only solve your problems now, it also solves your problems later on. And it all started with containerization.

If you wish to know more about my deployment or have any questions or comments, leave them below!

\n
Why is it called a reverse proxy instead of a normal (or forward) proxy? Forward proxy acts on behalf on the user/client side of the connection, while reverse proxy acts on the server side. Forward proxy collects requests from multiple clients and then dispatches the responses to correct clients. Reverse proxy dispatches the requests and forwards the responses. ↩
\n
\n
Traefik allows you to encrypt your sites with Let’s Encrypt, offering HTTPS out-of-the-box. It also automatically renewes the SSL certificates when they expire, meaning I get to serve my sites with HTTPS and spend roughly 0hrs per year dealing with it $\"😎\"$ ↩
\n
\n
It’s not admin:admin ↩
\n
\n
I’m usually not that self conscious. ↩
\n

","show":1},{"id":3,"date":"2022-02-09","title":"My deployment setup (Part 1)","subtitle":"The details of the system infrastructure of this website","content":"

Ever since I was a kid, I dreamt of having a personal website. I am not really sure why; I certainly did not know what would I put there, let alone how to build one. But the concept of having your own little corner in this upcoming-but-huge Internet thingie seemed cute enough for me.

As I grew older, I learned about making a website: all the nitty-gritty details of HTML, CSS (JavaScript, on the other hand, wasn’t really a part of my formal education - for better or for worse), computer networks, TCP/IP, HTTP(S) etc. I made them in various technologies at various stages of my education for various classes. I even (sort of) learned a thing or two about me, my, virtues and flaws, likes and dislikes, and most importantly what I would put up on my website.

However, no one ever really taught me how to deploy one. Ever. So I had to learn to do it by myself. I consider this a letter to the younger me, a lecture of sorts guided to teaching a young me. And, if you read this entire post, you may learn as well!¹

The server

An obvious prerequisite is the server machine, a big computer running a serving process which talks HTTP, runs programs and returns their outputs to the sender. Those programs can be as different as it gets: they can as simple as reading a file and returning the contents verbatim, or as complicated as crunching several gigabytes of data and generating the structured output. However, you still need the machine.

Although your computer can in theory be such a machine, that’s seldom a good idea. You would have to keep your computer on all the time², always attached to the internet, publicly available on a specific IP address and a TCP port, and always have some of your resources spent on the server process. Luckily, renting someone else’s computer for the exact purpose of spinning up a website is a thing - it’s called web hosting. Since that business is here for decades, there is an entire spectrum of possibilities. You could rent a bare server and doing everything by hand, or you could rent an almost entirely managed solution in which all you provide is the text and the service does the rest. There are tradeoffs, however: with fully managed solutions, you get that specific use case and nothing else, but a server instance gives you an opportunity to do other things. Since I had more plans, I decided to go with my own instance.

There is a lot of computing instance providers out there in the wild. One can choose between them on the basis of popularity, uptime, distance from your location etc. I chose on the basis of price $\"😅\"$ . By far, the cheapest server provider I found was Hetzner. Running an instance there literally costs me two coffees monthly.

After registration, I selected the cheapest option, put latest (at a time) Ubuntu and… that was it. Really.

Figure 2: Hetzner Cloud interface. I named my instance `cosmos` for no particular reason. The instance also obtains a public IP address. This will be cruial in the next step.

The domain

Before I make my webpage, it would be great to have a domain. A domain is a string that takes you to a dedicated IP address. That mapping is stored by IANA and retrieved using DNS protocol. Domain names cost money, though. msmetko.com cost tens of € which was too much for my student budget. msmetko.xyz, on the other hand, cost like 2€ for a year, which was acceptable $\"😄\"$ ³. Cheap domain names can be bought at https://namecheap.com (this is whatever opposite of “false advertising” is). The procedure was also quite easy, once you register, you can choose the domain name, and when you input payment data and click Buy! you now own your domain.

Pointing the domain name to the IP address

Just buying the domain name won’t magically make the internet send the traffic to the server instance. You must create a mapping that says “msmetko.xyz points to 157.90.253.79”. This mapping is called and A-record. The A-records are managed in Namecheap domain settings. When you change these settings, Namecheap propagates them to the entirety of Internet (although asynchonously). DNS servers learn about a particular msmetko.xyz ata certain IP adress, so the next time someone tries to visit that domain, they can answer with a correct IP address.

Figure 4: Domain management at namecheap. The A-record shown is genuine. The host part is `@` meaning root of the domain, which is `msmetko.xyz`. The IP address is that same Hetzner cloud server instance public IP address. TTL was left at a default value.

That’s it for the first part, the infrastructure around having a website. Now the requests can hit my server, but nothing waiting there for them. In the next part I’ll cover the deployment of my website, this blog, and other services.

\n
Note: I am not saying this is the One True Deployment $\"™️\"$ and that everybody should do it my way. It worked for me and my needs. Yours may be different. ↩
\n
\n
You do turn off your computer, right? RIGHT?? ↩
\n
\n
Besides, .xyz TLD really stands out, no one uses it $\"🙃\"$ ↩
\n

","show":1},{"id":2,"date":"2022-01-13","title":"The C method","subtitle":"An analytical knee/elbow searching method","content":"\n\n\n

\n\n\n\n

Description
- Constraint 1
- Constaint 2
\n
Analysis and reparametrization
- Analysis
\n
How to use it to find a knee?
- The intuitive way
- The technical way
- The hacky way
\n
Estimating the c
What’s next?

Real systems in nature, including computer systems, economy, physics, etc. may reach a point where the changes of the cost outweigh the performance changes with respect to some tunable parameter. This renders the further changes “not worth it” and sometimes maybe even harmful. Therefore, in many cases it is important to manage tradeoffs between the cost and performance. One particular point of interest in reaching a balanced tradeoff is called the knee or the elbow. Various definitions of a knee exist but the most popular one defines the knee as a point in which a graph obtains maximum curvature, or equivalently, an osculating circle at that point has the smallest radius.

Knee searching is quite important operation. In this post I’ll describe the method I personally developed: the C-method.

Description

Figure 1: A typical trade-off curves. A balancing point, a.k.a. a knee, might be found at 30% for the blue curve and below 20% for the red curve.

It all started with an observation: many tradeoff curves I’ve come across with vaguely look like $\\frac1x$ or $1-\\frac1x$ . The most generic form of this equation is therefore:

$\nf\\left(x\\right) = a+ \\frac{b}{x+c}\n$

It has three shape parameters: $a$ , $b$ , and $c$ , and fitting these parameters should be enough. However, I felt that this is way too much degrees of freedom; if I restrict the function with some constraints, I should ideally get the functional form with only one shape parameter. Most of my experience was that most of the time the function graphs are anchored to pass through the points $(0, 0)$ and $(1, 1)$ , so I restricted the function such that $f(0) = 0$ and $f(1) = 1$ .

Constraint 1

When $f(0)=0$ is fed into the equation form results in a relation:\n

$\n\\begin{align*}\n0 = f(0) &= a+\\frac{b}{0+c} =\\\\\n &= a+\\frac{b}c\\\\\n b &= -ac \\\\\n\\end{align*}\n$

\nFeeding the relation back into the equation results with:\n

$\n\\begin{align*}\n f(x) &= a - \\frac{ac}{x+c} =\\\\\n &= a\\left(1 - \\frac{c}{x+c}\\right) =\\\\\n &= a\\left(\\frac{x+c}{x+c} - \\frac{c}{x+c}\\right) =\\\\\n &= \\frac{ax}{x+c}\n\\end{align*}\n$

\nwhich is cute and simple.¹

Constaint 2

Feeding $f(1)=1$ gets us a quick win:\n

$\n\\begin{align*}\nf(1) &= \\frac{a}{1+c} = 1\\\\\na &= 1+c \\\\\n\\end{align*}\n$

\nand feeding it back results in:\n

$\nf(x) = \\frac{\\left(1+c\\right)x}{x+c}\n$

Analysis and reparametrization

The result has several properties:

$\\lim_{c \\rightarrow 0} = 1$
$\\lim_{c \\rightarrow +\\infty} = x$
When $c \\lt 0$ , the curve “flips”, meaning the curve avoids the unit square.

I decided I did not like this as, while perfectly mathematically correct, it does not match my intuition at all $\"😅\"$ to me, ideally $\\lim_{c \\rightarrow 0}$ should go to $x$ and $\\lim_{c \\rightarrow +\\infty}$ should go to $x$ . Also, I would like to restrict $c$ to all positive reals.

All of my problems are solved with a following substitution: $c \\rightarrow \\frac1{e^c}$ .² Doing the substitution gave me:\n

$\n\\begin{align*}\nf(x) = \\frac{\\left(1+c\\right)x}{x+c} \\Rightarrow f(x) &= \\frac{\\left(1+\\frac1{e^c}\\right)x}{x+\\frac1{e^c}} = \\\\\n &= \\frac{x\\left(e^c+1\\right)}{xe^c + 1}\\\\\n\\end{align*}\n$

\nMuch better, IMHO. It’s got a nice visual which is easy to remember. The only difference is the parantheses $\"😄\"$

The GeoGebra plugin animating the function as the

c

parameter changes

\n\n\n

Analysis

$\\lim_{c \\rightarrow -\\infty} = x$ , which was what I wanted
$\\lim_{c \\rightarrow +\\infty} = 1$ , which was also what I wanted
Flipping is now disabled

How to use it to find a knee?

Three ways: the intuitive way, the technical way, and the hacky way.

The intuitive way

The intuitive way starts with an observation that the function graph is symmetric with respect to the line $y=1-x$ . Intersecting the graph with the line gives:\n

$\n\\begin{align*}\n1-x &= \\frac{x\\left(e^c+1\\right)}{xe^c+1} \\\\\n\\left(1-x\\right)\\left(xe^c+1\\right) &= x\\left(e^c+1\\right) \\\\\ne^cx+1-e^cx^2-e^cx-x&=0 \\\\\ne^cx^2+2x-1&=0 \\\\\n\\end{align*}\n$

The quadratic equation has two solutions, however I must disregard one of them as it’s smaller than $0$ . Therefore, the knee point is at:\n

$\nx=\\frac{-1+\\sqrt{1+e^c}}{e^c}\n$

The technical way

The second way is way more technical as it involves a lot of calculus. If I define a curvature function $K(x)=\\frac{f''}{\\left(1+f'^2\\right)^\\frac32}$ , I could find an extreme point by setting $\\frac{d}{dx}K\\left(x\\right) = 0$ . Before substitution, let’s play with the expression first:\n

$\n\\begin{align*}\n\\frac{d}{dx}K\\left(x\\right) &= \\frac{d}{dx}\\left(\\frac{f''}{\\left(1+f'^2\\right)^\\frac32}\\right) = 0 \\\\\n\\frac{d}{dx}f''\\cdot\\left(1+f'^2\\right)^{\\frac32} &= f''\\cdot\\frac{d}{dx}\\left(\\left(1+f'^2\\right)^{\\frac32}\\right) \\\\\nf'''\\left(1+f'^2\\right)^{\\frac32} &= f''\\cdot\\frac32\\left(1+f'^2\\right)^{\\frac12}\\cdot2f'f''\\\\\nf'''\\left(1+f'^2\\right) &= 3f''^2f' \\\\\n\\end{align*}\n$

The higher derivatives of $f(x)$ are as follows:\n

$\n\\begin{align*}\nf(x) &= \\frac{x\\left(e^c+1\\right)}{xe^c+1} \\\\\nf'(x) = \\frac{d}{dx}f(x)&=\\frac{e^c+1}{\\left(xe^c+1\\right)^2} \\\\\nf''(x) = \\frac{d}{dx}f'(x)&=-\\frac{2e^c\\left(e^c+1\\right)}{\\left(xe^c+1\\right)^3} \\\\\nf'''(x) = \\frac{d}{dx}f''(x)&=\\frac{6e^{2c}\\left(e^c+1\\right)}{\\left(xe^c+1\\right)^4} \\\\\n\\end{align*}\n$

\nSubstituting these equations leads to:\n

$\n\\begin{align*}\nf'''\\left(1+f'^2\\right) &= 3f''^2f'\\\\\n\\frac{6e^{2c}\\left(e^c+1\\right)}{\\left(xe^c+1\\right)^4}\\left(1+\\left(\\frac{e^c+1}{\\left(xe^c+1\\right)^2}\\right)^2\\right) &= 3\\left(-\\frac{2e^c\\left(e^c+1\\right)}{\\left(xe^c+1\\right)^3}\\right)^2\\frac{e^c+1}{\\left(xe^c+1\\right)^2} \\\\\n\\frac{6e^{2c}\\left(e^c+1\\right)}{\\left(xe^c+1\\right)^4}\\frac{\\left(xe^c+1\\right)^4 + \\left(e^c+1\\right)^2}{\\left(xe^c+1\\right)^4} &= 12\\frac{e^{2c}\\left(e^c+1\\right)^2}{\\left(xe^c+1\\right)^6}\\frac{e^c+1}{\\left(xe^c+1\\right)^2} \\\\\n\\left(xe^c+1\\right)^4+\\left(e^c+1\\right)^2 &= 2\\left(e^c+1\\right)^2 \\\\\n\\left(xe^c+1\\right)^4 &= 2\\left(e^c+1\\right)^2 \\\\\n\\left(xe^c+1\\right)^2 &= e^c+1 \\\\\nxe^c+1 &= \\sqrt(e^c+1) \\\\\nx &= \\frac{\\sqrt{e^c+1}-1}{e^c} \\\\\n\\end{align*}\n$

\nwhich is what we’ve already obtained in the last step, which is great!

The hacky way

The third approach is rather hacky. By invoking a Mean Value Theorem, we know there must be a point on the curve of $f(x)$ in which the slope of the tangent is equal to the slope of the secant between $(0, 0)$ and $(1, 1)$ . That slope is, obviously, 1. Therefore, finding the derivative and evaluating it with 1 gives:\n

$\n\\begin{align*}\n\\frac{d}{dx}f(x) &= 1 \\\\\n\\frac{d}{dx}\\frac{x\\left(e^c+1\\right)}{xe^c+1} &= 1 \\\\\n\\frac{e^c+1}{\\left(xe^c+1\\right)^2} &= 1\\\\\n\\end{align*}\n$

\nwhich, once again, results with

x = \\frac{\\sqrt{e^c+1}-1}{e^c}

After three different proofs, I guess it’s safe to say that $x = \\frac{\\sqrt{e^c+1}-1}{e^c}$ is a good estimator of the theoretical knee.

Estimating the c

After this theoretical derivation, the next problem is fitting the $c$ coefficient to the real world data, $N$ -dimensional vectors $\\textbf{x}$ and $\\textbf{y}$ . The first, and only insofar, fitting procedure I’ve come up with is the ordinary least squares: minimization of:

$\nE = \\sum_{i=1}^{N}{\\left(y_i - f(x_i)\\right)^2} = \\sum_{i=1}^{N}{\\left(y_i - \\frac{x_i\\left(e^c+1)\\right)}{x_ie^c+1}\\right)^2} \n$

I’ve implemented a $c$ -fitting procedure in my project called knarrow in the form of the Newton-Raphson method.\n

$\n\\begin{align*}\n\\frac{\\partial E}{\\partial c} &= \\frac{\\partial}{\\partial c}\\left(\\sum_{i=1}^N{\\left(y_i - f(x_i)\\right)^2}\\right) \\\\\n&= 2 \\sum_{i=1}^N{\\left(f(x_i)-y_i\\right)\\frac{\\partial}{\\partial c}f(x_i)}\\\\\n&= 2 \\sum_{i=1}^N{\\left(y_i-\\frac{x_i\\left(e^c+1\\right)}{x_ie^c+1}\\right)}\\frac{\\left(x_i-1\\right)x_i\\mathrm{e}^c}{\\left(x_i\\mathrm{e}^c+1\\right)^2}\\\\\n\n\\frac{\\partial^2 E}{\\partial c^2} &= \\frac{\\partial^2}{\\partial c^2}\\left(\\sum_{i=1}^N{\\left(y_i - f(x_i)\\right)^2}\\right) \\\\\n&= 2\\sum_{i=1}^N{\\left(\\frac{\\partial}{\\partial c}f(x_i)\\right)^2} + 2\\sum_{i=1}^N{\\left(f(x_i) - y_i\\right)\\frac{\\partial^2}{\\partial c^2}f(x_i)} \\\\\n&= 2\\sum_{i=1}^N{\\left(\\frac{x_i\\left(e^c+1\\right)}{x_ie^c+1}\\right)^2 + \\left(\\frac{x_i\\left(e^c+1\\right)}{xe^c+1}-y_i\\right)\\dfrac{\\left(x_i-1\\right)x_i\\mathrm{e}^c\\left(x_i\\mathrm{e}^c-1\\right)}{\\left(x_i\\mathrm{e}^c+1\\right)^3}}\\\\\n\\end{align*}\n$

These equations are then simply converted to an update rule:\n

$\nc_{n+1} \\leftarrow c_n - \\frac{\\frac{\\partial E}{\\partial c}}{\\frac{\\partial^2 E}{\\partial c^2}}\n$

\nwhich works for any starting value

c_0

. This procedure is repeated until a satisfactory level of precision is reached. The resulting shape parameter

c

is then fed into the equation above to get the knee point. Optionally, one can also calculate which of the input

x_i

’s is the closest to the theoretical knee and denote that particular

x_i

as a knee.

What’s next?

I would be most happy if I found that $f'(x)$ could be written in terms of $f(x)$ or $f''(x)$ could be written in terms of $f'(x)$ in a nice manner (just like the derivative of a sigmoid). However, I am not that good in algebra.
Efficient implementation. Currenctly it’s implemented as a brain-dead verbatim implementation using only numpy. I’m even calling other functions to calculate the derivatives, which turned out to be rather slow. If I ever accomplished the point above, this would easily follow.
Sometimes, the graphs which are in need of the knee/elbow search do not behave like $1-\\frac1x$ but more like $1-\\frac1{x^2}$ or $1-\\frac1{\\sqrt{x}}$ . It would be great to investigate such possibilities and allow for one more shape parameter.

Thank you for your time and until next time,\nMarijan Smetko\nQED

\n
However it should be emphasised that this was only possible because the degree of the denominator was 1. Future generalizations which would allow for a different exponent ↩
\n
\n
Mathematicians probably hate me right now. ↩
\n

","show":1},{"id":1,"date":"2022-01-09","title":"Hello, world!","subtitle":"Description of what this is, how's it made and what it's supposed to be","content":"

Hello, world

$\"🚀\"$

What is this?

I’ve decided I want a blog. And I made it!

What you see here is custom-made blogging software. The reason I went building this thing myself is I wanted a blog that is themed just like my homepage https://msmetko.xyz. At the time it seemed easier to build a simple blogging system than customize an existing one.

I also kinda like challenges. I bet that had a minor role in my decision.

How it works?

In the beginning there was a file

This blog post you’re reading right now started its life as a Markdown *.md document. I was writing it in my living room in Kate text editor on my Asus notebook as a sort of a preview of what my blog may look like. After I finish my writing about anything, I commit the file to the git repository hosted (at the moment) on Github. (This may change in the future.)

Devops paradise

At the moment of this writing, I haven’t really built it yet, but at the moment of your reading, the blog itself was produced by a CI/CD pipeline. It’s got two parts:

The Github part, which is triggered on a push. It doesn’t do much: it simply connects to my server, goes into the GitHub repo on the server, and pulls all the latest changes. Then it spawns a second part.
The second part, running on my server, does a few things:\n - It builds a frontend, written in the Svelte framework by @amalija-ramljak. It boils down to yarn install && yarn build inside a docker container.\n - It compiles all my markdown blog posts into an sqlite3 database. Interesting!
- First, it reads the markdown file and converts it to HTML using the markdown library using a bunch of extensions, such as katex for math rendering, table of contents, emojis, and all sorts of interesting things
- While reading a blog post, it also builds an RSS .xml file for the RSS clients. While not many people use RSS nowadays, quite a few computers do, such as dev.to which pulls my blogposts and publishes them there. If you are reading this from dev.to now you know why :))
- After everything is built, the old deployment is torn down and the new is deployed. This is what you read.
\n

I’d say miraculous but you wouldn’t hear me as we’re in different parts of the world.

What’s it supposed to be?

First and foremost, this is my creative outlet space. I’ll write about topics I find interesting: Python, programming in general, Linux, my projects and project ideas, math, machine and deep learning, physics, astronomy, to name a few. I’ll try to write at least once a week, however, if I’m trying to really dive deep into my next blog post topic it may last longer. Or I may fill the time up with lower-quality, “filler”, blogposts. IDK ATM

Thank you for your time and until next time,\nMarijan Smetko\nQED

","show":1}],"lastPage":true}