text:
# sklearn.neighbors.radius_neighbors_graph¶

sklearn.neighbors.radius_neighbors_graph(X, radius, mode=’connectivity’, metric=’minkowski’, p=2, metric_params=None, include_self=False, n_jobs=None)[source]

Computes the (weighted) graph of Neighbors for points in X

Neighborhoods are restricted the points at a distance lower than radius.

Read more in the User Guide.

Parameters: X : array-like or BallTree, shape = [n_samples, n_features] Sample data, in the form of a numpy array or a precomputed BallTree. radius : float Radius of neighborhoods. mode : {‘connectivity’, ‘distance’}, optional Type of returned matrix: ‘connectivity’ will return the connectivity matrix with ones and zeros, and ‘distance’ will return the distances between neighbors according to the given metric. metric : string, default ‘minkowski’ The distance metric used to calculate the neighbors within a given radius for each sample point. The DistanceMetric class gives a list of available metrics. The default distance is ‘euclidean’ (‘minkowski’ metric with the param equal to 2.) p : int, default 2 Power parameter for the Minkowski metric. When p = 1, this is equivalent to using manhattan_distance (l1), and euclidean_distance (l2) for p = 2. For arbitrary p, minkowski_distance (l_p) is used. metric_params : dict, optional additional keyword arguments for the metric function. include_self : bool, default=False Whether or not to mark each sample as the first nearest neighbor to itself. If None, then True is used for mode=’connectivity’ and False for mode=’distance’ as this will preserve backwards compatibility. n_jobs : int or None, optional (default=None) The number of parallel jobs to run for neighbors search. None means 1 unless in a joblib.parallel_backend context. -1 means using all processors. See Glossary for more details. A : sparse matrix in CSR format, shape = [n_samples, n_samples] A[i, j] is assigned the weight of edge that connects i to j.

Examples

>>> X = [[0], [3], [1]]


text:
# Cannot prove inequality

#### idontknow

Prove that $$\displaystyle \: a_n =\frac{|\sin(n)|}{n} +\frac{|\sin(n+1)|}{n+1}>\frac{1}{6}\; ,n\in \mathbb{N}$$.

#### DarnItJimImAnEngineer

Pretty sure that's false.

1 person

#### romsek

Math Team
Pretty sure that's false.
It's pretty clearly false as $|\sin(x)|\leq 1$ and the denominators can increase without limit.

It looks like it's false $\forall n > 12$

1 person

#### romsek

Math Team
The angels are radians .
The angels are playing their harps.

The angles are in radians.

4 people

#### idontknow

The original inequality is $$\displaystyle a_n =\sum_{i=n}^{2n} \frac{|\sin(i)|}{i}>\frac{1}{6}$$.n-radian
Prove that $$\displaystyle a_n = \frac{|\sin(n)|}{n} + \frac{|\sin(n+1)|}{n+1} +...+\frac{|\sin(2n)|}{2n}>\frac{1}{6} \; , n\in \mathbb{N}$$. n-radian
But I'm not being able to prove it. Any hint?

Last edited by a moderator:

#### tahirimanov19

Prove that $$\displaystyle \: a_n =\frac{|\sin(n)|}{n} +\frac{|\sin(n+1)|}{n+1}>\frac{1}{6}\; ,n\in \mathbb{N}$$.
It is true if n<6. Else, it is false.

1 person

#### DarnItJimImAnEngineer

Prove that $$\displaystyle a_n=\displaystyle \frac{|\sin(n)|}{n} +\frac{|\sin(n+1)|}{n+1} +...+\frac{|\sin(2n)|}{2n}>\frac{1}{6} \; , n\in \mathbb{N}$$. n-radian
But I'm not being able to prove it. Any hint?
I would say compare it to $\displaystyle \int_n^{2n} \frac{|\sin~x|}{x} dx$, but the function is not monotonically decreasing, so I don't know how to prove the average value of |sin i| is large enough.

I can tell you practically the sums seem to converge to about 0.4413 for large n, but I don't know how to help with a rigorous proof.

Last edited by a moderator:
2 people

#### tahirimanov19

The original inequality is $$\displaystyle a_n =\sum_{i=n}^{2n} \frac{|\sin(i)|}{i}>\frac{1}{6}$$.n-radian
Prove that $$\displaystyle a_n = \frac{|\sin(n)|}{n} + \frac{|\sin(n+1)|}{n+1} +...+\frac{|\sin(2n)|}{2n}>\frac{1}{6} \; , n\in \mathbb{N}$$. n-radian
But I'm not being able to prove it. Any hint?
$$\left( \prod_{k=n}^{2n} \dfrac{|\sin(k)|}{k} \right)^{\frac{1}{n+1}} \approx 1?$$

Last edited by a moderator:
1 person
Similar threads

format: plain


text:
Appendix 09: Correcting Mass for the Buoyancy of Air

Calibrating a balance does not eliminate all sources of determinate error in the signal. Because of the buoyancy of air, an object always weighs less in air than it does in a vacuum. If there is a difference between the object’s density and the density of the weights used to calibrate the balance, then we can make a correction for buoyancy.1 An object’s true weight in vacuo, $$W_v$$, is related to its weight in air, $$W_a$$, by the equation

$W_\mathrm{v} = W_\ce{a} \times \left[1 + \left(\dfrac{1}{D_\ce{o} } - \dfrac{1}{D_\ce{w}} \right) \times 0.0012 \right] \tag {A9.1}$

where Do is the object’s density, Dw is the density of the calibration weight, and 0.0012 is the density of air under normal laboratory conditions (all densities are in units of g/cm3). The greater the difference between Do and Dw the more serious the error in the object’s measured weight.

The buoyancy correction for a solid is small, and frequently ignored. It may be significant, however, for low density liquids and gases. This is particularly important when calibrating glassware. For example, we can calibrate a volumetric pipet by carefully filling the pipet with water to its calibration mark, dispensing the water into a tared beaker, and determining the water’s mass. After correcting for the buoyancy of air, we use the water’s density to calculate the volume dispensed by the pipet.

Example

A 10-mL volumetric pipet was calibrated following the procedure just outlined, using a balance calibrated with brass weights having a density of 8.40 g/cm3. At 25 oC the pipet dispensed 9.9736 g of water. What is the actual volume dispensed by the pipet and what is the determinate error in this volume if we ignore the buoyancy correction? At 25 oC the density of water is 0.997 05 g/cm3.

Solution

Using equation A9.1 the water’s true weight is

$W_\mathrm{v} = \mathrm{9.9736\: g × \left[1 + \left(\dfrac{1}{0.99705} - \dfrac{1}{8.40}\right) × 0.0012\right] = 9.9842}$

and the actual volume of water dispensed by the pipet is

$\mathrm{\dfrac{9.9842\: g}{0.99705\: g/cm^3} = 10.014\: cm^3 = 10.014\: mL}$

If we ignore the buoyancy correction, then we report the pipet’s volume as

$\mathrm{\dfrac{9.9736\: g}{0.99705\: g/cm^3} = 10.003\: cm^3 = 10.003\: mL}$

introducing a negative determinate error of -0.11%.

Problems

The following problems will help you in considering the effect of buoyancy on the measurement of mass.

1. In calibrating a 10-mL pipet a measured volume of water was transferred to a tared flask and weighed, yielding a mass of 9.9814 grams. (a) Calculate, with and without correcting for buoyancy, the volume of water delivered by the pipet. Assume that the density of water is 0.99707 g/cm3 and that the density of the weights is 8.40 g/cm3. (b) What are the absolute and relative errors introduced by failing to account for the effect of buoyancy? Is this a significant source of determinate error for the calibration of a pipet? Explain.
2. Repeat the questions in problem 1 for the case where a mass of 0.2500 g is measured for a solid that has a density of 2.50 g/cm3.
3. Is the failure to correct for buoyancy a constant or proportional source of determinate error?
4. What is the minimum density of a substance necessary to keep the buoyancy correction to less than 0.01% when using brass calibration weights with a density of 8.40 g/cm3?

References

1. Battino, R.; Williamson, A. G. J. Chem. Educ. 1984, 61, 51–52.


text:
# source:doc/theses/andrew_beach_MMath/features.tex@33e1c91

Last change on this file since 33e1c91 was 33e1c91, checked in by Andrew Beach <ajbeach@…>, 20 months ago

Andrew MMath: Some feedback for additions to implement went to features instead.

