Forem: Ola Sk

Database normalization may be harmful to efficiency on large scale analytics projects.

Ola Sk — Sun, 05 Jan 2020 13:46:07 +0000

If the select queries to your relational database return big tables, additionally if you used one or more join statement in that query, let me guess it wasn't quick process to fetch the resulting table. JOIN operation adds a computation step for each record fetched. They accumulate over the number of records, or rows, for which records from a linked table need to be fetched. The worse it gets, the more joins there are in the query. This results in a computational expense that you might avoid using denormalized table design.

To decide which approach in a design to use to optimize the number of computations and the storage efficiency of your database, you need to consider the frequency of update and select operations and how many of them are going to result in queries returning a big number of records.

If you do not perform any separate analysis on a certain feature of a dataset (contained in one column), so in other words, if that data has a secondary relevance, you may want to consider merging the column with some other column with similar characteristics.

To back up the decision about merging/adding a summary column, consider:

whether your data to merge do not change too frequently. UPDATE, just like SELECT queries have their prices in terms of the number of computations performed. You "pay" for both of them, either it's updating some columns in a database upon the change of value in another column or users of your database waiting longer for the queries to JOIN the pieces of data.
one other thing to consider is the size of the pool of records that will usually gonna be returned from queries for analysis. You may want to think of any possible questions that may emerge and possible queries that may need to be performed in certain scenarios of analysis and consider the sizes of possible returns from those queries. If the data returned from most of the queries are gonna be big, you may save time for fetching records that are rather contained in a fewer number of cells that you do not need to JOIN before getting the results from RDBMS.

To sum this up, choosing the design—deciding whether to merge columns / add a summary column (denormalization practices)—aims at minimizing the time of return from the query, which involves minimizing the number of computations needed. It comes down to a trade-off between normalized and denormalized design, that should be carefully chosen and be mainly determined by:

the frequency of changes (UPDATE) in the data that involve computation if the table contains a summary column that needs to be updated along with a changing value in another column,
and the sizes and frequency of, especially big, SELECT queries.

But here again, there usually are not many updates in analytical DBs specifically, so I conclude that this type of database may benefit hugely from careful denormalization.

Jason Turner's gift C++ tutorial for Christmas

Ola Sk — Tue, 31 Dec 2019 20:13:54 +0000

Jason Turner has hit a 200 informational videos on modern C++ features this Christmas season. He's a multiple time speaker at CppCon—the biggest C++ conference and does industrial trainings on C++. He just came up with a tutorial series on C++ available on his YouTube channel. I personally enjoy watching his C++ weekly series, but never am able to catch up will all the episodes anyway. I highly recommend any adept of programming in C++ to take a look and hopefully stay for longer.

https://youtu.be/3hGSlUGEXtA

Happy learning.

Books to understand Causal Inference and Structured Causal Modeling (SCM) from level ~0

Ola Sk — Mon, 23 Dec 2019 19:06:25 +0000

I did some research and I’m coming to you with a few books that I found maybe the proper way to understand Causal Inference.

The first introductory book would be: “An Introduction to Statistical Learning”. It’s a companion to the MOOC from Stanford, which offers it on its ‘lagunita’ platform along with a free certificate:

An Introduction to Statistical Learning

Free book in PDF format

‘Statistical Learning’ MOOC on ‘lagunita’

Terran M’s Review on goodreads.com:

Adequate preparation for understanding “Principles and Practice of Structural Equation Modeling” would be a basic treatment of multivariate regression, such as Gelman and Hill. Introduction to Statistical Learning would also be sufficient. If you want to understand confirmatory factor analysis, you should probably already know something about factor analysis as well; I liked Gorsuch.

Data Analysis Using Regression and Multilevel/Hierarchical Models

by Andrew Gelman, Jennifer Hill

See on goodreads.com

A Mig’s review on goodreads.com

A go-to book for multilevel modeling but far from my favorite books on statistics. First, one should pass all the sections on probability distributions and linear regression, since there is much better elsewhere on the same topic (and with R codes), such as ‘An Introduction to Statistical Learning: With Applications in R’

