Despite tremendous advances in computational models of human analogy, a persistent challenge has been scaling up to find useful analogies in large, messy, real-world data. The availability of large idea repositories (e.g., the U.S. patent database) could significantly accelerate innovation and discovery in a way never previously possible. Previous approaches have been limited by relying on hand-created databases that have high relational structure but are very sparse (e.g., predicate calculus representations). Traditional machine-learning/information-retrieval similarity metrics (e.g., LSA) can scale to large, natural-language datasets; however, while these methods are good at detecting surface similarity, they struggle to account for structural similarity. In this paper, we propose to leverage crowdsourcing techniques to construct a dataset with rich “analogy-tuning” signals, used to guide machine learning models towards matches based on relations rather than surface features. We demonstrate our approach with a crowdsourced analogy identification task, whose results are used to train deep learning algorithms. Our initial results suggest that a deep learning model trained on positive/negative example analogies from the task can find more analogous matches than an LSA baseline, and that incorporating behavioral signals (such as queries used to retrieve an analogy) can further boost its performance.
Invention by analogy (i.e., transferring ideas from other domains that are
structurally similar to a target problem) is a powerful way to create new innovations.
For example, a car mechanic invented a new low-cost way to ease difficult
childbirth by drawing an analogy to a cork extraction method in wineries (inserting
and inflating a small plastic bag in the bottle) [
The recent growth of online innovation repositories represents an unparalleled opportunity for invention by analogy. These repositories contain hundreds of thousands (Quirky, OpenIDEO) or millions (the U.S. patent database, the Web) of ideas that have the potential to be applied to other structurally similar domains. However, the scale of these repositories presents a challenge to a person’s ability to find useful analogies.
Computational systems could greatly accelerate innovation by mining
analogies from these vast repositories. Indeed, decades of research on computational
models of human analogy-making have yielded tremendous advances in the
ability of computational systems to explain and simulate human-like analogical
reasoning. Yet, a persistent challenge has been scaling up computational
analogy systems to reliably find useful analogies in large, messy,
realworld data. Existing approaches are limited by either relying on hand-created
databases that have high relational structure but are small, domain-specific, and
costly to keep updated [
In this paper, we propose a hybrid approach which combines crowdsourcing with machine learning to develop a scalable approach to finding analogies in large idea repositories. A key insight is that we aim to externalize and capture the mental processes that humans use to find and evaluate analogies to serve as training data for a machine learning model. The intuition is that instead of trying to build a complete human-generated dataset or a machine learning model driven only from existing data, the rich behavioral traces of how people query for analogies can “tune” a more scalable computational approach towards matches based on relations rather than surface features.
We illustrate our approach through a crowdsourced analogy identification task where people query a repository and find analogical matches to a target. These matches and queries are used as training data (and for feature selection) for deep learning algorithms. Our initial results suggest that a deep learning model trained on positive/negative example analogies from the task can find more analogous matches than an LSA baseline, and that incorporating behavioral signals (such as queries entered) can further boost its performance. 2
Related Work
Computational Analogy Systems. We argue that a crucial reason behind
the difficulty in scaling up computational analogy lies in a trade-off between
accuracy and scale in existing approaches. On the one hand, models that have
been the most successful at approaching human-level performance in analogical
matching—such as Hummel and Holyoak’s LISA analogy engine [
Conversely, a number of machine learning approaches exist that make
minimal assumptions about the input data, and in particular do not require explicitly
coded relational representations. Examples include word embedding models like
Word2Vec [
Note that some approaches [
Computational Analogy at Scale with Crowdsourcing
and Machine Learning
We frame the problem of finding analogies in a large dataset as a hybrid human
and machine-learning problem. We propose to use crowdsourcing to obtain rich
“analogy-tuning” signals for machine learning models by capturing the process
by which people query for and evaluate analogies. By doing so we aim to collect
not just positive/negative examples of analogies, but also implicit and explicit
behavioral traces ranging from the queries people use to look for analogies to the
keywords they believe are discriminative. We believe these behavioral traces are
vital for bridging the gap between scalable machine learning approaches and the
structured representations of prior approaches. This machine-learning approach
is related to other efforts in case-based-reasoning that use machine-learning to
reduce the need for knowledge engineering [
The goal of the crowdsourcing component is to obtain rich behavioral data (e.g.,
positive/negative examples of analogies, query sequences, keywords) that signal
the core relational structures of documents. Guided by the psychological insight
that comparison is a powerful way to get people to attend to the core structural
features of a description [
Workers use a simple search interface to find product descriptions that are analogous to a seed product. Figure 1 depicts the interface and the four main components of the task: 1) searching for matches (A), 2) screening/processing matches (B), 3) describing the analogy (C), and 4) highlighting keywords (E).
This approach yields a rich set of signals that we can use for our machine learning models. For example: – What queries are used, in what sequence? – Which documents are tagged as possible matches? – Which documents are tagged as best matches? – Which documents are implicitly rejected (i.e., ignored in the search result list, despite appearing before matches)? – Which documents are directly rejected? – How is the best match described as being analogous to the seed document? – Which key terms are highlighted? Importantly, this task context enables us to harvest all these rich signals from a natural search task that is easy and familiar. Additionally, the task design could guide the instrumentation of an interface in a user-facing computational analogy system to yield similar signals for ongoing refinement of the underlying models. Deployment. We test our approach with a corpus of product descriptions from Quirky.com, an online crowdsourced product innovation website. Quirky is representative of the kinds of datasets we are interested in, because it is large (at the time of writing, it hosts upwards of 10,000 product ideas), unstructured (ideas are described in natural language), and covers a variety of domains (invention categories), which makes cross-domain analogies possible. The following example is representative of the length and “messiness” of product ideas in this dataset:
Proximity wristband: Control of childs in public places is very difficult and stressing. Parents fear that their childs may go too far unexpectedly for any reason, and that actually happens no matter how careful they are, especially in crowdy places. Because childs always run and move. Parents can’t relax and are obliged to keep their eyes continuously on their childs. Furthermore, the consequences of a child going too far from his parents may be very dangerous. A wristband is put on the wrist of the child. The wristband has a radio connection (bluetooth) with one of the parents’ smartphone, that has been previously matched with the wristband. Parents may activate/disactivate the alarm on the wristband by tapping on the App installed on their smartphone. When the alarm is activated, the App detects the distance between the 2 radio connected devices (the wristband and the smartphone). If the distance gets higher than the maximum value (changeable in the settings of the App) than a speaker integrated in the bracelet emits a loud alarm and the smartphone starts ringing. The inside of the wristband hosts a circular conductive element that loses its metallic continuity if the wristband opens for any reason, so if this circuit is opened the wristband is programmed to emit the alarm and alert the parents.
We crowdsourced analogy finding within a set of 400 randomly sampled Quirky products. Three hundred and ninety-four workers from Amazon Mechanical Turk collected analogies for 227 “seed” documents (median of 1 unique analogy per seed, range of 1-10 unique analogies). Median completion time for each seed was 10 minutes, and pay was $6/hr (or $1 per completed seed). Workers could complete as many seeds as they wanted.
An example behavioral trace sequence from our data illustrates how the act of comparison pushes people to focus on structure (along with the rich data we can mine from the behavioral traces). Worker X received the “proximity wristband” as a seed. She initially started with the query “alarm”, and tagged as a possible match a “voltage plug” product that automatically alerts the user if there are voltage problems for a given power outlet. She also rejected nonanalogous results like a “smart doorbell chime”. Dissatisfied with the results, she entered a new query (“wristband”), but didn’t find any useful matches. Finally, she entered “proximity” as a query, and tagged a product about a “digital dog fence” as a best match, explaining that both products are about “Proximity, keeping object within a set distance, the object has it attached.” 3.2
An important challenge of working with natural language is finding appropriate
semantic similarities. Many existing similarity metrics, like Word2vec [
We now use behavioral traces to expose similarity. We constructed a graph from queries entered in our study: Nodes correspond to queries; there is an edge if the queries resulted in the same analogy. In other words, if one user found an analogy using the query “cover”, and another used “protect”, we add an edge.
Figure 2 shows fragments from this graph. By construction, the query graph exposes a lot of the desired semantic similarity. Semantically similar verbs often form dense clusters (e.g., protect/defend/shield), and related terms (gps/location/find) also tend to be a short distance away. Traversing the query graph can also reveal analogies: for example, an analogy between a dog gps and a child tracking device (left), and between products that protect from rain, water, and sun (right). This graph could be used to guide feature selection in a machine learning model. 3.3
We now demonstrate how to frame analogy-finding as a machine learning problem. In this context, we are given a training set D = {(xi1, xi2, yi)}. (xi1, xi ) 2 are pairs of product descriptions. Label yi 2 { 0, 1} corresponds to whether the pair was tagged as an analogy (“best match”) or as a non-analogy (ignored in search result, directly rejected). Our goal is learn a decision function for new pairs whose score reflects their “degree of analogy": f (✓, ( ✓ (xi1), ✓ (xi2))), where ✓ (·) is function embedding xi into a shared feature space and ✓ are model parameters.
The document model we use to demonstrate our ideas is based on
convolutional neural network (CNN) architecture that has shown state-of-the-art results
in many NLP tasks [
We use a Siamese Network architecture [
To learn non-linear patterns, convolutional layers are followed by eleChild wristband with built-in Bluetooth mentwise activation functions. We Fig. 3. Siamese Network architecture. use the ReLU function, max(0, x). Words are embedded into a low-dimension The output of the activation funcrepresentation and combined into a matrix tion is passed through a pooling (left). Convolutional “sliding window fil- layer, which reduces dimensionality ters” (blue) are applied to the matrix. Mul- by aggregating information, capturtiple filters are applied (different colors), ing pertinent patterns and filtering forming a feature map pooled to form an ag- noise. The pooling layer performs gregated signal. The pooled representation max-pooling, returning the largest goes through a fully connected layer. The value for each column. Finally, values same weights are applied for both inputs pass through a fully connected layer iancproustss aisllcloamyeprus.teFdin(Calolyn,trdaissttiavneceLobsest)w.een which computes a linear transformation followed by ReLU non-linearity, combining local features into a global semantic view of the text.
This composition of functions, from embedding words to the final layer, yields our function ✓ (·), mapping a text input xi into a new vector representation. Crucially, in our model ✓ (·) is shared for (xi1, xi2), enabling the model to learn a symmetric representation that is invariant to the order in which the texts are provided. Finally, our objective function is the Contrastive Loss, defined as: L( ✓ (xi1), ✓ (xi2)) = yiL+( ✓ (xi1), ✓ (xi2)) + (1 yi)L ( ✓ (xi1), ✓ (xi2)), where
L+( ✓ (xi1), ✓ (xi2)) = || ✓ (xi1) ✓ (xi2))||22 L ( ✓ (xi1), ✓ (xi2)) = max(0, m || ✓ (xi1) ✓ (xi2))||22.
L+ penalizes positive pairs far apart, and L penalizes negative pairs (direct/implicit rejected pairs, from the crowd) closer than margin m. Learning is done with gradient descent, via backpropagation.
Results. We applied the model to the crowd-annotated Quirky data. We split our data into training and evaluation sets, each containing distinct sets of “seed" texts (to test the model’s ability to generalize). The training set consists of about 12500 pairs. Positive labels were assigned directly by crowd workers, while negative labels mean the pairs were implicitly rejected by not being tagged despite being viewed by a worker. Our evaluation set comprised of roughly 3000 pairs.
The data was imbalanced, with about 10 negatives for each positive (⇡ 1, 100 positive pairs). To counter the imbalance, we use a weighted loss function. For the LSA baseline, we compute the Singular Value Decomposition (SVD) on the document-term matrix, with term weights given by the TF-IDF score. Cosine similarity is then computed for each pair. The table below shows proportion of analogies among pairs with highest predicted scores (precision@K). For example, looking at the top 2% predictions of our model (2% evaluation-set instances with lowest predicted distance; about 60 pairs), 64% were tagged as positive (vs. 46% for LSA). The overall proportion of positive labels in the test set was only 11%. Importantly, negative labels are derived implicitly, so many pairs with negative annotations could possibly be “mislabeled” and are actually positive.
Method Top 2% Top 5% Top 10% Top 15% Top 25%
Siamese Net 0.64 0.54 0.39 0.32 0.28 Latent Semantic Analysis 0.46 0.40 0.34 0.29 0.25 In Table 1 we show examples of seed documents and their best predicted matches. Our model recovers both “purpose ” matches (e.g., gloves that hold nails, and a hammer handle to store tools) as well as “mechanism” (child / dog tracking devices). Comparing our model to LSA-based similarity, one can qualitatively observe that overall, LSA seems to focus more on surface similarity. For example, when starting from a wristband that monitors child proximity, LSA returns a baby recliner with sensors, a lawnmower connected to a wristband, and skateboard shoes; our model returns a pet tracker, a wallet finder and vehicle finder. Our model seems to “err" and return smart window blinds that detect when homeowners are away – possibly recognizing the semantic “analogy” between a child or pet wandering off and a homeowner being away. 3.4
We now extend our machine learning setting, adding the query as additional input. Our training data is now D = {(xi1, xi2, qi, yi)}, where qi is the user-entered query. We apply the same representation ✓ (·) we use for x1, xi2 to qi, embedding i the query into a shared feature space. We seek to measure similarity between seed and target in this space. Importantly, similarity should be relative in some sense to the user’s query. We do so by using the projection of the query vector onto the seed and target vectors – essentially “aligning" the query “concept" with each product text. We then compute the contrastive loss as before. More formally, we re-define the contrastive loss to incorporate the query as follows.
L+( ✓ (xi1), ✓ (xi2), ✓ (qi)) = || ✓✓ ((xqi1i))·· ✓✓ ((xxi1i1)) ✓ (xi1) ✓✓ ((xqi2i))·· ✓✓ ((xxi2i2)) ✓ (xi2)||22 and similarly for L . In the table below we report results for this new model and compare it to the model without the query. Since many queries did not have matching targets we filter the data to a smaller subset with full information (6000 less rows). The smaller training set drops base model accuracy to .46 (from .64). Interestingly, the query information has an apparent positive effect, compensating for lack of data and boosting accuracy from .46 to .54. These preliminary results validate our intuition that machine learning models would benefit from a variety of human-generated analogy-relevant signals.
Proximity wrist- A dog and cat collar that has Baby recliner - placing sensors on a band for children built-in GPS tracking. // A wal- baby being walked by parent, learn with a bluetooth let phone case that can be located movement and incorporate into reclinconnection to with a key-chain remote control. ing chair. // Clamp on a lawnmower parents’ smart- // Programmable smart window safety bar with a pin connected to a phone. App blinds that can also detect when wristband. When user is too far pin detects the dis- you are away. // A vehicle finder is pulled out and the clamp opens. tance, emits an with a small portable electronic // Magnetic skateboard shoes with RF alarm if child is device transmitting a signal from controller for turning on and off. Could too far. parked car to smartphone. be fabricated into a ring or wristband. Window louvers Programmable window blinds. // A window-mounted fan with sound that stop rain A window-mounted fan with sound dampening louvers. // A glare-stopper by funneling the dampening louvers. // Lamps that device preventing energy-efficient winrain out. work off batteries for additional dows from melting sides of buildings lighting without depending on or vehicles // A car screen to help reelectricity duce excessive heat buildup when parking outside.
A flat magnet A golf glove with a magnetic strip A glove with adhesive contours allowsewn into the around the wrist. // A hammer ing the user to pick up hair and lint in posterior hand of with a handle that stores nails hard-to-reach places. // A can opener a glove to hold and hex screwdrivers. // Tear- container device, with a magnet on nails or screws. proof gloves to work easily with both ends to hold the can in place. // tools. A box that clamps onto a ladder and holds screws, nails and small items.
Model with query Model without query Overall, we believe this is a promising time to make traction on the problem of finding analogies in complex, messy data. There is a confluence of new work on crowdsourcing complex cognition, machine learning tools for unsupervised learning of semantics, and hybrid approaches combining crowds and machine judgments to get the best of both worlds. We believe there is promise in an approach that positions the process of crowdsourced analogical knowledge base creation as input to machine learning models, using explicit and implicit signals to augment the written text. In this paper we describe a prototype of this approach and early results describing its potential value.
We note that the approach described here does not tackle a number of important problems that we acknowledge as limitations. For example, we do not yet deal with the rich relational structure inherent in the source and target analogs. We also note that our intent is to find interesting and useful analogs in large data repositories, and as such we make no claims that the processes we describe match up with those that human cognition engages in during analogical retrieval and reasoning. However, our capture of the process by which people engage in while searching for analogies, including the queries and keywords they use and their perceived relevance judgments of their resulting matches, may prove valuable for further psychological research on the process of analogical retrieval.