Darya is working on an online learning application in which false negatives are costlier than false positives. Therefore, she proposes the following variant of the Halving algorithm for learning a concept from class C. As in the Halving algorithm, her algorithm maintains a version space. Let VS+ denote the version space at time-step t. Instead of taking the label chosen by a majority of the functions in VSt (as the Halving algorithm does), Darya's algorithm first checks if there is a strong majority of functions in VS₁ that give the same label, where strong majority means at least 70 percent. More precisely, if at least [0.7 VS+|| functions in VS give a '+' label (respectively '-' label), Darya's algorithm predicts the label as '+' (respectively '-'). Otherwise, when there is no strong majority, Darya's algorithm always predicts the label as '+'. For example, if there are |VSt| = 100 functions in VSt out of which 75 functions give a '-', then the algorithm predicts the label as; but if 67 functions give a '-', the algorithm predicts a '+'. Use a similar analysis to the one we saw in the class for the Halving algorithm to derive an upper bound for the expected number of mistakes made by Darya's algorithm. You need to devise an asymptotic upper bound for the number of mistakes by Darya's algorithm. Show your work.

Darya is working on an online learning application in which false negatives are costlier than false positives. Therefore, she proposes the following variant of the Halving algorithm for learning a concept from class C. As in the Halving algorithm, her algorithm maintains a version space. Let VS+ denote the version space at time-step t. Instead of taking the label chosen by a majority of the functions in VSt (as the Halving algorithm does), Darya's algorithm first checks if there is a strong majority of functions in VS₁ that give the same label, where strong majority means at least 70 percent. More precisely, if at least [0.7 VS+|| functions in VS give a '+' label (respectively '-' label), Darya's algorithm predicts the label as '+' (respectively '-'). Otherwise, when there is no strong majority, Darya's algorithm always predicts the label as '+'. For example, if there are |VSt| = 100 functions in VSt out of which 75 functions give a '-', then the algorithm predicts the label as; but if 67 functions give a '-', the algorithm predicts a '+'. Use a similar analysis to the one we saw in the class for the Halving algorithm to derive an upper bound for the expected number of mistakes made by Darya's algorithm. You need to devise an asymptotic upper bound for the number of mistakes by Darya's algorithm. Show your work.

Similar questions

Design a deterministic finite state automaton (DFA) that accepts exactly the strings over the alphabet {A, B, ...,Z} that contain at least two R, at most one T, and where every E comes after some S (there may be other letters in between). For instance, your DFA should accept the strings: • MYSTICWARRIORS • MARSMATRIX • SHOCKTROOPERS • CONTRAHARDCORPS STRIDER but not the strings • CRAZYTAXI (it does not contain at least two Rs) LASTRESORT (it contains more than one T) AFTERBURNER (there are Es without a S somewhere before them) • BATTLECIRCUIT (all of these at the same time) Clearly indicate the meaning of each state. One way to do this is to number the states and have a numbered list of their meanings, but any readable method you use to label and explain your states is fine. Hint: there are three separate conditions accepted strings must meet; states will need to encode whether or not each one is met (or perhaps partially met). You can label an edge with the word “else" to indicate it…
Let A ={a, b, c} and B ={a, b} a. Is A a subset of B? b. Is Ba subset of A? c. What is A U B? d. What is A n B? e. What is A n B ? f. What is A x B?
The support vector machine does not need to be implemented. Linear classifiers, on the other hand, are intrinsically binary, and we have a 10-way classification issue (the library has handled it for you). You will train 10 binary, one-vs-all SVMs to determine which of ten categories a test instance belongs to. Each classifier will be taught to detect 'bird' versus 'non-bird,' 'cat' vs 'non-cat,' and so on. On each test case, all 10 classifiers are assessed, and the classifier with the highest degree of certainty "wins." For example, if the 'cat' classifier returns a score of -0.2 (where 0 is on the decision boundary), and the 'bird' classifier returns a score of -0.3, and all of the other classifiers are even more negative, the test case would be classified as a 'cat,' despite the fact that none of the classifiers put the test case on the positive side of the decision boundary. You have a free parameter C while learning an SVM that governs how strongly regularized the model is. Your…
Write a Python program for applying CNN with considering the following requirements: Shuffle the cifar 10 training set x_train( each input with corresponding label in y_train ) Select 2500 images and you must ensure that each class must contain at least 180 samples Apply CNN that keeps noisy examples. Overall, the pseudocode of CNN is as follows: The code must contain at least one lambda expression The code must contain at one comprehension list It is Not allowed to use the numpy library. Euclidean distance is the distance between two samples in Euclidean space. The formula can be expressed as:
Create an algorithm for calculating a circle and the Schreier vector.Output: the orbit G; a Schreier vector v and backward references w of the orbit 8 G relative to the set S of generators.
Implement two versions of the successor function for the 8-puzzle: one that generates all the successors at once by copying and editing the 8-puzzle data structure, and one that generates one new successor each time it is called and works by modifying the parent state directly (and undoing the modifications as needed). Write versions of iterative deepening depth-first search that use these functions and compare their performance.
Consider all words representing the sound a cow makes to be the following infinite set: "moo!", "mooo!", "moooo!", etc. Show a regular expression that would accept any line in which the sound a cow makes occurs at least two times (they don't have to be consecutive or identical). Each instance must be preceded by a non-letter or occur at the start of a line. It does not matter what occurs after the explanation points.
write python program 10x10 grid, agent top right corner, traversing terrain = 1 time unit, rough terrain = 5 time units, and others terain = cannot be reached An A* based search function that takes a list of lists as argument and generates as a result a list of grid cell coordinates starting at the upper right and ending at the lower left and representing the fastest path for the agent to travel. E.g., path = aStarSearch(map). The path can be empty if there is no route.
The following loop has multiple types of dependences. Find all the true dependences, output depende- nces and anti dependences and eliminate the output dependences by renaming. For( i 3D 1; i- 100; i 3D і+1) { Y[i] = X[i]/C; X[i] = X[i] + C; Z[i] = Y[i] + C; %3D Y[i] = C-Y[i]; %3| }
Dynamic Models can be represented by: а. Тext b. Cartoons O c. Graphs d. Classes e. Both "a" and "c" O f. All of the above
Write a Python program for applying CNN with considering the following requirements: Shuffle the cifar 10 training set x_train( each input with corresponding label in y_train ) Select 2500 images and you must ensure that each class must contain at least 180 samples Apply CNN that keeps noisy examples. Overall, the pseudocode of CNN is as follows: The code must contain at least one lambda expression The code must contain at one comprehension list It is Not allowed to use the numpy library. Euclidean distance is the distance between two samples in Euclidean space. The formula can be expressed as: USE THIS CODE import tensorflowimport cv2from tensorflow import kerasfrom PIL import Imageimport numpy as p (x_train, y_train), (_, _) = tf.keras.datasets.cifar10.load_data() x_train = [cv2.cvtColor(image, cv2.COLOR_BGR2GRAY).flatten().tolist() for image in x_train]##x_train=np.asarray(x_train)print(len(x_train))print(len(x_train[0])) # 32*32 NOTE: PLEAS USE THE CODE I ATTACHED NOTE 2:…
If F is a function and dom(F) is a set, then F is a set.Hint. Prove first that ran(F) is a set