University
of South
Africa
Department of Computer
Science
School of Computing
Module: Machine Learning COS4852
First names: Siviwe Shadrack
Surname: Khathangana
Student Number: 67799124
,Table of Content Page
Question 1 1
Question 2 2-5
Question 3 6-8
Question 4 8-16
Question 5 17-26
Question 6 27-45
,1
Question 1
Introduction to Machine Learning, Nils J. Nilsson, 1998
URL: https://ai.stanford.edu/~nilsson/MLBOOK.pdf
Size: 2,56 MB
A first encounter with Machine Learning, Max Welling, 2011
URL:https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.360.4637&rep=rep
1&type=pdf
Size: 415 KB
, 2
Question 2
Most significant notions about functions are most easily make use of special case of Boolean
functions. There are some major subclasses of Boolean functions that are used as
Hypothesis classes for function learning. For example a Boolean function, f (s1, s2,…, sn)
maps an n-tuple of (0,1) values to {0,1}. To represent the Boolean functions we make use of
Boolean algebra. The definition of Boolean algebra is the branch of algebra in which the
values of the variables are the truth values true and false, usually denoted 1 and 0,
respectively. Boolean algebra is a suitable notation to represent Boolean functions. Boolean
uses conjunctions ·, + and ¯. For example, the and function of two variables is written s1 ·
s2. By usage, the conjunction, “·” is normally quelled, and the and function is written s1s2.
s1s2 has a value 1 if and only if both a1 and a2 have value 1; if either s1 or s2 has a value 0,
s1s2 has a value 0. The (inclusive) or function of two variables is represented as s1+s2.
s1+s2 has value 1 if and only if either or both of s1 or s2 has a value 1; if both s1 and s2
have value 0, s1 + s2 has a value 0. The complement or negation of a variable, s. is
represent as ˜s. ˜s has a value 1 if and only if s has value 0; if s has a value 1, ˜s has a value
0. The definitions of Boolean functions are compactly given by the below rules
1+1 = 1, 1+0=1, 0+0=0
1·1=1, 1·0=0, 0·0=0 and
˜1=0, ˜0=1.
Sometimes the arguments and values of Boolean functions are expressed in terms of the
arguments of the constants T (True) and F (False) instead of 1 and 0, respectively. The
conjunctions · and + are each commutative and associative. As indicated for example,
s1(s2s3)=(s1,s2)s3 and both can be written as simply as s1,s2,s3 likewise for +. A Boolean
formula consisting of a single variable such as s1 is called an atom. One consisting either
single variable or its complement, such as ˜s1 is called a literal. The operations · and + do not
commute between themselves, instead we have DeMorgan’s laws below, which can be
confirmed using the above definitions. s1˜s2=˜s1+˜s2, and s1+˜s2=˜s1˜s2.
Boolean functions can also represented using Diagrams, we can use a labelled vertices of
cube. To represent a function of n variables, we can use n-dimensional hypercube. It is easy
to see how many Boolean functions of n dimensions using hypercube representation. One
diagrammatic technique for dimensions slightly higher than is the Karnaugh map. Karnaugh
map is used to simplify Boolean expressions where you have more than two variables.
Karnaugh Maps are quicker and easier to use than other simplification methods, including
computerized ones for Boolean expressions that contain between two and six variables. For
Boolean expressions with one to three variables, Boolean algebra is the best method. For
those expressions that contain more than six variables, computerized methods are best. In a
K-map, crossing a vertical or horizontal cell boundary is always a change of only one
variable.
of South
Africa
Department of Computer
Science
School of Computing
Module: Machine Learning COS4852
First names: Siviwe Shadrack
Surname: Khathangana
Student Number: 67799124
,Table of Content Page
Question 1 1
Question 2 2-5
Question 3 6-8
Question 4 8-16
Question 5 17-26
Question 6 27-45
,1
Question 1
Introduction to Machine Learning, Nils J. Nilsson, 1998
URL: https://ai.stanford.edu/~nilsson/MLBOOK.pdf
Size: 2,56 MB
A first encounter with Machine Learning, Max Welling, 2011
URL:https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.360.4637&rep=rep
1&type=pdf
Size: 415 KB
, 2
Question 2
Most significant notions about functions are most easily make use of special case of Boolean
functions. There are some major subclasses of Boolean functions that are used as
Hypothesis classes for function learning. For example a Boolean function, f (s1, s2,…, sn)
maps an n-tuple of (0,1) values to {0,1}. To represent the Boolean functions we make use of
Boolean algebra. The definition of Boolean algebra is the branch of algebra in which the
values of the variables are the truth values true and false, usually denoted 1 and 0,
respectively. Boolean algebra is a suitable notation to represent Boolean functions. Boolean
uses conjunctions ·, + and ¯. For example, the and function of two variables is written s1 ·
s2. By usage, the conjunction, “·” is normally quelled, and the and function is written s1s2.
s1s2 has a value 1 if and only if both a1 and a2 have value 1; if either s1 or s2 has a value 0,
s1s2 has a value 0. The (inclusive) or function of two variables is represented as s1+s2.
s1+s2 has value 1 if and only if either or both of s1 or s2 has a value 1; if both s1 and s2
have value 0, s1 + s2 has a value 0. The complement or negation of a variable, s. is
represent as ˜s. ˜s has a value 1 if and only if s has value 0; if s has a value 1, ˜s has a value
0. The definitions of Boolean functions are compactly given by the below rules
1+1 = 1, 1+0=1, 0+0=0
1·1=1, 1·0=0, 0·0=0 and
˜1=0, ˜0=1.
Sometimes the arguments and values of Boolean functions are expressed in terms of the
arguments of the constants T (True) and F (False) instead of 1 and 0, respectively. The
conjunctions · and + are each commutative and associative. As indicated for example,
s1(s2s3)=(s1,s2)s3 and both can be written as simply as s1,s2,s3 likewise for +. A Boolean
formula consisting of a single variable such as s1 is called an atom. One consisting either
single variable or its complement, such as ˜s1 is called a literal. The operations · and + do not
commute between themselves, instead we have DeMorgan’s laws below, which can be
confirmed using the above definitions. s1˜s2=˜s1+˜s2, and s1+˜s2=˜s1˜s2.
Boolean functions can also represented using Diagrams, we can use a labelled vertices of
cube. To represent a function of n variables, we can use n-dimensional hypercube. It is easy
to see how many Boolean functions of n dimensions using hypercube representation. One
diagrammatic technique for dimensions slightly higher than is the Karnaugh map. Karnaugh
map is used to simplify Boolean expressions where you have more than two variables.
Karnaugh Maps are quicker and easier to use than other simplification methods, including
computerized ones for Boolean expressions that contain between two and six variables. For
Boolean expressions with one to three variables, Boolean algebra is the best method. For
those expressions that contain more than six variables, computerized methods are best. In a
K-map, crossing a vertical or horizontal cell boundary is always a change of only one
variable.
