Е. Миркес - Учебное пособие по курсу «Нейроинформатика»

Пусть дана таблица данных, содержащая N записей, каждая из которых содержит M+1 поле. Обозначим значение i- о поля j- й записи через x i j , где i =0,…, M , j =1,…, N . Обозначим через V ( A,S ) задачник, в котором ответы заданы в полях с номерами i ∈ A , а входные данные содржатся в полях с номерами i ∈ S . Множество А будем называть множеством ответов, а множество S — множеством входных данных. Минимальное множество входных сигналов, полученное при обучении сети на задачнике V ( A,S ), обозначим через F ( A,S ). В случае, когда сеть не удалось обучить решению задачи будем считать, что F ( A,S )=∅. Число элементов в множестве A будем обозначать через | A |. Через T ( A,S ) будем обозначать сеть, обученную решать задачу предсказания всех полей (ответов), номера которых содержатся в множестве A , на основе входных сигналов, номера которых содержатся в множестве S .

Задача. Необходимо построить набор входных параметров, который позволяет надежно решать задачу V ({0},{1,…, M }).

Решение задачи будем называть множеством повышенной надежности, и обозачать S •′.

Для решения этой задачи необходимо определит набор параметров, дублирующих минимальный набор S 1= F ({0},{1,…, M }). Возможно несколько подходов к определению дублирующего набора. В следующих разделах рассмотрены некоторые из них.

Возможно два типа дублей — набор входных сигналов, способный заменить определенный входной сигнал или множество сигналов при получении ответа первоначальной задачи, и набор входных сигналов, позволяющий вычислить дублируемый сигнал (множество дублируемых сигналов). Дубли первого типа будем называть прямыми, а дубли второго типа — косвенными.

Возможна другая классификация, не зависящая от ранее рассмотренной. Дубли первого и второго рода будем различать по объекту дублирования. Дубль первого рода дублирует все множество вцелом, а дубль второго рода дублирует конкретный сигнал.

Очевидно, что возможны все четыре варианта дублей: прямой первого рода, косвенный первого рода, прямой второго рода и косвенный второго рода. В следующих разделах будут описаны алгоритмы получения дублей всех вышеперечисленных видов.

Для нахождения прямого дубля первого рода требуется найти такое множество сигналов D что существует сеть T ({0}, D ) и S 1∩ D =∅. Решение этой задачи очевидно. Удалим из множества входных сигналов те их них, которые вошли в первоначальное минимальное множество входных сигналов S 1. Найдем минимальное множествовходных сигналов среди оставшихся. Найденное множество и будет искомым дублем.

Формально описанную выше процедуру можно записать следующей формулой:

D= F ({0},{1,…, M }\ S 1).

Множество повышенной надежности в этом случае можно записать в следующем виде:

Очевидно, что последнюю формулу можно обобщить, исключив из первоначального множества входных сигналов найденное ранее множество повышенной надежности и попытавшись найти минимальное множество среди оставшихся входных сигналов. С другой стороны, для многих нейросетевых задач прямых дублей первого рода не существует. Примером может служить одна из классических тестовых задач — задача о предсказании результатов выборов президента США.

Для нахождения косвенного дубля первого рода необходимо найти такое множество входных сигналов D что существует сеть T ( S 1, D ) и S 1∩ D =∅. Другими словами, среди множества входных сигналов, не включающем начальное минимальное множество, нужно найти такие входные сигналы, по которым можно восстановит значения входных сигналов начального минимального множества. Формально описанную выше процедуру можно записать следующей формулой:

D = F ( S 1,{1,…, M }\ S 1).

Множество повышенной надежности в этом случае можно записать в следующем виде:

Эта формула так же допускает обобщение. Однако, следует заметить, что косвенные дубли первого рода встречаются еще реже чем прямые дубли первого рода. Соотношение между косвенным и прямым дублем первого рода описываются следующей теоремой.

Теорема 1. Если множество D является косвенным дублем первого рода, то оно является и прямым дублем первого рода.