DESIGN NOVELTY EVALUATION THROUGH ORDINAL EMBEDDING: COMPARISON OF NOVELTY AND TRIPLET ERRORS

Abstract

A practical and well-studied method for computing the novelty of a design is to construct an embedding via a collection of pairwise comparisons between items (called triplets), and use distances within that embedding to compute which designs are farthest from the center. These triplet comparisons are posed in the form of "Is Design A closer to Design B or Design C?'', and inform the placement of designs in the similarity-space embedding. This method of creating an embedding from non-metric relationship comparisons is known as ordinal embedding. Unfortunately, ordinal embedding methods can require a large number of triplets before their primary error measure--the proportion of violated triplet comparisons--converges. But if our goal is accurate novelty estimation, is it really necessary to fully minimize all triplet violations? Can we extract useful information regarding the novelty of all or some items using fewer triplets than existing convergence rates on the saturation of triplet violations might imply? This thesis addresses this question by studying the relationship between triplet violation error and novelty score error when using ordinal embeddings.

We find that estimating the novelty of a set of items via ordinal embedding can require significantly fewer human-provided triplets than is needed to converge the triplet error, and that this effect is modulated by the type of triplet sampling method (random versus uncertainty-informed active sampling). Having learned this, we propose the use of a custom metric we call the 'Expected Model Change' (EMC) which we use to observe when novelty information in the embedding has stopped updating under newly labeled triplets, so that conservative bounding functions need not be used. Moreover, to avoid the dangers of low accuracy in selecting the dimension of the ordinal embedding, we propose use of the Expected Model Change for tuning the embedding dimension to an appropriate value. In this framework, we explore the convergence properties of ordinal embeddings reconstructed from triplets taken from a variety of synthetic and real-world design spaces.