Задание:
Реализовать on-line алгоритм обучения конъюнктивной концепции.
Описание алгоритма:
Пусть X – вектор признаков, размером N, элементы которого принимают значения [0,1]. Последний элемент вектора – это некий результат, который должен получиться у «обучающейся» программы, на основе данных предыдущих элементов.
Пусть L – вектор размера 2*N, все элементы которого сначала равны 1. Вектор L определяет, какие элементы из вектора X будут использоваться для прогнозирования результата. В нем ‘1' месте (2*i-1) указывает на то, что в прогнозе участвует x(i), '0' означает, что x(i) не используется в прогнозирующей конъюнкции. Далее, '1' на месте (2*i) указывает на то, что в прогнозе участвует отрицание ~x(i), '0' означает, что ~x(i) не используется в прогнозирующей конъюнкции.
Предсказание вычисляется по формуле:
С(x) = С (x1,..,xn) =
[x1|(1-L(1))]*[(1-x1)|(1-L(2))]*…*[xn|(1-L(2*n-1))]*[(1-xn)|(1-L(2*n))],
где Xn – элементы вектора X, Ln – элементы вектора L.
В случае, если предсказание не совпало с ожидаемым результатом, из рассмотрения исключаются все элементы вектора X, принявшие нулевые значения.
Докажем, что алгоритм завершит работу с не более чем (N+1) ошибок.
Ошибка может возникнуть, только если ожидаемое значение равно 1.
При первой ошибке, алгоритм исключит из вектора L N литер, т.к. в начальном состоянии вектор L целиком состоит из единиц и, следовательно, формула C содержит N нулевых значений. Т.е. после первой ошибки, число теоретически ошибочных литер равно N. Следовательно, общее число ошибок никогда не превысит N+1.
Пример работы программы:
Исходные данные:
1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 |
0 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 |
0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 |
Результат работы программы:
Пример № 1
Вектор признаков Х = (1, 1, 1, 0, 1, 0, 0)
Ожидаемый результат: 0
Ошибок: 0
Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Пример № 2
Вектор признаков Х = (1, 1, 0, 0, 1, 1, 1)
Ожидаемый результат: 0
Ошибок: 0
Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Пример № 3
Вектор признаков Х = (1, 0, 1, 0, 0, 1, 1)
Ожидаемый результат: 0
Ошибок: 0
Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Пример № 4
Вектор признаков Х = (0, 0, 1, 1, 1, 0, 1)
Ожидаемый результат: 0
Ошибок: 0
Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Пример № 5
Вектор признаков Х = (1, 1, 1, 0, 0, 0, 0)
Ожидаемый результат: 0
Ошибок: 0
Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Пример № 6
Вектор признаков Х = (0, 0, 0, 1, 0, 1, 0)
Ожидаемый результат: 1
Ошибок: 1
Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
Пример № 7
Вектор признаков Х = (0, 1, 1, 1, 1, 0, 1)
Ожидаемый результат: 0
Ошибок: 1
Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
Пример № 8
Вектор признаков Х = (0, 1, 0, 0, 1, 1, 1)
Ожидаемый результат: 0
Ошибок: 1
Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
Пример № 9
Вектор признаков Х = (0, 1, 0, 1, 0, 0, 1)
Ожидаемый результат: 0
Ошибок: 1
Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
Пример № 10
Вектор признаков Х = (1, 0, 0, 1, 1, 0, 1)
Ожидаемый результат: 0
Ошибок: 1
Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
Пример № 11
Вектор признаков Х = (1, 0, 0, 0, 0, 1, 1)
Ожидаемый результат: 0
Ошибок: 1
Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
Пример № 12
Вектор признаков Х = (0, 1, 0, 1, 0, 0, 0)
Ожидаемый результат: 1
Ошибок: 2
Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)
Пример № 13
Вектор признаков Х = (0, 1, 1, 1, 1, 1, 1)
Ожидаемый результат: 0
Ошибок: 2
Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)
Пример № 14
Вектор признаков Х = (0, 1, 0, 0, 0, 0, 1)
Ожидаемый результат: 0
Ошибок: 2
Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)
Пример № 15
Вектор признаков Х = (0, 1, 1, 1, 0, 1, 1)
Ожидаемый результат: 0
Ошибок: 2
Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)
Пример № 16
Вектор признаков Х = (0, 1, 0, 1, 1, 1, 0)
Ожидаемый результат: 1
Ошибок: 3
Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 17
Вектор признаков Х = (0, 0, 1, 1, 0, 1, 0)
Ожидаемый результат: 1
Ошибок: 4
Вектор L = (0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 18
Вектор признаков Х = (1, 0, 0, 1, 0, 1, 0)
Ожидаемый результат: 1
Ошибок: 5
Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 19
Вектор признаков Х = (1, 0, 1, 0, 0, 0, 1)
Ожидаемый результат: 0
Ошибок: 5
Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 20
Вектор признаков Х = (0, 1, 1, 0, 0, 1, 1)
Ожидаемый результат: 0
Ошибок: 5
………………………………………………………………………………………………………………
Пример № 124
Вектор признаков Х = (1, 0, 1, 1, 1, 0, 1)
Ожидаемый результат: 0
Ошибок: 5
Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 125
Вектор признаков Х = (0, 0, 1, 0, 1, 1, 1)
Ожидаемый результат: 0
Ошибок: 5
Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 126
Вектор признаков Х = (1, 0, 0, 1, 1, 0, 0)
Ожидаемый результат: 1
Ошибок: 5
Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 127
Вектор признаков Х = (0, 0, 0, 1, 1, 1, 1)
Ожидаемый результат: 0
Ошибок: 5
Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Пример № 128
Вектор признаков Х = (1, 0, 0, 0, 0, 0, 1)
Ожидаемый результат: 0
Ошибок: 5
Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Окончательная версия вектора L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
Прогнозирующая функция С = x4 & ~x7
Текст программы:
namespace AI_lab4
{
public partial class Form1 : Form
{
Stream fileStream;
int[,] matrix;
int n = 0, height = 0, errorsCount = 0;
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
openFileDialog1.Filter = "Текстовые файлы (*.txt)|*.txt|Все файлы (*.*)|*.*";
openFileDialog1.FilterIndex = 2;
string str = "";
ConjunctionMethodTeaching CMT;
if (openFileDialog1.ShowDialog() == DialogResult.OK)
{
int i = 0, j = 0;
fileStream = openFileDialog1.OpenFile();
while ((i = fileStream.ReadByte()) != 0x0A) if (i == 48 || i == 49) n++; //определить кол-во символов в строке
if (checkBox1.Checked) //загрузить файл целиком в двумерный массив
{
matrix = new int[(height = (int)fileStream.Length / (n * 3 + 1)) + 2, n];
CMT = new ConjunctionMethodTeaching();
fileStream.Seek(0, SeekOrigin.Begin);
i = 0;
richTextBox1.Text = "";
for (int k = 0; k < fileStream.Length; k++)
{
matrix[i, j] = fileStream.ReadByte();
if (matrix[i, j] == 0x30 || matrix[i, j] == 0x31) { matrix[i, j] -= 0x30; j++; };
if (j == n) { i++; j = 0; }
}
richTextBox1.Text = "";
i = 0;
foreach (int[] l in CMT.ConjunctionConceptionTeachingMatrix(matrix, n, height))
{
if (checkBox2.Checked)
{
str = "Пример № " + ++i + "\nВектор признаков Х = (";
for (int k = 0; k < n - 1; k++)
str += matrix[i - 1, k] + ", ";
str = str.Remove(str.Length - 2) + ")\n";
str += "Ожидаемый результат: " + matrix[i - 1, n - 1] + "\n";
str += "Ошибок: " + CMT.GetErrorsCount + "\nВектор L = (";
foreach (int c in CMT.GetL)
str += c + ", ";
str = str.Remove(str.Length - 2) + ")\n";
richTextBox1.Text += str;
str = "";
}
}
}
i = 0;
str = "";
string str2 = "";
richTextBox1.Text += "\n\nОкончательная версия вектора L = (";
foreach (int l in CMT.GetL)
{
i++;
if (l == 1) str2 += (i % 2 != 0 ? "x" + (i / 2 + 1) : "~x" + i / 2) + " & ";
str += l + ", ";
}
str = str.Remove(str.Length - 2) + ")\nПрогнозирующая функция С = " + str2.Remove(str2.Length - 2);
richTextBox1.Text += str;
}
}
private void Form1_Load(object sender, EventArgs e)
{
checkBox1.Checked = checkBox2.Checked = true;
}
}
public class ConjunctionMethodTeaching
{
int[,] matrix;
int[] L;
int length, height, errorsCount;
public int[] GetL
{
get { return L; }
}
public int GetErrorsCount
{
get { return errorsCount; }
}
public ConjunctionMethodTeaching()
{
errorsCount = 0;
}
public ConjunctionMethodTeaching(int length)
{
this.length = length;
L = new int[2 * (length - 1)];
for (int i = 0; i < L.Length; i++)
L[i] = 1;
height = errorsCount = 0;
}
public ConjunctionMethodTeaching(int[,] matrix, int length, int height)
{
this.length = length;
this.height = height;
// this.matrix = new Matrix(matrix);
this.matrix = matrix;
errorsCount = 0;
L = new int[2 * (length - 1)];
for (int i = 0; i < L.Length; i++)
L[i] = 1;
}
public IEnumerable<int[]> ConjunctionConceptionTeachingMatrix(int[,] matrix, int length, int height)
{
L = new int[2 * (length - 1)];
for (int i = 0; i < L.Length; i++)
L[i] = 1;
int C;
errorsCount = 0;
for (int i = 0; i < height; i++)
{
C = 1;
for (int j = 0; j < length - 1; j++)
{
if (L[2 * j] == 1) C &= matrix[i, j];
if (L[2 * j + 1] == 1) C &= Convert.ToInt32(!Convert.ToBoolean(matrix[i, j]));
}
if (C == matrix[i, length - 1])
yield return L;
else
{
errorsCount++;
for (int k = 0; k < length - 1; k++)
{
if (matrix[i, k] == 0) L[2 * k] = 0;
if (!Convert.ToBoolean(matrix[i, k]) == false) L[2 * k + 1] = 0;
}
i--;
}
}
}
}
}