[發明專利]用于串變換的歸納合成的排序

在審

• 申請號: 201380054348.2
• 申請日: 2013-10-17
• 公開（公告）號: CN104737155A
• 公開（公告）日: 2015-06-24
• 發明（設計）人: S·古爾瓦尼;R·辛格
• 申請（專利權）人: 微軟公司
• 主分類號: G06F17/22
• 分類號: G06F17/22
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 管琦琦

1.一種計算機實現的用于對候選變換程序進行排序以建立一個或多個變換程序的經排序組的過程，每個所述候選變換程序包括含子表達式的程序表達式，每個所述變換程序從用戶輸入的輸入串產生具有用戶想要形式的輸出串，符合用戶提供的一個或多個輸入-輸出示例中的每一個，所述過程包括：

使用計算機來執行以下過程動作：

輸入從用戶提供的一個或多個輸入-輸出示例歸納地合成的候選變換程序的集合，每個所述候選變換程序從用戶提供的每個輸入示例產生具有用戶提供的每個輸出示例所展現的形式的輸出串；

針對每個候選變換程序，

對于已經為其建立了排序機制的按照從較小到較大次序的候選變換程序的每個子表達式，使用為所述子表達式建立的排序機制來建立似然度分數，以及

從為所述候選變換程序建立的子表達式似然度分數計算針對所述候選變換程序的總排序分數。

2.如權利要求1所述的過程，其特征在于，子表達式或者是正則表達式，或者是位置表達式，或者是原子表達式，或者是連接表達式，并且建立所述排序機制以供按所述次序對所述正則表達式、位置表達式、原子表達式和連接表達式中的每一個進行排序。

3.如權利要求2所述的過程，其特征在于，原子表達式或者是常量串表達式或者是子串表達式，并且建立用于原子表達式的排序機制的過程動作包括動作：

標識所述原子表達式是常量串表達式還是子串表達式；

輸入任務的訓練集合，其中每個任務包括多個輸入-輸出示例；

從所述訓練集合生成訓練數據；以及

訓練機器學習分類器以向每個子串表達式和每個常量串表達式指派似然度分數。

4.如權利要求3所述的過程，其特征在于，向每個子串表達式指派似然度分數的過程動作包括指派具有從0到1范圍內的值的似然度分數，并且向每個常量串表達式指派似然度分數的過程動作包括指派規定的似然度分數值。

5.如權利要求3所述的過程，其特征在于，從任務的所述訓練集合生成訓練數據的過程動作包括以下動作：

針對所述訓練集合中的每個任務，

針對所述任務中的每個輸入-輸出示例，

建立從所述輸入-輸出示例歸納地合成的變換程序的集合，其中每個所述變換程序從所述示例中的輸入串的元組產生所述示例中的輸出串，

從所述變換程序的集合建立正訓練子表達式集合，

從所述變換程序的集合建立負訓練子表達式集合，以及

從所述正訓練子表達式集合和所述負訓練子表達式集合中的每個子串表達式生成訓練數據。

6.如權利要求5所述的過程，其特征在于，從所述正訓練子表達式集合和所述負訓練子表達式集合中的每個子串表達式生成訓練數據的過程動作包括以下動作：

輸入一個或多個特征的集合，每個所述特征指示所述輸出串中的子串是否由所述正訓練子表達式集合和所述負訓練子表達式集合中的子串表達式產生；

對于所述正訓練子表達式集合和所述負訓練子表達式集合中的每個子串表達式，生成包括按規定次序的元素的特征向量，其中除了為類標記保留的那一個以外的每個元素對應于與所述特征之一分別相關聯的特征值，所述特征向量生成包括：

對于按與元素的規定次序相對應的次序的所述特征中的每一個，如果所述特征被展現在由考慮中的子串表達式產生的輸出串的子串中，則向對應的特征向量元素指派具有第一二進制值的特征值，并且如果所述特征沒被展現在由考慮中的子串表達式產生的輸出串的子串中，則向對應的特征向量元素指派具有第二二進制值的特征值，以及

對于為所述類標記保留的所述特征向量元素，如果所述子串表達式在正訓練子表達式集合中，則指派一個二進制值，并且如果所述子串表達式在負訓練子表達式集合中，則指派不同的二進制值。

7.如權利要求5所述的過程，其特征在于，從建立自任務中的輸入-輸出示例的所述變換程序的集合來建立正訓練子表達式的集合的過程動作包括將在從所述任務中的所述輸入-輸出示例合成的變換程序的所有集合的交集中發現的每個子表達式指定為正訓練子表達式。

8.如權利要求7所述的過程，其特征在于，從建立自任務中的輸入-輸出示例的所述變換程序的集合來建立負訓練子表達式的集合的過程動作包括將沒被標識為正訓練子表達式的變換程序的集合中的每個子表達式指定為負訓練子表達式。