Data Skeptic

Kyle pontificates on how impressed he is with BERT.

Direct download: bert-is-magic.mp3
Category:general -- posted at: 10:11pm PDT

Kyle sits down with Jen Stirrup to inquire about her experiences helping companies deploy data science solutions in a variety of different settings.

Direct download: applied-data-science-in-industry.mp3
Category:general -- posted at: 10:31pm PDT

Video annotation is an expensive and time-consuming process. As a consequence, the available video datasets are useful but small. The availability of machine transcribed explainer videos offers a unique opportunity to rapidly develop a useful, if dirty, corpus of videos that are "self annotating", as hosts explain the actions they are taking on the screen.

This episode is a discussion of the HowTo100m dataset - a project which has assembled a video corpus of 136M video clips with captions covering 23k activities.

Related Links

The paper will be presented at ICCV 2019

@antoine77340

Antoine on Github

Antoine's homepage

Direct download: building-the-howto100m-video-corpus.mp3
Category:general -- posted at: 1:12pm PDT

Kyle provides a non-technical overview of why Bidirectional Encoder Representations from Transformers (BERT) is a powerful tool for natural language processing projects.

Direct download: bert.mp3
Category:general -- posted at: 11:42pm PDT

Kyle interviews Prasanth Pulavarthi about the Onyx format for deep neural networks.

Direct download: onyx.mp3
Category:general -- posted at: 12:52am PDT

Kyle and Linhda discuss some high level theory of mind and overview the concept machine learning concept of catastrophic forgetting.

Direct download: catastrophic-forgetting.mp3
Category:general -- posted at: 1:40am PDT

Sebastian Ruder is a research scientist at DeepMind.  In this episode, he joins us to discuss the state of the art in transfer learning and his contributions to it.

Direct download: transfer_learning.mp3
Category:general -- posted at: 9:02pm PDT

In 2017, Facebook published a paper called Deal or No Deal? End-to-End Learning for Negotiation Dialogues. In this research, the reinforcement learning agents developed a mechanism of communication (which could be called a language) that made them able to optimize their scores in the negotiation game. Many media sources reported this as if it were a first step towards Skynet taking over. In this episode, Kyle discusses bargaining agents and the actual results of this research.

Direct download: facebook-language.mp3
Category:general -- posted at: 9:21am PDT

Priyanka Biswas joins us in this episode to discuss natural language processing for languages that do not have as many resources as those that are more commonly studied such as English.  Successful NLP projects benefit from the availability of like large corpora, well-annotated corpora, software libraries, and pre-trained models.  For languages that researchers have not paid as much attention to, these tools are not always available.

Direct download: under-resourced-languages.mp3
Category:general -- posted at: 3:17pm PDT

Kyle and Linh Da discuss the class of approaches called "Named Entity Recognition" or NER.  NER algorithms take any string as input and return a list of "entities" - specific facts and agents in the text along with a classification of the type (e.g. person, date, place).

Direct download: named-entity-recognition.mp3
Category:general -- posted at: 11:16am PDT

USC students from the CAIS++ student organization have created a variety of novel projects under the mission statement of "artificial intelligence for social good". In this episode, Kyle interviews Zane and Leena about the Endangered Languages Project.

Direct download: the-death-of-a-language.mp3
Category:general -- posted at: 2:47pm PDT

Kyle and Linh Da discuss the concepts behind the neural Turing machine.

Direct download: neuro-turing-machines.mp3
Category:general -- posted at: 9:05am PDT

Kyle chats with Rohan Kumar about hyperscale, data at the edge, and a variety of other trends in data engineering in the cloud.

Direct download: data-infrastructure-in-the-cloud.mp3
Category:general -- posted at: 12:28pm PDT

In this episode, Kyle interviews Laura Edell at MS Build 2019.  The conversation covers a number of topics, notably her NCAA Final 4 prediction model.

 

Direct download: ncaa-predictions-on-spark.mp3
Category:general -- posted at: 9:52am PDT

Kyle and Linhda discuss attention and the transformer - an encoder/decoder architecture that extends the basic ideas of vector embeddings like word2vec into a more contextual use case.

Direct download: transformer.mp3
Category:general -- posted at: 8:31am PDT

When users on Twitter post with geographic tags, it creates the opportunity for a variety of interesting questions to be posed having to do with language, dialects, and location.  In this episode, Kyle interviews Bruno Gonçalves about his work studying language in this way.

 

Direct download: mapping-dialects-with-twitter-data.mp3
Category:general -- posted at: 8:00am PDT

This is an interview with Ellen Loeshelle, Director of Product Management at Clarabridge.  We primarily discuss sentiment analysis.

Direct download: sentiment-analysis.mp3
Category:general -- posted at: 6:46pm PDT

A gentle introduction to the very high-level idea of "attention" in machine learning, as it will play a major role in some upcoming episodes over the next few weeks.

Direct download: attention-part-1.mp3
Category:general -- posted at: 7:46pm PDT

Modern messaging technology has facilitated a trend towards highly compact, short messages send by users who can presume a great amount of context held between the communicating parties.  The rules of grammar may be discarded and often visible errors are a normal part of the conversation.

>>> Good mornink

>>> morning

Yet such short messages are also important for businesses whose users are unlikely to read a large block of text upon completing an order.  Similarly, a business might want to offer assistance and effective question and answering solutions in an automated and ideally multi-lingual way.  In this episode, we discuss techniques for designing solutions like that.

 

Direct download: cross-lingual.mp3
Category:general -- posted at: 6:42am PDT

ELMo (Embeddings from Language Models) introduced the idea of deep contextualized word representations. It extends previous ideas like word2vec and GloVe. The ELMo model is a neural network able to map natural language into a vector space. This vector space, out of box, proved to be incredibly useful in a wide variety of seemingly unrelated NLP tasks like sentiment analysis and name entity recognition.

Direct download: elmo.mp3
Category:general -- posted at: 8:00am PDT

Bilingual evaluation understudy (or BLEU) is a metric for evaluating the quality of machine translation using human translation as examples of acceptable quality results. This metric has become a widely used standard in the research literature. But is it the perfect measure of quality of machine translation?

Direct download: bleu.mp3
Category:general -- posted at: 9:16pm PDT

While at NeurIPS 2018, Kyle chatted with Liang Huang about his work with Baidu research on simultaneous translation, which was demoed at the conference.

Direct download: simultaneous-translation.mp3
Category:general -- posted at: 8:00am PDT

Machine transcription (the process of translating audio recordings of language to text) has come a long way in recent years. But how do the errors made during machine transcription compare to the errors made by a human transcriber? Find out in this episode!

Direct download: human-vs-machine-transcription-errors.mp3
Category:general -- posted at: 8:00am PDT

A sequence to sequence (or seq2seq) model is neural architecture used for translation (and other tasks) which consists of an encoder and a decoder.

The encoder/decoder architecture has obvious promise for machine translation, and has been successfully applied this way. Encoding an input to a small number of hidden nodes which can effectively be decoded to a matching string requires machine learning to learn an efficient representation of the essence of the strings.

