III: Small: Collaborative Research: Explaining Unsupervised Learning: Combinatorial Optimization Formulations, Methods and Applications

聚类是一种常见的机器学习和数据挖掘技术，它获取实例/记录/事物的集合，并将它们划分为组。它被广泛应用于各种领域，包括社交网络(寻找社区)、生物学(创建分类法)和神经科学(寻找大脑中感兴趣的区域)。已有许多聚类算法，但这些算法并不总是解释聚类。该奖项解决了向包括数据科学家、领域科学家和普通公众在内的各种利益相关者描述集群算法结果的问题。解释这些算法的结果将使利益攸关方更好地理解它们，并使它们能够在需要透明度的具有挑战性和敏感性的领域使用。使用易于理解的辅助信息(如标签)以主动形式给出解释。这个项目将由三项相互交织的任务组成。第一个将开发易于理解的机制来解释集群，而第二个将允许人类通过询问有关解释的问题来与解释互动。最后，第三个任务将对任务一生成的解释进行稳定性、可信度和正确性的衡量。由于不需要标记数据，因此无监督学习领域非常流行，并且存在许多算法，可以处理各种数据类型：图像、图形、文档、空间和时间数据。许多域都有一种首选的/被广泛接受的集群算法。然而，大多数算法只提供了将实例/对象分组到具有有限描述的簇中。描述和/或解释解决方案的工作在有监督的学习环境中变得流行起来，但在无监督的环境中研究不足。该奖项通过离散组合优化公式探索这些新颖的解释问题。这样的表述有助于开发需要可解释的(因此是离散的)结果、最佳可能的解释(不是任何可信的解释)的解释，并有助于实施复杂的约束以使解释符合人类的期望。这项研究将利用理论计算机科学方面的大量工作，并使用声明性范例中的工具，如ILP求解器和约束编程语言。由于不同的领域可能需要不同的解释，这些工具允许对配方进行容易的修改，这是一个理想的特点。这些技术的实用性将通过它们在包括社交网络和基因组数据在内的几个领域的应用来展示，并由该领域的两名领域专家进行评估。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Clustering is a common machine learning and data mining technique which takes a collection of instances/records/things and divides them into groups. It is used in a large variety of domains including social networks (to find communities), biology (to create taxonomies) and neuroscience (to find regions of interest in the brain). There are many clustering algorithms already in existence, but these algorithms do not always explain the clustering. This award addresses the problem of describing the clustering algorithm results to a variety of stakeholders including data scientists, domain scientists and the general public. Explaining the results of these algorithms will allow them to be better understood by stakeholders and allow their use in challenging and sensitive domains where transparency is required. Explanations are given in an initiative form using easy to understand auxiliary information such as tags. This project will consist of three inter-twined tasks. The first will develop easy to understand mechanisms to explain a clustering, whilst the second will allow a human to interact with the explanation by asking queries about it. Finally the third task will attach measure of stability, trust and correctness to the explanations generated from task one.The area of unsupervised learning is immensely popular due to the lack of need for labeled data and there exist many algorithms that can work on a variety of data types: images, graphs, documents, spatial and temporal data. Many domains have a preferred/well-accepted clustering algorithm. However, most algorithms provide just a grouping of the instances/objects into clusters with limited description. The work on describing and/or explaining a solution has gained popularity in the supervised learning context but is under-studied in the unsupervised context. This award explores these novel explanation problems through discrete combinatorial optimization formulations. Such formulations help in developing explanations requiring interpretable (hence discrete) results, best possible explanations (not any plausible explanation) and in enforcing complex constraints to make explanations match human expectations. This research will leverage much work in theoretical computer science and use tools from declarative paradigms such as ILP solvers and constraint programming languages. Such tools allow for easy modifications of formulations, a desirable trait as different domains may need different variations in explanation. The usefulness of the techniques will be demonstrated through their applications to several domains including social networks and genomic data and evaluated by two domain experts in the area.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.