89 "контрпримеров"; 3) неоднозначность возможных решений даже для одного и того же исходного множества слов; 4) возможность (ввиду индуктивного характера решаемой задачи) появления в языке, порождаемом результирующей грамматикой, слов, не принадлежащих исходному языку. Перечисленные особенности, а также ряд других, не определяются используемыми методами решения рассматриваемой задачи, а вытекают из индуктивного характера ее решения и возможности неоднозначного (в том числе и неточного) "продолжения" языка, порождаемого грамматикой, на множество слов языка, не входящих в исходный "обучающий" материал. В этих случаях в работе [119] при решении каждой конкретной задачи предложено использовать некоторую количественную меру качества восстановления грамматики, по значениям которой можно было бы сравнивать различные возможные решения. Обычно эта мера характеризует сложность получаемой грамматики, а конкретный ее вид должен формулироваться исходя из существа решаемой прикладной задачи с учетом возможных последствий от неточности восстановления грамматики. Для данной группы методов рассмотрим, аналогично [3], основные понятия, используемые далее при решении задачи восстановления ТМГ. Последовательность цепочек множества {+ у\ у L} U {—у у — L) является информационной последовательностью I(L) языка L. Информационная последовательность, состоящая только из цепочек языка L, является положительной информационной последовательностью I+(L) языка L. Аналогично, информационная последовательность, состоящая только из цепочек множества— L, является отрицательной информационной последовательностью (L) языка L. |
97 решением задачи. В результате работы этого блока находятся описания разделяемых образов. Тем самым определяется окончательная, грамматическая система языка для анализа изображений, подобных тем, которые были показаны в процессе обучения. Система имеет несколько этапов поиска новых логических переменных. На первом этапе ищется описание в терминах, характеризующих изображение в целом, на втором в описание включаются термины, характеризующие части изображений, на третьем — термины, характеризующие части частей изображений, и т. д. Следует особо отметить, что основная часть рассмотренной процедуры, связанная с нахождением удовлетворительной логической функции, не содержит специфических особенностей, связанных с анализом объектов (образов) конкретной природы, и поэтому может оказаться полезной для решения более широкой задачи автоматического анализа слабоструктурированных образов, которую в каком-то смысле целесообразно решать поэтапно до полного решения. В более сложных случаях [40], для решения задач восстановления грамматик предложены процедуры, носящие индуктивный характер и имеющие следующие особенности: 1) существенную зависимость результата от выбранного подмножества слов языка, используемого для восстановления грамматики; 2) зависимость результата от мощности множества "примеров" и "контрпримеров"; 3) неоднозначность возможных решений даже для одного и того же исходного множества слов; 4) возможность (ввиду индуктивного характера решаемой задачи) появления в языке, порождаемом результирующей грамматикой, слов, не принадлежащих исходному языку. 98 -4, Ж' Л' Л9 Перечисленные особенности, а также ряд других, не определяются используемыми методами решения рассматриваемой задачи, а вытекают из индуктивного характера ее решения и возможности неоднозначного (в том числе и неточного) "продолжения" языка, порождаемого грамматикой, на множество слов языка, не входящих в исходный "обучающий" материал. В этих случаях в работе [119] при решении каждой конкретной задачи предложено использовать некоторую количественную меру качества восстановления грамматики, по значениям которой можно было бы сравнивать различные возможные решения. Обычно эта мера характеризует сложность получаемой грамматики, а конкретный ее вид должен формулироваться исходя из существа решаемой прикладной задачи с учетом возможных последствий от неточности восстановления грамматики. Для данной группы методов рассмотрим, аналогично [119], основные понятия, используемые далее при решении задачи восстановления ГС. Последовательность цепочек множества {+.у\уе L} U {—у 1у еу' — L} является информационной последовательностью I(L) языка L. Информационная последовательность, состоящая только из цепочек языка L, является положительной информационной последовательностью 7+(L) языка L. Аналогично, информационная последовательность, состоящая только из цепочек множества у* — L, является отрицательной информационной последовательностью /(L) языка L. Информационная последовательность языка L является полной, если 1) 7+ (L) содержит все цепочки языка L, и 2) I~ (L) содержит все цепочки, не принадлежащие L. Положительная информационная последовательность Г(L) полна, если каждая цепочка языка L содержится в f (L). Образцом St (L) языка L является множество {+у1,..., + у,} U { -yl, . . у, }, причем множество { +у1, . . + у( } -положительный образец, а множество { -yl, . . -yt }— отрицательный образец. Положительный образец St |