• Property mode set to 100644
File size: 34.2 KB
Line
1\chapter{Exception Features}
2\label{c:features}
3
4This chapter covers the design and user interface of the \CFA EHM
5and begins with a general overview of EHMs. It is not a strict
6definition of all EHMs nor an exhaustive list of all possible features.
7However it does cover the most common structure and features found in them.
8
9\section{Overview of EHMs}
10% We should cover what is an exception handling mechanism and what is an
11% exception before this. Probably in the introduction. Some of this could
12% move there.
13\subsection{Raise / Handle}
14An exception operation has two main parts: raise and handle.
15These terms are sometimes known as throw and catch but this work uses
16throw/catch as a particular kind of raise/handle.
17These are the two parts that the user writes and may
18be the only two pieces of the EHM that have any syntax in the language.
19
20\paragraph{Raise}
21The raise is the starting point for exception handling. It marks the beginning
22of exception handling by raising an exception, which passes it to
23the EHM.
24
25Some well known examples include the @throw@ statements of \Cpp and Java and
26the \code{Python}{raise} statement from Python. In real systems a raise may
27preform some other work (such as memory management) but for the
28purposes of this overview that can be ignored.
29
30\paragraph{Handle}
31The purpose of most exception operations is to run some user code to handle
32that exception. This code is given, with some other information, in a handler.
33
34A handler has three common features: the previously mentioned user code, a
35region of code they guard and an exception label/condition that matches
36certain exceptions.
37Only raises inside the guarded region and raising exceptions that match the
38label can be handled by a given handler.
39If multiple handlers could can handle an exception,
40EHMs will define a rule to pick one, such as best match" or first found".
41
42The @try@ statements of \Cpp, Java and Python are common examples. All three
43also show another common feature of handlers, they are grouped by the guarded
44region.
45
46\subsection{Propagation}
47After an exception is raised comes what is usually the biggest step for the
48EHM: finding and setting up the handler. The propagation from raise to
49handler can be broken up into three different tasks: searching for a handler,
50matching against the handler and installing the handler.
51
52\paragraph{Searching}
53The EHM begins by searching for handlers that might be used to handle
54the exception. Searching is usually independent of the exception that was
55thrown as it looks for handlers that have the raise site in their guarded
56region.
57The search includes handlers in the current function, as well as any in
58callers on the stack that have the function call in their guarded region.
59
60\paragraph{Matching}
61Each handler found has to be matched with the raised exception. The exception
62label defines a condition that is used with exception and decides if
63there is a match or not.
64
65In languages where the first match is used, this step is intertwined with
66searching; a match check is preformed immediately after the search finds
67a possible handler.
68
69\paragraph{Installing}
70After a handler is chosen it must be made ready to run.
71The implementation can vary widely to fit with the rest of the
72design of the EHM. The installation step might be trivial or it could be
73the most expensive step in handling an exception. The latter tends to be the
74case when stack unwinding is involved.
75
76If a matching handler is not guaranteed to be found, the EHM needs a
77different course of action for the case where no handler matches.
78This situation only occurs with unchecked exceptions as checked exceptions
79(such as in Java) can make the guarantee.
80This unhandled action is usually very general, such as aborting the program.
81
82\paragraph{Hierarchy}
83A common way to organize exceptions is in a hierarchical structure.
84This pattern comes from object-orientated languages where the
85exception hierarchy is a natural extension of the object hierarchy.
86
87Consider the following hierarchy of exceptions:
88\begin{center}
89\input{exception-hierarchy}
90\end{center}
91
92A handler labeled with any given exception can handle exceptions of that
93type or any child type of that exception. The root of the exception hierarchy
94(here \code{C}{exception}) acts as a catch-all, leaf types catch single types
95and the exceptions in the middle can be used to catch different groups of
96related exceptions.
97
98This system has some notable advantages, such as multiple levels of grouping,
99the ability for libraries to add new exception types and the isolation
100between different sub-hierarchies.
101This design is used in \CFA even though it is not a object-orientated
102language; so different tools are used to create the hierarchy.
103
104% Could I cite the rational for the Python IO exception rework?
105
106\subsection{Completion}
107After the handler has finished, the entire exception operation has to complete
108and continue executing somewhere else. This step is usually simple,
109both logically and in its implementation, as the installation of the handler
110is usually set up to do most of the work.
111
112The EHM can return control to many different places,
113the most common are after the handler definition (termination)
114and after the raise (resumption).
115
116\subsection{Communication}
117For effective exception handling, additional information is often passed
118from the raise to the handler and back again.
119So far only communication of the exceptions' identity has been covered.
120A common communication method is putting fields into the exception instance
122Passing the exception by reference instead of by value can allow data to be
123passed in both directions.
124
125\section{Virtuals}
126Virtual types and casts are not part of \CFA's EHM nor are they required for
127any EHM.
128However, it is one of the best ways to support an exception hierarchy
129is via a virtual hierarchy and dispatch system.
130
131Ideally, the virtual system would have been part of \CFA before the work
132on exception handling began, but unfortunately it was not.
133Hence, only the features and framework needed for the EHM were
134designed and implemented. Other features were considered to ensure that
135the structure could accommodate other desirable features in the future
136but they were not implemented.
137The rest of this section will only discuss the implemented subset of the
138virtual system design.
139
140The virtual system supports multiple trees" of types. Each tree is
141a simple hierarchy with a single root type. Each type in a tree has exactly
142one parent -- except for the root type which has zero parents -- and any
143number of children.
144Any type that belongs to any of these trees is called a virtual type.
145
146% A type's ancestors are its parent and its parent's ancestors.
147% The root type has no ancestors.
148% A type's descendants are its children and its children's descendants.
149
150Every virtual type also has a list of virtual members. Children inherit
151their parent's list of virtual members but may add new members to it.
152It is important to note that these are virtual members, not virtual methods
153of object-orientated programming, and can be of any type.
154
155\CFA still supports virtual methods as a special case of virtual members.
156Function pointers that take a pointer to the virtual type are modified
157with each level of inheritance so that refers to the new type.
158This means an object can always be passed to a function in its virtual table
159as if it were a method.
160\todo{Clarify (with an example) virtual methods.}
161
162Each virtual type has a unique id.
163This id and all the virtual members are combined
164into a virtual table type. Each virtual type has a pointer to a virtual table
165as a hidden field.
166\todo{Might need a diagram for virtual structure.}
167
168Up until this point the virtual system is similar to ones found in
169object-orientated languages but this where \CFA diverges. Objects encapsulate a
170single set of behaviours in each type, universally across the entire program,
171and indeed all programs that use that type definition. In this sense, the
172types are closed" and cannot be altered.
173
174In \CFA, types do not encapsulate any behaviour. Traits are local and
175types can begin to satisfy a trait, stop satisfying a trait or satisfy the same
176trait in a different way at any lexical location in the program.
177In this sense, they are open" as they can change at any time.
178This capability means it is impossible to pick a single set of functions
179that represent the type's implementation across the program.
180
181\CFA side-steps this issue by not having a single virtual table for each
182type. A user can define virtual tables that are filled in at their
183declaration and given a name. Anywhere that name is visible, even if it is
184defined locally inside a function (although that means it does not have a
185static lifetime), it can be used.
186Specifically, a virtual type is bound" to a virtual table that
187sets the virtual members for that object. The virtual members can be accessed
188through the object.
189
190While much of the virtual infrastructure is created, it is currently only used
191internally for exception handling. The only user-level feature is the virtual
192cast, which is the same as the \Cpp \code{C++}{dynamic_cast}.
193\label{p:VirtualCast}
194\begin{cfa}
195(virtual TYPE)EXPRESSION
196\end{cfa}
197Note, the syntax and semantics matches a C-cast, rather than the function-like
198\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
199a pointer to a virtual type.
200The cast dynamically checks if the @EXPRESSION@ type is the same or a sub-type
201of @TYPE@, and if true, returns a pointer to the
202@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
203
204\section{Exception}
205% Leaving until later, hopefully it can talk about actual syntax instead
206% of my many strange macros. Syntax aside I will also have to talk about the
207% features all exceptions support.
208
209Exceptions are defined by the trait system; there are a series of traits, and
210if a type satisfies them, then it can be used as an exception. The following
211is the base trait all exceptions need to match.
212\begin{cfa}
213trait is_exception(exceptT &, virtualT &) {
214        // Numerous imaginary assertions.
215};
216\end{cfa}
217The trait is defined over two types, the exception type and the virtual table
218type. Each exception type should have a single virtual table type.
219There are no actual assertions in this trait because the trait system
220cannot express them yet (adding such assertions would be part of
221completing the virtual system). The imaginary assertions would probably come
222from a trait defined by the virtual system, and state that the exception type
223is a virtual type, is a descendant of @exception_t@ (the base exception type)
224and note its virtual table type.
225
226% I did have a note about how it is the programmer's responsibility to make
227% sure the function is implemented correctly. But this is true of every
228% similar system I know of (except Agda's I guess) so I took it out.
229
230There are two more traits for exceptions defined as follows:
231\begin{cfa}
232trait is_termination_exception(
233                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
234        void defaultTerminationHandler(exceptT &);
235};
236
237trait is_resumption_exception(
238                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
239        void defaultResumptionHandler(exceptT &);
240};
241\end{cfa}
242Both traits ensure a pair of types are an exception type, its virtual table
243type
244and defines one of the two default handlers. The default handlers are used
245as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
246
247However, all three of these traits can be tricky to use directly.
248While there is a bit of repetition required,
249the largest issue is that the virtual table type is mangled and not in a user
250facing way. So these three macros are provided to wrap these traits to
251simplify referring to the names:
252@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
253
254All three take one or two arguments. The first argument is the name of the
255exception type. The macro passes its unmangled and mangled form to the trait.
256The second (optional) argument is a parenthesized list of polymorphic
257arguments. This argument is only used with polymorphic exceptions and the
258list is be passed to both types.
259In the current set-up, the two types always have the same polymorphic
260arguments so these macros can be used without losing flexibility.
261
262For example consider a function that is polymorphic over types that have a
263defined arithmetic exception:
264\begin{cfa}
265forall(Num | IS_EXCEPTION(Arithmetic, (Num)))
266void some_math_function(Num & left, Num & right);
267\end{cfa}
268
269\section{Exception Handling}
270\label{s:ExceptionHandling}
271As stated,
272\CFA provides two kinds of exception handling: termination and resumption.
273These twin operations are the core of \CFA's exception handling mechanism.
274This section will cover the general patterns shared by the two operations and
275then go on to cover the details each individual operation.
276
277Both operations follow the same set of steps.
279Then the exception propagates up the stack.
280If a handler is found the exception is caught and the handler is run.
281After that control continues at a raise-dependent location.
282If the search fails a default handler is run and, if it returns, then control
283continues after the raise.
284
285This general description covers what the two kinds have in common.
286Differences include how propagation is preformed, where exception continues
287after an exception is caught and handled and which default handler is run.
288
289\subsection{Termination}
290\label{s:Termination}
291Termination handling is the familiar kind and used in most programming
292languages with exception handling.
293It is a dynamic, non-local goto. If the raised exception is matched and
294handled, the stack is unwound and control (usually) continues in the function
295on the call stack that defined the handler.
296Termination is commonly used when an error has occurred and recovery is
297impossible locally.
298
299% (usually) Control can continue in the current function but then a different
300% control flow construct should be used.
301
302A termination raise is started with the @throw@ statement:
303\begin{cfa}
304throw EXPRESSION;
305\end{cfa}
306The expression must return a reference to a termination exception, where the
307termination exception is any type that satisfies the trait
308@is_termination_exception@ at the call site.
309Through \CFA's trait system, the trait functions are implicitly passed into the
310throw code and the EHM.
311A new @defaultTerminationHandler@ can be defined in any scope to
312change the throw's behaviour (see below).
313
314The throw copies the provided exception into managed memory to ensure
315the exception is not destroyed if the stack is unwound.
316It is the user's responsibility to ensure the original exception is cleaned
317up whether the stack is unwound or not. Allocating it on the stack is
318usually sufficient.
319
320% How to say propagation starts, its first sub-step is the search.
321Then propagation starts with the search. \CFA uses a first match" rule so
322matching is preformed with the copied exception as the search continues.
323It starts from the throwing function and proceeds towards base of the stack,
324from callee to caller.
325At each stack frame, a check is made for resumption handlers defined by the
326@catch@ clauses of a @try@ statement.
327\begin{cfa}
328try {
329        GUARDED_BLOCK
330} catch (EXCEPTION_TYPE$$$_1$$$ * [NAME$$$_1$$$]) {
331        HANDLER_BLOCK$$$_1$$$
332} catch (EXCEPTION_TYPE$$$_2$$$ * [NAME$$$_2$$$]) {
333        HANDLER_BLOCK$$$_2$$$
334}
335\end{cfa}
336When viewed on its own, a try statement simply executes the statements
337in \snake{GUARDED_BLOCK} and when those are finished,
338the try statement finishes.
339
340However, while the guarded statements are being executed, including any
341invoked functions, all the handlers in these statements are included in the
342search path.
343Hence, if a termination exception is raised these handlers may be matched
344against the exception and may handle it.
345
346Exception matching checks the handler in each catch clause in the order
347they appear, top to bottom. If the representation of the raised exception type
348is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
349(if provided) is
350bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
351are executed. If control reaches the end of the handler, the exception is
352freed and control continues after the try statement.
353
354If no termination handler is found during the search then the default handler
355(\defaultTerminationHandler) visible at the raise statement is run.
356Through \CFA's trait system the best match at the raise statement will be used.
357This function is run and is passed the copied exception.
358If the default handler is run control continues after the raise statement.
359
360There is a global @defaultTerminationHandler@ that is polymorphic over all
361termination exception types.
362Since it is so general a more specific handler can be
363defined and is used for those types, effectively overriding the handler
364for a particular exception type.
365The global default termination handler performs a cancellation
366(see \vref{s:Cancellation}) on the current stack with the copied exception.
367
368\subsection{Resumption}
369\label{s:Resumption}
370
371Resumption exception handling is less common than termination but is
372just as old~\cite{Goodenough75} and is simpler in many ways.
373It is a dynamic, non-local function call. If the raised exception is
374matched a closure is taken from up the stack and executed,
375after which the raising function continues executing.
376The common uses for resumption exceptions include
377potentially repairable errors, where execution can continue in the same
378function once the error is corrected, and
379ignorable events, such as logging where nothing needs to happen and control
380should always continue from the same place.
381
382A resumption raise is started with the @throwResume@ statement:
383\begin{cfa}
384throwResume EXPRESSION;
385\end{cfa}
386\todo{Decide on a final set of keywords and use them everywhere.}
387It works much the same way as the termination throw.
388The expression must return a reference to a resumption exception,
389where the resumption exception is any type that satisfies the trait
390@is_resumption_exception@ at the call site.
391The assertions from this trait are available to
392the exception system while handling the exception.
393
394At run-time, no exception copy is made.
395Resumption does not unwind the stack nor otherwise remove values from the
396current scope, so there is no need to manage memory to keep things in scope.
397
398The EHM then begins propagation. The search starts from the raise in the
399resuming function and proceeds towards the base of the stack,
400from callee to caller.
401At each stack frame, a check is made for resumption handlers defined by the
402@catchResume@ clauses of a @try@ statement.
403\begin{cfa}
404try {
405        GUARDED_BLOCK
406} catchResume (EXCEPTION_TYPE$$$_1$$$ * [NAME$$$_1$$$]) {
407        HANDLER_BLOCK$$$_1$$$
408} catchResume (EXCEPTION_TYPE$$$_2$$$ * [NAME$$$_2$$$]) {
409        HANDLER_BLOCK$$$_2$$$
410}
411\end{cfa}
412% I wonder if there would be some good central place for this.
413Note that termination handlers and resumption handlers may be used together
414in a single try statement, intermixing @catch@ and @catchResume@ freely.
415Each type of handler only interacts with exceptions from the matching
416kind of raise.
417When a try statement is executed, it simply executes the statements in the
418@GUARDED_BLOCK@ and then finishes.
419
420However, while the guarded statements are being executed, including any
421invoked functions, all the handlers in these statements are included in the
422search path.
423Hence, if a resumption exception is raised these handlers may be matched
424against the exception and may handle it.
425
426Exception matching checks the handler in each catch clause in the order
427they appear, top to bottom. If the representation of the raised exception type
428is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
429(if provided) is bound to a pointer to the exception and the statements in
430@HANDLER_BLOCK@$_i$ are executed.
431If control reaches the end of the handler, execution continues after the
432the raise statement that raised the handled exception.
433
434Like termination, if no resumption handler is found during the search,
435the default handler (\defaultResumptionHandler) visible at the raise
436statement is called. It will use the best match at the raise sight according
438passed the exception given to the raise. When the default handler finishes
439execution continues after the raise statement.
440
441There is a global \defaultResumptionHandler{} is polymorphic over all
442resumption exceptions and preforms a termination throw on the exception.
443The \defaultTerminationHandler{} can be overridden by providing a new
444function that is a better match.
445
446\subsubsection{Resumption Marking}
447\label{s:ResumptionMarking}
448A key difference between resumption and termination is that resumption does
449not unwind the stack. A side effect that is that when a handler is matched
450and run it's try block (the guarded statements) and every try statement
451searched before it are still on the stack. There presence can lead to
452the recursive resumption problem.
453
454The recursive resumption problem is any situation where a resumption handler
455ends up being called while it is running.
456Consider a trivial case:
457\begin{cfa}
458try {
459        throwResume (E &){};
460} catchResume(E *) {
461        throwResume (E &){};
462}
463\end{cfa}
464When this code is executed, the guarded @throwResume@ starts a
465search and matches the handler in the @catchResume@ clause. This
466call is placed on the stack above the try-block. The second raise then
467searches the same try block and puts another instance of the
468same handler on the stack leading to infinite recursion.
469
470While this situation is trivial and easy to avoid, much more complex cycles
471can form with multiple handlers and different exception types.
472
473To prevent all of these cases, a each try statement is marked" from the
474time the exception search reaches it to either when the exception is being
475handled completes the matching handler or when the search reaches the base
476of the stack.
477While a try statement is marked, its handlers are never matched, effectively
478skipping over it to the next try statement.
479
480\begin{center}
481\input{stack-marking}
482\end{center}
483
484There are other sets of marking rules that could be used,
485for instance, marking just the handlers that caught the exception,
486would also prevent recursive resumption.
487However, these rules mirror what happens with termination.
488
489The try statements that are marked are the ones that would be removed from
490the stack if this was a termination exception, that is those on the stack
491between the handler and the raise statement.
492This symmetry applies to the default handler as well, as both kinds of
493default handlers are run at the raise statement, rather than (physically
494or logically) at the bottom of the stack.
495% In early development having the default handler happen after
496% unmarking was just more useful. We assume that will continue.
497
498\section{Conditional Catch}
499Both termination and resumption handler clauses can be given an additional
500condition to further control which exceptions they handle:
501\begin{cfa}
502catch (EXCEPTION_TYPE * [NAME] ; CONDITION)
503\end{cfa}
504First, the same semantics is used to match the exception type. Second, if the
505exception matches, @CONDITION@ is executed. The condition expression may
506reference all names in scope at the beginning of the try block and @NAME@
507introduced in the handler clause. If the condition is true, then the handler
508matches. Otherwise, the exception search continues as if the exception type
509did not match.
510
511The condition matching allows finer matching by checking
512more kinds of information than just the exception type.
513\begin{cfa}
514try {
515        handle1 = open( f1, ... );
516        handle2 = open( f2, ... );
517        handle3 = open( f3, ... );
518        ...
519} catch( IOFailure * f ; fd( f ) == f1 ) {
520        // Only handle IO failure for f1.
521} catch( IOFailure * f ; fd( f ) == f3 ) {
522        // Only handle IO failure for f3.
523}
524// Can't handle a failure relating to f2 here.
525\end{cfa}
526In this example the file that experienced the IO error is used to decide
527which handler should be run, if any at all.
528
529\begin{comment}
530% I know I actually haven't got rid of them yet, but I'm going to try
531% to write it as if I had and see if that makes sense:
532\section{Reraising}
533\label{s:Reraising}
534Within the handler block or functions called from the handler block, it is
535possible to reraise the most recently caught exception with @throw@ or
536@throwResume@, respectively.
537\begin{cfa}
538try {
539        ...
540} catch( ... ) {
541        ... throw;
542} catchResume( ... ) {
543        ... throwResume;
544}
545\end{cfa}
546The only difference between a raise and a reraise is that reraise does not
547create a new exception; instead it continues using the current exception, \ie
548no allocation and copy. However the default handler is still set to the one
549visible at the raise point, and hence, for termination could refer to data that
550is part of an unwound stack frame. To prevent this problem, a new default
551handler is generated that does a program-level abort.
552\end{comment}
553
554\subsection{Comparison with Reraising}
555A more popular way to allow handlers to match in more detail is to reraise
556the exception after it has been caught, if it could not be handled here.
557On the surface these two features seem interchangeable.
558
559If @throw;@ (no argument) starts a termination reraise,
560which is the same as a raise but reuses the last caught exception,
561then these two statements have the same behaviour:
562\begin{cfa}
563try {
564    do_work_may_throw();
565} catch(exception_t * exc ; can_handle(exc)) {
566    handle(exc);
567}
568\end{cfa}
569
570\begin{cfa}
571try {
572    do_work_may_throw();
573} catch(exception_t * exc) {
574    if (can_handle(exc)) {
575        handle(exc);
576    } else {
577        throw;
578    }
579}
580\end{cfa}
581That is, they will have the same behaviour in isolation.
582Two things can expose differences between these cases.
583
584One is the existence of multiple handlers on a single try statement.
585A reraise skips all later handlers on this try statement but a conditional
586catch does not.
587Hence, if an earlier handler contains a reraise later handlers are
588implicitly skipped, with a conditional catch they are not.
589Still, they are equivalently powerful,
590both can be used two mimic the behaviour of the other,
591as reraise can pack arbitrary code in the handler and conditional catches
592can put arbitrary code in the predicate.
593% I was struggling with a long explanation about some simple solutions,
594% like repeating a condition on later handlers, and the general solution of
595% merging everything together. I don't think it is useful though unless its
596% for a proof.
597% https://en.cppreference.com/w/cpp/language/throw
598
599The question then becomes Which is a better default?"
600We believe that not skipping possibly useful handlers is a better default.
601If a handler can handle an exception it should and if the handler can not
602handle the exception then it is probably safer to have that explicitly
603described in the handler itself instead of implicitly described by its
604ordering with other handlers.
605% Or you could just alter the semantics of the throw statement. The handler
606% index is in the exception so you could use it to know where to start
607% searching from in the current try statement.
608% No place for the goto else; metaphor.
609
610The other issue is all of the discussion above assumes that the only
611way to tell apart two raises is the exception being raised and the remaining
612search path.
613This is not true generally, the current state of the stack can matter in
614a number of cases, even only for a stack trace after an program abort.
615But \CFA has a much more significant need of the rest of the stack, the
616default handlers for both termination and resumption.
617
618% For resumption it turns out it is possible continue a raise after the
619% exception has been caught, as if it hadn't been caught in the first place.
620This becomes a problem combined with the stack unwinding used in termination
621exception handling.
622The stack is unwound before the handler is installed, and hence before any
623reraises can run. So if a reraise happens the previous stack is gone,
624the place on the stack where the default handler was supposed to run is gone,
625if the default handler was a local function it may have been unwound too.
626There is no reasonable way to restore that information, so the reraise has
627to be considered as a new raise.
628This is the strongest advantage conditional catches have over reraising,
629they happen before stack unwinding and avoid this problem.
630
631% The one possible disadvantage of conditional catch is that it runs user
632% code during the exception search. While this is a new place that user code
633% can be run destructors and finally clauses are already run during the stack
634% unwinding.
635%
636% https://www.cplusplus.com/reference/exception/current_exception/
637%   exception_ptr current_exception() noexcept;
638% https://www.python.org/dev/peps/pep-0343/
639
640\section{Finally Clauses}
641\label{s:FinallyClauses}
642Finally clauses are used to preform unconditional clean-up when leaving a
643scope and are placed at the end of a try statement after any handler clauses:
644\begin{cfa}
645try {
646        GUARDED_BLOCK
647} ... // any number or kind of handler clauses
648... finally {
649        FINALLY_BLOCK
650}
651\end{cfa}
652The @FINALLY_BLOCK@ is executed when the try statement is removed from the
653stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
654finishes or during an unwind.
655The only time the block is not executed is if the program is exited before
656the stack is unwound.
657
658Execution of the finally block should always finish, meaning control runs off
659the end of the block. This requirement ensures control always continues as if
660the finally clause is not present, \ie finally is for cleanup not changing
661control flow.
662Because of this requirement, local control flow out of the finally block
663is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
664@return@ that causes control to leave the finally block. Other ways to leave
665the finally block, such as a long jump or termination are much harder to check,
667discouraged.
668
669Not all languages with unwinding have finally clauses. Notably \Cpp does
670without it as descructors, and the RAII design pattern, serve a similar role.
671Although destructors and finally clauses can be used in the same cases,
672they have their own strengths, similar to top-level function and lambda
673functions with closures.
674Destructors take more work for their first use, but if there is clean-up code
675that needs to be run every time a type is used they soon become much easier
676to set-up.
677On the other hand finally clauses capture the local context, so is easy to
678use when the clean-up is not dependent on the type of a variable or requires
679information from multiple variables.
680% To Peter: I think these are the main points you were going for.
681
682\section{Cancellation}
683\label{s:Cancellation}
684Cancellation is a stack-level abort, which can be thought of as as an
685uncatchable termination. It unwinds the entire current stack, and if
686possible forwards the cancellation exception to a different stack.
687
688Cancellation is not an exception operation like termination or resumption.
689There is no special statement for starting a cancellation; instead the standard
690library function @cancel_stack@ is called passing an exception. Unlike a
691raise, this exception is not used in matching only to pass information about
692the cause of the cancellation.
693(This also means matching cannot fail so there is no default handler.)
694
695After @cancel_stack@ is called the exception is copied into the EHM's memory
696and the current stack is unwound.
697The behaviour after that depends on the kind of stack being cancelled.
698
699\paragraph{Main Stack}
700The main stack is the one used by the program main at the start of execution,
701and is the only stack in a sequential program.
702After the main stack is unwound there is a program-level abort.
703
704There are two reasons for these semantics.
705The first is that it had to do this abort.
706in a sequential program as there is nothing else to notify and the simplicity
707of keeping the same behaviour in sequential and concurrent programs is good.
708Also, even in concurrent programs there may not currently be any other stacks
709and even if other stacks do exist, main has no way to know where they are.
710
712A thread stack is created for a \CFA @thread@ object or object that satisfies
714After a thread stack is unwound, the exception is stored until another
716which stores a reference to the thread and to the exception passed to the
717cancellation, is reported from the join to the joining thread.
718There is one difference between an explicit join (with the @join@ function)
719and an implicit join (from a destructor call). The explicit join takes the
720default handler (@defaultResumptionHandler@) from its calling context while
721the implicit join provides its own; which does a program abort if the
723
724The communication and synchronization are done here because threads only have
725two structural points (not dependent on user-code) where
726communication/synchronization happens: start and join.
727Since a thread must be running to perform a cancellation (and cannot be
728cancelled from another stack), the cancellation must be after start and
729before the join, so join is used.
730
731% TODO: Find somewhere to discuss unwind collisions.
732The difference between the explicit and implicit join is for safety and
733debugging. It helps prevent unwinding collisions by avoiding throwing from
735the user is not equipped to deal with it.
736It is always possible to add an explicit join if that is the desired behaviour.
737
738With explicit join and a default handler that triggers a cancellation, it is
739possible to cascade an error across any number of threads, cleaning up each
740in turn, until the error is handled or the main thread is reached.
741
742\paragraph{Coroutine Stack}
743A coroutine stack is created for a @coroutine@ object or object that
744satisfies the @is_coroutine@ trait.
745After a coroutine stack is unwound, control returns to the @resume@ function
746that most recently resumed it. @resume@ reports a
747@CoroutineCancelled@ exception, which contains a references to the cancelled
748coroutine and the exception used to cancel it.
749The @resume@ function also takes the \defaultResumptionHandler{} from the
750caller's context and passes it to the internal report.
751
752A coroutine knows of two other coroutines, its starter and its last resumer.
753The starter has a much more distant connection, while the last resumer just
754(in terms of coroutine state) called resume on this coroutine, so the message
755is passed to the latter.
756
757With a default handler that triggers a cancellation, it is possible to
758cascade an error across any number of coroutines, cleaning up each in turn,
759until the error is handled or a thread stack is reached.
Note: See TracBrowser for help on using the repository browser.


text:
# 15

Personal Blog

Outline: I describe a flaw in UDT that has to do with the way the agent defines itself (locates itself in the universe). This flaw manifests in failure to solve a certain class of decision problems. I suggest several related decision theories that solve the problem, some of which avoid quining thus being suitable for agents that cannot access their own source code.

EDIT: The decision problem I call here the "anti-Newcomb problem" already appeared here. Some previous solution proposals are here. A different but related problem appeared here.

Updateless decision theory, the way it is usually defined, postulates that the agent has to use quining in order to formalize its identity, i.e. determine which portions of the universe are considered to be affected by its decisions. This leaves the question of which decision theory should agents that don't have access to their source code use (as humans intuitively appear to be). I am pretty sure this question has already been posed somewhere on LessWrong but I can't find the reference: help? It also turns out that there is a class of decision problems for which this formalization of identity fails to produce the winning answer.

When one is programming an AI, it doesn't seem optimal for the AI to locate itself in the universe based solely on its own source code. After all, you build the AI, you know where it is (e.g. running inside a robot), why should you allow the AI to consider itself to be something else, just because this something else happens to have the same source code (more realistically, happens to have a source code correlated in the sense of logical uncertainty)?

Consider the following decision problem which I call the "UDT anti-Newcomb problem". Omega is putting money into boxes by the usual algorithm, with one exception. It isn't simulating the player at all. Instead, it simulates what would a UDT agent do in the player's place. Thus, a UDT agent would consider the problem to be identical to the usual Newcomb problem and one-box, receiving $1,000,000. On the other hand, a CDT agent (say) would two-box and receive$1,000,1000 (!) Moreover, this problem reveals UDT is not reflectively consistent. A UDT agent facing this problem would choose to self-modify given the choiceThis is not an argument in favor of CDT. But it is a sign something is wrong with UDT, the way it's usually done.

The essence of the problem is that a UDT agent is using too little information to define its identity: its source code. Instead, it should use information about its origin. Indeed, if the origin is an AI programmer or a version of the agent before the latest self-modification, it appears rational for the precursor agent to code the origin into the successor agent. In fact, if we consider the anti-Newcomb problem with Omega's simulation using the correct decision theory XDT (whatever it is), we expect an XDT agent to two-box and leave with $1000. This might seem surprising, but consider the problem from the precursor's point of view. The precursor knows Omega is filling the boxes based on XDT, whatever the decision theory of the successor is going to be. If the precursor knows XDT two-boxes, there is no reason to construct a successor that one-boxes. So constructing an XDT successor might be perfectly rational! Moreover, a UDT agent playing the XDT anti-Newcomb problem will also two-box (correctly). To formalize the idea, consider a program $P$ called the precursor which outputs a new program $A$ called the successor. In addition, we have a program $U$ called the universe which outputs a number $U()$ called utility. Usual UDT suggests for $A$ the following algorithm: (1) $A(i):=(\underset{f:I \rightarrow O}{\arg\max} \: E[U()|\forall j \in I: A(j)=f(j)])(i)$ Here, $I$ is the input space, $O$ is the output space and the expectation value is over logical uncertainty. $A$ appears inside its own definition via quining. The simplest way to tweak equation (1) in order to take the precursor into account is (2) $A(i):=(\underset{f:I \rightarrow O}{\arg\max} \: E[U()|\forall j \in I: P()(j)=f(j)])(i)$ This seems nice since quining is avoided altogether. However, this is unsatisfactory. Consider the anti-Newcomb problem with Omega's simulation involving equation (2). Suppose the successor uses equation (2) as well. On the surface, if Omega's simulation doesn't involve $P$1, the agent will two-box and get$1000 as it should. However, the computing power allocated for evaluation the logical expectation value in (2) might be sufficient to suspect $P$'s output might be an agent reasoning based on (2). This creates a logical correlation between the successor's choice and the result of Omega's simulation. For certain choices of parameters, this logical correlation leads to one-boxing.

The simplest way to solve the problem is letting the successor imagine that $P$ produces a lookup table. Consider the following equation:

(3) $A(i):=(\underset{f:I \rightarrow O}{\arg\max} \: E[U()|P()=LUT(f))(i)$

Here, $LUT(f)$ is a program which computes $f$ using a lookup table: all of the values are hardcoded.

For large input spaces, lookup tables are of astronomical size and either maximizing over them or imagining them to run on the agent's hardware doesn't make sense. This is a problem with the original equation (1) as well. One way out is replacing the arbitrary functions $f: I \rightarrow O$ with programs computing such functions. Thus, (3) is replaced by

(4) $A(i):=(\underset{\pi}{\arg\max} \: E[U()|P()=\pi)(i)$

Where $\pi$ is understood to range over programs receiving input in $I$ and producing output in $O$. However, (4) looks like it can go into an infinite loop since what if the optimal $\pi$ is described by equation (4) itself? To avoid this, we can introduce an explicit time limit $T$ on the computation. The successor will then spend some portion $T_1$ of $T$ performing the following maximization:

(4') $A(i):=(\underset{\pi}{\arg\max} \: E[U()|P()=S_{T_1}(\pi))(i)$

Here, $S_{T_1}(\pi)$ is a program that does nothing for time $T_1$ and runs $\pi$ for the remaining time $T_2=T-T_1$. Thus, the successor invests $T_1$ time in maximization and $T_2$ in evaluating the resulting policy $\pi$ on the input it received.

In practical terms, (4') seems inefficient since it completely ignores the actual input for a period $T_1$ of the computation. This problem exists in original UDT as well. A naive way to avoid it is giving up on optimizing the entire input-output mapping and focus on the input which was actually received. This allows the following non-quining decision theory:

(5) $A(i):=\underset{o \in O}{\arg\max} \: E[U()|P() \in F_{i,o}]$

Here $F_{i,o}$ is the set of programs which begin with a conditional statement that produces output $o$ and terminate execution if received input was $i$. Of course, ignoring counterfactual inputs means failing a large class of decision problems. A possible win-win solution is reintroducing quining2:

(6) $A(i):=\underset{o \in O}{\arg\max} \: E[U()|P()=\hat{F}_{i,o}(A)]$

Here, $\hat{F}_{i,o}$ is an operator which appends a conditional as above to the beginning of a program. Superficially, we still only consider a single input-output pair. However, instances of the successor receiving different inputs now take each other into account (as existing in "counterfactual" universes). It is often claimed that the use of logical uncertainty in UDT allows for agents in different universes to reach a Pareto optimal outcome using acausal trade. If this is the case, then agents which have the same utility function should cooperate acausally with ease. Of course, this argument should also make the use of full input-output mappings redundant in usual UDT.

In case the precursor is an actual AI programmer (rather than another AI), it is unrealistic for her to code a formal model of herself into the AI. In a followup post, I'm planning to explain how to do without it (namely, how to define a generic precursor using a combination of Solomonoff induction and a formal specification of the AI's hardware).

1 If Omega's simulation involves $P$, this becomes the usual Newcomb problem and one-boxing is the correct strategy.

2 Sorry agents which can't access their own source code. You will have to make do with one of (3), (4') or (5).

# 15

New Comment

I'm pretty sure we've had this anti-Newcomb problem discussion already. Short version: what this is is a constructive proof that any decision algorithm has to lose on some problems, because Omega could diagonalize against any algorithm, and then any agent implementing that algorithm is hosed. Therefore, it is fruitless to demand that a good decision algorithm or good agent never lose on any problems - one needs a more generous criterion of goodness. As for XDT, I don't see why it shouldn't get the $1M when playing an anti-Newcomb problem. 1,000,000 is bigger than 1,000, after all. I'm not totally sure why you need the further hardware in this post either. From what I can tell, the real trouble is that logical implication is not what you want here - we're still waiting on a reasonable system of logical counterfactuals. 3, 4', and if I understand it right, 5, are just not addressing that core problem. Hi Manfred, thx for commenting! ...what this is is a constructive proof that any decision algorithm has to lose on some problems, because Omega could diagonalize against any algorithm, and then any agent implementing that algorithm is hosed. See my reply to KnaveOfAllTrades. As for XDT, I don't see why it shouldn't get the$1M when playing an anti-Newcomb problem. 1,000,000 is bigger than 1,000, after all.

Which anti-Newcomb problem? In the XDT anti-Newcomb problem, 1000 is the maximal payoff. No decision theory gets more. In the UDT anti-Newcomb problem, XDT gets 1,000,1000 while UDT remains with 1,000,000.

...we're still waiting on a reasonable system of logical counterfactuals. 3, 4', and if I understand it right, 5, are just not addressing that core problem.

Well, there is more than one remaining problem :) Regarding logical counterfactuals, I think that the correct approach is going to be via complexity theory. Hope to write about it later, in the meanwhile you can check out this. By now I discovered some problems with the formalism I used there (and a possible path to fixing them), but I think the general direction is right.

As for XDT, I don't see why it shouldn't get the $1M when playing an anti-Newcomb problem. 1,000,000 is bigger than 1,000, after all. Which anti-Newcomb problem? In the XDT anti-Newcomb problem, 1000 is the maximal payoff. No decision theory gets more. Right, the XDT ANP. Because this is in fact a decision-controlled problem, only from the perspective of an XDT agent. And so they can simply choose to receive$1M on this problem if they know that that's what they're facing. $1M being bigger than$1000, I think they should do so.

But you do raise a good point, which is that there might be some way to avoid being beaten by other agents on decision-controlled problems, if you give up on maximizing payoff. It might depend on what metric of success you optimize the the decision procedure for. If you take the view logically upstream of filling the boxes, the maximum is $1.001M, and success is relative to that. If you take the view downstream, you might be satisfied with$1000 because that's the maximum.

Right, the XDT ANP. Because this is in fact a decision-controlled problem, only from the perspective of an XDT agent.

It is decision-determined from the perspective of any agent. The payoff only depends on the agent's decision: namely, it's 1000$for two-boxing and 0$ for one-boxing.

And so they can simply choose to receive $1M on this problem if they know that that's what they're facing.$1M being bigger than $1000, I think they should do so. Look on the problem from the perspective of the precursor. The precursor knows XDT two-boxes on the problem. There is no way to change this fact. So one box is going to be empty. Therefore building an XDT agent in this situation is no worse than building any other agent. It is decision-determined from the perspective of any agent. The payoff only depends on the agent's decision: namely, it's 1000$ for two-boxing and 0$for one-boxing. Yeah, sorry, I misspoke. The contents of the boxes are controlled by the agent's decision, only for an XTD agent. Look on the problem from the perspective of the precursor. The precursor knows XDT two-boxes on the problem. There is no way to change this fact. So one box is going to be empty. Therefore building an XDT agent in this situation is no worse than building any other agent. I am using XDT here in the sense of "the correct decision algorithm (whatever it is)." An XDT agent, if faced with the XDT-anti-Newcomb-problem, can, based on its decision, either get$1M, or $1k. If it takes the$1M, it loses in the sense that it does worse on this problem than a CDT agent. If it takes the $1k, it loses in the sense that it just took$1k over $1M :P And because of XDT's decision controlling the contents of the box, when you say "the payoff is$1000 for two-boxing and $0 for one-boxing," you're begging the question about what you think the correct decision algorithm should do. And because of XDT's decision controlling the contents of the box, when you say "the payoff is$1000 for two-boxing and \$0 for one-boxing," you're begging the question about what you think the correct decision algorithm should do.

The problem is in the definition of "correct". From my point of view, "correct" decision algorithm means the algorithm that a rational precursor should build. That is, it is the algorithm instantiating which by the precursor will yield at least as much payoff as instantiating any other algorithm.

Well, I agree with you there :P But I think you're cashing this out as the fixed point of a process, rather than as the maximization I am cashing it out as.

I didn't follow everything in the post, but it seems like the motivating problem is that UDT fails in an anti-Newcomb problem defined in terms of the UDT agent. But this sounds a lot like a fully general counterargument against decision algorithms; for any algorithm, we can form a decision problem that penalizes exactly that and only that agent. Take any algorithm running on a physical computer and place it in a world where we specify, as an axiom, that any physical instantiation of that algorithm is blasted by a proton beam as soon as it begins to run, before it can act. This makes any algorithm look bad, but this is just a no free lunch argument that every algorithm seems to fail in some worlds, especially ones where the deck is stacked against the algorithm by defining it to lose.

A decision process 'failing' in some worlds is a problem only if there exists some other decision process that does not suffer analogously. (Possible open problem: What do we mean by analogous failure or an analogously stacked world?)

Of course, it's possible this objection is headed off later in the post where I start to lose the train of thought.

Your proton beam problem is not decision-determined in the sense of Yudkowsky 2010. That is, it depends directly on the decision algorithm rather than depending only on the decisions it makes. Indeed it is impossible to come up with a decision theory that is optimal for all problems, but it might be possible to come up with a decision theory that is optimal for some reasonable class of problems (like decision-determined problems).

Now, there is a decision-determined version of your construction. Consider the following "diagonal" problem. The agent makes a decision out of some finite set. Omega runs a simulation of XDT and penalizes the agent iff its decision is equal to XDT's decision.

This is indeed a concern for deterministic agents. However, if we allow the decision algorithm access to an independent source of random bits, the problem is avoided. XDT produces all answers distributed uniformly and gets optimal payoff.

This is indeed a concern for deterministic agents. However, if we allow the decision algorithm access to an independent source of random bits, the problem is avoided. XDT produces all answers distributed uniformly and gets optimal payoff.

Omega can predict the probability distribution on the agent answers, and it is possible to construct a Newcomb-like problem that penalizes any specific distribution.

Hi V_V, thx for commenting!

In a Newcomb-like problem, Omega copies the agent and runs it many times to measure the decision distribution. It then penalizes the agent if the distribution matches an explicitly given one. Such a problem is easily solved by the agent since it knows which distribution to avoid.

In an anti-Newcomb-like problem, Omega measures the distribution produced by XDT and compares it with the agent's decision. It then penalizes the agent according to the likelihood of its decision in the distribution. However, if XDT produces a uniform distribution, all agents do equally well.

A trickier diagonalization is a hybrid Newcomb-anti-Newcomb (NAN) problem. Omega copies the agent and runs it multiple times to measure the distribution. It then compares the result with a similar procedure applied to XDT and penalizes the agent if there is a close match.

Now, the NAN diagonalization can be solved if we assume the agent has access to random bits which are common between all of its copies but inaccessible by the rest of the universe (Omega). This assumption can be interpreted to mean the precursor gives the agent a randomly generated "password" before Omega copies it.

Now, the NAN diagonalization can be solved if we assume the agent has access to random bits which are common between all of its copies but inaccessible by the rest of the universe (Omega). This assumption can be interpreted to mean the precursor gives the agent a randomly generated "password" before Omega copies it.

Sure, but this defeats the purpose of Omega being a predictor.

Not really. The idea is looking for a decision theory that performs optimally a natural class of problems which is as wide as possible. CDT is optimal for action-determined problems, UDT is supposed to be optimal for decision-determined problems. Allowing this use of randomness still leaves us with a class of problems much wider than action-determined: for example the Newcomb problem!

[-][anonymous]6y 0

Hi V_V, thx for commenting!

In Newcomb-like problems (i.e. when Omega copies the source code of the agent) you can penalize any specific distribution but the agent can always choose to produce a different distribution (because it knows which distribution is penalized).

In anti-Newcomb-like problems (i.e. when Omega uses hardcoded XDT) the payoff depends on a single decision rather than a distribution.

[This comment is no longer endorsed by its author]Reply

Your "UDT anti-Newcomb problem" reminds me of an open problem with TDT/UDT that was identified in the early days and still unsolved AFAIK. See the discussion here, but in short, it was pointed out that if most of the agents in the universe/multiverse are going to be UDT agents, they should be willing to play C in a one-shot PD game against a random agent sampled from the universe/multiverse. But human beings are not yet UDT agents, so it might be better to build some other kind of agent so we (or our successors) can play D instead. The approach suggested here looks like it could be relevant to solving that problem. What do you think?

One thing that worries me here is that if A has more computing power than P, it can compute P's actual output just by simulating it, so with the equations given in this post, you'd have to define how to condition the expectation of U() on statements that are known by the agent to be false. I was hoping that this is not actually a problem that needs to be solved in order to solve decision theory.

Hi Wei Dai, thx for commenting!

The "game of 3" problem indeed seems related. Apparently my decision theories solve it correctly, if we consider the precursor to be the "AI submitter". The discussion there is of enormous size, can you please point out the part about most of the agents in the multiverse?

Regarding successor-simulating-precursor, I think that any way of applying logical uncertainty that solves logical counterfactual mugging should handle this as well, since the precursor's "Tegmark V" should be preserved by the successor in some sense, and the precursor cannot simulate itself (see also this).

A possible solution is evaluating the expectation value at a depth of analysis (reference amount of computing resources) corresponding to the precursor's computing power. This doesn't mean the successor's superior computing power is wasted since it allows for more exhaustive maximization. In case of equation (4') the extra power is also used for evaluating pi.

Need to think more on this!

Apparently my decision theories solve it correctly, if we consider the precursor to be the "AI submitter".

Can you go into some detail on how your decision theories solve it?

The discussion there is of enormous size, can you please point out the part about most of the agents in the multiverse?

I guess it wasn't mentioned explicitly in that discussion, but it's how I've come to think of the problem. Perhaps the most relevant part of that discussion is Eliezer's direct reply, here.

Can you go into some detail on how your decision theories solve it?

Your problem can be written as

$U\(\$%20=%20\frac{1}{3}(PD_\alpha(A,%20B_1(A))+PD_\alpha(A,B_2(A))))

where $B\_1$ and $B\_2$ are Omega's players, $A=P\(\$) is your player and $PD\_\\alpha$ is the payoff of the first player in the Prisoner Dilemma with the (1,5,6) payoff matrix.

Omega's players end up playing C regardless of $A$. The agent can either understand this or at least fail to find a strong dependence of the logical probabilities of Omega's players' strategy on either their input (the agent's source) or the conditions in the expectation values it is evaluating (since the conditions are of the form $P\(\$=X) which seems to be correlated with $B\_i\(P\(\$)) only in the obvious way i.e. by determining the input to $B\_i$).

