Breadth-first search holds the search frontier in which data structure?

A priority queue ordered by a heuristic

Uniform-cost search always expands the frontier node with the lowest

cumulative path cost g(n) so far

The minimax algorithm assumes a game that is

two-player, zero-sum and deterministic, with perfect information

cooperative, with information hidden from both players

continuous-valued and infinite in depth

Alpha-beta pruning, compared with plain minimax search on the same game tree,

computes the identical minimax value while examining fewer nodes

computes a different, approximate value to save time

computes the identical minimax value while examining fewer nodes

only works for games with more than two players

requires no evaluation function at any leaf

Which of the following are true of propositional logic versus first-order (predicate) logic?

First-order logic adds quantifiers and predicates over objects that propositional logic lacks

Every propositional-logic sentence can be expressed as a special case of a first-order sentence

First-order logic is strictly more expressive than propositional logic

First-order logic adds quantifiers and predicates over objects that propositional logic lacks

Every propositional-logic sentence can be expressed as a special case of a first-order sentence

Propositional logic can express 'every student passed some exam' just as generally as first-order logic

First-order logic is strictly more expressive than propositional logic

A Bayesian network's directed acyclic graph structure primarily encodes

which conditional independence assumptions hold among the variables

the numerical value of every probability in the joint distribution

which conditional independence assumptions hold among the variables

the order in which variables were measured in an experiment

the total number of variables in the domain, and nothing else

Exact inference by variable elimination answers a probabilistic query by

marginalizing out non-query, non-evidence variables one at a time, multiplying only the factors that mention each

enumerating and summing the full joint distribution table directly

marginalizing out non-query, non-evidence variables one at a time, multiplying only the factors that mention each

drawing random samples from the network and counting their frequencies

ignoring the network's structure entirely and using only the prior

Variable elimination's computational cost depends heavily on

the elimination order chosen for the variables

the alphabetical order of the variable names

the elimination order chosen for the variables

whether the network diagram is drawn left-to-right or top-to-bottom

the programming language used to implement the algorithm

Approximate inference through sampling becomes preferable to exact inference mainly when

exact inference such as variable elimination becomes too expensive on a large, densely connected network

the network has only two variables

exact inference such as variable elimination becomes too expensive on a large, densely connected network

the query variable has no parent nodes at all

all the evidence variables happen to be continuous

Using A* with graph search and a heuristic that is admissible but NOT consistent, the guarantee that can fail is that

a node, once expanded, may still need to be re-expanded after a cheaper path to it is found later

the algorithm no longer terminates at all

a node, once expanded, may still need to be re-expanded after a cheaper path to it is found later

the search no longer finds any solution whatsoever

admissibility itself silently stops holding partway through the search

Which of the following are true of minimax and alpha-beta pruning?

Minimax assumes optimal play from both players at every turn

Alpha-beta's best-case node reduction (to roughly b^(d/2)) assumes a well-ordered tree

Alpha-beta pruning still needs an evaluation function at cut-off depth, exactly as minimax does

Minimax assumes optimal play from both players at every turn

Alpha-beta pruning can arrive at a different final move than plain minimax on the same tree

Alpha-beta's best-case node reduction (to roughly b^(d/2)) assumes a well-ordered tree

Alpha-beta pruning still needs an evaluation function at cut-off depth, exactly as minimax does

A Bayesian network shaped as a tree, where every variable has at most one parent, allows exact inference such as variable elimination to run in time that is

linear in the number of variables

exponential in the number of variables regardless of the network's shape

linear in the number of variables

always slower than on a fully, densely connected network of the same size

undefined, because a tree-structured network cannot represent conditional independence

कृत्रिम बुद्धिमत्ता

GATE आँकड़ा विज्ञान व कृत्रिम बुद्धिमत्ता (DA) पेपर का खंड 7, तथा इसका अंतिम: वह search जो किसी पथ या चाल को तब खोजती है जब संभावनाओं का स्थान संपूर्णतः देखने हेतु बहुत बड़ा हो — अनसूचित (uninformed), सूचित (informed) व adversarial — वह logic जो किसी तथ्य को केवल संग्रहित करने के बजाय निरूपित होने व उससे कोई नया तथ्य व्युत्पन्न होने देती है, प्रस्तावीय (propositional) व विधेय (predicate), तथा अनिश्चितता के अंतर्गत तर्क, जहाँ conditional independence, variable elimination से exact inference, व sampling से approximate inference किसी ऐसे probability distribution को, जो लिखने हेतु बहुत बड़ा हो, ऐसी चीज़ में बदल देते हैं जिससे कोई मशीन वास्तव में प्रश्न पूछ सके।