Principles and Practice of Structural Equation Modeling, Fourth Edition

Terran M’s Review on goodreads.com:

This is the correct first book to read on causal inference. It covers structural equation modeling (SEM), confirmatory factor analysis (CFA), and Pearl’s structured causal modeling (SCM).
Although this book claims to cover various software packages, the treatment is cursory and the code examples (online) are mostly uncommented; don’t expect to learn how to use the software from this book. Read this book for the principles and then also read the software manual for whatever tool you’re going to use.
Ironically, this book, whose title claims to be about SEM only, actually covers most of the modern causal inference, whereas Pearl’s book, with the grand title “Causality”, covers only his narrow work. This is definitely the one you want.

For a brief introduction to using causal graphs to select your controls, see Chapter 17 of “Statistical Modeling — A Fresh Approach”. That chapter is available free from the author at http://www.mosaic-web.org/go/Statisti...

For more about inferring causal graphs from the data, look for a series of papers by Colombo and Maathuis at ETH Zurich. Here are a couple of papers:

https://projecteuclid.org/euclid.aos/...
https://projecteuclid.org/euclid.aos/...

These papers are also on ArXiv, and there are more from the same authors. Also, they wrote an R package:

https://cran.r-project.org/web/packag...

The Elements of Statistical Learning: Data Mining, Inference, and Prediction

https://web.stanford.edu/~hastie/ElemStatLearn/

The challenge of understanding vast amounts of data in a variety of fields such as medicine, biology, finance, and marketing has led to the development of new tools in the field of statistics and spawned new areas such as data mining, machine learning, and bioinformatics. Many of these tools have common underpinnings but are often expressed with different terminology. This book describes the important ideas in these areas in a common conceptual framework. While the approach is statistical, the emphasis is on concepts rather than mathematics. Many examples are given, with liberal use of color graphics. It should be a valuable resource for statisticians and anyone interested in data mining in science or industry. The book’s coverage is broad, from supervised learning (prediction) to unsupervised learning. The many topics include neural networks, support vector machines, classification trees and boosting — the first comprehensive treatment of this topic in any book. Trevor Hastie, Robert Tibshirani, and Jerome Friedman are professors of statistics at Stanford University. They are prominent researchers in this area: Hastie and Tibshirani developed generalized additive models and wrote a popular book of that title. Hastie wrote much of the statistical modeling software in S-PLUS and invented principal curves and surfaces. Tibshirani proposed the Lasso and is co-author of the very successful An Introduction to the Bootstrap. Friedman is the co-inventor of many data-mining tools including CART, MARS, and projection pursuit.

Terran M’s Review on goodreads.com:

This is an excellent second or third book on statistical modeling after you have read something with code examples and done a few real projects. It is mathematically deeper and more comprehensive than An Introduction to Statistical Learning: With Applications in R and does more to tie together how and why algorithms work. It provides no code examples, and it is also correspondingly more demanding in the mathematical background of the reader. Even if you never read all of it, it’s worthwhile owning as a reference, and a PDF is even available for free from the author: https://web.stanford.edu/~hastie/ElemStatLearn/

Some basic differences between maths and statistics name conventions.

Ola Sk — Wed, 11 Dec 2019 18:54:28 +0000

I write this note because I was confused with the names used for different concepts in maths vs statistics and maybe someone else too is. It's gonna at least serve me as a small reminder.