Therefore, the highest expectation values will be computed for conditions of the form $P\(\$=DefectBot). Therefore the agent will defect.

I guess it wasn't mentioned explicitly in that discussion, but it's how I've come to think of the problem. Perhaps the most relevant part of that discussion is Eliezer's direct reply, here.

I see. However, your problem doesn't seem to be a realistic model of acausal bargaining with agents in other universes, since in such bargaining you know who you're cooperating with. For example, when an agent considers filling its universe with human utility, it does it in order to cooperate with a human FAI, not in order to cooperate with a paperclip maximizer (which would require a very different strategy namely filling its universe with paperclips).

It's more of a model for FAI meeting an alien AI in space. Suppose each side then has the choice of doing an arms buildup or not, and the payoffs for these choices are analogous to PD. (If one side builds up while the other doesn't, it can attack and conquer the other. If both sides build up, it's a stalemate and just wastes resources.) BTW, what was your "UDT anti-Newcomb problem" intended to be a model for?

I guess if both sides are using your decision theory, then whether the human FAI plays C or D against the alien AI depends on how much logical correlation the FAI thinks exists between its human designer and the alien AI's designer, which does make sense (assuming we solve the problem of the FAI just simulating its designer and already knowing what their output is).

It's more of a model for FAI meeting an alien AI in space.

