text:
|Publication number
|Publication type
|Application number
|Publication date
|Sep 12, 2002
|Filing date
|Feb 19, 2002
|Priority date
|Jul 14, 1999
|Also published as
|Publication number
|James Schreckengast, Claus Skaanning, Douglas Gilbert
|Original Assignee
|Schreckengast James O., Claus Skaanning, Gilbert Douglas M.
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (5), Referenced by (15), Classifications (4), Legal Events (5)
|External Links: USPTO, USPTO Assignment, Espacenet
[0001] This application is a continuation-in-part of application Ser. No. 09/758,891, filed Jan. 11, 2001 which is a continuation-in-part of application Ser. No. 09/353,727, filed Jul. 14, 1999.
[0002] The present invention pertains to knowledge-based systems and more particularly pertains to a scaleable investment tools and service for aiding users in making investment decisions based upon fundamental requirments of the individuals wishing to make the financial investments.
[0003] Investors often work alone or with investment managers to create an investment portfolio that in theory will provide a high return on investment consistent with a degree of risk that the individual investor is willing to take. In order to achieve what is an optimum investment portfolio, research is performed on fundamentals of particulars stock or on industry sectors, historical price data, price-to-earnings ratios, growth rates and so on. There is currently a very large amount of information available, for instance through the Internet, that aids investors in their task.
[0004] Barrons frequently lists what it considers to be the top ten websites for investors (e.g., moneycentral.com, quote.yahoo.com, cbs.marketwatch.com, etc.) all of which provide significant research data and investment tools for investors. What this website exemplifies is a principal problem facing today's investors. Investors using these tools quickly discover that the amount of investment data available today is overwhelming and cannot easily be interpreted or digested even by the more expert investor.
[0005] The number of potential investment options available to today's investors is equally daunting. Potential investment products include domestic and foreign stocks, mutual finds, stock options, futures, commodities commodity options, options, real estate finds, real estate investment trusts, currency funds, Treasury instruments, corporate and municipal bonds, futures contracts. etc. Generally, specialized knowledge is required in order to maximize profits when selecting investments as well as when timing purchases and sales. This usually gets into trading strategies and market patterns of which there are probably more opinions on than there are stocks to trade.
[0006] Computer systems have been used to aid in making investment decisions. One of their advantages is their ability to manipulate large amounts of numerical data over a relatively short period of time. For example, U.S. Pat. No. 5,761,442 describes using a predictive neural network for selecting a portfolio of securities. Each network is trained using available historical data relating to a corresponding security that is deemed to be "appropriate" by the person operating the system. Other experts in the field have tried applying artificial intelligence to the problem of manipulating financial data, for example, see R. Tripp and J. Lee "Artificial Intelligence in Finance and Investing," 1996.
[0007] Bayesian theory is also well suited to predicting outcomes given particular probabilistic data about the factors affecting the desired outcomes. In scientific literature Bayesian networks are referred to by various names: Bayes nets, causal probabilistic networks, Bayesian belief networks or simply belief networks. Loosely defined Bayesian networks are a concise (acyclic) graphical structure for modeling probabilistic relationships among discrete random variables. Bayesian networks are used to efficiently model problem domains containing uncertainty in some manner and therein lies their utility. Since they can be easily modeled on a computer, they are the subject of increasing interest and use in automated decision-support systems, whether for medical diagnosis, automated automotive troubleshooting, or in other areas as mundane as predicting a computer user's likely requirements.
[0008] In general, a Bayesian network consists of a set of nodes representing discrete-valued variables connected by arcs representing the causal dependencies between the nodes. A set of conditional probability tables, one for each node, defines the dependency between the nodes and its parents. And, nodes without parents, sometimes called source nodes, have associated therewith a prior marginal probability table. For specific applications the data for the probability tables for all other nodes are provided by what is termed domain experts in whatever field is being modeled. This involves assigning prior probabilities for all nodes without parents, and conditional probabilities for all nodes with parents. In diagnostic Bayesian networks nodes can represent causes, or outcomes of actions and questions. In very large diagnostic Bayesian networks, most of the events are very rare with probabilities in the range of 0.001 to 0.000001. But, since a primary goal of a computer decision support system is to provide likely outcomes of certain actions as accurate as is possible, it is imperative that the domain experts provide probabilistic information that is highly reliable and their best estimate of the situation.
[0009] Bayesian networks provide a way to model problem areas using probability theory. The Bayesian network representation of a problem can be used to provide information on a subset of variables given information on others. A Bayesian network consists of a set of variables (nodes) and a set of directed edges (connections between variables). Each variable has a set of mutually exclusive states. The variables together with the directed edges form a directed acyclic graph (DAG). For each variable υ with parents w1, . . . , wn, there is defined a conditional probability table P(υ|w1, . . . , wn). Obviously, if v has no parents, this table reduces to the marginal probability P(υ).
[0010] Bayesian networks have been used in many application domains with uncertainty, such as medical diagnosis, pedigree analysis, planning, debt detection, bottleneck detection, etc. However, one of the major application areas not heretofore studied is financial investment since Bayesian networks are well suited to decision support. Financial/investment decision support analysis lends itself nicely to the modeling techniques of Bayesian networks.
[0011] In accordance with a preferred embodiment of the present invention, a decision support system supports investment decisions. The decision support system includes a decision support engine and a Bayesian network. The Bayesian network is traversed by the decision support engine. The Bayesian network includes an investment decision node, potential investment nodes, and information nodes. The investment decision node identifies an investment decision. The potential investment nodes identify potential investments. The information nodes identify information to be obtained. The information to be obtained is matched to potential investments. Reliability of the information is estimated, for example, with the help of domain experts.
[0012]FIG. 1 is a simplified block diagram of a web server in accordance with a preferred embodiment of the present invention.
[0013]FIG. 2 is an overview of the diagnostic process as it is experienced by the user in accordance with a preferred embodiment of the present invention.
[0014]FIG. 3 is an overview of steps to perform knowledge acquisition in accordance with a preferred embodiment of the present invention.
[0015]FIG. 4 is an overview of the process of selecting the best next step to perform in accordance with a preferred embodiment of the present invention.
[0016]FIG. 5 shows an example of a Bayesian network built by a knowledge aquisition tool and used by a decision support engine in accordance with a preferred embodiment of the present invention.
[0017] A diagnostic system is used, for example, for decision support, selection, classification, prediction, and/or brokering.
[0018] In decision support, a user is taken through a sequence of questions leading him to the optimal solution to an issue. For example, decision support aids a user in making the right decision with regard to some issue.
[0019] To perform knowledge acquisition used to provide decision support, a domain in which to carry out the decision support is identified. Also identified are possible situations within the domain, possible sub-situations of the possible selections and informational steps. The informational steps are matched to the possible situations and the possible sub-situations. Probabilities are estimated for the possible situations the possible sub-situations. Also estimated are probabilities for actions and questions set out in the informational steps and costs for actions and questions set out in the informational steps.
[0020] In selection, a diagnostic system runs through a sequence of questions that aids the user in selecting between a number of possibilities. Multiple selections can be made. This is not completely general decision support. It is decision support in the manner that it aids the user to identify the situation that the use is looking at, and then suggests a solution. Causes correspond to situations. Informational steps correspond to diagnostic steps. In this case actions provide solutions, and questions gather information like in a diagnostic system.
[0021] To perform knowledge acquisition used to provide selection, a domain in which to carry out the selection is identified. Also identified are possible situations within the domain, possible sub-situations of the possible selections and informational steps. The informational steps are matched to the possible situations and the possible sub-situations. Probabilities are estimated for the possible situations the possible sub-situations. Also estimated are probabilities for actions and questions set out in the informational steps and costs for actions and questions set out in the informational steps. Causes correspond to selections. Informational steps correspond to diagnostic steps and are used to gather information useful for narrowing in on a selection.
[0022] In classification, a diagnostic system can be used to classify something according to a number of categories. For example, the diagnostic system can be used for path analysis, e.g., directing customer feedback e-mails to the correct person. Directing customer feedback e-mails to the correct person could entail, for example, classifying an e-mail into one of a number of categories, based on tags or keywords extracted from the e-mail.
[0023] In prediction, a diagnostic system can be used to create predictive systems. Basically, potential future causes are modeled instead of current causes, and questions that look for symptoms of future issues are modeled.
[0024] Brokering is a variant of selection where a diagnostic system is used to broker among a list of possible solutions. The preferred embodiment of the present invention is a scalable decision support service for securities brokering.
[0025]FIG. 1 is a simplified block diagram of a web-server 200. A diagnostic system 201 executes in a memory 301 of web-server 200. Diagnostic system 201 utilizes secondary storage devices 303 for storage of diagnostic models. A video display 304 can be used by a technician to monitor the diagnostic process and to maintain the diagnostic models. Web server 200 also includes an input device 305, such as a keyboard, a CPU 306 and a network card 307 for communication with web-browser 206 in a customer personal computer (PC) 205.
[0026] Diagnostics system 201 consists of a decision support engine (DSE) 203 capable of performing efficient and advanced decision support inference and analysis in Bayesian belief networks (BBNs), and a knowledge acquisition tool (KAT) 204 for construction of these decision support models. In the preferred embodiment, diagnostics system 201 is a scalable service allowing thousands of simultaneous users. Diagnostics system 201 can be accessed by e-services, web portals, extensible mark-up language (XML) communicating applications, appliances such as personal digital assistants (PDAs), wireless application protocol (WAP) phones, and so on.
[0027] Knowledge acquisition tool 204 is used to construct BBN models for stock brokering issues in order to create a stock brokering service. The BBN models are executed by the decision support engine 203. In alternative embodiments of the present invention, decision support engine 203 can be embedded in standalone applications as a part of a system where stock-brokering models can be utilized by many simultaneous systems or users.
[0028] In the preferred embodiment of the present application, diagnostic system 201 allows many different types of clients to utilize the stock-brokering models. Diagnostic system 201 service contains a default user interface that can be modified to suit any style of portal. A portal is a site on the Internet used as an entrance to other sites on the Internet. Also, in the preferred embodiment, diagnostic system 201 has an XML interface that allows applications to communicate directly with it. This makes it even more flexible for users to integrate diagnostic system 201 into their own applications. Also, diagnostic system 201 service allow PDAs, WAP phones to access diagnostic system 201 using their own protocols. For example diagnostic system 201 can be accessed using the wireless mark-up language (WML). PC) 205.
[0029]FIG. 2, is an overview of steps to be performed by knowledge acquisition tool 204 in order to implement decision support engine 203. The knowledge acquisition process is the process of constructing the diagnostic models by gathering sufficient information about the domain from so-called domain experts. The domain experts are familiar with the domain that is being modeled, in financial securities. These domain experts have intimate knowledge of the domain under consideration, being experts in the particular area of financial investing. The knowledge acquisition process has to be guided by someone familiar with the rules and requirements of the process. Participating in or guiding the knowledge acquisition process requires no expertise in the area of Bayesian networks.
[0030] In the preferred embodiment of the present invention, decision support engine 203 is used to guide investors in investment decisions.
[0031] In a step 900, the issues to diagnose are identified. The issue that is being modeled is identified, defined precisely and separated from other issues. Initially, it is very important to precisely define the issue under consideration and the audience of the diagnostic tool, as this will have a large impact on the following knowledge acquisition steps. The skill level of the audience is important when specifying both causes, actions and questions.
[0032] For example, causes represent problems with a portfolio or stock selections. Actions represent portfolio recommendations or stock suggestions.
[0033] One example of an issue is a diagnosis to make an investment recommendation. In this case, knowledge acquisition tool 204 constructs a Bayesian belief network for execution by decision support engine 203 that allows decision support engine 203 to provide a very simple session that queries an investor on a number of goals and recommends the best single investment that could be made to meet the overall needs of the investor. For example, the investment could be for selection of a mutual fund or a single stock.
[0034] Another example of an issue is portfolio troubleshooting. In this case, knowledge acquisition tool 204 constructs a Bayesian belief network for execution by decision support engine 203 that allows decision support engine 203 to perform an analysis of an investor's existing portfolio and to report a number of metrics into a model. The model is prepopulated from the analysis. Decision support engine 203 interviews the investor about problem symptoms. For example, the investor may be uncomfortable with the volatility of the portfolio. Or, the investor might like to see larger returns. Decision support engine 203 recommends the next best steps to address the issue based on belief in the possible causes of the investor's issue. A relatively persistent session can be maintained over time to observe the impact of these changes and to reassess the portfolio or to arrive at a new conclusion about the cause of the issue. Alternatively, the model can be repopulated with new fundamentals, based on executing the recommendation, and the model can decide whether the action improved the situation, proceeding iteratively and automatically, until the best set of recommendations are determined.
[0035] For example, the Bayesian belief network constructed by knowledge acquisition tool 204 can be a "supermodel" used for selecting between subservient (sub) models that are good at troubleshooting specific portfolio problems.
[0036] Another example of an issue is portfolio selection. In this case, knowledge acquisition tool 204 constructs a Bayesian belief network for execution by decision support engine 203 that allows decision support engine 203 to evaluate a set of predetermined portfolios against investor objectives and a prepopulated model. The prepopulated model includes, for example, the current financial situation of the investor, the age of the investor, and so on. A best portfolio is selected and then a detailed plan is developed to get the investor from the current situation to the new one.
[0037] Another example of an issue is a loan advisor. In this case, knowledge acquisition tool 204 constructs a Bayesian belief network for execution by decision support engine 203 that is used to help the investor to decide whether to sell stocks, borrow money, take a home equity loan, et cetera, to raise capital to be used for a particular objective.
[0038] Another example of an issue is service selection. In this case, knowledge acquisition tool 204 constructs a Bayesian belief network for execution by decision support engine 203 that allows decision support engine 203 to select from a number of brokerage services, based on the needs of the investor . This is, for example, a "supermodel" that selects among a number of consulting models, providing advice on a wide variety of financial topics. For example, this is used in the selection of a mutual fund for the investor. Alternatively, this is used for the selection of a single stock.
[0039] In a step 901, causes of the issue are identified. In this step, the domain experts identify the causes of the issue under consideration. Causes are basically all the different properties or events that can cause the issue.
[0040] It is usually impossible and/or not necessary to identify and specify all causes, as there are causes that are too rare to be worth considering. These causes are then gathered in a single leak cause termed "other causes".
[0041] One of the difficulties in identifying causes is the decision of whether to group sets of causes as a single cause or whether to keep the causes separate. As a rule of thumb it is easier to do the knowledge acquisition for actions, if causes for which there are different actions are kept separate.
[0042] For example, when the issue is stock selection, causes are all the stocks available, for example, on a particular stock exchange. When the issue is portfolio selection, in each of the sub models, causes are, for example, different potential causes of the portfolio problem. For example, potential causes could be too many high-risk stocks, all stocks in same industry sector, and so on. For example, when the issue is portfolio selection, causes correspond to the portfolios under evaluation.
[0043] In a step 902, subcauses, if any, are identified. Often, it is convenient to organize causes into categories. These categories are then seen as causes with a number of subcauses. It is not strictly necessary to use subcauses of causes, as it is entirely possible to have all subcauses on the same top level. However, this approach often leads to a high number of causes on the top level, making the acquisition of probabilities more difficult. Organizing the causes into a hierarchy allows the domain expert to consider fewer causes at a time when estimating probabilities, thus providing more accurate information.
[0044] While in FIG. 2 there are only represented two levels of the cause-structure in FIG. 2, there can be arbitrarily many levels of causes and subcauses.
[0045] In a step 903, diagnostic steps of the issue are identified. Actions that can solve any of the causes of the problem, and questions that can provide information regarding the causes are listed.
[0046] When listing the diagnostic steps of a problem, the domain experts basically consider the steps they themselves would perform or suggest for the customer to perform, if they were faced with the problem. Experience shows that it is beneficial to start out listing the steps without considering the previously listed causes, i.e., with a "blank" mind, as this will occasionally bring otherwise forgotten steps into mind. Then, when these first steps have been listed, it is good to consider the list of causes and add all steps that potentially solve these causes.
[0047] Again, the domain expert faces the problem of size and coverage of steps. There are diagnostic procedures that can be equivalently modeled as a single step or a series of steps. The rule of thumb here is that it depends on the user interface and the step itself how to represent a step. If the step can be conveniently represented as a deterministic flow-diagram if-then-else structure, and the user interface of the diagnostic system supports the implementation of such deterministic "programs", then the step should be modeled as a single step. If the flow-diagram of the step includes uncertain/probabilistic decisions, the step has to be represented as multiple steps.
[0048] There are two main categories of diagnostic steps, actions and questions. The first category, actions, are steps that require the user to perform some kind of intervention in the system, and report back to the diagnostic system whether the action solved the problem or not. Thus, actions have the potential to solve the problem. The second category, questions, are steps that require the user to obtain some information related with the problem at hand possibly by intervening with the system, and report back the result to the diagnostic system. Questions are grouped into two subcategories, information-gathering actions and general questions.
[0049] Information-gathering actions are actions that do not have the potential to solve the problem. They merely provide information that is relevant to solving the problem. Ordinary actions are also termed solution actions to distinguish them from the information-gathering actions. It is important to distinguish, as the two types of actions are handled differently in the diagnostic algorithms, as further described below where information-gathering actions are treated as questions. To clarify, this means that algorithmically there is no difference between information-gathering actions and questions. However, the distinction is kept during knowledge acquisition as it is easier for domain experts to elicit probabilities for information-gathering actions if they are treated as actions.
[0050] The distinction between information-gathering and solution actions should also be clarified. Solution actions have the potential to solve the problem while information-gathering actions cannot possibly solve the problem. Information-gathering actions only have the potential to temporarily remove the problem while some change to the environment is tried out. General questions are the remaining questions that are not information-gathering actions. Questions do not have the potential to solve the problem, and can have any number of answers as opposed to actions that only have two: yes (it helped) and no (it didn't).
[0051] When listing the diagnostic steps of a problem, they must be categorized as either solution actions (SA), information-gathering actions (IA) or questions (Q).
[0052] For all actions and questions, explanations should be written as early in the knowledge acquisition process as possible, as these explanations/definitions help to reduce future confusion and ensure that errors are caught as early as possible.
[0053] For example, when the issue is investment selection, diagnostic system 201 attempts to determine the characteristics of the investor by use of questions with respect to age, earning power, risk willingness, and so on. Characteristics of the individual stocks such as P/E ratio and capitalization are also represented in the model as questions since the stock market is a dynamic system and these characteristics have to be obtained automatically on a regular basis. The result of the analysis is, for example, a suggestion to purchase a specific stock or set of stocks represented by an action.
[0054] When the issue is portfolio selection, the questions pertain to the problem symptoms, for example, portfolio volatility or insufficient rate of return. Questions are both interactive where the investor enters information about the portfolio and automated where information on stocks is gleaned from databases. Actions are recommendations for changes to the portfolio.
[0055] In a step 904, causes and diagnostic steps are matched. The diagnostic steps are matched with the causes that they can solve. Additionally, the causes that are associated with questions are identified. In this step, the causes are matched with diagnostic steps such that actions are matched with the causes that they can solve, and questions are matched with the causes that they are associated with (i.e., affect the probabilities of).
[0056] For each action, Ai, it is considered for each cause, Cj, whether there is a non-zero probability that performing Ai will solve Cj. If this is so, there is a match which is registered for later use in the knowledge acquisition process.
[0057] Information-gathering actions can be handled almost similarly to solution actions. Even though they are not able to solve the problem, they are still able to temporarily remove the problem while trying some change in the environment.
[0058] For each question, Qi, it is considered for each cause, Cj, whether an answer to Qi will directly affect the belief in Cj (i.e., cause the probability to decrease or increase).
[0059] Questions do not have to affect the beliefs of any causes at all as they are sometimes used to provide information about the diagnostic scenario, user type, etc. to allow/disallow related actions.
[0060] In a step 905, a check is made to see if any new causes or subcauses have been identified. These may be identified, for example, when matching the causes and steps. If there are any new causes or subcauses identified, a return is made to step 901.
[0061] When matching the actions and questions with the causes that they are associated with, it often happens that causes are discovered for which there are no solution actions, and actions are discovered that cannot solve any causes, i.e., there are respectively actions and causes missing. When this occurs, it is necessary to go back to step 901.
[0062] In a step 906, a check is made to see if any new diagnostic steps have been identified, for example, when matching the causes and steps. If there are new diagnostic steps that have been identified, a jump is made back to step 903.
[0063] Causes and steps are often forgotten in the initial listing, and new causes and steps are often discovered when matching causes with steps. Therefore, it is optimal to perform the matching of causes and steps before eliciting the probabilities for causes, as this elicitation has to be performed partly over again each time a new cause is discovered.
[0064] In a step 907, probabilities of causes and subcauses are estimated. When there is a high degree of certainty that all causes have been listed, and causes and subcauses have been structured in a hierarchy, the probabilities of causes should be estimated. This is usually done bottom-up, so that the probabilities of subcauses given the cause are estimated first, and then the probabilities of causes given the problem.
[0065] The probabilities of subcauses are estimated first. The sets of subcauses are visited in sequence, such that a separate elicitation of probabilities is performed for each set of subcauses of the same cause. The probabilities of the subcauses are elicited assuming that the problem is present and the cause is present. When all probabilities of subcauses have been elicited, the probabilities of the causes are elicited, assuming that the problem is present.
[0066] Experience has shown that this method of probability elicitation where the probabilities are basically elicited against the causal direction (the subcauses cause the causes, and the causes cause the problem) is highly efficient as it provides the domain experts with maximum information to base their probabilities on as they are allowed to assume that the problem and/or the cause is present.
[0067] The usual procedure of eliciting the probabilities of a set of causes/subcauses is for one domain expert to give initial probabilities to most of the causes given the higher level cause-or at least a ranking (this is the highest, this is the next highest, etc.). Then the domain experts discuss the initial probabilities or rankings and adjust as a result of discussions. When final agreement is reached, the elicication is closed.
[0068] Obviously, there is always some amount of second-order uncertainty on the elicited probabilities. One standard method of representing this second-order uncertainty is to use probability intervals such that the domain expert states his/her belief that the probability is within a certain interval. When the domain experts have then agreed on a specific interval, there are methods that allows propagation of probability intervals in Bayesian networks. Rendering the second-order uncertainty explicit allows the domain expert to specify different size probability intervals for different probabilities, and the automated diagnostic system would be able to give its conclusions with the appropriate uncertainty.
[0069] In step 908, probabilities of actions and questions are estimated.
[0070] In the preferred embodiment, there are two types of questions, those that pertain to symptoms or effects of causes, and general questions that are not naturally seen as a symptom or an effect. The knowledge acquisition processes for the two types of questions are different, so it is important to determine the type of the question before eliciting the probabilities for it. The difference between these two types of questions is further elaborated below.
[0071] For general questions, the causes associated with the question, have been previously listed, i.e., the causes that will have their probabilities decreased or increased depending on the answer to the question. For this type of questions, the domain experts consider each answer to the question (e.g., yes, no, etc.) and estimate how much the probabilities of the affected causes will decrease or increase based on the new information. The elicitation proceeds much like the one for causes—there can be disagreements in understanding that have to be solved by discussions.
[0072] The domain experts focus on the causes that are affected by the answer to the question, thus the probabilities of causes that are not affected, are not modified by the experts. However, the fact that other causes are having their probabilities increased or decreased will cause the probabilities of the remaining to change accordingly, such that the sum is still 1.0. It is clearly easier for the experts to only adjust the probabilities that are directly affected, and then let the rest change accordingly, than having the experts assess the changes in all probabilities. Also, it was the experience that the experts were comfortable with letting the remaining probabilities change accordingly.
[0073] Also, for general questions the domain experts have to give prior probabilities for the answers to the question. It will be explained below how to check whether the experts have specified inconsistent information for general questions by analysing the unconditioned probability of the associated causes, P(C), the conditional probability, P(C|Q), and the priors on the question P(Q), i.e., by comparingΣQP(C|Q)P(Q) with P(C).
[0074] For questions about symptoms, the causes that are associated with the question are listed in step 904, shown in FIG. 2 and described above, that is, the causes that cause the symptom in question. Here, the elicitation consists of giving for each of the associated causes, the probability of the symptom given the cause. Also, the probability that the symptom appears if none of the specified causes are present should be estimated.
[0075] In a step 909, costs of actions and questions are estimated. In the diagnostic algorithms, it is necessary to know the cost of performing actions and questions to be able to determine which is the optimal step to perform next. The cost can either be estimated as a single factor, or as a combination of multiple factors. As the cost really is composed of multiple significant factors, it seems to be the most reliable and accurate approach to assess each of these factors separately, and then combine the factors into a single cost factor. The cost is composed of many factors.
[0076] For example, costs can include estimated price volatility, investment liquidity, transactions costs, minimum investment requirements, amount of time required to monitor/service an investment, and so on.
[0077] There are several other factors of cost that can be considered such as the inconvenience in purchasing and selling an investment.
[0078] The cost factors must be combined into a single figure to be useful for the diagnostic algorithms. To do this,all cost factors for investements must be converted to numbers, and finally the cost factors must be balanced and added. To determine how to do this, experiments can be performed with the domain experts asking them to rank steps which differ on cost factors. From a sufficient amount of such experiments, the conversion factors and weights can be determined.
[0079] In a step 910, actions and questions requiring special handling are identified and dealt with.
[0080] There are several pieces of additional information that it is necessary to specify for the diagnostic model to get a diagnostic system that performs as desired. These are collectively referred to as actions and questions requiring special handling.
[0081]FIG. 3 is an overview of the diagnostic process as it is experienced by the user. In a step, the diagnostic system is initiated by the user, either through a world wide web user interface or as a stand alone executable on the user's own computer. In a step 701, the user interface guides the user to an identification of the issue to be solved. This can be done in several ways, menu systems, graphical pictures and so on. In a step 702, the user now enters the main loop of the diagnostic system, where the diagnostic system first suggests either an action or a question and the user then responds to this (possibly after performing some sequence of actions) The diagnostic system also may go out on the Internet or use other resources to determine pertinent information such as current information pertaining to a particular investment. In a step 703 and a step 704, the user can choose not to perform the suggestions.
[0082] After the user has performed an action, he inputs to the diagnostic system, in a step 709, whether or not the action solved the problem (issue). If the action solved the problem, the diagnostic system terminates successfully in step 706, but if the action does not solve the problem, the diagnostic system has to check, in step 707, whether there are any remaining actions or questions that have not been suggested. If there are no remaining steps, the diagnostic process, in step 708, is terminated unsuccessfully. No resolution of the problem could be found. If there are remaining actions or questions, the diagnostic process, in step 702, is continued. Similarly, if the diagnostic system has suggested a question, the user may decide, in step 704, not to perform the question. Alternatively, in step 705, the user answers the question and the process continues. In step 707 a check is made as to whether there are any more actions or questions that have not been asked.
[0083]FIG. 4 is an overview of the process of selecting the best next step to perform. FIG. 4 basically covers the substeps performed to implement step 702 and step 707 shown in FIG. 3. In a step 800, a check is made as to whether there are any actions or questions left that have not been suggested yet. If there aren't any left, in a step 805, it is checked whether there are any actions or questions left that have been deferred earlier. If this is the case, in a step 806, the best of these is selected and a return is made in step 807. If there are no deferred actions or questions either, in step 808, nothing is returned, as everything has been tried and there is nothing else to suggest.
[0084] If in step 800, it is found that there are still actions or questions left that have not been suggested yet, in step 801 there is computed the optimal sequence of actions and questions. In a step 802, the expected cost (ECR) of executing this optimal sequence until the cause is identified. In a step 803, for each question, there is computed the expected cost (ECO) of first asking the question and then performing the optimal sequence of actions given the answer to the question. In a step 804, the ECO for each question is performed with the ECR of the optimal sequence to see whether there is a question that it is optimal to ask before performing the optimal sequence of actions. The optimal action or question is then finally returned in step 807.
[0085]FIG. 5 shows an example of a Bayesian network built by knowledge aquisition tool 204 and used by a decision support engine 203 in accordance with a preferred embodiment of the present invention.
[0086] The Bayesian network includes a brokering issue node 500, overall causes node 501. Overall causes node 501 includes cause nodes 502, 503, 504, 505, 506, 507, 508, 509, 510 and 511. The Bayesian network also includes a flow node 1, a flow node 2, a flow node 3, a flow node 4, a flow node 5, a flow node 6, a flow node 7, a flow node 8, a flow node 9, a flow node 10, a flow node 11 and an output node 531. Flow node 1 is also referred to as flow 1. Flow node 2 is also referred to as flow 2. And so on. Nodes 513, 514, 515, 516, 517, 518 and 519 are diagnostic steps nodes. The last column in FIG. 7 contains the subcause nodes 520, 521, 522, 523, 524, 525, 526, 527, 528, 529 and 530. Each of the subcause nodes 520-530 represents a Bayesian network modeling the subcauses of the cause.
[0087] For example, the brokering issue may have to do with the selection of a new investment for an investor. The causes can represent investment types such as stocks on a partiular stock exchange, bonds, stock mutual funds, bond mutual funds, real estate funds, and so on. The subcauses represent, for example, potential individual investment within an investment area. Diagnostic steps include, for example, information gathering about an investor for information such as investment time horizon, risk toleration, desired return, available capital, other investments and so on. Diagnostic steps can also include, for example, information gathering about an investment such as, for example, price fluctuations, price/earnings ratio, investment managers, company officers and so on. Flow nodes represent flows in the interaction between the investor and decision support engine 203. This brokering issue example is illustrated by FIG. 6 and FIG. 7 discussed below.
[0088] In FIG. 5, the arcs are directed from the issue towards the causes and the subcauses are against the causal direction. However, the arcs can be reversed if necessary, for representing, e.g., persistence. This direction for the arcs is used herein because the specification of probabilities becomes easier.
[0089] The conditional probability distribution for causes node 501 is as set out in Table 1 below:
TABLE 1 Brokering issue 500 states Causes 501 states yes no Cause 502 x1 0 Cause 503 x2 0 Cause 504 x3 0 Cause 505 x4 0 . . . . . . 0 Cause 512 x11 0 N/A 0 1
[0090] All the x's in Table 1 represent probabilities; for each cause the probability that it is the cause of the issue (e.g., a suitable investment choice for the investment decision). From the knowledge acquisition process defined above, a probability distribution over the causes in the issue is obtained which is then used directly in the above probability distribution.
[0091] Cause nodes 502, 503, 504, 505, 506, 507, 508, 509, 510, 511 and 512 represent investment areas suitable for the investment decision. Cause nodes 502 through 512 each have two states, yes and no. For example, cause node" 502 has conditional probability distribution as set out in Table 2 below:
TABLE 2 Cause 501 states Cause Cause Cause Cause 502 states 502 501 . . . 512 N/A yes 1 0 0 0 0 no 0 1 1 1 1
[0092] In Baysian network shown in FIG. 5, there are two levels of diagnostic steps. The first level of diagnostic steps are global diagnostic steps that are used to determine causes (e.g., investment types). The next level of diagnostic steps are local diagnostic steps that determine subcauses (e.g., particular securities within an investment type).
[0093] The global diagnostic steps 513, 514, 515, 516, 517, 518 and 519 are associated with some of the cause nodes 502-512 and/or some of the flow nodes. For example, global diagnostic step 513 is associated with "Flow 5"and cause node 512. This is modeled with the following conditional probability distribution for node 513, as set out in Table 3 below:
TABLE 3 "Flow 5" states ok lost Cause 512 states yes no yes no 513 states yes 0 1 − ε 0 0 no 1 ε 1 1
[0094] There is a probability (ε) that cause 512 is not able to solve the issue (e.g., purchasing or selling an investment does not satisfy the criteria of the investment decision). The probability ε is referred to as the inaccuracy of the action.
[0095] For the brokering implementation discussed above, FIG. 6 and FIG. 7 show how the processes set out in FIG. 2 and FIG. 3 are modified to accomplish this type of decision making.
[0096]FIG. 2, is an overview of steps to be performed by knowledge acquisition tool 204 in order to implement decision support engine 203. As described above, the knowledge acquisition process is the process of constructing the models by gathering sufficient information about the domain from so-called domain experts. The domain experts are familiar with the domain that is being modeled, in financial securities. These domain experts have intimate knowledge of the domain under consideration, being experts in the particular area of financial investing. The knowledge acquisition process has to be guided by someone familiar with the rules and requirements of the process. Participating in or guiding the knowledge acquisition process requires no expertise in the area of Bayesian networks.
[0097] In a step 600, the investment issue is identified. In this case the issue is selecting one or more investments that are appropriate to an investor.
[0098] In a step 601, investment types are identified. In this step, the domain experts identify the types of information that could be used by an investments. Investment types could be broad categories, such as "real estate", "stocks", "bonds", "precious metals". Alternatively, investment types might be sectors within the stock market. Investment types also could be different types of mutual funds such as "small capitalization value stock funds", or "mid cap growth funds".
[0099] In a step 602, individual investments within investment types are identified. For the case of "small capitalization value stock funds" this could include all mutual funds that currently invest in small capitalization stocks based on a value investment style. Particular investments that, according information available in the system, have the best potential are investigated further.
[0100] While in FIG. 6 there are only represented two levels of the investment structure in FIG. 2, there can be arbitrarily many levels of investments. For example, at a first level may be investment type (real estate, stocks, bonds, mutual funds etc). At a second level may be categories within investment types. For example within stocks there may be several categories (small capitalization value stocks, small capitalization growth stocks, mid capitalization value stocks, mid capitalization growth stocks, large capitalization value stocks, large capitalization growth stocks). At the same level or at a lower level, stocks may be further divided into sector categories (e.g., financial stocks, technology stocks, utilities, etc.). At the lowest level may exist individual stocks.
[0101] In a step 603, needed information is identified about selected potential investments are identified. This information will be obtained from databases with information on the investments and/or from the potential investor.
[0102] As discussed above, questions to be asked of the potential investor may be to determine the characteristics of the investor with respect to age, earning power, risk willingness, and so on. Current information to be obtained from databases includes, for example, projected earnings, potential growth rates, P/E ratio, capitalization and so on if the potential investment is a stock. For bonds the information may include, for example, current rate of return, bond rating, time to maturity, and so on.
[0103] In a step 604, individual investments are matched with information to be used to evaluation the information. This information is selected by domain experts based on information that is needed to determine what investments best meet particular investor profiles.
[0104] In a step 605, a check is made to see if additional investments need to be evaluated. If so, a return is made to step 601.
[0105] In a step 606, a check is made to see if any new information is needed to make a decision. When matching required information to investments, it may become clear that enough information will not be available to assure that a potential investment will or will not meet investor criteria. When this occurs, a jump is made back to step 603.
[0106] In a step 607, investment risks are identified. Risks of investment types as well as particular investments are calculated. These risks can be based on information obtained directly from the domain experts. Alternatively, the domain exports can point to historical data or other data to be used to calculate risks based or formulas supplied by the domain experts.
[0107] In step 608, the reliability of information is estimated. This is especially necessary when the information is based on future projections, such as projected earnings and projected growth rates. This reliability can be based on information obtained directly from the domain experts. Alternatively, the domain exports can point to historical data or other data to be used to calculate reliability based or formulas supplied by the domain experts.
[0108] In a step 609, transaction costs of the investments are calculated. This includes, for example, brokerage costs. This can also include an estimate of costs based on illiquidity of certain types of investments. Again this information is supplied by domain experts or based for formulas supplied by the domain experts to be used with current data supplied by financial or other databases.
[0109] In a step 610, information requiring special handling is identified and dealt with.
[0110] The use of domain experts to construct Bayesian networks as described above provides a significant advantage over systems that just provide screening for stocks. The use of expertise of domain experts, for example, to provide estimates of investment risk and/or reliability of information, etc. Allows the decision support system to reflect the decision making process of experts. Continual updating of information obtained from domain experts can further increase the usefulness of the systems based on preferred embodiments of the present invention.
[0111]FIG. 7 is an overview of the decision support process as it is experienced by the user. In a step 720, the decision support system is initiated by the user, either through a world wide web user interface or as a stand alone executable on the user's own computer. In a step 721, the user interface guides the user to an identification of the investment issue to be solved. This can be done in several ways, menu systems, graphical pictures and so on. In a step 722, the user now enters the main loop of the decision support system, where the decision support system first obtains information from the user (step 724) and obtains information from investment data bases (step 723). The decision support system may go out on the Internet or use other resources to determine pertinent information such as current information pertaining to a particular investment.
[0112] In step 723 a determination is made as to whether additional information is needed for a recommendation. If yes, the decision support system returns to step 722. If in step 723 no additional information is made for a recommendation, in a step 729, a recommendation to the user is made who has the opportunity to accept the recommendation or hold out for another recommendation. If the user accepts the recommendation, in a step 726, the decision support system terminates successfully.
[0113] In step 724, the user can choose not to answer a question. The decision support system receives the answer in step 725. In a step 727 a determination is made as to whether additional information is needed for a recommendation. If yes, the decision support system returns to step 722. If in step 727 no additional information is made for a recommendation, in step 729, a recommendation to the user is made who has the opportunity to accept the recommendation or hold out for another recommendation. If the user does not accept the recommendation, step 727 can be repeated, or when a loop between step 727 and step 729 occurs, the decision support system is terminated without a recommendation in a step 730.
[0114] This can map for the Bayesian network shown in FIG. 5, for example, as follows. Node 500 is an investment issue node. Node 501 is an overall investment node. Nodes 502, 503, 504, 505, 506, 507, 508, 509, 510 and 511 are investment type nodes. Flow nodes 1 through 11 and nodes 513, 514, 515, 516, 517, 518 and 519 are information gathering nodes. Nodes 520, 521, 522, 523, 524, 525, 526, 527, 528, 529 and 530 are particular investment nodes.
[0115] The foregoing discussion discloses and describes merely exemplary methods and embodiments of the present invention. As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.
|Cited Patent
|Filing date
|Publication date
|May 4, 1936
|Mar 28, 1939
|American Box Board Co
|Title not available
|Title not available
|Title not available
|Title not available
|Citing Patent
|Filing date
|Publication date
|Jul 12, 2000
|Jul 13, 2004
|Sentar, Inc.
|System and method for facilitating interaction with information stored at a web site
|May 26, 2001
|Oct 18, 2005
|Hewlett-Packard Development Company L.P.
|Model selection for decision support systems
|Nov 10, 2005
|Jan 20, 2009
|Brother Kogyo Kabushiki Kaisha
|Remote diagnosis device, remote diagnosis system and program product
|Oct 23, 2003
|Jan 19, 2010
|Hrl Laboratories, Llc
|Evaluation of Bayesian network models for decision support
|Oct 27, 2000
|Oct 18, 2011
|Citibank, N.A.
|Method and system for using a Bayesian belief network to ensure data integrity
|Apr 30, 2010
|Jul 10, 2012
|Trading Technologies International, Inc.
|System and method for providing market data in an electronic trading environment
|Sep 13, 2011
|Dec 25, 2012
|Citibank, N.A.
|Method and system for using a bayesian belief network to ensure data integrity
|Nov 22, 2004
|Feb 5, 2013
|Morgan Stanley
|Systems and methods for analyzing financial models with probabilistic networks
|Jun 7, 2012
|Jun 25, 2013
|Trading Technologies International, Inc
|System and method for providing market data in an electronic trading environment
|May 22, 2013
|Oct 28, 2014
|Trading Technologies International, Inc.
|System and method for providing market data in an electronic trading environment
|Oct 23, 2003
|Apr 28, 2005
|Przytula Krzysztof W.
|Evaluation of bayesian network models for decision support
|Nov 10, 2005
|Jun 8, 2006
|Brother Kogyo Kabushiki Kaisha
|Remote diagnosis device, remote diagnosis system and program product
|Jun 21, 2005
|Dec 21, 2006
|Capital One Financial Corporation
|Systems and methods for conducting due diligence
|Mar 4, 2010
|Martin Neil A
|Intelligent Dashboards With Heuristic Learning
|Feb 26, 2007
|Sep 4, 2008
|Siemens Ag
|System and method for planning a technical system
|U.S. Classification
|International Classification
|Cooperative Classification
|European Classification
|Apr 18, 2002
Owner name: HEWLETT-PACKARD COMPANY, COLORADO
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SCHRECKENGAST, JAMES O.;SKAANNING, CLAUS;GILBERT, DOUGLAS M.;REEL/FRAME:012819/0035;SIGNING DATES FROM 20011113 TO 20020208
|Jun 18, 2003
Owner name: HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P.,COLORADO
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HEWLETT-PACKARD COMPANY;REEL/FRAME:013776/0928
Effective date: 20030131
|Sep 30, 2003
Owner name: HEWLETT-PACKARD DEVELOPMENT COMPANY L.P.,TEXAS
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HEWLETT-PACKARD COMPANY;REEL/FRAME:014061/0492
Effective date: 20030926
|Nov 29, 2010
|Fee payment
Year of fee payment: 4
|Oct 23, 2014
|Fee payment
Year of fee payment: 8


text:
Did Leonard celebrate new contract? Of course not
Hopdoddy Burger Bar opening location at The Rim in San Antonio
16 arrested in South Texas prostitution sting
New Details Emerge on Shocking Death of 13-Year-Old YouTube...
10-year-old Texas girl kills 13-foot, 800-pound alligator with...
Sex with 12-year-old student gets teacher 10 years in prison
More leaked photos of AT&T Center renovations surface online...
Matthew McConaughey debuts balding, tubby look on set of new film
Police: Road rage leads man to use SUV to push another vehicle...
Air show at Randolph will be first here since 2011
Cancer becomes a growing concern for pet parents in the 21st century
At age 12, Callie, a Golden Retriever, was diagnosed with cancer. "She had tumors on her spleen and liver," says Callie's pet parent, Charlie Piscitello, Petco Foundation's Board Chair. "Through …
ACS in need of donations for Pet Pantry
The City of San Antonio's Animal Care Services (ACS) operates a Pet Pantry that helps local pet owners struggling to feed their companion animals. The program, however, is running low on supplies and …
Microchips become primary means of pet licensing in SA
It's official. San Antonio City Council unanimously approved a new pet licensing program making a registered microchip the primary means of licensing for pets living within the San Antonio city …
Help pets during Big Give S.A.
The Big Give S.A. begins and ends on May 5, 2015. According to the San Antonio Non Profit Council, this community-wide giving day was launched in 2014 to increase public awareness of the impact local …
Pets get in on the Fiesta Fun
In San Antonio, it's time for Fiesta and everyone celebrates, including our animal friends. Here's a few fun Fiesta activities that are raising money and awareness for local animal groups. San Antonio …
San Antonio brothers choose ADL for their joint "mitzvah" project
Benjamin and Jonathan Kressbach, 13-year-old twins, capped off their joint bar mitzvah celebrations by donating about $1,000 worth of cash and pet supplies to the Animal Defense League (ADL) in San …
Volunteers needed for San Antonio Pets Alive! Neonatal Kitten Nursery
Two years ago, San Antonio Pets Alive! introduced a Neonatal Kitten Nursery to San Antonio to help a fragile category of homeless pet — orphaned, unweaned kittens, and nursing mother cats taken into …
The life of one SA street dog
While Douglas the Nolan Street dog gets his happy ending, not all street dogs have such luck. Pause for Paws – Street Dog Rescue in San Antonio, Texas, estimates 75% of street dogs are lost dogs who …

subset: commoncrawl


text:
"Raisin Bun"-Like Nanocomposites of Palladium Clusters and Porphyrin for Superior Formic Acid Oxidation
A novel "raisin bun"-like nanocomposite, where Pd clusters are embedded in porphyrin matrix, is developed as a promising electrocatalyst. Thanks to the synergy between the Pd clusters and the porphyrin matrix, this composite exhibits a low oxidation potential, high mass activity and excellent stability toward electrochemical oxidation of formic acid, which opens new routes for the design of high-performance catalysts in fuel cells.
If you can't find a tool you're looking for, please click the link at the top of the page to "Go to old article view". Alternatively, view our Knowledge Base articles for additional help. Your feedback is important to us, so please let us know if you have comments or ideas for improvement.


text:
Page 1
arXiv:math/0605416v2 [math.MG] 5 Jun 2006HUREWICZ THEOREM FOR ASSOUAD-NAGATADIMENSIONN. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRAAbstract. Given a function f : X → Y of metric spaces, its as-ymptotic dimension asdim(f) is the supremum of asdim(A) suchthat A ⊂ X and asdim(f(A)) = 0. Our main result isTheorem 0.1. asdim(X) ≤ asdim(f) + asdim(Y ) for any largescale uniform function f : X → Y .0.1 generalizes a result of Bell and Dranishnikov [3] in which f isLipschitz and X is geodesic. We provide analogs of 0.1 for Assouad-Nagata dimension dimANand asymptotic Assouad-Nagata dimen-sion asdimAN. In case of linearly controlled asymptotic dimensionl-asdim we provide counterexamples to three questions of Dranish-nikov [14].As an application of analogs of 0.1 we proveTheorem 0.2. If 1 → K → G → H → 1 is an exact sequence ofgroups and G is finitely generated, thenasdimAN(G,dG) ≤ asdimAN(K,dG|K) + asdimAN(H,dH)for any word metrics metrics dGon G and dH on H.0.2 extends a result of Bell and Dranishnikov [3] for asymptoticdimension.Contents18.104.22.168.IntroductionOstrand theorem for asymptotic dimensionComponents, dimension, and coarsenessDimension of a function2258Date: May 17, 2006.1991 Mathematics Subject Classification.54E35, 18B30, 54D35, 54D40, 20H15.Key words and phrases. Asymptotic dimension, coarse category, Lipschitz func-tions, Nagata dimension.The second-named and third-named authors were partially supported by GrantNo.2004047 from the United States-Israel Binational Science Foundation (BSF),Jerusalem, Israel.1Primary: 54F45, 54C55, Secondary:
Page 2
2N. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRA188.8.131.52.ReferencesAsymptotic dimension of groupsLinearly controlled asymptotic dimension of groupsAssouad-Nagata dimensionAsymptotic Assouad-Nagata dimension12141616181. IntroductionThe well-known Hurewicz Theorem for maps (also known as Dimension-Lowering Theorem, see [18], Theorem 1.12.4 on p.109) says dim(X) ≤dim(f) + dim(Y ) if f : X → Y is a closed map of separable met-ric spaces and dim(f) is defined as the supremum of dim(f−1(y)),y ∈ Y . Bell and Dranishnikov [3] proved a variant of Hurewicz The-orem for asymptotic dimension without defining the asymptotic di-mension of a function. However, Theorem 1 of [3] may be restated asasdim(X) ≤ asdim(f)+asdim(Y ), where asdim(f) is the smallest inte-ger n such that asdim(f−1(BR(y))) ≤ n uniformly for all R > 0. As anapplication it is shown in [3] that asdim(G) ≤ asdim(K) + asdim(H)for any exact sequence 1 → K → G → H → 1 of finitely generatedgroups. That inequality was extended subsequently by Dranishnikovand Smith [16] to all countable groups.The purpose of this paper is to generalize Hurewicz Theorem to vari-ants of asymptotic dimension: asymptotic Assouad-Nagata dimensionand Assouad-Nagata dimension. In the process we produce a muchsimpler proof than that in [3] and a stronger result: the function isonly assumed to be large scale uniform instead of Lipschitz, and thedomain is not required to be geodesic.One of the main tools is Kolmogorov's idea used in his solution toHilbert's 13th Problem. In dimension theory it is known as OstrandTheorem. Another tool is reformulating Gromov's [19] definition ofasymptotic dimension in terms of r-components of spaces. That leadsto a definition of asymptotic dimension of a function in terms of double-parameter components, a concept well-suited for Kolmogorov Trick.2. Ostrand theorem for asymptotic dimensionThe aim of this section is to prove a variant of Ostrand's Theoremfor large scale dimensions. As an application we present a simple proofof the Logarithmic Law for large scale dimensions.Intuitively, a metric space is of dimension 0 at scale r if it can berepresented as a collection of r-disjoint and uniformly bounded subsets.The following definition of Gromov [19] defines asymptotic dimension
Page 3
HUREWICZ THEOREM FOR ASSOUAD-NAGATA DIMENSION3at most n in terms of being represented, for each r > 0, as the union ofn+1 sets of dimension 0 at scale r. That corresponds to the well-knownproperty of topologically n-dimensional spaces.Definition 2.1. A metric space X is said to be of asymptotic dimensionat most n (notation: asdim(X) ≤ n) if there is a function DX: R+→R+such that for all r > 0 there is a cover U =n+1?i=1Uiof X so thateach Uiis r-disjoint (that means d(a,b) ≥ r for any two points a and bbelonging to different elements of Ui) and the diameter of elements ofU is bounded by DX(r).We refer to the function DXas an n-dimensional control function forX. When discussing variants of asymptotic dimension it is convenientto allow DXto assume infinity as its value at some range of r.Definition 2.2. A metric space X is said to be of Assouad-Nagatadimension (see [20] and [7]) at most n (notation: dimAN(X) ≤ n) if ithas an n-dimensional control function DXthat is a dilation (DX(r) =c · r for some c > 0).A metric space X is said to be of asymptotic Assouad-Nagata dimen-sion at most n (notation: asdimAN(X) ≤ n) if it has an n-dimensionalcontrol function DXthat is linear (DX(r) = c·r+b for some b,c ≥ 0).A metric space X is said to be of linearly controlled asymptotic di-mension at most n (Dranishnikov [14], notation: l-asdim(X) ≤ n) ifit has an n-dimensional control function DX satisfying DX(r) = c · rfor some c > 0 and for all r belonging to some unbounded subset ofR+. Strictly speaking, the original definition of Dranishnikov [14] isformulated in terms of Lebesque numbers. However, just as in the caseof asymptotic dimension, it is equivalent to our definition.A metric space X is said to be of microscopic Assouad-Nagata dimen-sion at most n if it has an n-dimensional control function DX: R+→R+∪ ∞ that is a dilation near 0: DX(r) = c · r for some c > 0 and allr smaller than some positive number M, DX(r) = ∞ for all r ≥ M.Definition 2.3. Given a metric space X and k ≥ n+1 ≥ 1 an (n,k)-dimensional control function for X is a function DX: R+→ R+suchthat for any r > 0 there is a family U =k?i=1Uisatisfying the followingconditions:(1) each Uiis r-disjoint,(2) each Uiis DX(r)-bounded,
Page 4
4N. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRA(3) each element x ∈ X belongs to at least k − n elements ofU (equivalently,?i∈T{1,... ,k} consisting of n + 1 elements).Ui is a cover of X for every subset T ofThe following result is an adaptation of a theorem by Ostrand [25].Theorem 2.4. If D(n+1)one defines a sequence of functions {D(i)D(i)control function of X for all k ≥ n + 1.Xis an n-dimensional control function of X andX}i≥n+1inductively by D(i+1)Xis an (n,k)-dimensionalX(r) =X(3r)+2r for all i ≥ n+1, then each D(k)Proof. The proof is by induction on k. The case of k = n + 1 isobvious. Suppose the result holds for some k ≥ n+1. Let U =k?i=1Uibea family such that each Uiis 3r-disjoint, each Uiis D(k)and each element x ∈ X belongs to at least k − n elements of U.Define U′elements of U′U′X(3r)-bounded,ito be the r-neighborhoods of elements of Uifor i ≤ k. Noticeiare (D(k)k+1as the collection of all sets of the formX(3r) + 2r)-bounded and are r-disjoint. Define?s∈SAs\?i/ ∈SU′i, where S is asubset of {1,... ,k} consisting of exactly k − n elements and As∈ Us.Notice that any element of U′some Uj. Thus elements of each U′Given two different sets A =?k+1is contained in a single element ofiare (D(k)s∈SAs\?i/ ∈Sf(3r) + 2r)-bounded.U′i, where S is a subsetof {1,... ,k} consisting of exactly k − n elements and As∈ Us, andB =?t∈Ti/ ∈Texactly k − n elements and Bt ∈ Ut, we need to show A and B arer-disjoint. It is clearly so if S = T, so assume S ?= T. If a ∈ A, b ∈ B,and d(a,b) < r, then there is s ∈ S \ T such that a ∈ Aspromptingb ∈ U ∈ U′Suppose x ∈ X belongs exactly to k − n sets?U′S = {i ≤ k | x ∈?U′for some j / ∈ S, a contradiction. Thus each x ∈ X belongs to at leastk + 1 − n elements of {?U′The product theorem for asymptotic dimension was proved in [15]using maps to polyhedra. The product theorem for Nagata dimensionwas proved in [20] using Lipschitz maps to polyhedra. Below we useTheorem 2.4 to give a simplified proof for all dimension theories. Notethe metric on X ×Y is the sum of corresponding metrics on X and Y .Bt\?U′i, where T is a subset of {1,... ,k} consisting ofs, a contradiction.i, i ≤ k, and leti}. If x / ∈?U′k+1, then x must belong to?U′ji}k+1i=1.?
Page 5
HUREWICZ THEOREM FOR ASSOUAD-NAGATA DIMENSION5Theorem 2.5. If X and Y are metric spaces, thenD(X × Y ) ≤ D(X) + D(Y ),where D stands for any of the following dimension theories: asymptoticdimension, asymptotic Assouad-Nagata dimension, Assouad-Nagata di-mension, or microscopic Assouad-Nagata dimension.Proof. Let D(X) = m, D(Y ) = n and let k = m+n+1. Pick (m,k)-dimension control function DX of X and (n,k)-dimensional controlfunction DY of Y , both of the correct type (arbitrary, linear, dilation,or a dilation near 0). There are families {Ui}kY that are r-disjoint and bounded by DX(r) and DY(r) respectively,that cover X and Y at least k −m times and k −n times respectively.Then the family {Ui×Vi}kcontained in sets from at least k−m = n+1 families from {Ui}ky is contained in sets from at least k−n = m+1 families from {Vi}kso there is at least one index j such that x is covered by Ujand y iscovered by Vj. The family {Ui×Vi}kDX(r) + DY(r).i=1in X and {Vi}ki=1ini=1covers X ×Y , as for any point (x,y), x isi=1andi=1,i=1is r-disjoint and is bounded by?3. Components, dimension, and coarsenessIn this section we replace the language of r-disjoint families by thelanguage of r-components. This language has the advantage of beingportable to functions. It also allows for simple proofs of known results3.11-3.12.Definition 3.1. Let f : X → Y be a function of metric spaces, A is asubset of X, and rX, rY are two positive numbers.A is (rX,rY)-bounded if for any points x,x′∈ A we havedX(x,x′) ≤ rXanddY(f(x),f(x′)) ≤ rY.An (rX,rY)-chain in A is a sequence of points x1,... ,xkin A suchthat for every i < k the set {xi,xi+1} is (rX,rY)-bounded.A is (rX,rY)-connected if for any points x,x′∈ A can be connectedin A by an (rX,rY)-chain.Notice that any subset A of X is a union of its (rX,rY)-components(the maximal (rX,rY)-connected subsets of A).Definition 3.2. Let f : X → Y be a function of metric spaces. f iscalled large scale uniform if there is function cf: R+→ R+such thatdX(x,y) ≤ r implies dY(f(x),f(y)) ≤ cf(r). The function cf will becalled a coarseness control function of f.
Page 6
6N. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRANotice f is Lipschitz if and only if it has a coarseness control functionthat is a dilation. f is asymptotically Lipschitz if and only if it has acoarseness control function that is linear.The following Lemma describes a useful case in which double pa-rameter components coincide with single parameter components. Theproof of this Lemma is an easy exercise.Lemma 3.3. Let f : X → Y be a function of metric spaces. cf: R+→R+is a coarseness control function of f if and only if for any subsetA of X its (r,cf(r))-components coincide with its r-components.The following Lemma describes the way we construct a subset of Xwith all (rX,rY)-components being (RX,RY)-bounded. The proof ofthis Lemma is an easy exercise.Lemma 3.4. Let f : X → Y be a function of metric spaces, B bea subset of X, and A be a subset of Y . If all rX-components of Bare RX-bounded and all rY-components of A are RY-bounded then all(rX,rY)-components of the set B ∩ f−1(A) are (RX,RY)-bounded.Lemma 3.5. Let f : X → Y be a function of metric spaces and A,B besubsets of X. Suppose that all (rAbounded and all (rBRBA ∪ B are (RAX,rAY)-components of A are (RAY)-components of B are (RBXand RBX+ 2rAProof. Let x = x1,x2,...,xn= x′form an (rBNotice that, if for some indices i < j we have xk∈ B for all i < k < j,then xi+1and xj−1are in one (rBdX(xi+1,xj−1) ≤ RBIf xi,xj∈ A and xk∈ B for all i < k < j, thendX(xi,xj) ≤ dX(xi,xi+1)+dX(xi+1,xj−1)+dX(xj−1,xj) ≤ rBand, similarly, dY(f(xi),f(xj)) ≤ rBxi,xjbelong to the same (rAall points in the chain x = x1,x2,...,xn= x′belonging to A are in one(rANow let xsbe the first point in the chain belonging to A and xtbethe last point in the chain belonging to A. ThenX,RAY)-X,rBX,RBX,rBY)-bounded. IfY)-components ofX+ 2rBX< rAY+ 2rBX,RAY< rAY)-bounded.Ythen all (rBY+ 2rAX,rBY)-chain in A ∪ B.X,rBY)-component of B and thereforeY.Xand dY(f(xi+1),f(xj−1)) ≤ RBX+RBX+rBX< rAXY+RBY)-component of A. This implies thatY+rBY< rAY. Thus the pointsX,rAX,rAY)-component of A.dX(x,x′) ≤dX(x1,xs−1)+dX(xs−1,xs)+dX(xs,xt)+dX(xt,xt+1)+dX(xt+1,xn) ≤≤ RBSimilarly, dY(f(x),f(x′)) ≤ RBX+ rBX+ RAX+ rBY+rBX+ RBY+RAX< RAY+rBX+ 2rAY+RBX.Y< RAY+2rAY.?
Page 7
HUREWICZ THEOREM FOR ASSOUAD-NAGATA DIMENSION7Corollary 3.6. Let f : X → Y be a function of metric spaces and{Bi}nof Biare (R(i)and R(i+1)Y+ 2r(i+1)Y< r(i)i=1be subsets of X. Suppose that for every i all (r(i)X,R(i)Y, then all (r(n)X,r(i)+2r(i+1)Y)-componentsY)-bounded. If, for every i < n, R(i+1)XX< r(i)XX,r(n)Y)-components ofn ?i=1Biare(R(1)X+ 2r(1)X,R(1)Y+ 2r(1)Y)-bounded.Proof. By induction using Lemma 3.5.?Proposition 3.7. Suppose A is a subset of a metric space X, m ≥ 0,and R > 0. If DA is an m-dimensional control function of A, thenDB(x) := DA(x + 2R) + 2R is an m-dimensional control function ofthe R-neighborhood B = B(A,R) of A.Proof.Given r > 0 express A asm+1?i=1Ai such that (r + 2R)-components of Ai are DA(r + 2R)-bounded. Given an r-componentof Bi := B(Ai,R), each point in that component is R-close to asingle (r + 2R)-component of Ai. Therefore r-components of Bi are(DA(r + 2R) + 2R)-bounded.?Definition 3.8. Given a metric space X and r > 0 the r-scale di-mension r-dim(X) is the smallest integer n ≥ 0 such that X can ben+1?i=1bounded.expressed as X =Xiand r-components of each Xiare uniformlyNotice asdim(X) is the smallest integer n such that r-dim(X) ≤ nfor all r > 0. Also, asdim(X) is the smallest integer such that foreach r > 0 the space X can be expressed as X =n+1?i=1Xi so thatr-dim(Xi) ≤ 0 for each i ≤ n + 1.Corollary 3.9. Suppose X is a metric space. If, for every r > 0, thereis a subspace Xrof X such that asdim(Xr) ≤ n and r-dim(X\Xr) ≤ n,then asdim(X) ≤ n.Proof.Express X \ Xr asn+1?i=1Ai such that r-components of Ain+1?i=1Bi so that (R + 2r)-componentsare R-bounded. Express Xr asof Bi are M-bounded. By Lemma 3.5, r-components of Ai∪ Biare(M + 2R + 4r)-bounded.?
Page 8
8N. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRACorollary 3.10. Suppose G is a group with a left-invariant metricand Gris the subgroup of G generated by B(1G,r). If, for every r > 0,asdim(Gr) ≤ n, then asdim(G) ≤ n.Proof. Consider gs∈ G, s ∈ S, so that [gs] enumerate G/Gr\ [Gr].Notice Y =?s∈Sgs·Gris of r-dim(Y ) ≤ asdim(Gr) and Y ∪Gr= G. ?Corollary 3.11 (Dranishnikov-Smith [16]). If G is a group with aproper left-invariant metric, then asdim(G) is the supremum of asdim(H)over all finitely generated subgroups H of G.Proof. Since balls B(1G,r) are finite, the groups Gr in 3.10 arefinitely generated.?Corollary 3.12 (Bell-Dranishnikov [3]). Suppose X is a metric spaceand {Xs}s∈Sis a family of subsets of X such that X =?s∈SXsand thereis a single n-dimensional control function D for all Xs. If, for everyr > 0, there is a subspace Xrof X such that asdim(Xr) ≤ n and thefamily {Xs\ Xr}s∈Sis r-disjoint, then asdim(X) ≤ n.Proof. Notice r-dim(X \ Xr) ≤ n.?4. Dimension of a functionWhen trying to generalize Hurewicz Theorem from covering dimen-sion to any other dimension theory, the issue arises of how to definethe dimension of a function. Let us present an example of a Lipschitzfunction demonstrating that replacing sup{dim(f−1(y)) | y ∈ Y } bysup{asdim(f−1(B)) | B ⊂ Y is bounded} does not work.Proposition 4.1. There is a Lipschitz function f : X → Y of metricspaces such thatasdim(Y ) = 0 = sup{asdim(f−1(B)) | B ⊂ Y is bounded}and asdim(X) > 0.Proof. Let Y consist of points 2n, n ≥ 1, on the x-axis and X is theunion of vertical segments Inof length n and starting at 2n. f : X → Yis the projection. Since f−1(B) is bounded for every bounded B ⊂ Y ,sup{asdim(f−1(B)) | B ⊂ Y is bounded} = 0. Also, asdim(Y ) = 0.However, asdim(X) > 0 as for each n it has n-components of arbitrarilylarge size.?Remark 4.2. 4.1 shows the answer to a problem of Dranishnikov [14] innegative. That problem asks if l-asdim(X) ≤ l-asdim(Y )+l-asdimf−1,where l-asdimf−1is defined as sup{l-asdim(f−1(B)) | B ⊂ Y is bounded}
Page 9
HUREWICZ THEOREM FOR ASSOUAD-NAGATA DIMENSION9and f is Lipschitz (see 2.2 for the definition of l-asdim). Notice l-asdim(Y ) =0, l-asdimf−1= 0, and l-asdim(X) ≥ asdim(X) > 0 in 4.1.In view of 4.1 we define asymptotic dimension of a function as follows:Definition 4.3. Given a function f : X → Y of metric spaces we definethe asymptotic dimension asdim(f) of f as the supremum of asymptoticdimensions of A ⊂ X so that f(A) ⊂ Y is of asymptotic dimension 0.Definition 4.4. Given a function f : X → Y of metric spaces andgiven m ≥ 0, an m-dimensional control function of f is a functionDf: R+×R+→ R+such that for all rX> 0 and RY > 0 any (∞,RY)-bounded subset A of X can be expressed as the union of m + 1 setswhose rX-components are Df(rX,RY)-bounded.Proposition 4.5. Suppose f : X → Y is a function of metric spacesand m ≥ 0. If asdim(f) ≤ m, then f has an m-dimensional controlfunction Df.Proof.yn ∈ Y such that An = f−1(B(yn,RY)) cannot be expressed as theunion of m + 1 sets whose rX-components are n-bounded. The set∞ ?Fix rX > 0 and RY > 0. Suppose for each n there isC =n=1B(yn,RY) cannot be bounded as asdim(f−1(C)) ≤ m for anybounded subset C of Y . By passing to a subsequence we may arrangeyn→ ∞ and asdim(C) = 0, a contradiction.?Definition 4.6. Given a function f : X → Y of metric spaces andgiven k ≥ m + 1 ≥ 1, an (m,k)-dimensional control function of f isa function Df: R+× R+→ R+such that for all rX> 0 and RY > 0any (∞,RY)-bounded subset A of X can be expressed as the union ofk sets {Ai}kany x ∈ A belongs to at least k − m elements of {Ai}ki=1whose rX-components are Df(rX,RY)-bounded so thati=1.Proposition 4.7. Let f : X → Y be a function of metric spaces andm ≥ 0. Suppose there is an m-dimensional control function D(m+1)R+→ R+of f. If one defines inductively functions D(k)by D(k)f(3rX,RY)+2rX, then each D(k)dimensional control function of f.f: R+×ffor k > m+1f(rX,RY) = D(k−1)fis an (m,k)-Proof. The proof is by induction on k. The case of k = m + 1 isobvious. Suppose the result holds for some k ≥ n + 1 and a subsetA of X is (∞,RY)-bounded. There are k subsets {Ai}k3rX-components bounded by D(k)m + 1 of those sets covers A.i=1, each hasf(3rX,RY) such that the union of any
Page 10
10N. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRADefine A′rX-components of each A′are contained in rX-neighborhoods of 3rX-components of Ai.Define A′ito be the rX-neighborhood of Aiin A for i ≤ k. Noticeiare (D(k)f(3rX,RY) + 2rX)-bounded as theyk+1as the union of all sets?i∈SAi\?i/ ∈SA′i, where S is a subsetof {1,... ,k} consisting of exactly k − m elements.Suppose x ∈ A belongs exactly to k −m sets Aisuch that i ≤ k andlet S = {i ≤ k | x ∈ Ai}. If x / ∈ A′some j / ∈ S. Thus each x ∈ A belongs to at least k + 1 − m elementsof {A′Notice that any rX-component of A′component of some Aj resulting in rX-components of each A′(D(k)k+1, then x must belong to A′jfori}k+1i=1.k+1is contained in a single rX-ibeingf(3rX,RY) + 2rX)-bounded.?Proposition 4.8. Let f : X → Y be a function of metric spaces andk,m ≥ 0. If Df: R+×R+→ R+is an (m,k)-dimensional control func-tion of f, then for any B ⊂ Y whose rY-components are RY-bounded,the set f−1(B) can be covered by k sets whose (rX,rY)-components areDf(rX,RY)-bounded and every element of f−1(B) belongs to at leastk − m elements of that covering.Proof. Given an rY-component S of B express f−1(S) as ASASelement of f−1(S) belongs to at least k −m elements of that covering.Put Ai=?Sin an rX-component of some AS1∪...∪ksuch that rX-components of ASiare Df(rX,RY)-bounded and everyASiand notice each (rX,rY)-component of Aiis containedi.?Theorem 4.9. Let k = m+n+1, where m,n ≥ 0. Suppose f : X → Yis a large scale uniform function of metric spaces and asdim(Y ) ≤ n.asdim(X) ≤ m + nif there is an (m,k)-dimensional control function Df of f.over, if one can choose the coarseness control function cf of f, then-dimensional control function of Y , and Dfto be linear (respectively,a dilation), then X has a (k − 1)-dimensional control function that islinear (respectively, a dilation).More-Proof. Let cfbe a coarseness control function of f. Let DY: R+→ R+be an (n,k)-dimensional control function of Y . Notice we may requirecf(r) > r, DY(r) > r, and Df(r,R) > r + R as we may redefine thosefunctions by adding r or r + R without losing their properties or type(linear, dilation or dilation near 0).
Page 11
HUREWICZ THEOREM FOR ASSOUAD-NAGATA DIMENSION11Given a number r > 0 we are going to construct a number DX(r)and represent the space X as a union of k sets {Dj}kcomponents of Djbeing DX(r)-bounded for every j.Define inductively a sequence of numbers r(n+1)R(n)Y< ··· < r(1)Ymoving to lower indices so that for every i we have R(i)r(i)Y.Express Y as the union of k sets {Ai}kof Aiare R(0)set Aias the union of k sets {UjUjleast m sets.Define inductively a sequence of numbers r(n+1)R(n)R(i)XFor every i we express the set f−1(Ai) as the union of k sets {Bjsuch that all (r(i)every j and every point x ∈ f−1(Ai) belongs to at least n sets.Put DjDj's cover X by the use of Kolmogorov's argument: given x ∈ X thereis i so that f(x) ∈ Ai. The set of j's such that x ∈ Bjk − m elements, the set of j's such that f(x) ∈ Ujelements, so they cannot be disjoint.Notice all (r(i)By 3.6 all (r(n+1)X,r(n+1)Y)-components of the set Djare (3R(1)bounded. Since (r(n+1)X,r(n+1)Y) = (r,cf(r)), by 3.3 all r-componentsof Djare 3R(1)spectively, a dilation), if the coarseness control function cf of f, then-dimensional control function of Y , and Df are linear (respectively,dilations).j=1with all r-Y< R(n+1)Y< r(n)Y<Y < R(1)Y < r(0)Y < R(0)starting from r(n+1)YY= DY(r(i)= cf(r) andY) andY= 3R(i+1)i=1such that all r(0)Y-componentsY-bounded for every i. Since Ai⊂ Y , we can express thei}kY-bounded for every j and every point y ∈ Aibelongs to atj=1such that all r(i)Y-components ofiare R(i)X< R(n+1)X< r(n)X <X··· < r(1)X= Df(r(i)X< R(1)X,R(i)Xstarting with r(n+1)Y) and r(i)X= r and for every i we haveX= 3R(i+1).i}kj=1X,r(i)Y)-components of Bjiare (R(i)X,R(i)Y)-bounded fori= Bji∩ f−1(Uji) and let Djbe the union of all Dji. Noticeihas at leastihas at least k − nX,r(i)Y)-components of the set Djiare (R(i)X,R(i)Y)-bounded.X,3R(1)Y)-X-bounded. Observe, 3R(1)Xis a linear function of r (re-?Corollary 4.10. Suppose f : X → Y is a function of metric spacesand m ≥ 0. asdim(f) ≤ m if and only if f has an m-dimensionalcontrol function.Proof. In one direction use 4.5. In the other direction apply 4.9 inthe case of n = 0.?Theorem 4.11.asdim(X) ≤ asdim(f) + asdim(Y )
Page 12
12N. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRAfor any large scale uniform function f : X → Y .Proof. Follows from 4.9, 4.10, and 4.7.In [3] there is a concept of a family {Xα} of subsets of X satisfyingasdim(Xα) ≤ n uniformly. Notice that in our language it means thereis one function that serves as an n-dimensional control function for allXα.?Corollary 4.12 (Bell-Dranishnikov [3]). Let f : X → Y be a Lipschitzfunction of metric spaces. Suppose that, for every R > 0,asdim{f−1(BR(y))} ≤ nuniformly (in y ∈ Y ). If X is geodesic, then asdim(X) ≤ asdim(Y )+n.Proof.dimensional control function, so apply 4.9 and 4.7.asdim{f−1(BR(y))} ≤ n uniformly means f has an n-?Remark 4.13. Notice Bell-Dranishnikov's version of Hurewicz type the-orem 4.12 (see [3]) assumes that X is geodesic. We do not use thisassumption in 4.11.5. Asymptotic dimension of groupsJ.Smith [27] showed that any two proper and left-invariant metricson a given countable group G are coarsely equivalent. We generalizethat result as follows.Proposition 5.1. Suppose f : G → H is a homomorphism of groupsand dG, dH are left-invariant metrics on G and H, respectively. Iff : (G,dG) → (H,dH) is coarsely proper (i.e., it sends bounded subsetsof G to bounded subsets of H), then f : (G,dG) → (H,dH) is large scaleuniform.Proof.R > 0 such that dH(1H,f(g)) < R for all g ∈ B(1G,r). If x,y ∈ Gsatisfy dG(x,y) < r, then x−1· y ∈ B(1G,r), so dH(f(x),f(y)) =dH(1H,f(x−1y)) < R.Suppose r > 0. Since f(B(1G,r)) is bounded, there is?Corollary 5.2. Suppose f : G → H is a homomorphism of groups anddG, dH are left-invariant metrics on G and H, respectively. If dG isproper, then f : (G,dG) → (H,dH) is large scale uniform.Proof. Since bounded subsets of G are finite, f is coarsely proper.?Corollary 5.3 (J.Smith [27]). Any two proper left-invariant metricson a group G are coarsely equivalent.
Page 13
HUREWICZ THEOREM FOR ASSOUAD-NAGATA DIMENSION 13The subsequent result is derived in [16] from the corresponding the-orem for finitely generated groups. We deduce it directly from 4.11.Theorem 5.4 (Dranishnikov-Smith [16]). If 1 → K → G → H → 1is a short exact sequence of countable groups, thenasdim(G) ≤ asdim(K) + asdim(H).Proof. It suffices to show asdim(f) = k = asdim(K), where f : G →H. Given RH > 0, the subspace f−1(B(1H,RH)) is in a boundedneighborhood of K as B(1H,RH) is finite, so it has the same asymptoticdimension as K. Fix the dimension control function D(rG,RH) for thatspace. Notice that all spaces f−1(B(h,RH)), h ∈ H, are isometric tof−1(B(1H,RH)), so D(rG,RH) is a dimension control function of all ofthem. By 4.10, asdim(f) ≤ k and by applying 4.11 we are done.In [16] the asymptotic dimension of a group G is defined as the supre-mum of asdim(H), H ranging through all finitely generated subgroupsof G. We provide an alternative definition which will be applied in thenext section.?Definition 5.5. Given a finite subset S of a group G, an S-componentof G is an equivalence class of G of the relation x ∼ y iff x can beconnected to y by a finite chain xiso that x−1A family of subsets {Ai}i∈Jis S-bounded if x−1·y ∈ S for each i ∈ Jand all x,y ∈ Ai.i· xi+1∈ S for all i.Proposition 5.6. Let G be a group. asdim(G) ≤ n if and only iffor each finite subset S of G there is a finite subset T of G and adecomposition G = A1∪ ... ∪ An+1such that S-components of AiareT-bounded for all i ≤ n + 1.Proof. Suppose for each finite subset S of G there is a finite subset Tof G and a decomposition G = A1∪...∪An+1such that S-componentsof Aiare T-bounded for all i ≤ n + 1. Given a countable subgroupH of G and given a proper left-invariant metric dH on H, we putS = B(1H,r) and R = max{dH(1H,t) | t ∈ T · T ∩ H} (by T · T wemean all products t · s, where t,s ∈ T). Notice that r-components ofAi∩ H are R-bounded.Conversely, suppose asdim(H) ≤ n for all finitely generated sub-groups H of G. Given a finite subset S of G let H be the subgroup ofG generated by S and let d be the word metric on H induced by S.Since asdim(H) ≤ n, there is a decomposition of H into A1∪...∪An+1such that 1-components of Aiare m-bounded for all i ≤ n+1 and somem > 0. Let T = B(1H,m + 1). Pick a representative gj∈ G, j ∈ J, of
Page 14
14N. BRODSKIY, J. DYDAK, M. LEVIN, AND A. MITRAeach left coset of H in G. Put Bi=?j∈Jgj·Aiand notice S componentsof Biare T-bounded.?6. Linearly controlled asymptotic dimension of groupsUnlike the asymptotic dimension of countable groups, the asymptoticAssouad-Nagata dimension may depend on the left-invariant metric.Piotr Nowak [23] constructed finitely generated groups Gnof asymp-totic dimension n ≥ 2 and asdimAN(Gn) = ∞. Obviously, there isno such example for n = 0 as finitely generated groups of asymptoticdimension 0 are finite. However, 6.4 does provide a countable group Gwith a proper, left-invariant metric d such that asdim(G,d) = 0 andasdimAN(G,d) = ∞.The purpose of this section is to solve in negative the following twoproblems of Dranishnikov [14].Problem 6.1. Does l-asdim(X) = asdimAN(X) hold for metric spaces?Problem 6.2. Find a metric space X of minimal asdim(X) such thatasdim(X) < l-asdim(X).Here is an answer to 6.2.Proposition 6.3. There is a proper, left-invariant metric dGon G =∞?n=2Z/n such that l-asdim(G,dG) > 0 = asdim(G,dG).Proof. Pick a generator gnof Z/n and assign it the norm of n forn ≥ 2. Extend the norm over all elements g of G as the minimum∞?n=1|kn| · n, where g =dG(g,h) := |g − h| is a proper and invariant metric on G. Supposethere is an unbounded subset U of R+such that for some C > 0 allr-components of G are (C·r)-bounded for r ∈ U. Pick r ∈ U such that4C + 4 < r and let n be an integer such that r − 2 < 2n ≤ r. Noticeall 2n-components of G are contained in some r-components of G, sothey are (n − 1) · (n + 1)-bounded as C <r−4However, the 2n-component of 0 contains Z/2n and |n · g2n| = 2n2>(n − 1) · (n + 1), a contradiction.of∞?n=1kn· gnand knare integers. Notice that4≤n−22and r < 2n + 2.?Proposition 6.4. There is an Abelian torsion group G with a properinvariant metric dGsuch that l-asdim(G,dG) = 0 and asdimAN(G,dG) =∞.Proof.asdim(Zn+1) > n, there is r(n) > 0 such that any decomposition ofConsider Zn+1with the standard word metric ρn. Since
Page 15
HUREWICZ THEOREM FOR ASSOUAD-NAGATA DIMENSION 15Zn+1as the union X0∪...∪Xnforces one Xito have r(n)-componentswithout a common upper bound. Without loss of generality we mayassume r(n) is an integer greater than n.and consider Gn= (Zs(n))n+1with the metric dnequal to t(n) timesthe standard word metric. Numbers t(n) are chosen so that t(n+1) >diam(G1)+...+diam(Gn) for all n ≥ 1. Since diam(Gn) = 4nt(n)r(n),we want t(n + 1) = 1 + 4 · t(1)r(1) + ... + 4n · t(n)r(n) for all n ≥ 1.The group G is the direct sum of all Gnwith the obvious metric d:d({xn},{yn}) =?dn(xn,yn). Notice thatof size at most t(n). Indeed, anyx + G1⊕ ... ⊕ Gn−1for some x ∈ G. Thus l-asdim(G,d) = 0.Consider the projection πn: Zn+1→ Gnand notice it is t(n)-Lipschitz.Moreover, if two points x and y in Zn+1satisfy ρn(x,y) ≤ 4nr(n), thendn(x,y) = t(n) · ρn(x,y).Suppose Gnequals Y0∪ ... ∪ Yn. Assume r(n)-components of someXj= π−1x0,... ,xk in Xj such that ρn(xi,xi+1) < r(n) and (n + 2) · r(n) >ρn(x0,xk) > n·r(n). Assume such a sequence does not exist with num-ber of elements smaller than k + 1. Therefore dn(πn(xi),πn(xi+1)) =t(n)·ρn(xi,xi+1) < t(n)·r(n) and (n+2)·t(n)r(n) > ρn(πn(x0),πn(xk)) >n·t(n)r(n). Thus, one (t(n)·r(n))-component of Yiis of diameter biggerthan n · t(n)r(n).Suppose asdimAN(G,d) = k < ∞ and DG(r) = c · r + b is a k-dimension control function of (G,d). Pick n > max(k,|c|,|b|) + 2 andchoose a decomposition Y0∪...∪Ykof G so that (t(n)·r(n))-componentsof each Yiare bounded by c·t(n)·r(n)+b < (c·t(n)+1)·r(n). Noticethere is a 1-Lipschitz projection pn: G → Gn. Therefore each set pn(Yi)has (t(n) · r(n))-components bounded by (c · t(n) + 1) · r(n). On theother hand, for some j, there is an (t(n) · r(n))-component of pn(Yj)of diameter bigger than nt(n) · r(n). Thus, c · t(n) + 1 > nt(n) andc > n − 1/t(n), a contradiction.Put s(n) = 8 · n · r(n)t(n)2-components of G are2-component of G is contained int(n)n(Yj) are not uniformly bounded. Therefore there is a sequence?Remark 6.5. Proposition 6.4 solves Problem 6.1 in negative.Proposition 6.6. For any countable group G there is a proper left-invariant metric dGsuch that asdimAN(G,dG) = asdim(G).Proof.increasing sequence S0⊂ S1... of its finite subsets so that {1G} = S0,each Siis symmetric, and for each i there is a decomposition of G asAidG(x,y) as the smallest i so that x−1·y ∈ Si. Notice that in the metricdGall i-components of AiLet asdim(G) = n − 1. Express G as the union of an1∪ ... ∪ Ainso that Si-components of Aikare Si+1-bounded. Definekare (i + 1)-bounded.?
An error occurred while rendering template.


text:
Got a minute?
Got a minute?
The Booking Manager position is much like running a business. We have an immediate opening for a full time *Booking Manager*.... - Indeed
The company has an immediate need for an Office Manager and Talent Liaison. Prior experience working with talent a plus.... - Indeed
Director of Talent. Design and distribute recruitment materials, including the Envision talent web page.... - Indeed
Sourcing Manager – Talent Acquisition. Mentor sourcing team and recruiters, with a focus on implementing innovative solutions to continually build talent... - Indeed
Talent Acquisition Sourcing Manager is responsible for developing and executing proactive talent sourcing campaigns to recruit top talent for pipeline and high... - Indeed
The Talent Acquisition /Client Relationship Manager is responsible for developing a partnership with our client accounts by working directly with the client... - Indeed
Utilizes multiple sourcing channels such as LinkedIn, social media, talent communities and professional associations or online groups to identify and recruit... - Indeed
We need an energetic, people person as our Office Manager. You will support our General Manager for Texas and ensure that everything runs smoothly in our new... - Indeed
The IBM Analytics Platform Development Operations team is looking for an experienced Program Manager for our Talent Development and Recognition programs to will... - Indeed
Talent Acquisition Manager is responsible for achieving growth targets as defined by Regional Manager, Sales in an assigned Territory.... - Indeed
Thanks! We'll send you a welcome newsletter as soon as we can.
In the meantime, check out our research center.
Looks like your email already exists in our database.
Please log in here.
You are already logged in.


text:
In This Section
Journal Forum
Synthetic Reverberator - January 1960
1 comment
Multichannel Sound Reproduction Quality Improves with Angular Separation of Direct and Reflected Sounds - June 2015
1 comment
Clean Audio for TV broadcast: An Object-Based Approach for Hearing-Impaired Viewers - April 2015
2 comments
AES E-Library
The CD-I Authoring System
This paper relates to the authoring system newly developed by Matsushita for production CD-I discs. Features of the system, configuration of hardware and software, and the data processing method are described in this paper. In order to realize this authoring system, original multimedia data base management techniques and audio video synchronization editing methods have been developed. For the construction of system hardware, real time ADPCM audio encoder/decoder, -YUV video encoder/decoder, and simulator have been designed and constructed. System software, utility items have been developed, including the multimedia handling software making full use of the UNIX operating system and structure-conversion software used for converting information into the CD-I file structure, etc. These programs have been written in the C language. Also, this system can execute the pre-mastering of High Sierra format CD-ROM.
Click to purchase paper or login as an AES member. If your company or school subscribes to the E-Library then switch to the institutional version. If you are not an AES member and would like to subscribe to the E-Library then Join the AES!
This paper costs $20 for non-members, $5 for AES members and is free for E-Library subscribers.
Learn more about the AES E-Library
Start a discussion about this paper!


text:
Edmunds.com features a complete listing of Nissan dealerships in Fulton County, making it simple to the find new or used Nissan vehicle of your dreams. Compare local dealer prices in Fulton County with instant online quotes for Nissan car, truck, wagon, SUV, and minivan models. At Edmunds.com car buyers can search a comprehensive network of trusted Nissan car dealerships in their region, allowing them to pinpoint the lowest prices at the most convenient location.
Non Display Review Name "We bought our new vehicle from Andrew D. at Yark Nissan. Andrew was very genuine and he did a great job helping us find the car that was right for us."... Read more Review by: Customer24601
Non Display Review Name "I had a great experience at Dave's. My wife totaled our 05 Mitsubishi gallant and our insurance didn't cover the entire balance of the loan. I talked "... Read more Review by: WintersMarcy


text:
Web Design Courses: Learn to Design a Website
Web Design Skill level
- Advanced
Web Design Software
More options
Learn to spiff up your HTML5 slideshows with automatic playback, integrated audio and video, and more.
"I have yet to find a course that I didn't find useful, well organized, and informative. And it's always at my fingertips." —Leslie M.
more from our members »