Say we have a multidimensional dataset, the data points have particular coordinates (that's what is taught in linear algebra) that in statistics are called 'variables', and the data points themselves in n-dimensional space (with n 'variables' or 'features' as their dimensions) are called 'individuals', 'cases' or sometimes 'observations'.

Variables (or features) can be categorical, discrete or continuous.

Data points or individuals sometimes don't have identities (names, identifiers) and in order for a data person to clean the data (order it, look for missing or funny values, handle them in a sensible way) and start performing some statistical testing on a data set (graph the data, look at averages, standard deviations etc.), then there may be need to get them back in some kind of order after operating on them, so they need to be 'tagged'.

Review: Mathematics for Machine Learning @ Coursera. Linear Algebra; Multivariate Calculus; PCA.

Ola Sk — Wed, 11 Dec 2019 10:54:37 +0000

I recently was doing the Mathematics for Machine Learning specialization on Coursera, which consists of 3 courses. I was always trying to get deeper into Calculus, Algebra, but I was never satisfied with the quality of different materials I stumbled upon in the past and never really went with my studies far. But then this series of courses happened and I was never more motivated to learn those concepts. I enjoyed it so much. It lies a quite solid mathematical foundation under concepts of Machine Learning. Every bit of the course is applied instantly into practical settings and there are plenty of exercises in Python. I didn't know Python much before, but I programmed in C++ and a bit in JS. I studied it in the meantime. W/o that my interest in Machine Learning was merely learning some high-level functions w/o any knowledge about underlying math and statistics involved. I'm glad I got a deeper grasp of the inner workings and I want to recommend this series of courses to everyone who starts studying Machine Learning.

Cheers.

STL Algorithms: Counting and Finding

Ola Sk — Mon, 09 Dec 2019 02:08:48 +0000

Foreword

(TL;DR)
STL isn't a very big library compared to many libraries available in other languages. But it's very robust, well tested and documented and it is included with every copy of a compiler. It handles most edge cases you can think of for a particular application of functions there included. So there are definitely good reasons for which it's worth to use it. Plus there's an undergoing work by C++ Standard Committee, on developing and maintaining the library. Moreover, your code just gets more readable.
For a person who's at least a bit familiar with what is there in an <algorithm> header, the code is so much more concise. It goes without saying that we as developers should not reinvent what is out there well tested and maintained, so why to contribute to a mental burden for anyone else reading your code.

I include a GitHub "Gist" for an overview of all code snippets from the article, see: gist.

You should also be familiar with the concepts of:

iterators to collections (the <algorithm> header is completely coupled with iterators),
predicates (for them I don't include two first parameters in all the descriptions of functions)

Remarks:

Iterators are similar to pointers: they can be dereferenced to access the value, incremented or/and decremented to iterate through elements of a container, besides, they can be passed to other functions that take iterator as its parameter, which we will se in the examples. Each container type in STL has a specific iterator designed to iterate through its elements.
Your IDE probably won't be able to hint about the functions you could use on a particular collection since all of the functions from the algorithm header are free functions. They're not member functions of some collections. Some collections from STL implement a few of some useful algorithms as their member functions—for those you should get autocomplete suggestions in your IDE for them, but it ain't Java-like experience.

What is a predicate

Condition the element must meet (usually a lambda)

A predicate is an expression that evaluates to true or false and serves as an internal switch/condition for STL algorithms to determine, basing on its value, whether the given element should or should not be considered as a subject for counting or as a result of a search.

1st and 2nd parameter serve the same consistent purpose for all counting/searching functions!

All of the counting and finding functions take a range of the collection to count or search over:

1st param: iterator to the beginning of the range.
2nd param: iterator to the end of the range.

There may be one or two more parameters specific for each function, but first two in order all do the same thing: declare what range of given collection we want to consider in the algorithm.

A collection for examples

In the article I use this vector for all examples:

std::vector<int> v{ 2, 5, 7, 1, 0, 6, 6, 2, -2, 4, 4, 7, 9, 0, 5}; 
//6 odd values

Counting

Count elements in the collection that have a particular value or meet a particular condition.

Functions

count()

2nd+ parameters

3rd: value to which compare elements of a sequence in a range determined by the two iterators (1st and 2nd parameter to count function) in order to count them.

Return

The number of elements of a given value.

//count how many entries have the target value (2)
int const target = 2;
int count_twos = count(begin(v), end(v), target); 
//alternative:
//int twos = count(v.begin(), v.end(), target);

count_if()

2nd+ parameters

3rd: predicate—condition the element should meet.

Return

Number of elements satisfying the condition.

//count how many entries are odd
int count_odds = count_if(begin(v), end(v), [](auto elem) { return elem % 2 != 0; }); 

//count how many long months are there
std::map<int, int> month_lengths{{1, 31}, {2, 28}, {3, 31}, {4, 30}, {5, 31}, {6, 30}, {7, 31}, {8, 31}, {9, 30}, {10, 31}, {11, 30}, {12, 31}}; 
int long_months = count_if(begin(month_lengths), end(month_lengths), [](auto elem) { /*elem is a pair*/ return elem.second == 31; });

all_of; none_of; any_of, and naming conventions of STL

Once you face a problem, you may find yourself splitting it into "manageable pieces". But you don't have to always do it this way. Different questions, in order to get answered, require you to formulate them well. There are many ready-made STL algorithms that are probable to do the task and most of them tend to follow a naming convention you should get comfortable with after some time.

Q: Are all of these elements...? [Null; odd; high priority etc.]
Q: Are any of these elements...?
Q: Are none of these elements...?

One way (too long) to answer these questions is to count and do some comparisons with your count:

bool all_of_them_are_odd = (count_odds == v.size()); 
bool none_of_them_is_odd = (count_odds == 0); 
bool any_of_them_are_odd = (count_odds > 0);

There's a better, STL way though:

bool allof = all_of(begin(v), end(v), [](auto elem) { return elem % 2 != 0; }); 
bool anyof = any_of(begin(v), end(v), [](auto elem) { return elem % 2 != 0; }); 
bool noneof = none_of(begin(v), end(v), [](auto elem) { return elem % 2 != 0; });

Finding

Find elements in the collection that have a particular value or meet a particular condition.

Functions

Chain calls to searching functions

As most of the searching functions take a pair of iterators and return an iterator to the first occurrence of an element with a given value or condition met, you can perform chain calls inside a loop, reusing the return iterators (using return iterators from the previous searches as arguments for next searches), in a loop, comparing current iterator to the end() iterator.

In most of the following functions, you can pass in either a value or a lambda (predicate), so you call search_n(...) function to find a number of consecutive elements that are all returning true from some condition like e.g. being over a €1000, etc. or a consecutive elements that give the same value from the evaluation of some expression based on the value.

find()

2nd+ parameters

3rd: value to search for.

Return

An iterator to an element in a collection (first occurrence) that has a value passed in as a third argument.
If the element isn't found, the end() iterator of a collection is returned.

// find the first zero in the collection
std::vector<int>::iterator result = find(begin(v), end(v), 0); 
int we_looked_for;
if (result != end(v))
{
    we_looked_for = *result; // result is a pointer
}

// find the first 2 after that 0
result = find(result, end(v), 2); 
// result as a "starting from" iterator
if (result != end(v))
{
    we_looked_for = *result;
}

//find the first 'a'
std::string s{ "So, find this a!" };
auto letter = find(begin(s), end(s), 'a');
if (letter != end(s))
{
    char a = *letter; // result is a pointer
}

find_if()

2nd+ parameters

3rd: predicate; a condition that the value of an element shall meet.

Return

Iterator to an element in a collection that meets the condition (first occurrence).
If the element isn't found, the end() iterator of a collection is returned.

// find the first occurence of an odd value (in a vector)
result = find_if(begin(v), end(v), [](auto elem) { return elem % 2 != 0; });
if (result != end(v))
{
    we_looked_for = *result;
}

find_if_not()

Works exactly like find_if, except it finds the first element that doesn't return the true from the predicate.

It's trivially easy to change an equals to a non-equals, or a less than to greater than or equal to. Some conditions though can be harder to negate easily, or you may go after, the code being more readable if you put explicit find_if_not in there.

2nd+ parameters

3rd: predicate; condition that the value of an element shall not meet.

Return

Iterator to an element in a collection that doesn't meet the condition (first occurrence).
If the element isn't found, the end() iterator of a collection is returned.

// find first even value
result = find_if_not(begin(v), end(v), [](auto elem) { return elem % 2 != 0; });
if (result != end(v))
{
    we_looked_for = *result;
}

find_first_of()

Lets you pass in two additional arguments–iterators to a collection and whichever element of that collection is found first—that element's iterator is returned.

2nd+ parameters

3rd: iterator to the beginning of the sub-range to search for.
4th: iterator to the end of the sub-range.

Return

Iterator to the first occurrence of an element, the value of which equals to any of the values from the collection of values to search for.

// here as third and fourth arguments we pass the iterators
// to the beginning and an end of a collection of values, 
// one of which we wanna find.
std::vector<int> primes = { 1, 2, 3, 5, 7, 11, 13, 17 };
result = find_first_of(begin(v), end(v), begin(primes), end(primes));
if (result != end(v))
{
    we_looked_for = *result;
}

search()

Rather than for a single value—it looks for a sequence. So in a collection of integers it may look for 1 followed by 2.
In a collection of characters, it may look for the word "is".

2nd+ parameters

3rd: iterator to the beginning of the sub-range to search for.
4th: iterator to the end of the sub-range.

Return

Iterator to the first element of the first occurrence of the subsequence.

std::vector<int> subsequence = { 2, 4 };
result = search(begin(v), end(v), begin(subsequence), end(subsequence));
if (result != end(v))
{
    we_looked_for = *result;
}

find_end()

It's exactly like search, with the exception that it gives you back the iterator to the first element of the last occurrence in a collection we look for that subsequence in.

2nd+ parameters

Same as search() above

Return

Iterator to the first element of the last occurrence of the subsequence.

//std::vector<int> subsequence = { 2, 4 };
result = search(begin(v), end(v), begin(subsequence), end(subsequence));
if (result != end(v))
{
    we_looked_for = *result;
}

search_n()

Finds consequtive instances. So if you don't just wanna find a zero—you wanna find 4 0s in a row, you use search_n().

2nd+ parameters

3rd: number of consecutive matches we want.
4th: the value that we want to have matched.

// We're looking for two fours in a row (inside of v vector)
// The resulting iterator points to the first element (earlier in terms of an index) of the sequence that we looked for.

result = search_n(begin(v), end(v), 2, 4); 
if (result != end(v))
{
    we_looked_for = *result;
}

adjacent_find()

Finds two consecutive elements that have the same value—whether they are two int values for a collection of integers or two same customers for a collection of customers.
They have to be consecutive, so it's not just that there are two elements with the same value anywhere in the collection, but they have to be right next to each other.

Parameters

notice that it doesn't take any parameters besides two iterators that specify the range to look in.

result = adjacent_find(begin(v), end(v)); 
if (result != end(v))
{
    //there are two sixes in a row in v, 
    //so the value expected is 6/
    we_looked_for = *result;
}

Summary

A well named (they're usually well named with some exceptions) function says more than a comment.
Algorithms work with any collection or part of such a collection that provides the right iterators.
The pattern used in code samples—to prefer end(v) over v.end() is because it works on more kinds of collections and it makes no difference for a common, regarded vector.

Side note

Have you set-up your C++ IDE already? You may want to take a look at how to perform a quick and easy set-up of Visual Studio Code on Linux.

Easy set-up: Automate building and debugging a currently active C++ source file with VS Code on Linux

Ola Sk — Fri, 06 Dec 2019 23:32:05 +0000

First build, then debug

In order to properly debug a C++ program, it needs to be built with debugging information first (-g flag with g++ compiler).

Set-up the development environment

If you're on a Linux, so you should have build-essential installed. To install or upgrade though, here's the command: $ sudo apt install build-essential This will install the necessary C/C++ development environment (compilers, libraries, linkers, etc.). $ g++ –version or $ g++ –v will print the version of the compiler on your system.
Get the VS Code (snap version available—you'll get it in "Ubuntu Software") and install "C/C++" extension (ms-vscode.cpptools) from Microsoft inside of VS Code -> extensions. The extension provides you with C/C++ IntelliSense and debugging.
Configure a build system for building a single file. Assuming you've created a directory for your C/C++ project and opened it inside the VS Code (you can do it from bash using code . while in the project directory). This is easy to set up as long as you haven't played with configuring build tasks inside the VS Code in your project yet. If you did though, and the tasks.json file was created inside the .vscode directory of your project, you can leverage getting great suggestions for detected tasks for C++ programs by removing the tasks.json file and choosing from the menu bar Terminal -> Configure Default Build Task.... If there's no configuration file yet, the Select environment window pops up and you get the option C++ (GDB/LLDB) which you shall choose. Now you probably want to choose "g++ build active file" from the suggestion list (creates tasks.json in the result).
Configure the interactive debugger inside the VS Code. You can't use the interactive debugger right away—it needs to set up its configuration file. If you created the "g++ build active file" and you don't have the launch.json configuration file yet inside the .vscode (you can try to delete it if you have one), then you should get the automatic suggestion for creating a "g++ build and debug active file". To get them, head to Debug, and now either: Open Configuration, Add configuration... or Start debugging—all options will let you configure the debugger settings if there's no configuration file yet. The Select environment window pops up and you get the option C++ (GDB/LLDB) which you shall choose. If you've messed up with the configuration inside the launch.json, you can delete the file from the .vscode directory and perform the steps above—for configuring the debugger from 0—to get the suggested configuration, which usually sets most of the things necessary. Once the set up is performed, the file named launch.json indeed is created inside the .vscode directory.
Content of the debugger configuration file launch.json—some of the arguments:
- "preLaunchTask"—the automatic building of source files just before debugging. The "preLaunchTask" argument's value serves as a link to the build task (specified inside tasks.json file in project's .vscode directory) with the "label" argument of the same value, e.g. "preLaunchTask": "g++ build active file", specified in launch.json links to "label": "g++ build active file" specified in tasks.json. "preLaunchTask" argument sets up the task of building the file first (compiling and linking), just before running the debugger. This is because the debugger needs to operate on files that are already built with the debugging information attached to them (-g option to g++ compiling command adds this information).
- "program"—compiled file's naming convention. "program": "${fileDirname}/${fileBasenameNoExtension}",. With this setup the debugger will look for the compiled file which has the same name as the source file, just w/o the .cpp ending and debug it as long as it was compiled with the -g option, which provides debugging information for later use by the debugger. The value of the "program" should correspond to how the file which is now taken as a subject for debugging was built by the mini build system that we established in .vscode/tasks.json:
```
"args": [
            "-g",
            "${file}",
            "-o",
            "${fileDirname}/${fileBasenameNoExtension}"
        ],
```
Possible problem with permissions on Linux while debugging C++ with GDB for the first time. When you run the debugger and then try to Step Over or Step Into while running it, the GDB debugger needs to store or access some temporary files inside the /build directory in the root of your system. The problem here is that the /build directory inside your system root / directory may not exist yet. So once it tries to put the files inside such a path it needs to create a /build directory inside a / root first, which it doesn't have permissions to do so. What you can do in such a situation would be that you create a /build directory yourself with sudo/su ([]:/$ sudo mkdir build) and then make the /build/ directory that you've just created permissible. In this step you can either try []:/$ sudo chown -R $USER:$GROUP /build or if it doesn't work, all permissions may be necessary to be given []:/$ sudo chmod 777 /build. It's difficult for me to reproduce the error as I deleted the /build folder on my machine and debugger doesn't look for any file in a path involving /build directory anymore. I'm bringing this issue up though since it existed for me once and creating the directory manually and giving it all permissions worked for me. The important thing here is not to get an idea of giving all permissions to the root directory as you'll break your entire filesystem's permissions and make it vulnerable, you'll also lose access to sudo.

Summary

What we've just done is that we automated the building and debugging operations inside of VS Code IDE. Every time we press the Debug button or F5, we get the currently active file built and performed debugging on instantaneously.