Makes sense.

BTW, what was your "UDT anti-Newcomb problem" intended to be a model for?

Frankly, I didn't have a specific realistic scenario in mind. I came up with the anti-Newcomb problem as simple semi-artificial problem demonstrating the problems with quining in UDT. The reason I started thinking about these problems is that it doesn't seem "classical" UDT can be translated to realistic AGI architecture. UDT takes a finite number of bits and produces a finite number of bits whereas a realistic AGI has continuous input and output streams. Such an AGI has to somehow take into account a formal specification of its own hardware, and the natural way of introducing such a specification seems to me to go through introducing a precursor, specifically a precursor which is a Solomonoff average over all "theories of physics" containing the formal specification.

Consider the following decision problem which I call the "UDT anti-Newcomb problem". Omega is putting money into boxes by the usual algorithm, with one exception. It isn't simulating the player at all. Instead, it simulates what would a UDT agent do in the player's place.

This was one of my problematic problems for TDT. I also discussed some Sneaky Strategies which could allow TDT, UDT or similar agents to beat the problem.

This is an interesting approach. The way I'm currently thinking of this is that you ask what agent a UDT would design, and then do what that agent does, and vary what type an agent is between the different designs. Is this correct?

Consider the anti-Newcomb problem with Omega's simulation involving equation (2)

