codezonediitj / adaboost

Implementation of AdaBoost Algorithm

AdaBoost

About Us

We are some machine learning enthusiasts who aim to implement the adaboost algorithm from scratch.

Technologies

We are using the following technologies in our project,

1. C++
2. Python
3. CUDA C
4. Google Test
5. Boost.Python

Building from source

Linux

1. Clone Repository to local machine git clone https://github.com/codezonediitj/adaboost
2. Move to back to parent directory, cd ../
3. Execute, mkdir build-adaboost
4. Execute, cd build-adaboost
5. Execute, cmake -D[OPTIONS] ../adaboost
6. Execute, make. Do not execute, make -j5 if you are using -DINSTALL_GOOGLETEST=ON otherwise make will try to link tests with gtest gtest_main before GoogleTest is installed into your system.
7. To test, run, ./bin/*. Ensure that you have used the option -DBUILD_TESTS=ON in step 5 above.

Windows

1. git clone https://github.com/codezonediitj/adaboost
2. Move to back to parent directory, cd ../
3. Execute, mkdir build-adaboost
4. Execute, cd build-adaboost
5. Install CMake from https://cmake.org/download/. You can also follow the steps given at, https://cgold.readthedocs.io/en/latest/first-step/installation.html#windows
6. Open cmake GUI and put the adaboost directory as source code in the source code field and build-adaboost directory in the build binaries field.
7. Select the cmake options(see below) which you want to use for building, then click Configure and Generate, to build the files .

We provide the following options for cmake,

1. BUILD_TESTS

By default OFF, set it to ON if you wish to run the tests. Tests are stored in the bin under your build directory.

2. INSTALL_GOOGLETEST

By default ON, set it to OFF if you do not want to update the already existing GoogleTest on your system. Note that it uses this release of googletest.

3. CMAKE_INSTALL_PREFIX

Required for installing if not installing to /usr/local/include on Linux based systems. Defines the path where the library is to be installed.

Installing

Follow the steps for building from source. After that run the following,

Linux

sudo make install

Windows

cmake install <path to your build directory>

How to contribute?

Follow the steps given below,

1. Fork, https://github.com/codezonediitj/adaboost
2. Execute, git clone https://github.com/codezonediitj/adaboost/
3. Change your working directory to ../adaboost.
4. Execute, git remote add origin_user https://github.com/<your-github-username>/adaboost/
5. Execute, git checkout -b <your-new-branch-for-working>.
6. Make changes to the code.
7. Add your name and email to the AUTHORS, if you wish to.
8. Execute, git add ..
9. Execute, git commit -m "your-commit-message".
10. Execute, git push origin_user <your-current-branch>.
11. Make a PR.

That's it, 10 easy steps for your first contribution. For future contributions just follow steps 5 to 10. Make sure that before starting work, always checkout to master and pull the recent changes using the remote origin and then start following steps 5 to 10.

See you soon with your first PR.

Guidelines

We recommend you to introduce yourself on our gitter channel. You can include the literature you have studied relevant to adaboost, some projects, prior experience with the technologies mentioned above, in your introduction.

Please follow the rules and guidelines given below,

1. For Python we follow the numpydoc docstring guide.
2. For C++ we follow our own coding style mentioned here.
3. For C++ documentation we follow, Doxygen style guide. Refer to various modules in the existing master branch for the pattern.
4. Follow the Pull Request policy given here. All changes are made through Pull Requests, no direct commits to the master branch.

Keep contributing!!

adaboost's Issues

Removing unnecessary lines from .travis.yml and fixing CMakeLists.txt

Description of the problem

1. The following line is not needed,

   adaboost/.travis.yml

   Line 13 in 5df11ee

   - ls -a

2. The following should be changed to use 1.10.0 release

   adaboost/CMakeLists.txt

   Lines 23 to 31 in 5df11ee

   	if(INSTALL_GOOGLETEST AND BUILD_TESTS)
   	include(${CMAKE_ROOT}/Modules/ExternalProject.cmake)
   	ExternalProject_Add(googletest
   	GIT_REPOSITORY https://github.com/google/googletest
   	GIT_TAG master
   	SOURCE_DIR "${CMAKE_CURRENT_BINARY_DIR}/googletest-src"
   	BINARY_DIR "${CMAKE_CURRENT_BINARY_DIR}/googletest-build"
   	TEST_COMMAND "")
   	endif()

Example of the problem

References/Other comments

CUDA libraries are installed even if they aren't built

Description of the problem

libbnn_cuda* files are installed even if they aren't built. See,

adaboost/CMakeLists.txt

Lines 46 to 51 in 5164fea

	install(FILES
	${CMAKE_BINARY_DIR}/libs/libadaboost_core.so
	${CMAKE_BINARY_DIR}/libs/libadaboost_utils.so
	${CMAKE_BINARY_DIR}/libs/libadaboost_cuda.so
	${CMAKE_BINARY_DIR}/libs/libadaboost_cuda_wrappers.so
	DESTINATION ${CMAKE_INSTALL_PREFIX}/lib)

A minor check is needed to fix this,

if(BUILD_CUDA)
    install(...)
endif()

The above is just a hint not a complete solution.

Example of the problem

References/Other comments

Using non-default streams in CUDA

Description of the problem

Currently, in #6 all the operations are issued to default stream. However, I was thinking that we can use non-default streams for issuing various kernels to different operations for their parallel execution.
An example of such a situation is filling n vectors parallelly with fill_vector_kernel launched in n separate streams. In fact, one more example can be to fill n*m matrix with n or m kernels launched in separate streams.
Before moving on to the implementation we can discuss the API for the above use case.
Please comment below if you have thought of something. I will come up with the design soon.
One more advantage of using non-default streams as claimed by https://devblogs.nvidia.com/how-overlap-data-transfers-cuda-cc/ is the overlap of data transfers and kernel execution. However IMO, this isn't really useful for this library because it may be the case that user wants to copy back only small sized Vector to host and for that wasting time in creating streams isn't a good idea.

Example of the problem

Parallelizing Artifical Neural Networks Using CUDA C

Description of the problem : Perform parallelization of Artificial Neural Networks buy using CUDA C on the MNIST dataset.

Me and my teammate Riddhi Thakker from Team Cutting Edge. Would like to perform this task, to get more familiar to the project,

Design Discussions

Description of the problem

This issue aims at discussing the design of the software that is going to be developed covering the below topics,

1. File structure
2. User facing APIs
3. Class design
4. Hardware requirements(mainly GPUs)

I will try to come up with the first one ASAP. However, if you already prepared something then let us know in the comments.

Example of the problem

References/Other comments

We will follow https://web.stanford.edu/~hastie/Papers/samme.pdf
If you have something to suggest which can be used in the project then let us know.

Complete documentation

Description of the problem

Documentation for some classes and functions isn't complete in .hpp files. The issue can be resolved by adding docstrings to all the missing places.

Example of the problem

References/Other comments

[Discussion] Implementation of AdaBoost

Description of the problem

Task is to discuss implementation of both Multi-Class and Two-Class AdaBoost. Paper we have referred to is this: https://web.stanford.edu/~hastie/Papers/samme.pdf

Current Thoughts

• For the multi-class adaboost we will implement Algorithm 4 in the paper which is SAMME.R

Initial Doubts

• For two-class adaboost, which algorithm should we be following?
• We are having some trouble understanding the paper. Especially this line in Algorithm 4:
  

where the RHS is expanded as:

We are not able to understand what the f and the I symbol mean.

Bug in matrix multiplication using shared memory

Description of the problem

The following code doesn't give correct results for matrix multiplication using shared memory,

template <class data_type_matrix>
            __device__
            data_type_matrix get_element(
            data_type_matrix* mat,
            unsigned row,
            unsigned col,
            unsigned stride)
            {
                return mat[row*stride+col];
            }

            template <class data_type_matrix>
            __device__
            void set_element(
            data_type_matrix* mat,
            unsigned row,
            unsigned col,
            data_type_matrix value,
            unsigned stride)
            {
                mat[row*stride+col] = value;
            }

            template <class data_type_matrix>
            __device__
            data_type_matrix* get_sub_matrix(
            data_type_matrix* mat,
            unsigned block_row,
            unsigned block_col,
            unsigned stride)
            {
                data_type_matrix* mat_sub =
                new data_type_matrix[BLOCK_SIZE*BLOCK_SIZE];
                mat_sub = &mat[stride*BLOCK_SIZE*block_row+BLOCK_SIZE*block_col];
                return mat_sub;
            }

            template <class data_type_matrix>
            __global__
            void multiply_kernel(
            data_type_matrix* mat1,
            data_type_matrix* mat2,
            data_type_matrix* result,
            unsigned mat1_cols,
            unsigned mat2_cols,
            unsigned result_cols)
            {
                unsigned block_row = blockIdx.y;
                unsigned block_col = blockIdx.x;
                data_type_matrix* result_sub = get_sub_matrix(result, block_row,
                                                              block_col, result_cols);

                unsigned row = threadIdx.y;
                unsigned col = threadIdx.x;

                for(unsigned m = 0; m < (mat1_cols + BLOCK_SIZE - 1)/BLOCK_SIZE; m++)
                {
                    data_type_matrix* mat1_sub = get_sub_matrix(mat1, block_row,
                                                                m, mat1_cols);
                    data_type_matrix* mat2_sub = get_sub_matrix(mat2, m,
                                                                block_col, mat2_cols);

                    __shared__ data_type_matrix mat1_shared[BLOCK_SIZE][BLOCK_SIZE];
                    __shared__ data_type_matrix mat2_shared[BLOCK_SIZE][BLOCK_SIZE];

                    mat1_shared[row][col] = get_element(mat1_sub, row, col, mat1_cols);
                    mat2_shared[row][col] = get_element(mat2_sub, row, col, mat2_cols);

                    data_type_matrix cvalue = 0.0;

                    __syncthreads();

                    for(unsigned e = 0; e < BLOCK_SIZE; e++)
                    {
                        cvalue += mat1_shared[row][e] * mat2_shared[e][col];
                    }

                    __syncthreads();

                    set_element(result_sub, row, col, cvalue, result_cols);
                }
            }

            template <class data_type_matrix>
            void multiply_gpu(const MatrixGPU<data_type_matrix>& mat1,
                              const MatrixGPU<data_type_matrix>& mat2,
                              MatrixGPU<data_type_matrix>& result)
            {
                adaboost::utils::check(mat1.get_cols() == mat2.get_rows(),
                                       "Order of matrices don't match.");
                dim3 gridDim((mat2.get_cols() + BLOCK_SIZE)/BLOCK_SIZE,
                             (mat1.get_rows() + BLOCK_SIZE)/BLOCK_SIZE);
                dim3 blockDim(BLOCK_SIZE, BLOCK_SIZE);
                multiply_kernel
                <<<gridDim, blockDim>>>
                (mat1.get_data_pointer(),
                 mat2.get_data_pointer(),
                 result.get_data_pointer(),
                 mat1.get_cols(),
                 mat2.get_cols(),
                 result.get_cols());
            }

Example of the problem

#include<gtest/gtest.h>
#include<string>
#include<adaboost/cuda/cuda_data_structures.hpp>
#include<adaboost/utils/cuda_wrappers.hpp>
#include<stdexcept>

TEST(Cuda, MatricesGPU)
{
    adaboost::utils::cuda::cuda_event_t has_happened;
    adaboost::utils::cuda::cuda_event_create(&has_happened);
    adaboost::cuda::core::MatrixGPU<float> mat_f;
    EXPECT_EQ(0, mat_f.get_cols())<<"Number of columns should be 0";
    EXPECT_EQ(0, mat_f.get_rows())<<"Number of rows should be 0.";
    adaboost::cuda::core::MatrixGPU<float> mat1(3, 3), mat2(3, 3), mat3(2, 1);
    mat1.fill(4.0);
    mat2.fill(5.0);
    mat1.copy_to_device();
    mat2.copy_to_device();
    adaboost::utils::cuda::cuda_event_record(has_happened);
    adaboost::utils::cuda::cuda_event_synchronize(has_happened);
    adaboost::cuda::core::MatrixGPU<float> result1(3, 3);
    adaboost::cuda::core::multiply_gpu(mat1, mat2, result1);
    adaboost::utils::cuda::cuda_event_record(has_happened);
    adaboost::utils::cuda::cuda_event_synchronize(has_happened);
    result1.copy_to_host();
    for(unsigned int i = 0; i < 3; i++)
    {
        for(unsigned int j = 0; j < 3; j++)
        {
            std::cout<<i<<" "<<j<<" "<<result1.at(i, j)<<std::endl;
            EXPECT_EQ(60.0, result1.at(i, j));
        }
    }
    mat3.set(0, 0, 6.0);
    mat3.set(1, 0, 6.0);
    EXPECT_THROW({
        try
        {
            adaboost::cuda::core::multiply_gpu(mat1, mat3, result1);
        }
        catch(const std::logic_error& e)
        {
            EXPECT_STREQ("Order of matrices don't match.", e.what());
            throw;
        }
    }, std::logic_error);
}

int main(int ac, char* av[])
{
    testing::InitGoogleTest(&ac, av);
    return RUN_ALL_TESTS();
}

References/Other comments

Adding support for Windows

Description of the problem

There isn't any documentation in README for building the project and working with it on Windows.

Example of the problem

References/Other comments

Refactoring Codebase

Description of the problem

Currently the code base has mixed up CUDA kernels with C++ class and the API is too confusing. Some changes are to be made summarised in the following points,

• Remove fill method from both Matrix and Vector classes - The first phase of refactoring should include removing fill method from both of these classes and their GPU counter parts and shifting it to operations module. This will avoid kernel calls inside class methods and the APIs for Matrix and Vector will be unambiguous.

• Shift product and multiply functions to operations module - The reason for doing this are similar to the above.

• Discuss API for using streams i.e., working on #2. Currently, methods like, Vector.fill decipher from the block_size whether to use GPU or not. Instead separate functions should be used for GPU and CPU with clean APIs.

Example of the problem

References/Other comments

Boost.Python or SWIG or PyBindGen

Description of the problem

I was just exploring options to generate Python wrappers for C++ code and came across PyBindGen . SWIG is fine but I think PyBindGen is more logical to use.
What do you say?

I was going through the Boost.Python as well and I believe that this is much better than both of the above alternatives due to the greatest amount of content available on the web.

Example of the problem

References/Other comments

[1] https://pybindgen.readthedocs.io/en/latest/tutorial/#what-is-pybindgen