2
$\begingroup$

I took a tangent from a student project I had done a number of years ago and spent some time studying distance functions.

(please note that the above link contains the full question with links as I don't have sufficient reputation to post more than two links)

I found this textbook on data mining which includes a chapter on Similarity and Distances (chapter 3 of Data Mining The Textbook by Charu C. Aggarwal)

And so the text says:

Sometimes, data analysts use the Euclidean function as a “black box” without much thought about the overall impact of such a choice. It is not uncommon for an inexperienced analyst to invest significant effort in the algorithmic design of a data mining problem, while treating the distance function subroutine as an afterthought. This is a mistake.

And so there are a number of sections addressing quantitative data, categorical, text, etc.

I'd be curious about how distance functions are used in similar and different ways across varied fields such as data mining, machine learning, computer vision, natural language processing, error-correcting codes, or for example in specific applications like spell checkers.

On the one hand, in my independent study, I saw various passages speaking about the necessity of applying domain knowledge.

From 3.6 Supervised Similarity Functions of the above mentioned book:

In practice, the relevance of a feature or the choice of distance function heavily depends on the domain at hand.

Also in An Introduction to Statistical Learning with Applications in R they mention:

The choice of dissimilarity measure is very important, as it has a strong effect on the resulting dendrogram. In general, careful attention should be paid to the type of data being clustered and the scientific question at hand. These considerations should determine what type of dissimilarity measure is used for hierarchical clustering

Section 10.3.3 Practical Issues in Clustering also talks about some related issues.

On the other hand I took a brief look at this Ph.D. thesis by Ofir Pele on distance functions, and so at the beginning it says:

Our proposed methods have been successfully used both by computer vision researchers and by researchers in other fields. The success of the methods in other fields is probably because the noise characteristics in those fields are similar to image noise characteristics.

which suggested to me that there could be some overlap in different cases; however, I haven't read those papers in detail.

Anyway, the question is: what are similarities and differences in how distance functions are used among disparate fields, and in what ways do those similarities and differences arise.

Few Thoughts on this Question

I thought to myself this may be a bit of an unusual question. After all people don't generally study looping in Java, Python, Lisp and Prolog and then go on to study variable declaration in five other programming languages. People more often study one particular programming language as a whole not a certain construct in multiple ones. But on the other hand within programming languages as an academic discipline at universities people might certainly talk about similarities and dissimilarities. Those very similarities and differences could be seen in light of differences as to whether the code is (usually) interpreted or compiled, or whether it tends to favor an imperative style or a recursive one. One might also seek to see how various characteristics developed within the evolution of programming languages throughout history and how different programming languages built on earlier ones. Certain design decisions could very well derive from certain goals: ease of learning, readability, speed, verifiability.

Similarly in human languages people don't usually study a set of words or phrases in multiple human languages but usually study one particular human language as a whole. Yet linguists might certainly study similarities and differences in particular words or phrases across languages as that can be indicative of how various human languages evolved and could also be indicative of various aspects of culture. I could also mention that browsing through Encyclopedia of Distances I read about how linguists have sought to create ways to measure distances between languages.

Also, as a practical application of such a cross-sectional approach within human languages, one might think of the airline and travel industry where employees learn how to say particular words and phrases in multiple languages so that it is possible to communicate with the passengers.

So anyway I think such comparisons could be interesting.

I could mention that I don't think it's necessary to have a huge number of examples. I think a few would be fine with some brief explanation. I think perhaps more interesting than a lot of breadth would be how constraints, goals, or the problem domain lead to different approaches. I'm not an expert at all in any of those fields, so I may not be familiar with some of the terms. For people who find this page later on and are trying to find more details there can be a few resources listed such as books, websites, or search strategies.

I've thought about how I might answer this question based on my independent study and what I looked into, so I could seek to work on my response tonight and probably tomorrow. As long as the question meets the site guidelines perhaps there could be then at least one response. Other responses though might be more comprehensive, more incisive and trenchant, or better educationally. So a better response would be more deserving of the credit from the asker and also reputation points.

I was thinking of waiting a week or two before awarding an answer; however, if a response is made beforehand which I think is good I could just decide to award it to that one.

There also might be a response before I post mine, and so if that one is good and I haven't finished mine I might not post mine at all.

Hope this meets the site guidelines, but if not let me know.

$\endgroup$
  • 1
    $\begingroup$ This seems to be more of an invitation for discussion, less so a question. This platform does not work to well for open-ended discussions or surveys. Can you formulate a clear, reasonably scoped question? (Also, the title doesn't represent your post well.) $\endgroup$ – Raphael Aug 22 '17 at 12:14
  • $\begingroup$ I do not know what is exactly your question. The distance should reflect the data dependencies - this covers the topic as I understand it. Finding it may be non-trivial task. Euclidean distance is easy to implement and easy to understand, but fails in high-dimensions, also there is no single distance that covers all cases. Take Mangattan or spherical distance, when these are proper the Euclidean simply fails. The quote you gave is absolutely true and trivial to show why. There is overlap, many problems from different fields encounter noise, and define the same thing using various wording. $\endgroup$ – Evil Aug 22 '17 at 21:17
0
$\begingroup$

Okay, so here are some of my thoughts along with some links to some of the things that I found interesting in my independent study.

(please note that a version with additional links is available on GitHub)

In multiple books I found sections speaking about clustering. In particular within these three books:

  • Introduction to Artificial Intelligence by Mariusz Flasiński
  • An Introduction to Statistical Learning with Applications in R by Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani
  • Data Mining: The Textbook by Charu C. Aggarwal

there are sections speaking about hierarchical clustering.

For hierarchical clustering one can use an arbitrary dissimilarity measure and so they talk about that choice.

It's not as though one dissimilarity measure predominates in artificial intelligence, another in statistical or machine learning, and then a third in data mining, but the dissimilarity measure is determined by the data, and what the data means in the context of the situation.

In the statistical learning book an example is given in the section on hierarchical clustering of how an online retailer might prefer a correlation based dissimilarity measure to the Euclidean distance. Clustering together shoppers who purchase less from shoppers who purchase more may not be as desirable as clustering together shoppers who purchase similar items.

In the data mining textbook an example is given of how the cosine measure can be used as a comparison between texts. That section speaks about how with a bag-of-words representation document length would be prominent. That wouldn't necessarily be desirable as similar documents on the same or similar subjects but with different lengths wouldn't get grouped together.

In any event, as stated above, the dissimilarity measure is not determined by the field and nor is it being determined by the domain (say medical, legal, business, etc.), but is being driven by the nature of the data and what that data means.

In the case of hierarchical clustering then, if the algorithm is the same and the dissimilarity measures are being driven by the data (so they could certainly by the same across the three fields), then for that case these three fields are using distance functions in similar ways.

To go out on a tangent, this raises a question in my mind concerning what are the distinctions between these three fields (and perhaps other fields).

I thought it was interesting to read in the lead of the Wikipedia article on data mining that the title of a book was changed from Practical machine learning to Data mining: Practical machine learning tools and techniques with Java and the reason given was that it was largely for marketing purposes.

And so the Wikipedia articles on machine learning and data mining both say that those terms are buzzwords. The end of the lead for the article on machine learning speaks about how projects may fail to work because the problems can be difficult.

On that note I found it interesting in my independent study to read in the Wikipedia article on the history of artificial intelligence how the initial optimism and few strings attached funding was then met with disappointment in the mid to late 1970's. So the article speaks about various failures (machine translation) and also successes (the DART battle management system).

In terms of distinctions between the three fields the Wikipedia article on machine learning states:

Machine learning is sometimes conflated with data mining, where the latter subfield focuses more on exploratory data analysis and is known as unsupervised learning

Yet on the other hand in Data Mining: The Textbook the preface speaks of classification as being one of the four main super problems of data mining where it seems to me that classification as defined in chapter 10 of the book is basically supervised learning.

In any event it suggests in my mind that the distinctions between these three fields might be a bit fuzzy, and the example above indicates that naming decisions could be driven by a variety of factors including marketing.

Based on my independent study, to my ear, artificial intelligence being the first term coined, carries with it a connotation of a more theoretical field while machine learning and data mining are more focused on developing practical solutions.

In the text on artificial intelligence chapter 17 includes a section called Determinants of AI Development where artificial intelligence is seen as drawing from such fields as: computer science, biology, neuroscience, physics, mathematics, logics, philosophy, linguistics, and psychology.

There's a discussion of Searle's Chinese room, strong AI and weak AI, and a chapter on theories of intelligence in philosophy and psychology. There's a brief section on artificial intelligence as it pertains to social intelligence, emotional intelligence, and creativity.

In Russell and Norvig's book Artificial Intelligence: A Modern Approach there is a chapter on philosophical foundations.

In comparison within Data Mining: The Textbook privacy is addressed but essentially as a technical problem.

In Elements of Statistical Learning (from which the above mentioned statistical learning book is based) the chapters look to be all of a technical nature.

So I think this sentence from History and relationships to other fields section of the machine learning article is consistent with that assessment:

The field changed its goal from achieving artificial intelligence to tackling solvable problems of a practical nature.

Thinking back to the article on the history of artificial intelligence one might wonder about how various funders of different kinds (government, corporate, philanthropic, etc.) began to see AI as a longer term prospect while machine learning and data mining were more likely to produce working results more quickly.

I was curious about books in these three fields that were written from the perspective of a particular domain (medical, business, legal, etc.). So I did Google searches of the form: textbook <field> <domain> for field being either artificial intelligence, machine learning, or data mining, and domain being either medical, business, or legal. So a variety of different books have been written from the standpoint of a particular domain.

Data miners might be able to apply domain knowledge in the course of exploratory analysis, or in other kinds of analysis.


So back to distance functions.

I see a difference in the way distance functions are used in hierarchical clustering within the fields artificial intelligence, machine learning, data mining and applications discussed in Ofir Pele's thesis within computer vision (which could be seen as a subfield of machine learning). Simply put various applications of the distance functions developed do not involve clustering. This is true for the multiple view geometry application mentioned at the beginning of the abstract for the thesis.

In error-correcting codes the simple concept of Hamming distance is used; however in this case it seems to me that unlike the hierarchical clustering case no distance function choice is going on. Hamming distance arises from the mathematical model which in turn is from the physics of information transmission over noisy channels.

In the case of a spell checker a simple implementation could just list words that are say 1 or 2 hops away under the edit distance; however, a more sophisticated approach can work better.

Spell checkers can take into account properties of language, keyboards, common errors, etc.

At another level of sophistication one could have spell checkers that seek to automatically learn characteristics of users so as to improve suggestions and other aspects of performance.

In the case of a spell checker it doesn't seem to me that a distance function is necessarily warranted or helpful.

If a mathematical concept doesn't seem useful for an application then one doesn't have to use it.


I also wrote a summary of my independent study including listings of some of the various sources I went through:

Summary of Independent Study (link removed, see top of response)

There is also an extended response which is available here:

Extended response to distance function question on CS StackExchange (link removed, see top of response)

The length of the extended response ended up growing to a size of about 14 regular pages, so I can summarize what it is about:

In the extended response I continue the tangent in the middle which starts by comparing the fields of artificial intelligence, machine learning, and data mining. I speak about the question of whether research has shifted from universities to companies, the factor of motivation in education, economic systems and other systems for the organization of labor, social hierarchy, economic inequality, and climate change.

To a certain extent I wonder if I did not entirely follow my own advice in terms of more breadth rather than depth; however, perhaps that's partly just the nature of the Internet.

I didn't do any portions of this for a class, but worked on it over the past few days. I brought in things that I had seen or read over the years.

I think that a lot of various other people have probably had similar thoughts and questions.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.