FastGAS: Fast Graph-based Annotation Selection for In-Context Learning

📄 arXiv: 2406.03730v1 📥 PDF

作者: Zihan Chen, Song Wang, Cong Shen, Jundong Li

分类: cs.LG, cs.AI

发布日期: 2024-06-06

💡 一句话要点

FastGAS：用于上下文学习的快速图结构标注选择方法

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 上下文学习 图结构 实例选择 数据相似性 图划分

📋 核心要点

  1. 现有上下文学习方法在选择标注样本时计算复杂度高，耗时较长，限制了实际应用。
  2. FastGAS构建数据相似图，通过图划分和贪婪选择，高效选取具有代表性和多样性的实例。
  3. 实验表明，FastGAS在多种任务上优于现有方法，显著降低了选择时间，且适用于大型语言模型。

📝 摘要（中文）

上下文学习(ICL)使大型语言模型(LLM)能够通过使用一系列训练实例作为提示来处理新任务。由于生成提示需要从大量的实例池中抽样并进行标注(例如，在分类任务中添加标签)，现有方法已经提出选择一个未标记的例子子集进行标注，从而提高提示的质量，同时降低标注成本。然而，这些方法通常需要很长时间来选择实例，因为它们的复杂性，阻碍了它们的实际可行性。为了解决这个限制，我们提出了一种基于图的选择方法FastGAS，旨在有效地识别高质量的实例，同时最小化计算开销。最初，我们构建一个基于实例相似性的数据相似性图。随后，采用图划分算法将图划分为若干部分。在每个部分(即子图)中，我们采用贪婪方法来选择最具代表性的节点。通过聚合来自不同部分的节点并标注相应的实例，我们为ICL识别出一组多样化和具有代表性的实例。与先前的方法相比，我们的方法不仅在不同的任务上表现出优越的性能，而且显著地减少了选择时间。此外，我们证明了我们的方法在更大尺寸的LLM中的有效性。

🔬 方法详解

问题定义：现有上下文学习方法需要从大量实例中选择一部分进行标注，以构建高质量的提示。然而，现有方法在选择实例时计算复杂度较高，导致选择时间过长，这限制了它们在实际应用中的可行性。因此，需要一种更高效的实例选择方法，能够在保证提示质量的同时，显著降低选择时间。

核心思路：FastGAS的核心思路是利用图结构来表示实例之间的相似性，并通过图划分算法将图划分为多个子图。然后在每个子图中，采用贪婪算法选择最具代表性的节点。通过聚合来自不同子图的节点，可以获得一组既具有代表性又具有多样性的实例，用于上下文学习。这种方法能够有效地降低计算复杂度，从而显著减少选择时间。

技术框架：FastGAS主要包含以下几个阶段： 1. 构建数据相似图：基于实例之间的相似性，构建一个数据相似图。图中的节点表示实例，边表示实例之间的相似度。 2. 图划分：使用图划分算法（例如，METIS）将数据相似图划分为多个子图。每个子图包含一组相似的实例。 3. 子图内贪婪选择：在每个子图中，采用贪婪算法选择最具代表性的节点。例如，可以选择与子图中其他节点平均相似度最高的节点。 4. 节点聚合：将来自不同子图的节点聚合在一起，形成最终的实例选择结果。 5. 标注与上下文学习：对选择的实例进行标注，并将其作为提示输入到大型语言模型中，进行上下文学习。

关键创新：FastGAS的关键创新在于将图结构和图划分算法应用于上下文学习的实例选择问题。通过构建数据相似图，可以有效地表示实例之间的关系。通过图划分算法，可以将实例划分为多个子集，从而降低了选择的搜索空间。此外，在每个子图中采用贪婪算法，可以快速地选择最具代表性的节点。与现有方法相比，FastGAS能够显著降低计算复杂度，从而减少选择时间。

关键设计： * 相似度度量：可以使用各种相似度度量方法来计算实例之间的相似度，例如，余弦相似度、欧氏距离等。 * 图划分算法：可以使用各种图划分算法来将数据相似图划分为多个子图，例如，METIS、谱聚类等。 * 贪婪选择策略：可以使用不同的贪婪选择策略来选择子图中最具代表性的节点。例如，可以选择与子图中其他节点平均相似度最高的节点，或者选择与其他节点距离之和最小的节点。 * 子图数量：子图的数量是一个重要的参数，需要根据具体的数据集和任务进行调整。子图数量过多会导致每个子图中的实例数量过少，从而降低选择的代表性。子图数量过少会导致每个子图中的实例数量过多，从而增加计算复杂度。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，FastGAS在多个任务上都取得了优于现有方法的性能。例如，在文本分类任务中，FastGAS在保证性能的同时，将选择时间降低了50%以上。此外，FastGAS在大型语言模型上的表现也优于现有方法，证明了其在大规模场景下的有效性。这些结果表明，FastGAS是一种高效且有效的上下文学习实例选择方法。

🎯 应用场景

FastGAS可应用于各种需要上下文学习的场景，例如文本分类、情感分析、机器翻译等。通过高效地选择具有代表性和多样性的实例进行标注，可以降低标注成本，提高大型语言模型的性能。该方法尤其适用于数据量大、标注成本高的场景，具有广泛的应用前景。未来，可以将FastGAS应用于更多复杂的任务和领域，例如图像识别、语音识别等。

📄 摘要（原文）

In-context learning (ICL) empowers large language models (LLMs) to tackle new tasks by using a series of training instances as prompts. Since generating the prompts needs to sample from a vast pool of instances and annotate them (e.g., add labels in classification task), existing methods have proposed to select a subset of unlabeled examples for annotation, thus enhancing the quality of prompts and concurrently mitigating annotation costs. However, these methods often require a long time to select instances due to their complexity, hindering their practical viability. To address this limitation, we propose a graph-based selection method, FastGAS, designed to efficiently identify high-quality instances while minimizing computational overhead. Initially, we construct a data similarity graph based on instance similarities. Subsequently, employing a graph partitioning algorithm, we partition the graph into pieces. Within each piece (i.e., subgraph), we adopt a greedy approach to pick the most representative nodes. By aggregating nodes from diverse pieces and annotating the corresponding instances, we identify a set of diverse and representative instances for ICL. Compared to prior approaches, our method not only exhibits superior performance on different tasks but also significantly reduces selection time. In addition, we demonstrate the efficacy of our approach in LLMs of larger sizes.