So is this equation (2) with P replaced with something else?

However, the computing power allocated for evaluation the logical expectation value in (2) might be sufficient to suspect P's output might be an agent reasoning based on (2).

I don't understand this sentence.

Hi jessicat, thx for commenting!

The way I'm currently thinking of this is that you ask what agent a UDT would design, and then do what that agent does, and vary what type an agent is between the different designs. Is this correct?

So is this equation (2) with P replaced with something else?

No, it's the same P. When I say "Omega's simulation doesn't involve P" I mean Omega is not executing P and using the result. Omega is using equation (2) directly, but P still enters into equation (2).

I don't understand this sentence.

Logical uncertainty (the way I see it), is a way to use a certain amount of computing resources to assign probabilities to the outcomes of a computation requiring a larger amount of computing resource. These probabilities depend on the specific resource bound. However, this is not essential to the point I'm making. The point I'm making is that if the logical uncertainty ensemble assigns non-zero probability to P producing XDT, we end up with logical correlation that is better avoided.

By the way, there are other reasons that we use quining to study decision theories within (virtual) mathematical universes. Most importantly, it lets us play with the logic of provability in a straightforward way, which gives us some really nice polynomial-time tools for analyzing the outcomes. See Benja's modal UDT implementation in Haskell and my intro to why this works (especially Sections 6 and 7).

