2010 Лекции МОТП. Записки (2010 Лекции МОТП. Записки.pdf), страница 6

Строка αA(S), содержащая одни нули, интерпретируется какотсутствие классов, на которые похож распознаваемый объект.4. Нахождение логических закономерностей при обучающих выборкахбольшой длины.Изложенный в п.2 подход для построения множества логическихзакономерностей предполагает нахождение предикатов вида (2) для каждогоэталонного объекта, т.е. решение задач БМС-ЦЛП (7-8) для каждого эталона.Решение большого числа задач БМС-ЦЛП приводит к существеннымзатратам процессорного времени для поиска предикатов и памяти дляхранения предикатов, времени распознавания новых объектов. Ясно, чтонайденные множества логических закономерностей будут содержать многопохожих предикатов (2), а само их число будет «избыточным».

Такимобразом представляет интерес вычисление множеств логическихзакономерностей различной мощности.Естественным подходом для решения данной задачи являетсяреализация следующей общей схемы.Пусть задан критерий γ(Sj) оценки важности (представительности)произвольного объекта Sj обучающей выборки, I={S1, S2,…, Sm }, η≥ 1 –некоторое фиксированное число, π = {π 1 ,π 2 ,...,π m },π i = 0, i = 1,2,..., m.Рассмотрим следующий алгоритм вычисления множеств Pj , j=1,2,…l.1. Полагаем2.

ПустьPj = ∅, j=1,2,…,l, v=1.S iv ∈ I -эталонный объект,Siv ∈ K λ ,для которогоγ ( S j ) . Решается задача БМС-ЦЛП (7-8)выполнено γ ( S iv ) = maxS j ∈IотносительноSivинаходитсямножествологических34закономерностейP iv = {PivΩ,ε ( x)} ,опорным. МножествоPλдополняется предикатами из3. Для каждого i∈I величинаP ivπiSivдля которыхP ivявляется.увеличивается на число предикатов из, принимающих единичные значения на объекте Si .4.

Из I исключаетсяSiv и все Si, для которых π i ≥ η.Если I=∅, множестваPj ,j=1,2,…l, считаются построенными иалгоритм заканчивает свою работу.В противном случае значение v увеличивается на единицу иосуществляется переход на второй этап.При выборе η=1 множество Pj содержит множество предикатов (2),причем для каждого эталонного объекта из Kj имеется хотя бы одинпредикат, принимающий на данном объекте значение 1. При выборе η=mмножество Pj является, как правило, объединением всех предикатов (2),вычисленных для всех задач БМС-ЦЛП с использованием всех эталонов Kj вкачестве опорных.Рассмотрим теперь вопрос выбора функции γ(Sp), оценивающей«представительность» объекта Sp.Здесь можно использовать различные подходы, например, следующий.Выбирается некоторая метрика (полуметрика) ρ ( Si , S j ) в пространствепризнаковых описаний и при некотором фиксированном значении kпредставительностьγ(Sj)объектаS j ∈ Kλопределяется как числообъектов данного класса из ближайших k соседей , т.е.

если J ( S j ) -{}.множество ближайших k соседей к Sj, то γ(Sj)= Si ∈ K λ ∩ J ( S j )5. Оптимизация логических закономерностей.Пусть по данным обучающей выборки с использованиемэвристического функционала (3) вычислены некоторые множестваΩ ,εP=P( x) по всем классам Kj , j=1,2,tлогических закономерностей jt…,l.Полученные множества "элементарных знаний" содержат большоечисло элементов, которые используются как в процедурах голосования приклассификации новых объектов, так имеют и самостоятельную ценность дляпонимания и описания классов. Независимо от метода их поиска наиболееестественным критерием их оценки является (понятный и наглядный)стандартный функционал качества предикатов.35В самом начале сложная задача поиска логических закономерностей (1)со стандартным критерием их оценки была заменена более простой.Ω ,εP=P( x) каждогоjtМножества «элементарных знаний»tклассавычислялись при двух существенных ограничениях: поиск логическихзакономерностей осуществляется лишь на множестве предикатов c опорнымиэталонами и с использованием эвристического функционала качества.

Приэтом, конкретный используемый метод решения задачи БМС-ЦЛП негарантирует вычисление всех локально-оптимальных экстремумов (темболее, на длинных выборках) или нахождение глобального экстремума. Витоге, найденные множества логических закономерностей содержат близкиеили даже равные элементы. С другой стороны, существуют логическиезакономерности, имеющие более высокие значения стандартного критериякачества, но данные «элементарные знания» найти не удалось в силуограниченности процедур поиска, использования более простыхфункционалов и множества предикатов частного вида. Таким образом,∗возникает вопрос о поиске множеств P j логических закономерностей сболее высокими значениями стандартного функционала качества чем уPj , используянайденных измножества P jв качестве начальныхприближений и естественные гипотезы о связи "близких" знаний.

