In our previous article, we touched on the Travelling Salesman problem and highlighted how it belongs to the subfield of combinatorial optimisation. The topic of combinatorial optimisation seeks to discover the most efficient object from a finite set of items.  The three main combinatorial optimisation problems are Travelling Salesman Problem (TSP), Knapsack problem and Minimum Spanning Tree (MST). Our focus will be on the Knapsack problem in this article. A subsequent piece will touch on MST. 

Diving  into the Knapsack Problem

Let’s now assume a deeper look into the logic of the Knapsack Problem. The decision version of the Knapsack problem is considered NP-Complete. Firstly, we will briefly examine the problem statement. Providing a set of objects with attributable value and weights (Vi, Wi), what is the maximum value that can be attained when the sum of the subsets of these objects are selected to be within the knapsack capacity.

The comparing of entities is usually important in human decision making. 

We are constantly comparing entities daily from holiday destinations, new mobile phone and next family car. Comparing entities look at the relatedness of these objects or concepts. Relatedness does not look at only similarity (analogy) but other relational structures such as resistance (antithesis), discrepancy (anomaly) and incompatibility (antinomy). 

Comparative entity mining is crucial to any keyword, concept, content, product and marketing strategy. This is because no product exists in isolation. It is therefore important for businesses to place themselves in the shoes of potential customers and explore the alternative products that are vying for the same attention and mind space. Conducting this exercise will help brands position their products in a more compellingly through  through engaging branding and compelling storytelling. 

The field of biomedical informatics have employed comparative entity mining between genes and proteins. These comparisons have now extended to diseases. The comparisons in the biomedical field looks at functional similarities more than sequential similarities. This has inspired me to classify comparative entity mining to three stages: structural, functional and sequential. 

This blog will focus on the structural stage of comparing entities. We will be comparing bananas to plantains. When looking at an entity or a concept from the structural level we focus more on the size, colour, shape and physical properties. The internal properties that make up the product. 

Computer applications such as search engines and dialogue systems usually process a large volume of text on a regular basis. These systems have progressed over the years due to advanced word embeddings, progressive research and modern machine learning libraries.  It is believed that audio and visual datasets have dense high-dimensional datasets encoded as vectors of a separate raw pixel. Text generated from natural language is usually understood to contain vectors that are sparse when compared to video and visuals.  

Vector space models (VSM) embed or represent words in a continuous vector space. In this respect, words that are semantically similar are plotted to nearby points.  As representing words as unique and distinct ids can usually lead to a sparsity of data. Going this route will require a large amount of data to be collected to effectively train statistical models. This is why vector representation of words is useful to address the problem of sparsity and enhance semantic interpretation.  I ran a search for romantic dinner on Google and one of the people also ask questions was ‘Where can I eat for anniversary?’ We can clearly see the semantic similarity of the term ‘romantic’ and ‘anniversary’ used within the context of food or dining. You would normally expect a distance between the vector representation of these words but from a contextual perspective, an anniversary is usually expected to be romantic as it will involve couples celebrating a milestone in their relationship or marriage.