In addition to translation, seq2seq models have been used in a number of other NLP tasks such as summarization and image captioning.

Related Links

Direct download: seq2seq.mp3
Category:general -- posted at: 8:00am PDT

Kyle interviews Julia Silge about her path into data science, her book Text Mining with R, and some of the ways in which she's used natural language processing in projects both personal and professional.

Related Links

Direct download: text-mining-in-r.mp3
Category:general -- posted at: 8:00am PDT

One of the most challenging NLP tasks is natural language understanding and reasoning. How can we construct algorithms that are able to achieve human level understanding of text and be able to answer general questions about it?

This is truly an open problem, and one with the bAbI dataset has been constructed to facilitate. bAbI presents a variety of different language understanding and reasoning tasks and exists as benchmark for comparing approaches.

In this episode, Kyle talks to Rasmus Berg Palm about his recent paper Recurrent Relational Networks

Direct download: recurrent-relational-networks.mp3
Category:general -- posted at: 7:47am PDT

In the first half of this episode, Kyle speaks with Marc-Alexandre Côté and Wendy Tay about Text World.  Text World is an engine that simulates text adventure games.  Developers are encouraged to try out their reinforcement learning skills building agents that can programmatically interact with the generated text adventure games.

 

In the second half of this episode, Kyle interviews Kevin Patel about his paper Towards Lower Bounds on Number of Dimensions for Word Embeddings.  In this research, the explore an important question of how many hidden nodes to use when creating a word embedding.

Direct download: text-world-and-word-embedding-lower-bounds.mp3
Category:general -- posted at: 8:00am PDT

Word2vec is an unsupervised machine learning model which is able to capture semantic information from the text it is trained on. The model is based on neural networks. Several large organizations like Google and Facebook have trained word embeddings (the result of word2vec) on large corpora and shared them for others to use.

The key algorithmic ideas involved in word2vec is the continuous bag of words model (CBOW). In this episode, Kyle uses excerpts from the 1983 cinematic masterpiece War Games, and challenges Linhda to guess a word Kyle leaves out of the transcript. This is similar to how word2vec is trained. It trains a neural network to predict a hidden word based on the words that appear before and after the missing location.

Direct download: word2vec.mp3
Category:general -- posted at: 8:00am PDT

In a recent paper, Leveraging Discourse Information Effectively for Authorship Attribution, authors Su Wang, Elisa Ferracane, and Raymond J. Mooney describe a deep learning methodology for predict which of a collection of authors was the author of a given document.

Direct download: authorship-attribution.mp3
Category:general -- posted at: 8:44am PDT

The earliest efforts to apply machine learning to natural language tended to convert every token (every word, more or less) into a unique feature. While techniques like stemming may have cut the number of unique tokens down, researchers always had to face a problem that was highly dimensional. Naive Bayes algorithm was celebrated in NLP applications because of its ability to efficiently process highly dimensional data.

Of course, other algorithms were applied to natural language tasks as well. While different algorithms had different strengths and weaknesses to different NLP problems, an early paper titled Scaling to Very Very Large Corpora for Natural Language Disambiguation popularized one somewhat surprising idea. For many NLP tasks, simply providing a large corpus of examples not only improved accuracy, but it also showed that asymptotically, some algorithms yielded more improvement from working on very, very large corpora.

Although not explicitly in about NLP, the noteworthy paper The Unreasonable Effectiveness of Data emphasizes this point further while paying homage to the classic treatise The Unreasonable Effectiveness of Mathematics in the Natural Sciences.

In this episode, Kyle shares a few thoughts along these lines with Linh Da.

The discussion winds up with a brief introduction to Zipf's law. When applied to natural language, Zipf's law states that the frequency of any given word in a corpus (regardless of language) will be proportional to its rank in the frequency table.

Direct download: extremely-large-corpora.mp3
Category:general -- posted at: 8:00am PDT

Github is many things besides source control. It's a social network, even though not everyone realizes it. It's a vast repository of code. It's a ticketing and project management system. And of course, it has search as well.

In this episode, Kyle interviews Hamel Husain about his research into semantic code search.

Direct download: semantic-search-at-github.mp3
Category:general -- posted at: 8:00am PDT

This episode reboots our podcast with the theme of Natural Language Processing for the next few months.

We begin with introductions of Yoshi and Linh Da and then get into a broad discussion about natural language processing: what it is, what some of the classic problems are, and just a bit on approaches.

Finishing out the show is an interview with Lucy Park about her work on the KoNLPy library for Korean NLP in Python.

If you want to share your NLP project, please join our Slack channel.  We're eager to see what listeners are working on!

http://konlpy.org/en/latest/

 

 

Direct download: natural-language-processing.mp3
Category:general -- posted at: 8:15am PDT

Kyle shares a few thoughts on mistakes observed by job applicants and also shares a few procedural insights listeners at early stages in their careers might find value in.

Direct download: data-science-hiring-processes.mp3
Category:general -- posted at: 8:00am PDT

Epicac by Kurt Vonnegut.

Direct download: epicac.mp3
Category:general -- posted at: 10:07pm PDT

In today's episode, Kyle chats with Alexander Zhebrak, CTO of Insilico Medicine, Inc.

Insilico self describes as artificial intelligence for drug discovery, biomarker development, and aging research.

The conversation in this episode explores the ways in which machine learning, in particular, deep learning, is contributing to the advancement of drug discovery. This happens not just through research but also through software development. Insilico works on data pipelines and tools like MOSES, a benchmarking platform to support research on machine learning for drug discovery. The MOSES platform provides a standardized benchmarking dataset, a set of open-sourced models with unified implementation, and metrics to evaluate and assess their performance.

Direct download: drug-discovery.mp3
Category:general -- posted at: 8:00am PDT

At the NeurIPS 2018 conference, Stradigi AI premiered a training game which helps players learn American Sign Language.

This episode brings the first of many interviews conducted at NeurIPS 2018.

In this episode, Kyle interviews Chief Data Scientist Carolina Bessega about the deep learning architecture used in this project.

The Stradigi AI team was exhibiting a project called the American Sign Language (ASL) Alphabet Game at the recent NeurIPS 2018 conference. They also published a detailed blog post about how they built the system found here.

Direct download: sign-language-recognition.mp3
Category:general -- posted at: 8:00am PDT

 This week, Kyle interviews Scott Nestler on the topic of Data Ethics.

Today, no ubiquitous, formal ethical protocol exists for data science, although some have been proposed. One example is the INFORMS Ethics Guidelines.

Guidelines like this are rather informal compared to other professions, like the Hippocratic Oath. Yet not every profession requires such a formal commitment.

In this episode, Scott shares his perspective on a variety of ethical questions specific to data and analytics.

Direct download: data-ethics.mp3
Category:general -- posted at: 8:00am PDT

Kyle interviews Mick West, author of Escaping the Rabbit Hole: How to Debunk Conspiracy Theories Using Facts, Logic, and Respect about the nature of conspiracy theories, the people that believe them, and how to help people escape the belief in false information.

Mick is also the creator of metabunk.org.