Еслиданная задача решается положительно, то «элементарные знания» изP∗jмогут рассматриваться как обобщения множеств «элементарных знаний» Pj .Пусть Pt(x)∈ Pj .Обозначим черезψ ( Pt ) = (ψ l ( Pt ),ψ l ( Pt ),...,ψ l ( Pt )) - оценочныйвектор предиката Pt(x), где ψПредикатPt(x)j( Pt ) = {Si : ⋅S i ∈ K j , Pt ( Si ) = 1} / K j .из множестваPjназовемλ- допустимым, еслиψ i ( Pt ) ≤ λψ j ( Pt ), i ≠ j , , λ ≥ 0.

Далее предполагаем, что множестваPjсодержат лишь λ-допустимые предикаты, а λ для краткости будем опускать.Пусть P1(x),P2(x) - пара допустимых предикатов из P j ,P1 ( x) = & (a1j ≤ x j ≤ b1j ) & (c1j ≤ x j ≤ d 1j ) ,j∈Ω1j∈ΩP2 ( x) = & (a 2j ≤ x j ≤ b 2j ) & (c 2j ≤ x j ≤ d 2j ) , гдеj∈Ω 2j∈ΩΩ1 , Ω 2 , Ω ∈ {1,2,..., n},⋅ Ω1 ∩ Ω 2 = ∅, Ω1 ∩ Ω = ∅, Ω 2 ∩ Ω = ∅.36Допустимыйназовемпредикатрасширениемпредикатаσ ∈{−∞ ,⋅c ,⋅ min{c , c }} ,1j1j1jP( x) = & (a1j ≤ x j ≤ b1j ) & (σ 1j ≤ x j ≤ δ 1j )2jj∈Ω1P1(x) по предикату P2(x),δ 1j ∈ {d 1j ,⋅ max{d 1j , d 2j },⋅ + ∞} .11случаях, когда σ j = −∞ , δ j = +∞ , переменнаяМножество предикатовP1j ,P j2j∈ΩxjеслиВстановится фиктивной.назовем расширением множества предикатовесли оно состоит из всех расширений предикатов множестваP1jпопредикатам этого же множества.Допустимый предикат P(x) назовем максимальным по множествуPj ,если не существует его расширений ни по одному предикату из Pj .Рис.2.

ABCD и EFGH соответствуют элементарным предикатам.AKMD и GHBK их максимальные допустимые обобщения при λ=0.Обобщение AKGL не является допустимым.В результате построения последовательных расширенийP1j , P j2 ,…,P ij ,…, будут построены множества P∗j , состоящие только из максимальныхрасширений. Конечность настоящего процесса очевидна. В случае λ=0 поисходным множествам логических закономерностей классов будутпостроены множества логических закономерностей классов, обладающиемаксимально возможными значениями стандартного функционала качествасреди всевозможных допустимых расширений начальныхPj .37Построенные множества максимальных предикатовP∗jобладаютрядом благоприятных свойств, которые делают их более предпочтительнымиPj .

Сам процесс построения по множествам Pjотносительно исходных∗(исходным "элементарным знаниям") множеств P j естественно называтьоптимизацией исходных элементарных знаний. Максимальные предикаты изP∗j имеют более высокие показатели для ϕ j ( Pt ) чем их "предки", причемзначенияϕi ( Pt ) , i# j, не превосходят установленных ограничений сверху.ЛЕКЦИЯ № 96. Нахождение логических закономерностей, оптимальных постандартному критерию качества (дискретный подход).Вернемся к общей задаче поиска логических закономерностей.

Пустьзадано множество элементарных предикатов, параметрически зависящих отчисловых неизвестных c j , c j , j = 1,2,..., n :121, c1j ≤ x j ≤ c 2j ,Pj (c , c , x j ) = иначе.0,1jи2jΩ ⊆ {1,2,..., n} . Будем рассматривать более общее определениелогической закономерности, чем ранее введенное. Пусть ζ≥ 0 некоторыйпараметр.Определение.

ПредикатP Ω (c1 , c 2 , x) = & Pj (c1j , c 2j , x j )j∈Ω(1)называется логической закономерностью класса Kλ , если4.5.Ω∃ St ∈ Kλ : P (c , c , S t ) = 1,{ Si ∉ K λ | P( Si ) = 1}≤ ς (доля объектов P ( S i ) = 1{P ( S i ) = 1}12классов не превышает заданный порог ζ).6.ϕ ( P Ω (c1 , c 2 , x)) =extrΟ12{ P ( d , d , x )}чужихϕ ( P Ο (d 1 , d 2 , x)) ,гдеϕ ( P Ω (c1 , c 2 , S )) = {Si : Si ∈ K λ , P Ω (c1 , c 2 , Si ) = 1} .В настоящем разделе будет рассмотрен метод прямого поискалогических закономерностей классов при ζ=0. Рассмотрим данную задачу38при ограниченииP Ω (c1 , c 2 , S t ) = 1, гдеSt ∈ Kλ- произвольныйфиксированный объект.ПустьDi1 = {di11 , di12 ,..., diu1 } , Di2 = {d i21 , di22 ,..., d iv2 } - некоторыеварианты выбора возможных значений левых и правых границ предикатов222111(1), соответственно, − ∞ = d iu < ...