Of course, there are things outside that scope we want to study, but for the moment provability logic is a good lamppost under which we can search for keys.

When one is programming an AI, it doesn't seem optimal for the AI to locate itself in the universe based solely on its own source code. After all, you build the AI, you know where it is (e.g. running inside a robot), why should you allow the AI to consider itself to be something else, just because this something else happens to have the same source code

IIUC, the point of making the agent use quining to locate itself in the world is that it allows it to cooperate with copies of itself in games such as program-equilibrium prisoner dilemma.
Your proposal based on origin will fail to cooperate in such cases.

(more realistically, happens to have a source code correlated in the sense of logical uncertainty)?

I'm not sure I understand what you are referring to. Quining allows the agent to shortcut Gödelian logical uncertainty in certain cases: the agent can not predict its own actions before it executes them, but if it notices that certain parts of the world contain copies of itself, it can infer that, whatever function they compute, it is the same function as its own. In various cases this is sufficient to achieve coordination.

IIUC, the point of making the agent use quining to locate itself in the world is that it allows it to cooperate with copies of itself in games such as program-equilibrium prisoner dilemma. Your proposal based on origin will fail to cooperate in such cases.

Not really. Two XDT agents with symmetric precursors will cooperate since conditioning on the output of one precursor will determine the output of the other precursor. An agent running equation (4') will cooperate with a regular UDT agent e.g. by letting pi be a UDT agent. In fact, this latter property doesn't seem to generalize to the other variants which looks like a good argument in favor of (4')!

Quining allows the agent to shortcut Gödelian logical uncertainty in certain cases: the agent can not predict its own actions before it executes them, but if it notices that certain parts of the world contain copies of itself, it can infer that, whatever function they compute, it is the same function as its own. In various cases this is sufficient to achieve coordination.

The problem is that from the precursor's point of view, such behavior is not always rational. More precisely, it is rational when there is a logical relation between the precursor's decision and the other copy (e.g. Omega copied the successor after its creation or Omega copied the precursor and used it to create a copy of the successor). It is not rational when the other copy occurs by coincidence. Indeed, a precursor running UDT will not choose to build a UDT agent in such situations.


text:
# Is Yahoo finance volume written in shares per day or $value per day? [closed] Unfortunately, the Yahoo finance website does not mention any units for the data listed. Is the volume for each stock written in shares per day or in$ value per day?

• volume is number of shares. voted to close as too basic.
– Attack68
Jun 21, 2018 at 10:30
• There's actually a fair bit of complexity relating to volume - I've made a generic answer on this. Jun 21, 2018 at 11:04


text:
## Algebra 2 (1st Edition)

$0.75\leq x\leq0.85$
Using part a). Let $x$ be the pill's weight. Then our inequality according to the exercise is: $|x-0.8|\leq0.05$. This implies $-0.05\leq x-0.8\leq0.05\\0.75\leq x\leq0.85$


text:
# Source code for mushroom_rl.policy.policy

from mushroom_rl.core import Serializable

[docs]class Policy(Serializable):
"""
Interface representing a generic policy.
A policy is a probability distribution that gives the probability of taking
an action given a specified state.
A policy is used by mushroom agents to interact with the environment.
"""
[docs]    def __call__(self, *args):
"""
Compute the probability of taking action in a certain state following
the policy.

Args:
*args (list): list containing a state or a state and an action.

Returns:
The probability of all actions following the policy in the given
state if the list contains only the state, else the probability
of the given action in the given state following the policy. If
the action space is continuous, state and action must be provided

"""
raise NotImplementedError

[docs]    def draw_action(self, state):
"""
Sample an action in state using the policy.

Args:
state (np.ndarray): the state where the agent is.

Returns:
The action sampled from the policy.

"""
raise NotImplementedError

[docs]    def reset(self):
"""
Useful when the policy needs a special initialization at the beginning
of an episode.

"""
pass

[docs]class ParametricPolicy(Policy):
"""
Interface for a generic parametric policy.
A parametric policy is a policy that depends on set of parameters,
called the policy weights.
If the policy is differentiable, the derivative of the probability for a
specified state-action pair can be provided.
"""

[docs]    def diff_log(self, state, action):
"""
Compute the gradient of the logarithm of the probability density
function, in the specified state and action pair, i.e.:

.. math::
\\nabla_{\\theta}\\log p(s,a)

Args:
state (np.ndarray): the state where the gradient is computed
action (np.ndarray): the action where the gradient is computed

Returns:
The gradient of the logarithm of the pdf w.r.t. the policy weights
"""
raise RuntimeError('The policy is not differentiable')

[docs]    def diff(self, state, action):
"""
Compute the derivative of the probability density function, in the
specified state and action pair. Normally it is computed w.r.t. the
derivative of the logarithm of the probability density function,
exploiting the likelihood ratio trick, i.e.:

.. math::
\\nabla_{\\theta}p(s,a)=p(s,a)\\nabla_{\\theta}\\log p(s,a)

Args:
state (np.ndarray): the state where the derivative is computed
action (np.ndarray): the action where the derivative is computed

Returns:
The derivative w.r.t. the  policy weights
"""
return self(state, action) * self.diff_log(state, action)

[docs]    def set_weights(self, weights):
"""
Setter.

Args:
weights (np.ndarray): the vector of the new weights to be used by
the policy.

"""
raise NotImplementedError

[docs]    def get_weights(self):
"""
Getter.

Returns:
The current policy weights.

"""
raise NotImplementedError

@property
def weights_size(self):
"""
Property.

Returns:
The size of the policy weights.

"""
raise NotImplementedError


text:
MLB.com Columnist

Anthony Castrovince

# No debating the fact that DH isn't going away

## Designated hitter more likely to be added to NL than removed from AL

Well, here's a topic that comes up once or twice or 3,000 times every year in Major League Baseball, and especially on the slowest of slow days in January:

The designated hitter -- yay or nay?

If you're like me, and you have a Twitter feed dominated by baseball banter, you saw it emerge as a trending topic this week. And if you're like me, and you tend to flip on MLB Network's "Hot Stove" program, you saw it examined at length again Thursday. And even if you're not all that plugged in to baseball from a social media or cable standpoint, you might have at least seen that recent Volkswagen commercial in which the guy buying a Passat and the salesman spend more time arguing about the DH than they do haggling over the price of the car.

The DH discussion endures as much as any other major debate because:

A. It inspires passionate feelings on both sides of the equation

B. All those passionate exchanges have resulted in absolutely zero change to the respective rules of the American League and National League.

Oh, sure, maybe there was some slight chance of change in 1996, when MLB was preparing to initiate Interleague Play. At the time, there was thought that the AL might actually revert back to what had become known as the NL rules. But why in the world would the MLBPA sign off on any arrangement that would cause the elimination of 14 such prominent Major League jobs? It wasn't going to happen then, just as it's not going to happen now.

That's the fundamental reason people need to understand that the DH, for better or worse, isn't going anywhere. And frankly, it's hilarious when people dismiss the DH as some sort of non-traditional travesty. In what other sport or business or endeavor is anything that's been around for 40 years considered novel or non-traditional?

No, one thing needs to be understood: If baseball ever does go with the same set of rules for both leagues, the DH will be implemented in NL cities. That's the only way it's going to happen.

And another thing needs to be understood: It might actually happen -- perhaps as soon as the next Collective Bargaining Agreement.

Once Interleague Play became a reality, baseball put itself on an irreversible course, a dulling of the distinction between the two leagues (one that ought to be acknowledged by the abolition of the silliness that is resetting a player's stats to zero when he is traded from one league to the other midseason ... but that's another topic for another time).

As MLB embarks upon a 2013 season that will be the first to incorporate Interleague games into the schedule on a daily basis, that dulling of distinction has reached a new level, and having the two leagues play by two different sets of rules has completely ceased to make sense, if it ever made any sense at all.

To argue, then, in favor of the so-called "traditional" NL rules is all well and good, as we're each, of course, entitled to our own opinions. Just understand that, ultimately, it will prove about as effective as arguing in favor of rotary phones, VCRs and, at some point, fax machines. The world keeps evolving, and baseball keeps evolving right along with it. I'm not saying it's always right, necessarily, but it is a reality.

It would, then, seem healthy (though admittedly not easy) for the traditionalists to consider some factors that might help them embrace this reality.

For one, consider the development of the modern pitcher. He is often identified for his raw pitching prowess at an early age, and, in lieu of a focus on all-around skills, he is taught to refine his command and/or light up a radar gun. The DH is an option for high school coaches and a requirement for NCAA coaches. And though some pitchers do hit at those levels, not all do. Those that reach the pros don't hit at all at the Rookie or Class A levels. They hit sporadically at the Double-A and Triple-A levels, and only then if they are, of course, affiliated with an NL club (so those groomed in NL systems but traded to AL teams have absolutely no prior professional hitting experience).

Well, obviously, this has had a debilitating effect on the skill of pitchers at the plate. They are brutal. Last year, NL pitchers batted .129 with a .330 OPS. It has been 18 seasons since NL pitchers collectively hit even a notch above .150. This is entertainment?

The common counter, of course, is that the pitcher's spot in the batting order brings more strategy to the game, and this is true. But if the strategizing forces quicker hooks for starters and more time-consuming pitching changes and intentional walks, it's fairly easy to argue that all this strategizing isn't nearly as stimulating as some claim.

Listen, I love the old-school soul of the game, and I love the strategic elements of the sport. But watching a postseason game in which the team at the plate starts to mount a two-out rally, only to have it quelled by the No. 8 hitter getting intentionally walked to set up yet another strikeout or routine grounder off the bat of the pitcher is kind of a buzzkill, is it not?

These days, a team has every rational and financial incentive to protect its pitchers, and that means more awkward plate appearances, more bats sitting on shoulders. Even mere practice is problematic, as the Pirates can attest after A.J. Burnett moved to the NL last year and promptly bunted a ball off his eye, fracturing his orbital bone.

So while the purists have their point, that point has slowly been eroded by the winds of change. And while it is fair to bemoan the inclusion of Interleague Play in the season schedule, the moaning gets us nowhere. Because Interleague Play is viewed as a revenue-generator, and baseball is a business. So that's that.

The DH is going nowhere; eventually, it will be everywhere. This evolution is natural, though it is, admittedly, a little sad. Because when the DH argument goes away, what will we talk about on slow news days in January?

Anthony Castrovince is a reporter for MLB.com. Read his columns and follow him on Twitter at @Castrovince. This story was not subject to the approval of Major League Baseball or its clubs.