The discussion explores conspiracies like chemtrails, 9/11 conspiracy theories, JFK assassination theories, and the flat Earth theory. We live in a complex world in which no person can have a sufficient understanding of all topics. It's only natural that some percentage of people will eventually adopt fringe beliefs. In this book, Mick provides a fantastic guide to helping individuals who have fallen into a rabbit hole of pseudo-science or fake news.

Direct download: escaping-the-rabbit-hole.mp3
Category:general -- posted at: 9:06am PDT

Fake news attempts to lead readers/listeners/viewers to conclusions that are not descriptions of reality.  They do this most often by presenting false premises, but sometimes by presenting flawed logic.

An argument is only sound and valid if the conclusions are drawn directly from all the state premises, and if there exists a path of logical reasoning leading from those premises to the conclusion.

While creating a theorem does feel to most mathematicians as a creative act of discovery, some theorems have been proven using nothing more than search.  All the "rules" of logic (like modus ponens) can be encoded into a computer program.  That program can start from the premises, applying various combinations of rules to inference new information, and check to see if the program has inference the desired conclusion or its negation.  This does seem like a mechanical process when painted in this light.  However, several challenges exist preventing any theorem prover from instantly solving all the open problems in mathematics.  In this episode, we discuss a bit about what those challenges are.

 

Direct download: theorem-provers.mp3
Category:general -- posted at: 8:09am PDT

Fake news can be responded to with fact-checking. However, it's easier to create fake news than the fact check it.

Full Fact is the UK's independent fact-checking organization. In this episode, Kyle interviews Mevan Babakar, head of automated fact-checking at Full Fact.

Our discussion talks about the process and challenges in doing fact-checking. Full Fact has been exploring ways in which machine learning can assist in automating parts of the fact-checking process. Progress in areas like this allows journalists to be more effective and rapid in responding to new information.

Direct download: automated-fact-checking.mp3
Category:general -- posted at: 8:45am PDT

In mathematics, truth is universal.  In data, truth lies in the where clause of the query.

As large organizations have grown to rely on their data more significantly for decision making, a common problem is not being able to agree on what the data is.

As the volume and velocity of data grow, challenges emerge in answering questions with precision.  A simple question like "what was the revenue yesterday" could become mired in details.  Did your query account for transactions that haven't been finalized?  If I query again later, should I exclude orders that have been returned since the last query?  What time zone should I use?  The list goes on and on.

In any large enough organization, you are also likely to find multiple copies if the same data.  Independent systems might record the same information with slight variance.  Sometimes systems will import data from other systems; a process which could become out of sync for several reasons.

For any sufficiently large system, answering analytical questions with precision can become a non-trivial challenge.  The business intelligence community aspires to provide a "single source of truth" - one canonical place where data consumers can go to get precise, reliable, and trusted answers to their analytical questions.

Direct download: single-source-of-truth.mp3
Category:general -- posted at: 7:00am PDT

Fast radio bursts are an astrophysical phenomenon first observed in 2007. While many observations have been made, science has yet to explain the mechanism for these events. This has led some to ask: could it be a form of extra-terrestrial communication?

Probably not. Kyle asks Gerry Zhang who works at the Berkeley SETI Research Center about this possibility and more importantly, about his applications of deep learning to detect fast radio bursts.

Radio astronomy captures observations from space which can be converted to a waterfall chart or spectrogram. These data structures can be formatted in a visual way and also make great candidates for applying deep learning to the task of detecting the fast radio bursts.

Direct download: detecting-fast-radio-bursts-with-deep-learning.mp3
Category:general -- posted at: 9:38am PDT

This episode explores the root concept of what it is to be Bayesian: describing knowledge of a system probabilistically, having an appropriate prior probability, know how to weigh new evidence, and following Bayes's rule to compute the revised distribution.

We present this concept in a few different contexts but primarily focus on how our bird Yoshi sends signals about her food preferences.

Like many animals, Yoshi is a complex creature whose preferences cannot easily be summarized by a straightforward utility function the way they might in a textbook reinforcement learning problem. Her preferences are sequential, conditional, and evolving. We may not always know what our bird is thinking, but we have some good indicators that give us clues.

Direct download: bayesian-redux.mp3
Category:general -- posted at: 8:00am PDT

This is our interview with Dorje Brody about his recent paper with David Meier, How to model fake news. This paper uses the tools of communication theory and a sub-topic called filtering theory to describe the mathematical basis for an information channel which can contain fake news.

 

Thanks to our sponsor Gartner.

Direct download: modeling-fake-news.mp3
Category:general -- posted at: 8:00am PDT

Without getting into definitions, we have an intuitive sense of what a "community" is. The Louvain Method for Community Detection is one of the best known mathematical techniques designed to detect communities.

This method requires typical graph data in which people are nodes and edges are their connections. It's easy to imagine this data in the context of Facebook or LinkedIn but the technique applies just as well to any other dataset like cellular phone calling records or pen-pals.

The Louvain Method provides a means of measuring the strength of any proposed community based on a concept known as Modularity. Modularity is a value in the range [-1, 1] that measure the density of links internal to a community against links external to the community. The quite palatable assumption here is that a genuine community would have members that are strongly interconnected.

A community is not necessarily the same thing as a clique; it is not required that all community members know each other. Rather, we simply define a community as a graph structure where the nodes are more connected to each other than connected to people outside the community.

It's only natural that any person in a community has many connections to people outside that community. The more a community has internal connections over external connections, the stronger that community is considered to be. The Louvain Method elegantly captures this intuitively desirable quality.

Direct download: louvain-community-detection.mp3
Category:general -- posted at: 8:22am PDT

In this episode, our guest is Dan Kahan about his research into how people consume and interpret science news.

In an era of fake news, motivated reasoning, and alternative facts, important questions need to be asked about how people understand new information.

Dan is a member of the Cultural Cognition Project at Yale University, a group of scholars interested in studying how cultural values shape public risk perceptions and related policy beliefs.

In a paper titled Cultural cognition of scientific consensus, Dan and co-authors Hank Jenkins‐Smith and Donald Braman discuss the "cultural cognition of risk" and establish experimentally that individuals tend to update their beliefs about scientific information through a context of their pre-existing cultural beliefs. In this way, topics such as climate change, nuclear power, and conceal-carry handgun permits often result in people.

The findings of this and other studies tell us that on topics such as these, even when people are given proper information about a scientific consensus, individuals still interpret those results through the lens of their pre-existing cultural beliefs.

The ‘cultural cognition of risk’ refers to the tendency of individuals to form risk perceptions that are congenial to their values. The study presents both correlational and experimental evidence confirming that cultural cognition shapes individuals’ beliefs about the existence of scientific consensus, and the process by which they form such beliefs, relating to climate change, the disposal of nuclear wastes, and the effect of permitting concealed possession of handguns. The implications of this dynamic for science communication and public policy‐making are discussed.

Direct download: cultural-cognition.mp3
Category:general -- posted at: 8:24am PDT

A false discovery rate (FDR) is a methodology that can be useful when struggling with the problem of multiple comparisons.

