Hierarchy and Multi-Granular Computing

Abstract

The word ‘hierarchy’ has two meanings. First, it means a sort of architecture or organization in natural and man-made systems. Second, it represents the hierarchical analysis methodology in human problem-solving activities. In this book, we mainly focus on the second meaning.

The hierarchical analysis methodology is also the key idea in quotient space theory. We discuss the characteristics of the hierarchical analysis strategy, i.e., the multi-granular computing strategy, in human problem-solving activities and show that by the strategy, the computational complexity can be reduced. We use both the deterministic and probabilistic models to estimate the computational complexity and show in what conditions multi-granular computing can bring about the reduction of computational complexity. We also discuss one of the main issues in hierarchical problem solving, the extraction of global information from the local ones.

We extend the concept of quotient space theory based on equivalence relations to fuzzy equivalence relations. We discuss the structure of fuzzy quotient spaces and the applications of fuzzy quotient space theory.

The multi-granular computing strategy not only can be used for human deliberative behaviors but also to perception recently.

Keywords

computational complexity; fuzzy equivalence relation; fuzzy quotient space; hierarchy; multi-granular computing; quotient attribute function

Chapter Outline

2.1. The Hierarchical Model

The concept of hierarchy has long been used in many fields, e.g., information, control, and management sciences. Recently, AI researchers also use it extensively in, for example, hierarchical planning, hierarchical learning, etc.

In this book, the word ‘hierarchy’ has two meanings. First, it means a sort of architecture or organization in natural and man-made systems. Second, it represents the hierarchical analysis methodology in human problem-solving activities. In the book, we mainly focus on the second meaning.

For example, in a national administration, the whole nation is divided into several provinces. Each province is further divided into several counties and so on.

A man-made control system is generally divided into several levels. The whole system is decomposed into several subsystems. Each subsystem has its own functions, and is controlled by higher-level controllers. The subsystem may further be split into smaller ones. This is the well-known ‘hierarchical control’ as the system has a hierarchical structure.

The above two examples are typical hierarchical organizations.

In human problem solving, instead of considering all the details of the problem at once, the original complex problem is first simplified by ignoring some details. The simplified model is then gradually refined until the problem is finally solved. That is, we solve the problem from top to bottom, from the coarse grain to the fine one, or from global to local gradually. This is called hierarchical problem solving. The examples are given below.

Example 2.1

To make a nation-wide economic development plan, a plan for each department, such as power supply, transportation, etc., is usually worked out first. Then the plans for factories and enterprises are worked out on the basis of the departments' plans. Similarly, when making a long-term 5-year plan, we generally work out annual plans first, and then monthly plans and so on. The plan is refined gradually according to the chronological order.

Example 2.2

In troubleshooting, a complex electronic instrument is tested. One always examines its components such as power supply, display unit, etc., first, and then go deep into the elements of each component until some faults are detected.

A similar process can be seen in many engineering designs.

Example 2.3

Suppose that someone is looking into the structure of the age distribution of a city, he/she would prefer first grouping the citizens in terms of junior, adult, senior or the like to going through the statistics of the recent census. This means that he/she is consciously using the concept of hierarchy. Each group may contain a lower level of hierarchy, e.g., the senior group may be divided into smaller groups like ‘below 60’, ‘above 60’, and so on. We can see that grouping is done at different levels (higher or lower) and we sometimes refer to them as abstraction levels.

Why has a nation to be organized as a hierarchical structure? The fact is that it is impossible for the head of the state to look after all his citizens directly. The same is true for the case of armed forces. A general cannot command each soldier directly. The soldiers have to be grouped into divisions, regiments and battalions, etc. In man-made machines, as mentioned above, it is not true that the central controller deals with every single element directly.

It is generally recognized that the hierarchical structure can enhance the efficiency. This is just the hierarchical problem-solving strategy that humans use for dealing with complex problems. We call the strategy multi-granular computing.

There are two cases for using the strategy. First, we sometimes only need to know the general properties of the domain rather than the details. Thus, just one proper granularity (or abstraction level) is needed. For example, we expect to survey the distribution of a disease over some region. It is unlikely to investigate each citizen in the region. Generally, a region is divided into several typical areas. Taking samples from these areas, a statistical distribution of the disease over that region will be obtained. The other case is that since the problem in question is quite complex, it is hard to handle the whole problem at once. Then the problem is decomposed into several different grain-size worlds (abstraction levels). From the analysis of the coarse granular levels (higher abstraction levels), some primary results are obtained. Then, going deeper into the fine granular levels (lower abstraction levels), more information is gained under the guidance of the results already collected, until the problem is finally solved.

It seems that the multi-granular computing is aimed at improving efficiency, or in terms of computer science, reducing the computational complexity. Whether or not the strategy can reduce the computational complexity, in what conditions the goal can be reached, etc., we will discuss them in this chapter.

Generally, there are two kinds of partition paradigms in multi-granular computing. One is called branching. A problem is divided into several sub-problems. And each sub-problem is divided into sub-sub-problems and so on. When the decomposition does not have overlapped parts, it is a tree structure. Otherwise, it is a graph. The other is called nested. A problem is divided into several levels with different details. For example, we investigate the transportation problem in some area, in a map with 1:40,000,000 scale, the main cities, rivers and railways, etc., are indicated. Further, in a map with 1:15,000,000 scale, more details such as counties, highways, etc., are shown. The maps with different scales compose a nested structure.

Obviously, the branching structure can be represented by the mathematical model presented in Chapter 1. For a nested structure, in some coarse granularity, some details are missing. The missing parts can be classified into an equivalence class. When entering into a fine one, some missing parts appear. Then, they are further classified. Hence, the nested structure can be represented by the quotient structure model as well.

The above hierarchical structures can be obtained in two ways, one from prior knowledge, and the other from data. Many machine learning and data mining methods (Mitchell, 1997; Hand et al., 2001) can be used to get the structures behind data that are not involved in the book.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Chapter 2. Hierarchy and Multi-Granular Computing

Create new playlist

Sign In

Sign Up