1. अनसूचित (uninformed) search: BFS, DFS, uniform-cost search

कोई search समस्या एक आरंभिक अवस्था, हर अवस्था में उपलब्ध क्रियाओं, यह बताने वाले transition मॉडल कि कोई क्रिया किस अवस्था तक ले जाती है, एक goal test, तथा एक path cost से परिभाषित होती है। Uninformed (blind) search रणनीतियाँ इस परिभाषा के अतिरिक्त कुछ उपयोग नहीं करतीं — कोई अवस्था लक्ष्य के कितने निकट है इसका कोई अनुमान नहीं — और मुख्यतः इसमें भिन्न होती हैं कि विस्तार हेतु प्रतीक्षारत अवस्थाओं का frontier किस डेटा संरचना में रखा जाए। Breadth-first search (BFS) एक FIFO क्यू उपयोग करता है, complete है (यदि किसी सीमित स्पेस में कोई लक्ष्य मौजूद हो तो यह उसे खोज लेता है) व optimal है जब हर क्रिया की लागत समान हो, पर इसका स्मृति-उपयोग गहराई के साथ घातांकीय रूप से बढ़ता है। Depth-first search (DFS) एक स्टैक (स्पष्ट, या recursion के ज़रिए) उपयोग करता है, अब तक पहुँची गहराई के अनुपात में ही स्मृति उपयोग करते हुए, पर यह न तो बिना गहराई-सीमा के किसी अनंत-गहराई स्पेस पर complete है और न ही समाप्त होने पर भी optimal।

⚠️ DFS की स्मृति-दक्षता स्वतः कोई लाभ नहीं है

एक सामान्य ग़लती DFS को केवल इसलिए BFS से 'बेहतर' मान लेना है क्योंकि यह कम स्मृति उपयोग करता है। बिना गहराई-सीमा के किसी अनंत या बहुत गहरी अवस्था-स्पेस पर, DFS एक अंतहीन या बहुत गहरी शाखा में उतर सकता है और उस लक्ष्य को कभी नहीं खोज पाता जो किसी दूसरी शाखा में केवल कुछ ही कदम दूर बैठा हो — इसका कम स्मृति-चिह्न यह कुछ नहीं बताता कि यह वास्तव में किसी उत्तर के साथ समाप्त होगा भी या नहीं।

Uniform-cost search BFS को उन ग्राफ़ों तक सामान्यीकृत करता है जहाँ क्रियाओं की लागत भिन्न हो: यह सदा उस frontier नोड को विस्तारित करता है जिसकी अब-तक की संचयी path लागत सबसे कम हो, एक साधारण FIFO क्यू के बजाय priority queue का उपयोग करते हुए। यह चरण-लागत भिन्न होने पर भी optimality बनाए रखता है, केवल किनारे गिनने के बजाय लागतों को ट्रैक व तुलना करने की क़ीमत पर — BFS की optimality गारंटी ठीक वही विशेष स्थिति है जहाँ हर चरण की लागत बराबर हो।

2. सूचित (informed) search: heuristics, greedy best-first search, A*

एक heuristic फ़ंक्शन h(n) अवस्था n से निकटतम लक्ष्य तक की लागत का अनुमान लगाता है, उस डोमेन-ज्ञान का उपयोग करते हुए जिसे uninformed search पूर्णतः अनदेखा करता है। Greedy best-first search सदा उस frontier नोड को विस्तारित करता है जिसका h(n) सबसे कम हो — व्यवहार में तेज़, चूँकि यह सीधे उस ओर जाता है जो लक्ष्य जैसा दिखे, पर optimal नहीं (कोई कम-h(n) पथ फिर भी समग्र रूप से लंबा या महँगा हो सकता है) और लूप के विरुद्ध अतिरिक्त सावधानी के बिना complete नहीं। A* search इसके बजाय उस नोड को विस्तारित करता है जिसका f(n) = g(n) + h(n) सबसे कम हो, अब तक चुकाई गई लागत व शेष अनुमानित लागत का योग, 'अब तक कितना चला हूँ' को 'कितना शेष बचा है' के विरुद्ध संतुलित करते हुए।

ℹ️ Admissibility optimality देती है; consistency दोबारा-विस्तार से बचाती है