In any experiment, if the experimenter checks more than one dependent variable, then they are making multiple comparisons. Naturally, if you make enough comparisons, you will eventually find some correlation.

Classically, people applied the Bonferroni Correction. In essence, this procedure dictates that you should lower your p-value (raise your standard of evidence) by a specific amount depending on the number of variables you're considering. While effective, this methodology is strict about preventing false positives (type i errors). You aren't likely to find evidence for a hypothesis that is actually false using Bonferroni. However, your exuberance to avoid type i errors may have introduced some type ii errors. There could be some hypotheses that are actually true, which you did not notice.

This episode covers an alternative known as false discovery rates. The essence of this method is to make more specific adjustments to your expectation of what p-value is sufficient evidence. 

Direct download: false-discovery-rates.mp3
Category:general -- posted at: 8:09am PDT

Digital videos can be described as sequences of still images and associated audio. Audio is easy to fake. What about video?

A video can easily be broken down into a sequence of still images replayed rapidly in sequence. In this context, videos are simply very high dimensional sequences of observations, ripe for input into a machine learning algorithm.

The availability of commodity hardware, clever algorithms, and well-designed software to implement those algorithms at scale make it possible to do machine learning on video, but to what end? There are many answers, one interesting approach being the technology called "DeepFakes".

The Deep of Deepfakes refers to Deep Learning, and the fake refers to the function of the software - to take a real video of a human being and digitally alter their face to match someone else's face. Here are two examples:

This software produces curiously convincing fake videos. Yet, there's something slightly off about them. Surely machine learning can be used to determine real from fake... right? Siwei Lyu and his collaborators certainly thought so and demonstrated this idea by identifying a novel, detectable feature which was commonly missing from videos produced by the Deep Fakes software.

In this episode, we discuss this use case for deep learning, detecting fake videos, and the threat of fake videos in the future.

Direct download: deepfakes.mp3
Category:general -- posted at: 8:00am PDT

In this episode, Kyle reviews what we've learned so far in our series on Fake News and talks briefly about where we're going next.

Direct download: fake-news-midterm.mp3
Category:general -- posted at: 8:00am PDT

Two weeks ago we discussed click through rates or CTRs and their usefulness and limits as a metric. Today, we discuss a related metric known as quality score.

While that phrase has probably been used to mean dozens of different things in different contexts, our discussion focuses around the idea of quality score encountered in Search Engine Marketing (SEM). SEM is the practice of purchasing keyword targeted ads shown to customers using a search engine.

Most SEM is managed via an auction mechanism - the advertiser states the price they are willing to pay, and in real time, the search engine will serve users advertisements and charge the advertiser.

But how to search engines decide who to show and what price to charge? This is a complicated question requiring a multi-part answer to address completely. In this episode, we focus on one part of that equation, which is the quality score the search engine assigns to the ad in context. This quality score is calculated via several factors including crawling the destination page (also called the landing page) and predicting how applicable the content found there is to the ad itself.

Direct download: quality_score.mp3
Category:general -- posted at: 10:28pm PDT

Kyle interviews Steven Sloman, Professor in the school of Cognitive, Linguistic, and Psychological Sciences at Brown University. Steven is co-author of The Knowledge Illusion: Why We Never Think Alone and Causal Models: How People Think about the World and Its Alternatives. Steven shares his perspective and research into how people process information and what this teaches us about the existence of and belief in fake news.

Direct download: the-knowledge-illusion.mp3
Category:general -- posted at: 8:00am PDT

A Click Through Rate (CTR) is the proportion of clicks to impressions of some item of content shared online. This terminology is most commonly used in digital advertising but applies just as well to content websites might choose to feature on their homepage or in search results.

A CTR is intuitively appealing as a metric for optimization. After all, if users are disinterested in some content, under normal circumstances, it's reasonable to assume they would ignore the content, rather than clicking on it. On the other hand, the best content is likely to elicit a high CTR as users signal their interest by following the hyperlink.

In the advertising world, a website could charge per impression, per click, or per action. Both impression and action based pricing have asymmetrical results for the publisher and advertiser. However, paying per click (CPC based advertising) seems to strike a nice balance. For this and other numeric reasons, many digital advertising mechanisms (such as Google Adwords) use CPC as the payment mechanism.

When charging per click, an advertising platform will value a high CTR when selecting which ad to show. As we learned in our episode on Goodhart's Law, once a measure is turned into a target, it ceases to be a good measure. While CTR alone does not entirely drive most online advertising algorithms, it does play an important role. Thus, advertisers are incentivized to adopt strategies that maximize CTR.

On the surface, this sounds like a great idea: provide internet users what they are looking for, and be awarded with their attention and lower advertising costs. However, one possible unintended consequence of this type of optimization is the creation of ads which are designed solely to generate clicks, regardless of if the users are happy with the page they visit after clicking a link.

So, at least in part, websites that optimize for higher CTRs are going to favor content that does a good job getting viewers to click it. Getting a user to view a page is not totally synonymous with getting a user to appreciate the content of a page. The gap between the algorithmic goal and the user experience could be one of the factors that has promoted the creation of fake news.

Direct download: ctrs.mp3
Category:general -- posted at: 8:00am PDT

The scale and frequency with which information can be distributed on social media makes the problem of fake news a rapidly metastasizing issue. To do any content filtering or labeling demands an algorithmic solution.

In today's episode, Kyle interviews Kai Shu and Mike Tamir about their independent work exploring the use of machine learning to detect fake news.

Kai Shu and his co-authors published Fake News Detection on Social Media: A Data Mining Perspective, a research paper which both surveys the existing literature and organizes the structure of the problem in a robust way.

Mike Tamir led the development of fakerfact.org, a website and Chrome/Firefox plugin which leverages machine learning to try and predict the category of a previously unseen web page, with categories like opinion, wiki, and fake news.

Direct download: algorithmic-detection-of-fake-news.mp3
Category:general -- posted at: 8:06am PDT

If you prepared a list of creatures regarded as highly intelligent, it's unlikely ants would make the cut. This is expected, as on an individual level, ants do not generally display behavior that most humans would regard as intelligence. In fact, it might even be true that most species of ants are unable to learn. Despite this, ant colonies have evolved excellent survival mechanisms through the careful orchestration of ants.

Direct download: ant-intelligence.mp3
Category:general -- posted at: 8:00am PDT

With publications such as "Prior exposure increases perceived accuracy of fake news", "Lazy, not biased: Susceptibility to partisan fake news is better explained by lack of reasoning than by motivated reasoning", and "The science of fake news", Gordon Pennycook is asking and answering analytical questions about the nature of human intuition and fake news.

Gordon appeared on Data Skeptic in 2016 to discuss people's ability to recognize pseudo-profound bullshit.  This episode explores his work in fake news.

Direct download: human-detection-of-fake-news.mp3
Category:general -- posted at: 8:00am PDT

Today's spam filters are advanced data driven tools. They rely on a variety of techniques to effectively and often seamlessly filter out junk email from good email.