कोई heuristic admissible तब होती है जब वह लक्ष्य तक की वास्तविक न्यूनतम लागत को कभी अधिआंकलित न करे, और यही ठीक वह शर्त है जो A* (tree search उपयोग करते हुए) को इष्टतम हल खोजने देती है। कोई heuristic consistent (या monotonic) तब होती है जब, n से पड़ोसी n' तक हर किनारे हेतु, h(n) ≤ cost(n, n') + h(n') हो — एक कठोर शर्त जो अतिरिक्त रूप से यह गारंटी देती है कि A* (graph search उपयोग करते हुए) किसी नोड के एक बार विस्तारित होने के बाद उसे कभी दोबारा विस्तारित करने की ज़रूरत नहीं, क्योंकि पहली बार खोजा गया उसका पथ पहले से ही सबसे सस्ता ज्ञात होता है।

📖 A* एक वास्तविक रोबोट को दिशा देने हेतु बना था

A* को 1968 में Peter Hart, Nils Nilsson व Bertram Raphael द्वारा Stanford Research Institute में प्रकाशित किया गया था, Shakey को नियंत्रित करने वाले सॉफ़्टवेयर के भाग के रूप में — एक आरंभिक चल रोबोट जिसे बाधाओं से भरे किसी कमरे में मार्ग की योजना बनानी होती थी, जो भी ऑन-बोर्ड गणना वह वहन कर सकता था उसका उपयोग करते हुए। एल्गोरिथ्म का पूरा डिज़ाइन-लक्ष्य ठीक वही व्यापार-बंद (trade-off) था जिसे यह खंड वर्णित करता है: uninformed search की अंधी खोज से बचने हेतु एक heuristic उपयोग करें, पर केवल तेज़ दिखने वाले मार्ग के बजाय सबसे छोटा मार्ग खोजने की गारंटी बनाए रखें।

3. Adversarial search: minimax एवं alpha-beta pruning

Minimax किसी दो-खिलाड़ी, zero-sum, नियतात्मक (deterministic) पूर्ण-सूचना खेल पर लागू होता है: यह game tree बनाता है, MAX खिलाड़ी की बारी व MIN खिलाड़ी की बारी को बारी-बारी लेते हुए, हर पत्ती (leaf) को एक मान देता है (जीत/हार/बराबरी, या यदि ट्री जल्दी काट दिया जाए तो एक heuristic मूल्यांकन), और उन मानों को ट्री में ऊपर वापस लाता है — MAX अपनी बारी पर सर्वाधिक मान वाली संतान चुनता है, MIN अपनी बारी पर सबसे कम मान वाली — ताकि मूल (root) पर मान वह परिणाम हो जो दोनों खिलाड़ी उस मान्यता के अंतर्गत पाते हैं कि हर एक दूसरे के विरुद्ध इष्टतम खेलता है।

Alpha-beta pruning वही game tree खोजता है पर किसी भी ऐसी शाखा को काट देता है जो प्रमाणतः अंतिम निर्णय को बदल नहीं सकती, खोज में नीचे ले जाई गई दो सीमाओं का उपयोग करते हुए: α, वह सर्वश्रेष्ठ मान जो MAX पहले ही गारंटी कर सकता है, व β, वह सर्वश्रेष्ठ मान जो MIN पहले ही गारंटी कर सकता है। यह पूर्ण खोज जितना ही minimax मान गणित करता है, कम नोड जाँचते हुए — सर्वश्रेष्ठ स्थिति में, अच्छी तरह क्रमबद्ध ट्री के साथ, प्रभावी शाखा-कारक (branching factor) लगभग आधा हो जाता है, जाँचे गए नोड लगभग bᵈ से घटकर लगभग b^(d/2) रह जाते हैं।

🎯 Alpha-beta pruning एक अनुकूलन है, कोई सन्निकटन नहीं

इसे सटीकता से कहना उपयोगी है, क्योंकि 'pruning' शब्द यह सुझा सकता है कि कुछ छोड़ा जा रहा है: alpha-beta pruning कभी उस अंतिम निर्णय को नहीं बदलता जिस तक minimax पूर्ण खोज से पहुँचता। यह केवल उन शाखाओं को छोड़ता है जिनके मान अब तक स्थापित सीमाओं को देखते हुए उस निर्णय हेतु प्रमाणतः अप्रासंगिक हैं — यह ठीक minimax ही है, बस तेज़ी से गणित किया गया, इसका कोई सस्ता पर जोखिम-भरा विकल्प नहीं।

4. Logic: प्रस्तावीय (propositional) एवं विधेय (predicate)

Propositional logic अणु-प्रस्तावों (atomic propositions, हर एक सत्य या असत्य) से sentences बनाती है जो ¬, ∧, ∨, → व ↔ जोड़कों से संयुक्त हैं। n भिन्न अणुओं हेतु, एक truth table सभी 2ⁿ संभव निर्धारण गिनती है, जिनके विरुद्ध कोई sentence satisfiable है यदि कम-से-कम एक निर्धारण उसे सत्य बनाए, valid (एक tautology) है यदि हर निर्धारण उसे सत्य बनाए, तथा unsatisfiable है यदि कोई निर्धारण उसे सत्य न बनाए। कोई knowledge base KB किसी sentence α को entail करता है (KB ⊨ α लिखा जाता है) ठीक तब जब α हर उस model — हर उस निर्धारण — में सत्य हो जिसमें KB स्वयं सत्य हो।

⚠️ Satisfiable व valid किसी एक पैमाने के विपरीत छोर नहीं हैं

कोई sentence valid हुए बिना satisfiable हो सकता है — कुछ models में सत्य व अन्य में असत्य — जो अधिकांश दिलचस्प sentences की सामान्य स्थिति है, कोई किनारा-मामला नहीं। Valid का अर्थ है हर model में सत्य; unsatisfiable का अर्थ है हर model में असत्य; satisfiable केवल इनमें से दूसरे को रद्द करता है, अतः 'satisfiable' व 'valid' एक-दूसरे का निषेध नहीं हैं, और किसी sentence का satisfiable होना यह कुछ नहीं बताता कि वह valid भी है या नहीं।

First-order (predicate) logic वस्तुएँ, उन वस्तुओं पर predicates, फ़ंक्शन व दो quantifiers — ∀ (सभी हेतु) व ∃ (अस्तित्व है) — जोड़ती है, जो इसे वे तथ्य बताने देते हैं जिन्हें propositional logic के पास व्यक्त करने का कोई सामान्य तरीका नहीं, जैसे 'हर student ने कोई-न-कोई exam पास किया': propositional logic के पास केवल स्थिर अणु-तथ्य हैं, वस्तुओं या उन पर चलने वाले चरों की कोई अवधारणा नहीं, अतः यह उस sentence का एक विशिष्ट उदाहरण तो कूट-बद्ध कर सकती है पर सामान्य quantified कथन को स्वयं नहीं। हर propositional sentence को बिना किसी argument वाले predicate की विशेष स्थिति के रूप में first-order logic में व्यक्त किया जा सकता है, पर हर first-order sentence किसी propositional sentence में घटित नहीं होती — first-order logic दोनों में सख्ती से अधिक अभिव्यंजक है।

5. अनिश्चितता के अंतर्गत तर्क: conditional independence, variable elimination, sampling

X, Y से Z दिए जाने पर सशर्त स्वतंत्र है जब P(X | Y, Z) = P(X | Z) — Z पहले से ज्ञात होने पर Y जानना कुछ नहीं जोड़ता। यही वह है जो कई चरों पर किसी joint distribution को एक ऐसी टेबल के बजाय, जिसमें हर चर के हर मान-संयोजन हेतु एक प्रविष्टि हो और जो चरों की संख्या के साथ घातांकीय रूप से बढ़े, संक्षिप्त ढंग से निरूपित करने देता है। एक Bayesian network इन स्वतंत्रताओं को सीधे निरूपित करता है, एक directed acyclic graph के रूप में जिसमें हर नोड का distribution केवल उसके parents पर सशर्त है — ग्राफ़ की संरचना स्वयं यह कथन है कि मॉडल कौन-सी सशर्त स्वतंत्रताएँ मानता है, केवल उसके साथ खींचा गया कोई चित्र नहीं।

Variable elimination द्वारा exact inference किसी probabilistic प्रश्न का उत्तर non-query, non-evidence चरों को किसी चुने क्रम में एक-एक करके समाप्त करके देता है: समाप्त किए जा रहे हर चर हेतु, यह केवल उन factors (conditional-probability टेबल) को गुणा करता है जो उसका उल्लेख करते हैं, और उस चर को गुणनफल से जोड़कर (marginalise करके) निकाल देता है — सामान्यतः, पूरे joint distribution टेबल को सीधे बनाकर जोड़ने से सस्ता, चूँकि यह कभी पूरे joint को एक साथ भौतिक रूप में नहीं बनाता।

⚠️ Elimination क्रम variable elimination की सटीकता ही नहीं, लागत भी तय करता है

Variable elimination सही उत्तर देता है चाहे चर किसी भी क्रम में समाप्त किए जाएँ, पर बुरी तरह चुना गया क्रम एक साथ कई चरों पर बड़े मध्यवर्ती factors पैदा कर सकता है, जो गणना को उतना ही महँगा बना देता है जितना उस पूरे joint distribution को बनाना जिससे बचना इसका उद्देश्य था — ग्राफ़ की वास्तविक संरचना का लाभ उठाने वाला सुविचारित क्रम ही वह है जो विधि के लाभ को सैद्धांतिक के बजाय वास्तविक बनाए रखता है।

जब exact inference बहुत महँगा हो जाए — जो सामान्यतः बड़े, सघन रूप से जुड़े networks पर होता है — sampling द्वारा approximate inference इसके बजाय प्रश्न का आकलन करता है: यह network के distribution के अनुरूप कई नमूने खींचता है और उत्तर को ठीक-ठीक गणित करने के बजाय उनकी प्रेक्षित आवृत्तियों से गणित करता है। इसकी सटीकता केवल पर्याप्त नमूनों की सीमा में सुधरती है, और यह उन networks तक स्केल करने की क्षमता के बदले सटीकता की गारंटी छोड़ देता है जहाँ exact विधियाँ बिलकुल असंभव हैं।

मुख्य बिंदु

BFS (FIFO क्यू) समान चरण-लागत के साथ complete व optimal है पर स्मृति में घातांकीय; DFS (स्टैक) स्मृति में रैखिक है पर न किसी अनंत स्पेस पर complete न optimal; uniform-cost search priority queue का उपयोग करते हुए BFS की optimality को असमान चरण-लागतों तक सामान्यीकृत करता है।
एक admissible heuristic (कभी अधिआंकलित नहीं करती) A* को optimal बनाती है; एक consistent heuristic अतिरिक्त रूप से गारंटी देती है कि A* किसी नोड को कभी दोबारा विस्तारित नहीं करता — और अकेले h(n) उपयोग करने वाला greedy best-first search तेज़ है पर इनमें से कोई भी गारंटी उस पर लागू नहीं होती।
Alpha-beta pruning कम नोड जाँचते हुए भी वही minimax मान गणित करता है — अच्छी तरह क्रमबद्ध ट्री प्रभावी शाखा-कारक को लगभग आधा कर देता है — और यह उस अंतिम निर्णय को कभी नहीं बदलता जिस तक minimax पहुँचता।
किसी sentence का satisfiable होना (किसी model में सत्य) उसे valid (हर model में सत्य) नहीं बनाता; first-order logic quantifiers व वस्तुओं सहित propositional logic को सख्ती से विस्तारित करती है, अतः हर propositional sentence किसी predicate sentence की विशेष स्थिति है, इसका विलोम नहीं।
Conditional independence वही है जिसे Bayesian network की ग्राफ़-संरचना सीधे कूट-बद्ध करती है; variable elimination किसी प्रश्न का उत्तर चरों को एक-एक करके किसी ऐसे क्रम में जोड़कर देता है जो इसकी लागत तय करता है, और sampling उस सटीकता के बदले उन networks तक स्केल करने की क्षमता देता है जिन्हें exact विधियाँ नहीं संभाल सकतीं।

अभ्यास प्रश्न (18)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

Breadth-first search खोज-frontier को किस डेटा संरचना में रखता है?
1. एक स्टैक
2. एक FIFO क्यू
3. किसी heuristic से क्रमबद्ध priority queue
4. एक हैश टेबल
उत्तर देखें
उत्तर: B — एक FIFO क्यू
BFS frontier नोड को उसी क्रम में विस्तारित करता है जिसमें वे जोड़े गए, जो ठीक वही है जो एक FIFO क्यू देता है — यही इसे स्तर-दर-स्तर खोजने देता है।
किसी अनंत अवस्था-स्पेस पर बिना गहराई-सीमा के चलाया गया depth-first search है
1. complete व optimal
2. complete, पर optimal नहीं
3. न complete न optimal
4. optimal, पर complete नहीं
उत्तर देखें
उत्तर: C — न complete न optimal
DFS एक अनंत शाखा में हमेशा के लिए उतर सकता है और कहीं और मौजूद किसी लक्ष्य तक कभी नहीं पहुँचता, अतः यह complete नहीं है; समाप्त होने पर भी, यह सबसे छोटा पथ खोजने की कोई गारंटी नहीं देता।
Uniform-cost search सदा उस frontier नोड को विस्तारित करता है जिसका सबसे कम हो
1. heuristic अनुमान h(n)
2. अब तक की संचयी path लागत g(n)
3. search tree में गहराई
4. उस नोड पर branching factor
उत्तर देखें
उत्तर: B — अब तक की संचयी path लागत g(n)
Uniform-cost search priority queue का उपयोग करते हुए सदा सबसे कम g(n) से विस्तार करता है, जो इसे चरण-लागत असमान होने पर भी optimal बनाए रखता है।
A* search किस चीज़ के सबसे कम होने के क्रम में नोड विस्तारित करता है
1. अकेला g(n)
2. अकेला h(n)
3. f(n) = g(n) + h(n)
4. शाखा-कारक (branching factor)
उत्तर देखें
उत्तर: C — f(n) = g(n) + h(n)
A* पहले सबसे कम f(n) = g(n) + h(n) विस्तारित करके पहले से चुकाई गई लागत g(n) को अनुमानित शेष लागत h(n) के विरुद्ध संतुलित करता है।
Tree search का उपयोग करने वाला A* search इष्टतम हल खोजने की गारंटी तब देता है जब उसकी heuristic हो
1. consistent
2. admissible
3. सदा ठीक शून्य
4. greedy
उत्तर देखें
उत्तर: B — admissible
Admissibility — सच्ची शेष लागत को कभी अधिआंकलित न करना — वह शर्त है जो tree search के अंतर्गत A* की optimality की गारंटी देती है; consistency एक कठोर शर्त है जो graph search की दोबारा-विस्तार-न-करने की गारंटी हेतु चाहिए।
Greedy best-first search, A* के विपरीत, नोड विस्तारित करने हेतु उपयोग करता है
1. f(n) = g(n) + h(n)
2. अकेला h(n)
3. अकेला g(n)
4. एक यादृच्छिक रूप से चुना क्रम
उत्तर देखें
उत्तर: B — अकेला h(n)
Greedy best-first search उस नोड को विस्तारित करता है जो अकेले h(n) से लक्ष्य के सबसे निकट दिखे, वहाँ तक पहुँचने हेतु पहले से चुकाई गई लागत को अनदेखा करते हुए — यही ठीक कारण है कि यह तेज़ पर non-optimal हो सकता है।
Minimax एल्गोरिथ्म एक ऐसे खेल को मानता है जो है
1. एकल-खिलाड़ी व stochastic
2. दो-खिलाड़ी, zero-sum व नियतात्मक, पूर्ण सूचना सहित
3. सहयोगी, दोनों खिलाड़ियों से छिपी सूचना सहित
4. सतत-मूल्यित व गहराई में अनंत
उत्तर देखें
उत्तर: B — दो-खिलाड़ी, zero-sum व नियतात्मक, पूर्ण सूचना सहित
Minimax ठीक इसी वर्ग के खेल हेतु बना है: दो विरोधी खिलाड़ी, एक zero-sum परिणाम, नियतात्मक transitions, तथा दोनों खिलाड़ियों हेतु अवस्था की पूर्ण दृश्यता।
Alpha-beta pruning, उसी game tree पर plain minimax search की तुलना में,
1. समय बचाने हेतु एक भिन्न, सन्निकट मान गणित करता है
2. कम नोड जाँचते हुए वही minimax मान गणित करता है
3. केवल दो से अधिक खिलाड़ियों वाले खेलों हेतु काम करता है
4. किसी भी पत्ती पर किसी evaluation फ़ंक्शन की ज़रूरत नहीं
उत्तर देखें
उत्तर: B — कम नोड जाँचते हुए वही minimax मान गणित करता है
Alpha-beta pruning केवल उन शाखाओं को छोड़ता है जो अंतिम निर्णय हेतु प्रमाणतः अप्रासंगिक हैं, अतः इसका परिणाम सदा पूर्ण minimax search के समान होता है, बस कम नोड जाँचकर पहुँचा जाता है।
अच्छी तरह क्रमबद्ध game tree के साथ, alpha-beta pruning जाँचे गए प्रभावी नोड की संख्या को लगभग bᵈ से घटाकर लगभग कर देता है
1. bᵈ / 2
2. b^(d/2)
3. log(bᵈ)
4. bᵈ − d
उत्तर देखें
उत्तर: B — b^(d/2)
अच्छी तरह क्रमबद्ध ट्री alpha-beta pruning को प्रभावी शाखा-कारक को लगभग आधा करने देती है, अतः नोड-संख्या लगभग bᵈ से घटकर लगभग b^(d/2) रह जाती है — किसी योज्य या लघुगणकीय कमी से बिलकुल भिन्न।
एक propositional-logic sentence जो हर संभव सत्य-निर्धारण के अंतर्गत सत्य हो, कहलाता है
1. केवल satisfiable
2. valid (एक tautology)
3. unsatisfiable
4. एक contradiction
उत्तर देखें
उत्तर: B — valid (एक tautology)
हर model में सत्य होना ठीक valid (एक tautology) की परिभाषा है; satisfiable को केवल कम-से-कम एक model में सत्य होना चाहिए, जो एक कमज़ोर दावा है।
Propositional logic बनाम first-order (predicate) logic के बारे में निम्न में से कौन-से सत्य हैं?
1. First-order logic quantifiers व वस्तुओं पर predicates जोड़ती है जो propositional logic में नहीं हैं
2. हर propositional-logic sentence को किसी first-order sentence की विशेष स्थिति के रूप में व्यक्त किया जा सकता है
3. Propositional logic 'हर student ने कोई-न-कोई exam पास किया' को first-order logic जितनी ही व्यापकता से व्यक्त कर सकती है
4. First-order logic propositional logic से सख्ती से अधिक अभिव्यंजक है
उत्तर देखें
उत्तर: A — First-order logic quantifiers व वस्तुओं पर predicates जोड़ती है जो propositional logic में नहीं हैं; B — हर propositional-logic sentence को किसी first-order sentence की विशेष स्थिति के रूप में व्यक्त किया जा सकता है; D — First-order logic propositional logic से सख्ती से अधिक अभिव्यंजक है
Propositional logic के पास quantify करने हेतु कोई वस्तुएँ या चर नहीं हैं, अतः यह सामान्य quantified तथ्य नहीं बता सकती — केवल first-order logic बता सकती है, यही ठीक कारण है कि यह दोनों में सख्ती से अधिक अभिव्यंजक है।
किसी Bayesian network की directed acyclic graph संरचना मुख्यतः क्या कूट-बद्ध करती है
1. joint distribution में हर प्रायिकता का संख्यात्मक मान
2. चरों के बीच कौन-सी सशर्त स्वतंत्रता मान्यताएँ लागू होती हैं
3. किसी प्रयोग में चरों को मापने का क्रम
4. डोमेन में चरों की कुल संख्या, और कुछ नहीं
उत्तर देखें
उत्तर: B — चरों के बीच कौन-सी सशर्त स्वतंत्रता मान्यताएँ लागू होती हैं
ग्राफ़ के किनारे (हर नोड केवल अपने parents पर निर्भर) स्वयं यह कथन हैं कि मॉडल कौन-सी सशर्त स्वतंत्रताएँ मानता है; संख्यात्मक प्रायिकताएँ अलग से, हर नोड की conditional probability table में संग्रहित होती हैं।
Variable elimination द्वारा exact inference किसी probabilistic प्रश्न का उत्तर किस प्रकार देता है
1. पूरी joint distribution टेबल को सीधे गिनकर व जोड़कर
2. non-query, non-evidence चरों को एक-एक करके marginalise करके, केवल उन factors को गुणा करते हुए जो हर एक का उल्लेख करते हैं
3. network से यादृच्छिक नमूने खींचकर व उनकी आवृत्तियाँ गिनकर
4. network की संरचना को पूर्णतः अनदेखा करके व केवल prior का उपयोग करके
उत्तर देखें
उत्तर: B — non-query, non-evidence चरों को एक-एक करके marginalise करके, केवल उन factors को गुणा करते हुए जो हर एक का उल्लेख करते हैं
Variable elimination एक बार में एक चर समाप्त करता है, केवल उन factors को गुणा करते हुए जो उसका उल्लेख करते हैं व उसे उस गुणनफल से जोड़कर निकालते हुए — विकल्प 3 का sampling-आधारित वर्णन इसके बजाय approximate inference करता है।
Variable elimination की गणनात्मक लागत भारी रूप से किस पर निर्भर करती है
1. चरों के नामों का वर्णानुक्रम
2. चरों हेतु चुना गया elimination क्रम
3. क्या network आरेख बाएँ-से-दाएँ या ऊपर-से-नीचे बनाया गया है
4. एल्गोरिथ्म को क्रियान्वित करने हेतु उपयोग की गई प्रोग्रामिंग भाषा
उत्तर देखें
उत्तर: B — चरों हेतु चुना गया elimination क्रम
बुरी तरह चुना गया elimination क्रम बड़े मध्यवर्ती factors पैदा कर सकता है, जो गणना को उतना ही महँगा बना देता है जितनी वह पूरी joint distribution जिससे बचना विधि का उद्देश्य है।
Sampling द्वारा approximate inference मुख्यतः तब exact inference से बेहतर हो जाता है जब
1. network में केवल दो चर हों
2. किसी बड़े, सघन रूप से जुड़े network पर variable elimination जैसा exact inference बहुत महँगा हो जाए
3. प्रश्न-चर के बिलकुल कोई parent नोड न हों
4. सभी evidence चर संयोगवश सतत (continuous) हों
उत्तर देखें
उत्तर: B — किसी बड़े, सघन रूप से जुड़े network पर variable elimination जैसा exact inference बहुत महँगा हो जाए
Sampling सटीकता के बदले scalability देता है, जो ठीक तब सार्थक है जब बड़े, सघन रूप से जुड़े networks पर exact विधियाँ गणनात्मक रूप से असंभव हो जाएँ।
graph search के साथ A* में एक ऐसी heuristic उपयोग करना जो admissible है पर consistent नहीं, तो कौन-सी गारंटी विफल हो सकती है
1. एल्गोरिथ्म अब बिलकुल समाप्त ही नहीं होता
2. एक बार विस्तारित नोड को बाद में उस तक कोई सस्ता पथ मिलने पर फिर भी दोबारा विस्तारित करना पड़ सकता है
3. search अब बिलकुल कोई हल नहीं खोजता
4. admissibility स्वयं खोज के बीच में चुपचाप लागू होना बंद कर देती है
उत्तर देखें
उत्तर: B — एक बार विस्तारित नोड को बाद में उस तक कोई सस्ता पथ मिलने पर फिर भी दोबारा विस्तारित करना पड़ सकता है
अकेली admissibility फिर भी एक इष्टतम अंतिम उत्तर देती है, पर consistency के बिना graph search किसी पहले-से-विस्तारित नोड तक बाद में कोई सस्ता पथ खोज सकता है, जो दोबारा-विस्तार को मजबूर करता है — consistency ठीक वह कठोर शर्त है जो इसे रोकती है।
Minimax व alpha-beta pruning के बारे में निम्न में से कौन-से सत्य हैं?
1. Minimax हर बारी पर दोनों खिलाड़ियों से इष्टतम खेल मानता है
2. Alpha-beta pruning उसी ट्री पर plain minimax से भिन्न अंतिम चाल तक पहुँच सकता है
3. Alpha-beta की best-case नोड-कमी (लगभग b^(d/2) तक) एक अच्छी तरह क्रमबद्ध ट्री मानती है
4. Alpha-beta pruning को भी कट-ऑफ गहराई पर एक evaluation फ़ंक्शन चाहिए, ठीक जैसे minimax को
उत्तर देखें
उत्तर: A — Minimax हर बारी पर दोनों खिलाड़ियों से इष्टतम खेल मानता है; C — Alpha-beta की best-case नोड-कमी (लगभग b^(d/2) तक) एक अच्छी तरह क्रमबद्ध ट्री मानती है; D — Alpha-beta pruning को भी कट-ऑफ गहराई पर एक evaluation फ़ंक्शन चाहिए, ठीक जैसे minimax को
Alpha-beta pruning उसी ट्री पर सदा पूर्ण minimax जितने ही निर्णय तक पहुँचता है — दूसरा विकल्प यहाँ ग़लत है; शेष तीन दोनों एल्गोरिथ्मों के मानक, सही गुण हैं।
एक ट्री-आकार का Bayesian network, जहाँ हर चर का अधिकतम एक parent हो, variable elimination जैसे exact inference को किस समय में चलने देता है
1. network के आकार से निरपेक्ष चरों की संख्या में घातांकीय
2. चरों की संख्या में रैखिक
3. उसी आकार के पूर्णतः, सघन रूप से जुड़े network से सदा धीमा
4. अपरिभाषित, क्योंकि ट्री-आकार का network conditional independence निरूपित नहीं कर सकता
उत्तर देखें
उत्तर: B — चरों की संख्या में रैखिक
ट्री-आकार के network की विरल, एकल-parent संरचना का अर्थ है कि variable elimination के मध्यवर्ती factors छोटे रहते हैं, जो रैखिक-समय inference देता है — ठीक वही लाभ जो network की वास्तविक संरचना का उपयोग करने से मिलता है, जिसे किसी सघन network पर बुरी तरह क्रमबद्ध elimination छोड़ देता है।