Whitelists, blacklists, traffic analysis, network analysis, and a variety of other tools are probably employed by most major players in this area. Naturally content analysis can be an especially powerful tool for detecting spam.

Given the binary nature of the problem (Spam or \neg Spam) its clear that this is a great problem to use machine learning to solve. In order to apply machine learning, you first need a labelled training set. Thankfully, many standard corpora of labelled spam data are readily available. Further, if you're working for a company with a spam filtering problem, often asking users to self-moderate or flag things as spam can be an effective way to generate a large amount of labels for "free".

With a labeled dataset in hand, a data scientist working on spam filtering must next do feature engineering. This should be done with consideration of the algorithm that will be used. The Naive Bayesian Classifer has been a popular choice for detecting spam because it tends to perform pretty well on high dimensional data, unlike a lot of other ML algorithms. It also is very efficient to compute, making it possible to train a per-user Classifier if one wished to. While we might do some basic NLP tricks, for the most part, we can turn each word in a document (or perhaps each bigram or n-gram in a document) into a feature.

The Naive part of the Naive Bayesian Classifier stems from the naive assumption that all features in one's analysis are considered to be independent. If x and y are known to be independent, then Pr(x \cap y) = Pr(x) \cdot Pr(y). In other words, you just multiply the probabilities together. Shh, don't tell anyone, but this assumption is actually wrong! Certainly, if a document contains the word algorithm, it's more likely to contain the word probability than some randomly selected document. Thus, Pr(\text{algorithm} \cap \text{probability}) > Pr(\text{algorithm}) \cdot Pr(\text{probability}), violating the assumption. Despite this "flaw", the Naive Bayesian Classifier works remarkably will on many problems. If one employs the common approach of converting a document into bigrams (pairs of words instead of single words), then you can capture a good deal of this correlation indirectly.

In the final leg of the discussion, we explore the question of whether or not a Naive Bayesian Classifier would be a good choice for detecting fake news.

 
Direct download: spam-filtering.mp3
Category:general -- posted at: 8:00am PDT

How does fake news get spread online? Its not just a matter of manipulating search algorithms. The social platforms for sharing play a major role in the distribution of fake news. But how significant of an impact can there be? How significantly can bots influence the spread of fake news?

In this episode, Kyle interviews Filippo Menczer, Professor of Computer Science and Informatics.

Fil is part of the Observatory on Social Media ([OSoMe][https://osome.iuni.iu.edu/tools/]). OSoMe are the creators of HoaxyBotometerFakey, and other tools for studying the spread of information on social media.

The interview explores these tools and the contributions Bots make to the spread of fake news.

Direct download: the-spread-of-fake-news.mp3
Category:general -- posted at: 8:00am PDT

This episode kicks off our new theme of "Fake News" with guests Robert Sheaffer and Brad Schwartz.

Fake news is a new label for an old idea. For our purposes, we will define fake news information created to deliberately mislead while masquerading as a legitimate, journalistic source of truth. It's become a modern topic of discussion as our cultures evolve to the fledgling mechanisms of communication introduced by online platforms.

What was the earliest incident of fake news? That's a question for which we may never find a satisfying answer. While not the earliest, we present a dramatization of an early example of fake news, which leads us into a discussion with UFO Skeptic Robert Sheaffer. Following that we get into our main interview with Brad Schwartz, author of Broadcast Hysteria: Orson Welles's War of the Worlds and the Art of Fake News.

Direct download: fake-news.mp3
Category:general -- posted at: 8:00am PDT

We revisit the 2018 Microsoft Build in this episode, focusing on the latest ideas in DevOps. Kyle interviews Cloud Developer Advocates Damien Brady, Paige Bailey, and Donovan Brown to talk about DevOps and data science and databases.

For a data scientist, what does it even mean to “build”? Packaging and deployment are things that a data scientist doesn't normally have to consider in their day-to-day work. The process of making an AI app is usually divided into two streams of work: data scientists building machine learning models and app developers building the application for end users to consume.

DevOps includes all the parties involved in getting the application deployed and maintained and thinking about all the phases that follow and precede their part of the end solution. So what does DevOps mean for data science? Why should you adopt DevOps best practices?

In the first half, Paige and Damian share their views on what DevOps for data science would look like and how it can be introduced to provide continuous integration, delivery, and deployment of data science models. In the second half, Donovan and Damian talk about the DevOps life cycle of putting a database under version control and carrying out deployments through a release pipeline.

Direct download: devops-for-data-science.mp3
Category:general -- posted at: 1:23pm PDT

Logic is a fundamental of mathematical systems. It's roots are the values true and false and it's power is in what it's rules allow you to prove. Prepositional logic provides it's user variables. This episode gets into First Order Logic, an extension to prepositional logic.

Direct download: first-order-logic.mp3
Category:general -- posted at: 8:00am PDT

An intelligent agent trained in a simulated environment may be prone to making mistakes in the real world due to discrepancies between the training and real-world conditions. The areas where an agent makes mistakes are hard to find, known as "blind spots," and can stem from various reasons. In this week’s episode, Kyle is joined by Ramya Ramakrishnan, a PhD candidate at MIT, to discuss the idea “blind spots” in reinforcement learning and approaches to discover them.

Direct download: blind-spots-in-reinforcement-learning.mp3
Category:data science -- posted at: 8:00am PDT

In this week’s episode, our host Kyle interviews Gokula Krishnan from ETH Zurich, about his recent contributions to defenses against adversarial attacks. The discussion centers around his latest paper, titled “Defending Against Adversarial Attacks by Leveraging an Entire GAN,” and his proposed algorithm, aptly named ‘Cowboy.’

Direct download: defending-against-adversarial-attacks.mp3
Category:general -- posted at: 8:00am PDT

On a long car ride, Linhda and Kyle record a short episode. This discussion is about transfer learning, a technique using in machine learning to leverage training from one domain to have a head start learning in another domain.

Transfer learning has some obvious appealing features. Take the example of an image recognition problem. There are now many widely available models that do general image recognition. Detecting that an image contains a "sofa" is an impressive feat. However, for a furniture company interested in more specific details, this classifier is absurdly general. Should the furniture company build a massive corpus of tagged photos, effectively starting from scratch? Or is there a way they can transfer the learnings from the general task to the specific one.

A general definition of transfer learning in machine learning is the use of taking some or all aspects of a pre-trained model as the basis to begin training a new model which a specific and potentially limited dataset.

Direct download: transfer-learning.mp3
Category:general -- posted at: 8:00am PDT

Medical imaging is a highly effective tool used by clinicians to diagnose a wide array of diseases and injuries. However, it often requires exceptionally trained specialists such as radiologists to interpret accurately. In this episode of Data Skeptic, our host Kyle Polich is joined by Gabriel Maicas, a PhD candidate at the University of Adelaide, to discuss machine learning systems that can be used by radiologists to improve their accuracy and speed of diagnosis.

Direct download: medical-imaging-training-techniques.mp3
Category:data science -- posted at: 7:00am PDT

Thanks to our sponsor Galvanize

A Kalman Filter is a technique for taking a sequence of observations about an object or variable and determining the most likely current state of that object. In this episode, we discuss it in the context of tracking our lilac crowned amazon parrot Yoshi.

Kalman filters have many applications but the one of particular interest under our current theme of artificial intelligence is to efficiently update one's beliefs in light of new information.

The Kalman filter is based upon the Gaussian distribution. This distribution is described by two parameters: \mu (the mean) and standard deviation. The procedure for updating these values in light of new information has a closed form. This means that it can be described with straightforward formulae and computed very efficiently.

You may gain a greater appreciation for Kalman filters by considering what would happen if you could not rely on the Gaussian distribution to describe your posterior beliefs. If determining the probability distribution over the variables describing some object cannot be efficiently computed, then by definition, maintaining the most up to date posterior beliefs can be a significant challenge.

Kyle will be giving a talk at Skeptical 2018 in Berkeley, CA on June 10.

Direct download: kalman-filters.mp3
Category:general -- posted at: 12:47am PDT

There's so much to discuss on the AI side, it's hard to know where to begin. Luckily,  Steve Guggenheimer, Microsoft’s corporate vice president of AI Business, and Carlos Pessoa, a software engineering manager for the company’s Cloud AI Platform, talked to Kyle about announcements related to AI in industry.

Direct download: ms-ai.mp3
Category:data science -- posted at: 8:00am PDT

Today's interview is with the authors of the textbook Artificial Intelligence and Games.

Direct download: ai-in-games-master.mp3
Category:general -- posted at: 6:00am PDT

Thanks to our sponsor The Great Courses.

This week's episode is a short primer on game theory.

For tickets to the free Data Skeptic meetup in Chicago on Tuesday, May 15 at the Mendoza College of Business (224 South Michigan Avenue, Suite 350), click here,

Direct download: game-theory.mp3
Category:general -- posted at: 11:16am PDT

In this episode of Data Skeptic, Kyle chats with Jerry Schwarz from the Independent Investigations Group (IIG)'s SF Bay Area chapter about testing claims of the paranormal. The IIG is a volunteer-based organization dedicated to investigating paranormal or extraordinary claim from a scientific viewpoint. The group, headquartered at the Center for Inquiry-Los Angeles in Hollywood, offers a $100,000 prize to anyone who can show, under proper observing conditions, evidence of any paranormal, supernatural, or occult power or event.

CHICAGO Tues, May 15, 6pm. Come to our Data Skeptic meetup.

CHICAGO Saturday, May 19, 10am. Kyle will be giving a talk at the Chicago AI, Data Science, and Blockchain Conference 2018.

Direct download: the-experimental-design-of-paranormal-claims.mp3
Category:skepticism -- posted at: 8:00am PDT

Our guest this week, Hector Levesque, joins us to discuss an alternative way to measure a machine’s intelligence, called Winograd Schemas Challenge. The challenge was proposed as a possible alternative to the Turing test during the 2011 AAAI Spring Symposium. The challenge involves a small reading comprehension test about common sense knowledge.

Direct download: winograd_episode.mp3
Category:data science -- posted at: 9:52am PDT

This week on Data Skeptic, we begin with a skit to introduce the topic of this show: The Imitation Game. We open with a scene in the distant future. The year is 2027, and a company called Shamony is announcing their new product, Ada, the most advanced artificial intelligence agent. To prove its superiority, the lead scientist announces that it will use the Turing Test that Alan Turing proposed in 1950. During this we introduce Turing’s “objections” outlined in his famous paper, “Computing Machinery and Intelligence.”

Following that, we talk with improv coach Holly Laurent on the art of improvisation and Peter Clark from the Allen Institute for Artificial Intelligence about question and answering algorithms.

Direct download: the-imitation-game.mp3
Category:general -- posted at: 8:00am PDT

In this episode, Kyle shares his perspective on the chatbot Eugene Goostman which (some claim) "passed" the Turing Test. As a second topic Kyle also does an intro of the Winograd Schema Challenge.

Direct download: eugene-goostman.mp3
Category:general -- posted at: 8:00am PDT

In this episode, Kyle and Linhda discuss the theory of formal languages. Any language can (theoretically) be a formal language. The requirement is that the language can be rigorously described as a set of strings which are considered part of the language. Those strings are any combination of alphabet characters in the given language.

Read more

 

Direct download: the-theory-of-formal-languages.mp3
Category:general -- posted at: 8:00am PDT

The Loebner Prize is a competition in the spirit of the Turing Test.  Participants are welcome to submit conversational agent software to be judged by a panel of humans.  This episode includes interviews with Charlie Maloney, a judge in the Loebner Prize, and Bruce Wilcox, a winner of the Loebner Prize.

Direct download: the-loebner-prize.mp3
Category:general -- posted at: 8:00am PDT

In this episode, Kyle chats with Vince from iv.ai and Heather Shapiro who works on the Microsoft Bot Framework. We solicit their advice on building a good chatbot both creatively and technically.

Our sponsor today is Warby Parker.

Direct download: chatbots.mp3
Category:general -- posted at: 8:00am PDT

In this week’s episode, Kyle Polich interviews Pedro Domingos about his book, The Master Algorithm: How the quest for the ultimate learning machine will remake our world. In the book, Domingos describes what machine learning is doing for humanity, how it works and what it could do in the future. He also hints at the possibility of an ultimate learning algorithm, in which the machine uses it will be able to derive all knowledge — past, present, and future.

Direct download: the-master-algorithm.mp3
Category:general -- posted at: 8:00am PDT

What's the best machine learning algorithm to use? I hear that XGBoost wins most of the Kaggle competitions that aren't won with deep learning. Should I just use XGBoost all the time? That might work out most of the time in practice, but a proof exists which tells us that there cannot be one true algorithm to rule them.

Direct download: no-free-lunch-theorems.mp3
Category:general -- posted at: 8:00am PDT

For a long time, physicians have recognized that the tools they have aren't powerful enough to treat complex diseases, like cancer. In addition to data science and models, clinicians also needed actual products — tools that physicians and researchers can draw upon to answer questions they regularly confront, such as “what clinical trials are available for this patient that I'm seeing right now?” In this episode, our host Kyle interviews guests Alex Grigorenko and Iker Huerga from Memorial Sloan Kettering Cancer Center to talk about how data and technology can be used to prevent, control and ultimately cure cancer.

Direct download: ml-at-sloan-kettering-cancer-center.mp3
Category:general -- posted at: 8:00am PDT

In a previous episode, we discussed Markov Decision Processes or MDPs, a framework for decision making and planning. This episode explores the generalization Partially Observable MDPs (POMDPs) which are an incredibly general framework that describes most every agent based system.

Direct download: optimal-decision-making-with-pomdps.mp3
Category:general -- posted at: 8:00am PDT

Making a decision is a complex task. Today's guest Dongho Kim discusses how he and his team at Prowler has been building a platform that will be accessible by way of APIs and a set of pre-made scripts for autonomous decision making based on probabilistic modeling, reinforcement learning, and game theory. The aim is so that an AI system could make decisions just as good as humans can.

Direct download: ai-decision-making.mp3
Category:data science -- posted at: 8:00am PDT

In many real world situations, a person/agent doesn't necessarily know their own objectives or the mechanics of the world they're interacting with. However, if the agent receives rewards which are correlated with the both their actions and the state of the world, then reinforcement learning can be used to discover behaviors that maximize the reward earned.

Direct download: reinforcement-learning.mp3
Category:general -- posted at: 8:00am PDT

In this week’s episode, Kyle is joined by Risto Miikkulainen, a professor of computer science and neuroscience at the University of Texas at Austin. They talk about evolutionary computation, its applications in deep learning, and how it’s inspired by biology. They also discuss some of the things Sentient Technologies is working on in stock and finances, retail, e-commerce and web design, as well as the technology behind it-- evolutionary algorithms.

Direct download: evolutionary-computation.mp3
Category:data science -- posted at: 8:00am PDT

Formally, an MDP is defined as the tuple containing states, actions, the transition function, and the reward function. This podcast examines each of these and presents them in the context of simple examples.  Despite MDPs suffering from the curse of dimensionality, they're a useful formalism and a basic concept we will expand on in future episodes.

Direct download: markov-decision-process.mp3
Category:general -- posted at: 8:00am PDT

Last week on Data Skeptic, we visited the Laboratory of Neuroimaging, or LONI, at USC and learned about their data-driven platform that enables scientists from all over the world to share, transform, store, manage and analyze their data to understand neurological diseases better. We talked about how neuroscientists measure the brain using data from MRI scans, and how that data is processed and analyzed to understand the brain. This week, we'll continue the second half of our two-part episode on LONI.

Direct download: neuroscience-frontiers.mp3
Category:general -- posted at: 8:00am PDT

Last year, Kyle had a chance to visit the Laboratory of Neuroimaging, or LONI, at USC, and learn about how some researchers are using data science to study the function of the brain. We’re going to be covering some of their work in two episodes on Data Skeptic. In this first part of our two-part episode, we'll talk about the data collection and brain imaging and the LONI pipeline. We'll then continue our coverage in the second episode, where we'll talk more about how researchers can gain insights about the human brain and their current challenges. Next week, we’ll also talk more about what all that has to do with data science machine learning and artificial intelligence. Joining us in this week’s episode are members of the LONI lab, which include principal investigators, Dr. Arthur Toga and Dr. Meng Law, and researchers, Farshid Sepherband, PhD and Ryan Cabeen, PhD.

Direct download: neuroimaging-and-big-data.mp3
Category:data science -- posted at: 8:00am PDT

In artificial intelligence, the term 'agent' is used to mean an autonomous, thinking agent with the ability to interact with their environment. An agent could be a person or a piece of software. In either case, we can describe aspects of the agent in a standard framework.

Direct download: the-agent-model-of-intelligence.mp3
Category:general -- posted at: 8:00am PDT

This episode kicks off the next theme on Data Skeptic: artificial intelligence.  Kyle discusses what's to come for the show in 2018, why this topic is relevant, and how we intend to cover it.

Direct download: artificial-intelligence-a-podcast-approach.mp3
Category:general -- posted at: 8:00am PDT

We break format from our regular programming today and bring you an excerpt from Max Tegmark's book "Life 3.0".  The first chapter is a short story titled "The Tale of the Omega Team".  Audio excerpted courtesy of Penguin Random House Audio from LIFE 3.0 by Max Tegmark, narrated by Rob Shapiro.  You can find "Life 3.0" at your favorite bookstore and the audio edition via penguinrandomhouseaudio.com.

Kyle will be giving a talk at the Monterey County SkeptiCamp 2018.

Direct download: the-tale-of-the-omega-team.mp3
Category:general -- posted at: 8:00am PDT

This week, our host Kyle Polich is joined by guest Tim Henderson from Google to talk about the computational complexity foundations of modern cryptography and the complexity issues that underlie the field. A key question that arises during the discussion is whether we should trust the security of modern cryptography.

Direct download: complexity-and-cryptography.mp3
Category:data science -- posted at: 8:00am PDT

This episode features an interview with Rigel Smiroldo recorded at NIPS 2017 in Long Beach California.  We discuss data privacy, machine learning use cases, model deployment, and end-to-end machine learning.

Direct download: mercedes-benz-machine-learning-research.mp3
Category:general -- posted at: 11:07pm PDT

When computers became commodity hardware and storage became incredibly cheap, we entered the era of so-call "big" data. Most definitions of big data will include something about not being able to process all the data on a single machine. Distributed computing is required for such large datasets.

Getting an algorithm to run on data spread out over a variety of different machines introduced new challenges for designing large-scale systems. First, there are concerns about the best strategy for spreading that data over many machines in an orderly fashion. Resolving ambiguity or disagreements across sources is sometimes required.

This episode discusses how such algorithms related to the complexity class NC.

Direct download: parallel-algorithms.mp3
Category:general -- posted at: 8:00am PDT

In this week's episode, Scott Aaronson, a professor at the University of Texas at Austin, explains what a quantum computer is, various possible applications, the types of problems they are good at solving and much more. Kyle and Scott have a lively discussion about the capabilities and limits of quantum computers and computational complexity.

Direct download: quantum-computing.mp3
Category:general -- posted at: 8:00am PDT

I sat down with Ali Ghodsi, CEO and found of Databricks, and John Chirapurath, GM for Data Platform Marketing at Microsoft related to the recent announcement of Azure Databricks.

When I heard about the announcement, my first thoughts were two-fold.  First, the possibility of optimized integrations with existing Azure services.  This would be a big benefit to heavy Azure users who also want to use Spark.  Second, the benefits of active directory to control Databricks access for large enterprise.

Hear Ali and JG's thoughts and comments on what makes Azure Databricks a novel offering.

 

Direct download: azure-databricks.mp3
Category:general -- posted at: 8:00am PDT

In this episode we discuss the complexity class of EXP-Time which contains algorithms which require $O(2^{p(n)})$ time to run.  In other words, the worst case runtime is exponential in some polynomial of the input size.  Problems in this class are even more difficult than problems in NP since you can't even verify a solution in polynomial time.

We mostly discuss Generalized Chess as an intuitive example of a problem in EXP-Time.  Another well-known problem is determining if a given algorithm will halt in k steps.  That extra condition of restricting it to k steps makes this problem distinct from Turing's original definition of the halting problem which is known to be intractable.

Direct download: exp-time.mp3
Category:general -- posted at: 8:00am PDT

In this week's episode, host Kyle Polich interviews author Lance Fortnow about whether P will ever be equal to NP and solve all of life’s problems. Fortnow begins the discussion with the example question: Are there 100 people on Facebook who are all friends with each other? Even if you were an employee of Facebook and had access to all its data, answering this question naively would require checking more possibilities than any computer, now or in the future, could possibly do. The P/NP question asks whether there exists a more clever and faster algorithm that can answer this problem and others like it.

Direct download: p-vs-np.mp3
Category:data science -- posted at: 8:00am PDT

Algorithms with similar runtimes are said to be in the same complexity class. That runtime is measured in the how many steps an algorithm takes relative to the input size.

The class P contains all algorithms which run in polynomial time (basically, a nested for loop iterating over the input).  NP are algorithms which seem to require brute force.  Brute force search cannot be done in polynomial time, so it seems that problems in NP are more difficult than problems in P.  I say it "seems" this way because, while most people believe it to be true, it has not been proven.  This is the famous P vs. NP conjecture.  It will be discussed in more detail in a future episode.

Given a solution to a particular problem, if it can be verified/checked in polynomial time, that problem might be in NP.  If someone hands you a completed Sudoku puzzle, it's not difficult to see if they made any mistakes.  The effort of developing the solution to the Sudoku game seems to be intrinsically more difficult.  In fact, as far as anyone knows, in the general case of all possible examples of the game, it seems no strategy can do better on average than just random guessing.

This notion of random guessing the solution is where the N in NP comes from: Non-deterministic.  Imagine a machine with a random input already written in its memory.  Given enough such machines, one of them will have the right answer.  If they all ran in parallel, one of them could verify it's input in polynomial time.  This guess / provided input is often called a witness string.

NP is an important concept for many reasons.  To me, the most reason to know about NP is a practical one.  Depending on your goals or the goals of your employer, there are many challenging problems you may attempt to solve.  If a problem you are trying to solve happens to be in NP, then you should consider the implications very carefully.  Perhaps you'll be lucky and discover that your particular instance of the problem is easy.  Sudoku is pretty easy if only 2 remaining squares need to be filled in.  The traveling salesman problem is easy to solve if you live in a country where all roads for a ring with exactly one road in and out.

If the problem you wish to solve is not trivial, or if you will face many instances of the problem and expect some will not be trivial, then it's unlikely you'll be able to find the exact solution.  Sure, maybe you can grab a bunch of commodity servers and try to scale the heck out of your attempt.  Depending on the problem you're solving, that might just work.  If you can out-purchase your problem in computing power, then problems in NP will surrender to you.  But if your input size ever grows, it's unlikely you'll be able to keep up.

If your problem is intractable in this way, all is not lost.  You might be able to find an approximate solution to your problem.  Good enough is better than no solution at all, right?  Most of the time, probably.  However, some tremendous work has also been done studying topics like this.  Are there problems which are not even approximable in polynomial time?  What approximation techniques work best?  Alas, those answers lie elsewhere.

This episode avoids a discussion of a few key points in order to keep the material accessible.  If you find this interesting, you should next familiarize yourself with the notions of NP-Complete, NP-Hard, and co-NP.  These are topics we won't necessarily get to in future episodes.  Michael Sipser's Introduction to the Theory of Computation is a good resource.

 

Direct download: sudoku-in-np.mp3
Category:general -- posted at: 8:00am PDT

In this episode, Professor Michael Kearns from the University of Pennsylvania joins host Kyle Polich to talk about the computational complexity of machine learning, complexity in game theory, and algorithmic fairness. Michael's doctoral thesis gave an early broad overview of computational learning theory, in which he emphasizes the mathematical study of efficient learning algorithms by machines or computational systems.

When we look at machine learning algorithms they are almost like meta-algorithms in some sense. For example, given a machine learning algorithm, it will look at some data and build some model, and it’s going to behave presumably very differently under different inputs. But does that mean we need new analytical tools? Or is a machine learning algorithm just the same thing as any deterministic algorithm, but just a little bit more tricky to figure out anything complexity-wise? In other words, is there some overlap between the good old-fashioned analysis of algorithms with the analysis of machine learning algorithms from a complexity viewpoint? And what is the difference between strategies for determining the complexity bounds on samples versus algorithms?

A big area of machine learning (and in the analysis of learning algorithms in general) Michael and Kyle discuss is the topic known as complexity regularization. Complexity regularization asks: How should one measure the goodness of fit and the complexity of a given model? And how should one balance those two, and how can one execute that in a scalable, efficient way algorithmically? From this, Michael and Kyle discuss the broader picture of why one should care whether a learning algorithm is efficiently learnable if it's learnable in polynomial time.

Another interesting topic of discussion is the difference between sample complexity and computational complexity. An active area of research is how one should regularize their models so that they're balancing the complexity with the goodness of fit to fit their large training sample size.

As mentioned, a good resource for getting started with correlated equilibria is: https://www.cs.cornell.edu/courses/cs684/2004sp/feb20.pdf

Thanks to our sponsors:

Mendoza College of Business - Get your Masters of Science in Business Analytics from Notre Dame.

brilliant.org - A fun, affordable, online learning tool.  Check out their Computer Science Algorithms course.

Direct download: the-computational-complexity-of-machine-learning.mp3
Category:general -- posted at: 8:00am PDT

TMs are a model of computation at the heart of algorithmic analysis.  A Turing Machine has two components.  An infinitely long piece of tape (memory) with re-writable squares and a read/write head which is programmed to change it's state as it processes the input.  This exceptionally simple mechanical computer can compute anything that is intuitively computable, thus says the Church-Turing Thesis.

Attempts to make a "better" Turing Machine by adding things like additional tapes can make the programs easier to describe, but it can't make the "better" machine more capable.  It won't be able to solve any problems the basic Turing Machine can, even if it perhaps solves them faster.

An important concept we didn't get to in this episode is that of a Universal Turing Machine.  Without the prefix, a TM is a particular algorithm.  A Universal TM is a machine that takes, as input, a description of a TM and an input to that machine, and subsequently, simulates the inputted machine running on the given input.

Turing Machines are a central idea in computer science.  They are central to algorithmic analysis and the theory of computation.

Direct download: turing-machines.mp3
Category:general -- posted at: 8:00am PDT

Over the past several years, we have seen many success stories in machine learning brought about by deep learning techniques. While the practical success of deep learning has been phenomenal, the formal guarantees have been lacking. Our current theoretical understanding of the many techniques that are central to the current ongoing big-data revolution is far from being sufficient for rigorous analysis, at best. In this episode of Data Skeptic, our host Kyle Polich welcomes guest John Wilmes, a mathematics post-doctoral researcher at Georgia Tech, to discuss the efficiency of neural network learning through complexity theory.

Direct download: the-complexity-of-learning-neural-networks.mp3
Category:data science -- posted at: 8:00am PDT

How long an algorithm takes to run depends on many factors including implementation details and hardware.  However, the formal analysis of algorithms focuses on how they will perform in the worst case as the input size grows.  We refer to an algorithm's runtime as it's "O" which is a function of its input size "n".  For example, O(n) represents a linear algorithm - one that takes roughly twice as long to run if you double the input size.  In this episode, we discuss a few everyday examples of algorithmic analysis including sorting, search a shuffled deck of cards, and verifying if a grocery list was successfully completed.

Thanks to our sponsor Brilliant.org, who right now is featuring a related problem as their Brilliant Problem of the Week.

Direct download: big-oh-analysis.mp3
Category:general -- posted at: 8:00am PDT